diff --git a/lib/cmdlib/cluster/verify.py b/lib/cmdlib/cluster/verify.py
index 79fa0d8..c32820a 100644
--- a/lib/cmdlib/cluster/verify.py
+++ b/lib/cmdlib/cluster/verify.py
@@ -1015,6 +1015,11 @@
                       " should node %s fail (%dMiB needed, %dMiB available)",
                       self.cfg.GetNodeName(prinode), needed_mem, n_img.mfree)
 
+  def _CertError(self, *args):
+    """Helper function for _VerifyClientCertificates."""
+    self._Error(constants.CV_ECLUSTERCLIENTCERT, None, *args)
+    self._cert_error_found = True
+
   def _VerifyClientCertificates(self, nodes, all_nvinfo):
     """Verifies the consistency of the client certificates.
 
@@ -1029,20 +1034,25 @@
       all nodes
 
     """
-    candidate_certs = self.cfg.GetClusterInfo().candidate_certs
-    if candidate_certs is None or len(candidate_certs) == 0:
-      self._ErrorIf(
-        True, constants.CV_ECLUSTERCLIENTCERT, None,
-        "The cluster's list of master candidate certificates is empty."
-        " If you just updated the cluster, please run"
+
+    rebuild_certs_msg = (
+        "To rebuild node certificates, please run"
         " 'gnt-cluster renew-crypto --new-node-certificates'.")
+
+    self._cert_error_found = False
+
+    candidate_certs = self.cfg.GetClusterInfo().candidate_certs
+    if not candidate_certs:
+      self._CertError(
+        "The cluster's list of master candidate certificates is empty."
+        " This may be because you just updated the cluster. " +
+        rebuild_certs_msg)
       return
 
-    self._ErrorIf(
-      len(candidate_certs) != len(set(candidate_certs.values())),
-      constants.CV_ECLUSTERCLIENTCERT, None,
-      "There are at least two master candidates configured to use the same"
-      " certificate.")
+    if len(candidate_certs) != len(set(candidate_certs.values())):
+      self._CertError(
+        "There are at least two master candidates configured to use the same"
+        " certificate.")
 
     # collect the client certificate
     for node in nodes:
@@ -1055,45 +1065,42 @@
 
       (errcode, msg) = nresult.payload.get(constants.NV_CLIENT_CERT, None)
 
-      self._ErrorIf(
-        errcode is not None, constants.CV_ECLUSTERCLIENTCERT, None,
-        "Client certificate of node '%s' failed validation: %s (code '%s')",
-        node.uuid, msg, errcode)
-
+      if errcode is not None:
+        self._CertError(
+          "Client certificate of node '%s' failed validation: %s (code '%s')",
+          node.uuid, msg, errcode)
       if not errcode:
         digest = msg
         if node.master_candidate:
           if node.uuid in candidate_certs:
-            self._ErrorIf(
-              digest != candidate_certs[node.uuid],
-              constants.CV_ECLUSTERCLIENTCERT, None,
-              "Client certificate digest of master candidate '%s' does not"
-              " match its entry in the cluster's map of master candidate"
-              " certificates. Expected: %s Got: %s", node.uuid,
-              digest, candidate_certs[node.uuid])
+            if digest != candidate_certs[node.uuid]:
+              self._CertError(
+                "Client certificate digest of master candidate '%s' does not"
+                " match its entry in the cluster's map of master candidate"
+                " certificates. Expected: %s Got: %s", node.uuid,
+                digest, candidate_certs[node.uuid])
           else:
-            self._ErrorIf(
-              True, constants.CV_ECLUSTERCLIENTCERT, None,
+            self._CertError(
               "The master candidate '%s' does not have an entry in the"
               " map of candidate certificates.", node.uuid)
-            self._ErrorIf(
-              digest in candidate_certs.values(),
-              constants.CV_ECLUSTERCLIENTCERT, None,
-              "Master candidate '%s' is using a certificate of another node.",
-              node.uuid)
+            if digest in candidate_certs.values():
+              self._CertError(
+                "Master candidate '%s' is using a certificate of another node.",
+                node.uuid)
         else:
-          self._ErrorIf(
-            node.uuid in candidate_certs,
-            constants.CV_ECLUSTERCLIENTCERT, None,
-            "Node '%s' is not a master candidate, but still listed in the"
-            " map of master candidate certificates.", node.uuid)
-          self._ErrorIf(
-            (node.uuid not in candidate_certs) and
-              (digest in candidate_certs.values()),
-            constants.CV_ECLUSTERCLIENTCERT, None,
-            "Node '%s' is not a master candidate and is incorrectly using a"
-            " certificate of another node which is master candidate.",
-            node.uuid)
+          if node.uuid in candidate_certs:
+            self._CertError(
+              "Node '%s' is not a master candidate, but still listed in the"
+              " map of master candidate certificates.", node.uuid)
+          if (node.uuid not in candidate_certs and
+              digest in candidate_certs.values()):
+            self._CertError(
+              "Node '%s' is not a master candidate and is incorrectly using a"
+              " certificate of another node which is master candidate.",
+              node.uuid)
+
+    if self._cert_error_found:
+      self._CertError(rebuild_certs_msg)
 
   def _VerifySshSetup(self, nodes, all_nvinfo):
     """Evaluates the verification results of the SSH setup and clutter test.
diff --git a/test/py/cmdlib/cluster_unittest.py b/test/py/cmdlib/cluster_unittest.py
index d865dc2..22701d9 100644
--- a/test/py/cmdlib/cluster_unittest.py
+++ b/test/py/cmdlib/cluster_unittest.py
@@ -1231,8 +1231,13 @@
         .Build()
     op = opcodes.OpClusterVerifyGroup(group_name="default", verbose=True)
     self.ExecOpCode(op)
-    self.mcpu.assertLogContainsRegex("Client certificate")
-    self.mcpu.assertLogContainsRegex("failed validation")
+    regexps = (
+      "Client certificate",
+      "failed validation",
+      "gnt-cluster renew-crypto --new-node-certificates",
+    )
+    for r in regexps:
+      self.mcpu.assertLogContainsRegex(r)
 
   def testVerifyNoMasterCandidateMap(self):
     client_cert = "client-cert-digest"
@@ -1246,6 +1251,8 @@
     self.ExecOpCode(op)
     self.mcpu.assertLogContainsRegex(
       "list of master candidate certificates is empty")
+    self.mcpu.assertLogContainsRegex(
+      "gnt-cluster renew-crypto --new-node-certificates")
 
   def testVerifyNoSharingMasterCandidates(self):
     client_cert = "client-cert-digest"
@@ -1261,6 +1268,8 @@
     self.ExecOpCode(op)
     self.mcpu.assertLogContainsRegex(
       "two master candidates configured to use the same")
+    self.mcpu.assertLogContainsRegex(
+      "gnt-cluster renew-crypto --new-node-certificates")
 
   def testVerifyMasterCandidateCertMismatch(self):
     client_cert = "client-cert-digest"
@@ -1273,6 +1282,8 @@
     op = opcodes.OpClusterVerifyGroup(group_name="default", verbose=True)
     self.ExecOpCode(op)
     self.mcpu.assertLogContainsRegex("does not match its entry")
+    self.mcpu.assertLogContainsRegex(
+      "gnt-cluster renew-crypto --new-node-certificates")
 
   def testVerifyMasterCandidateUnregistered(self):
     client_cert = "client-cert-digest"
@@ -1285,6 +1296,8 @@
     op = opcodes.OpClusterVerifyGroup(group_name="default", verbose=True)
     self.ExecOpCode(op)
     self.mcpu.assertLogContainsRegex("does not have an entry")
+    self.mcpu.assertLogContainsRegex(
+      "gnt-cluster renew-crypto --new-node-certificates")
 
   def testVerifyMasterCandidateOtherNodesCert(self):
     client_cert = "client-cert-digest"
@@ -1297,6 +1310,8 @@
     op = opcodes.OpClusterVerifyGroup(group_name="default", verbose=True)
     self.ExecOpCode(op)
     self.mcpu.assertLogContainsRegex("using a certificate of another node")
+    self.mcpu.assertLogContainsRegex(
+      "gnt-cluster renew-crypto --new-node-certificates")
 
   def testNormalNodeStillInList(self):
     self._AddNormalNode()
@@ -1314,8 +1329,13 @@
         .Build()
     op = opcodes.OpClusterVerifyGroup(group_name="default", verbose=True)
     self.ExecOpCode(op)
-    self.mcpu.assertLogContainsRegex("not a master candidate")
-    self.mcpu.assertLogContainsRegex("still listed")
+    regexps = (
+      "not a master candidate",
+      "still listed",
+      "gnt-cluster renew-crypto --new-node-certificates",
+    )
+    for r in regexps:
+      self.mcpu.assertLogContainsRegex(r)
 
   def testNormalNodeStealingMasterCandidateCert(self):
     self._AddNormalNode()
@@ -1331,9 +1351,13 @@
         .Build()
     op = opcodes.OpClusterVerifyGroup(group_name="default", verbose=True)
     self.ExecOpCode(op)
-    self.mcpu.assertLogContainsRegex("not a master candidate")
-    self.mcpu.assertLogContainsRegex(
-      "certificate of another node which is master candidate")
+    regexps = (
+      "not a master candidate",
+      "certificate of another node which is master candidate",
+      "gnt-cluster renew-crypto --new-node-certificates",
+    )
+    for r in regexps:
+      self.mcpu.assertLogContainsRegex(r)
 
 
 class TestLUClusterVerifyGroupMethods(CmdlibTestCase):