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>
+
 #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 209 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-19#section-10.4.1

[davidben, 2016/10/18 22:18:57]

Nit: Kind of similar to VerifyConsistencyProof, I might add a second paragraph
here like:

//
// It maintains a hash |r|, initialized to |leaf_hash|, and hashes nodes from
|proof| into it. The proof is then valid if |r| is |root_hash|, proving that
|root_hash| includes |leaf_hash|.

The gist here is that, if you're trying to just confirm this function will never
erroneously say YES, you don't care about the exact mess around |fn| and |sn|,
which is a bit harder to verify. You only care that |r| starts at |leaf_hash|,
gets junk hashed into it, and ends at |root_hash|. (Erroneously saying YES is a
security bug, erroneously saying NO is merely an availability bug.)

[Rob Percival, 2016/10/20 13:51:47]

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) {

[davidben, 2016/10/18 22:18:57]

Shouldn't this check if sn == 0 here? That means you have more proof nodes than
you're supposed to have. It's similar to how the other algorithm was missing
checks.

Specifically, I believe if you have a valid proof for leaf_index = 7, tree_size
= 8, it will also work for leaf_index = 3, tree_size = 4; leaf_index = 1,
tree_size = 2; and leaf_index = 0, tree_size = 1.

[Rob Percival, 2016/10/20 13:51:47]

Done. Also reported this as a bug in RFC6962-bis
(https://trac.tools.ietf.org/wg/trans/trac/ticket/159).

+    // 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;
+  }

[davidben, 2016/10/18 22:18:57]

[Convinced myself this algorithm is correct, the note above aside.[

+
+  // 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