Adds a VerifyAuditProof method to CTLogVerifier

net/cert/ct_log_verifier.cc

 // Copyright 2013 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "net/cert/ct_log_verifier.h"
 
 #include <string.h>
 #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"
 
 namespace net {
 
 namespace {
 
 // The SHA-256 hash of the empty string.
 const unsigned char kSHA256EmptyStringHash[ct::kSthRootHashLength] = {
     0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14, 0x9a, 0xfb, 0xf4,
@@ skipping 208 matching lines @@
     sn >>= 1;
   }
 
   // 6. After completing iterating through the "consistency_path" array as
   // described above, verify that the "fr" calculated is equal to the
   // "first_hash" supplied, that the "sr" calculated is equal to the
   // "second_hash" supplied and that "sn" is 0.
   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);
 
   if (public_key_)
     EVP_PKEY_free(public_key_);
 }
 
 bool CTLogVerifier::Init(const base::StringPiece& public_key) {
   crypto::OpenSSLErrStackTracer err_tracer(FROM_HERE);
 
@@ skipping 50 matching lines @@
                                    data_to_sign.size()) &&
        1 == EVP_DigestVerifyFinal(
                 &ctx, reinterpret_cast<const uint8_t*>(signature.data()),
                 signature.size()));
 
   EVP_MD_CTX_cleanup(&ctx);
   return ok;
 }
 
 }  // namespace net