Adds a VerifyAuditProof method to CTLogVerifier

net/cert/ct_log_verifier.cc

Index: net/cert/ct_log_verifier.cc
diff --git a/net/cert/ct_log_verifier.cc b/net/cert/ct_log_verifier.cc
index 0626baa9d3051745121188d632dfc6b3a1eca11b..db875cef6766e01b4f14658b07a6aac15827ee70 100644
--- a/net/cert/ct_log_verifier.cc
+++ b/net/cert/ct_log_verifier.cc
@@ -8,12 +8,15 @@
 #include <openssl/bytestring.h>
 #include <openssl/evp.h>
 
+#include <vector>

[Ryan Sleevi, 2016/07/26 19:33:44]

Unnecessary

[Rob Percival, 2016/07/28 05:18:47]

Why? Vector is already used in this file, the #include was just missing.

[Ryan Sleevi, 2016/07/28 14:54:49]

The use is from proof.nodes on line 188, which means it should be coming from
line 20. For example, line 188 could have said "auto" and you still would have
had the dependency on line 20.

This is the sort of change that bears commenting, at least, when publishing for
reviewers - when it's a cleanup unrelated at all to the substance of the CL, but
you happened to notice on the CL. Otherwise, it becomes a test for reviewers,
and that's not ideal.

+
 #include "base/logging.h"
 #include "crypto/openssl_util.h"
 #include "crypto/scoped_openssl_types.h"
 #include "crypto/sha2.h"
 #include "net/cert/ct_log_verifier_util.h"
 #include "net/cert/ct_serialization.h"
+#include "net/cert/merkle_audit_proof.h"
 #include "net/cert/merkle_consistency_proof.h"
 #include "net/cert/signed_tree_head.h"
 
@@ -242,6 +245,53 @@ bool CTLogVerifier::VerifyConsistencyProof(
   return fr == old_tree_hash && sr == new_tree_hash && sn == 0;
 }
 
+bool CTLogVerifier::VerifyAuditProof(const ct::MerkleAuditProof& proof,
+                                     const std::string& root_hash,
+                                     const std::string& leaf_hash) const {
+  // Implements the algorithm described in
+  // https://tools.ietf.org/html/draft-ietf-trans-rfc6962-bis-17#section-10.4.1.

[Ryan Sleevi, 2016/07/28 16:40:46]

Omit the period at the end, it's getting interpreted as part of the URL :)

[Rob Percival, 2016/08/25 17:44:59]

Done.

+
+  // 1.  Compare "leaf_index" against "tree_size".  If "leaf_index" is
+  //     greater than or equal to "tree_size" fail the proof verification.
+  if (proof.leaf_index >= proof.tree_size)
+    return false;
+
+  // 2.  Set "fn" to "leaf_index" and "sn" to "tree_size - 1".
+  uint64_t fn = proof.leaf_index;
+  uint64_t sn = proof.tree_size - 1;
+  // 3.  Set "r" to "hash".
+  std::string r = leaf_hash;
+
+  // 4.  For each value "p" in the "inclusion_path" array:
+  for (const std::string& p : proof.nodes) {
+    // If "LSB(fn)" is set, or if "fn" is equal to "sn", then:
+    if ((fn & 1) || fn == sn) {
+      // 1.  Set "r" to "HASH(0x01 || p || r)"
+      r = ct::internal::HashNodes(p, r);
+
+      // 2.  If "LSB(fn)" is not set, then right-shift both "fn" and "sn"
+      //     equally until either "LSB(fn)" is set or "fn" is "0".
+      while (!(fn & 1) && fn != 0) {
+        fn >>= 1;
+        sn >>= 1;
+      }
+    } else {  // Otherwise:
+      // Set "r" to "HASH(0x01 || r || p)"
+      r = ct::internal::HashNodes(r, p);
+    }
+
+    // Finally, right-shift both "fn" and "sn" one time.
+    fn >>= 1;
+    sn >>= 1;
+  }
+
+  // 5.  Compare "sn" to 0.  Compare "r" against the "root_hash".  If "sn"
+  //     is equal to 0, and "r" and the "root_hash" are equal, then the
+  //     log has proven the inclusion of "hash".  Otherwise, fail the
+  //     proof verification.
+  return sn == 0 && r == root_hash;
+}
+
 CTLogVerifier::~CTLogVerifier() {
   crypto::OpenSSLErrStackTracer err_tracer(FROM_HERE);