ct_log_verifier_unittest.cc | Explore in Territory

// Copyright 2013 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifdef UNSAFE_BUFFERS_BUILD
// TODO(crbug.com/40284755): Remove this and spanify to fix the errors.
#pragma allow_unsafe_buffers
#endif

#include "net/cert/ct_log_verifier.h"

#include <stdint.h>

#include <algorithm>
#include <memory>
#include <string>
#include <vector>

#include "base/strings/string_number_conversions.h"
#include "base/time/time.h"
#include "crypto/secure_hash.h"
#include "net/base/hash_value.h"
#include "net/cert/ct_log_verifier_util.h"
#include "net/cert/merkle_audit_proof.h"
#include "net/cert/merkle_consistency_proof.h"
#include "net/cert/signed_certificate_timestamp.h"
#include "net/cert/signed_tree_head.h"
#include "net/test/ct_test_util.h"
#include "testing/gtest/include/gtest/gtest.h"

namespace net {

namespace {

// Calculate the power of two nearest to, but less than, |n|.
// |n| must be at least 2.
size_t CalculateNearestPowerOfTwo(size_t n) { … }

// All test data replicated from
// https://github.com/google/certificate-transparency/blob/c41b090ecc14ddd6b3531dc7e5ce36b21e253fdd/cpp/merkletree/merkle_tree_test.cc

// The SHA-256 hash of an empty Merkle tree.
const uint8_t kEmptyTreeHash[32] = …;

std::string GetEmptyTreeHash() { … }

// SHA-256 Merkle leaf hashes for the sample tree that all of the other test
// data relates to (8 leaves).
const char* const kLeafHashes[8] = …;

// SHA-256 Merkle root hashes from building the sample tree leaf-by-leaf.
// The first entry is the root when the tree contains 1 leaf, and the last is
// the root when the tree contains all 8 leaves.
const char* const kRootHashes[8] = …;

// A single consistency proof. Contains at most 3 proof nodes (all test proofs
// will be for a tree of size 8).
struct ConsistencyProofTestVector { … };

// A collection of consistency proofs between various sub-trees of the sample
// tree.
const ConsistencyProofTestVector kConsistencyProofs[] = …;

// A single audit proof. Contains at most 3 proof nodes (all test proofs will be
// for a tree of size 8).
struct AuditProofTestVector { … };

// A collection of audit proofs for various leaves and sub-trees of the tree
// defined by |kRootHashes|.
const AuditProofTestVector kAuditProofs[] = …;

// Decodes a hexadecimal string into the binary data it represents.
std::string HexToBytes(const std::string& hex_data) { … }

// Constructs a consistency/audit proof from a test vector.
// This is templated so that it can be used with both ConsistencyProofTestVector
// and AuditProofTestVector.
template <typename TestVectorType>
std::vector<std::string> GetProof(const TestVectorType& test_vector) { … }

// Creates a ct::MerkleConsistencyProof from its arguments and returns the
// result of passing this to log.VerifyConsistencyProof().
bool VerifyConsistencyProof(const CTLogVerifier& log,
                            size_t old_tree_size,
                            const std::string& old_tree_root,
                            size_t new_tree_size,
                            const std::string& new_tree_root,
                            const std::vector<std::string>& proof) { … }

// Creates a ct::MerkleAuditProof from its arguments and returns the result of
// passing this to log.VerifyAuditProof().
bool VerifyAuditProof(const CTLogVerifier& log,
                      size_t leaf,
                      size_t tree_size,
                      const std::vector<std::string>& proof,
                      const std::string& tree_root,
                      const std::string& leaf_hash) { … }

class CTLogVerifierTest : public ::testing::Test { … };

// Given an audit proof for a leaf in a Merkle tree, asserts that it verifies
// and no other combination of leaves, tree sizes and proof nodes verifies.
void CheckVerifyAuditProof(const CTLogVerifier& log,
                           size_t leaf,
                           size_t tree_size,
                           const std::vector<std::string>& proof,
                           const std::string& root_hash,
                           const std::string& leaf_hash) { … }

// Given a consistency proof between two snapshots of the tree, asserts that it
// verifies and no other combination of tree sizes and proof nodes verifies.
void CheckVerifyConsistencyProof(const CTLogVerifier& log,
                                 int old_tree_size,
                                 int new_tree_size,
                                 const std::string& old_root,
                                 const std::string& new_root,
                                 const std::vector<std::string>& proof) { … }

TEST_F(CTLogVerifierTest, VerifiesCertSCT) { … }

TEST_F(CTLogVerifierTest, VerifiesPrecertSCT) { … }

TEST_F(CTLogVerifierTest, FailsInvalidTimestamp) { … }

TEST_F(CTLogVerifierTest, FailsInvalidLogID) { … }

TEST_F(CTLogVerifierTest, VerifiesValidSTH) { … }

TEST_F(CTLogVerifierTest, DoesNotVerifyInvalidSTH) { … }

TEST_F(CTLogVerifierTest, VerifiesValidEmptySTH) { … }

TEST_F(CTLogVerifierTest, DoesNotVerifyInvalidEmptySTH) { … }

// Test that excess data after the public key is rejected.
TEST_F(CTLogVerifierTest, ExcessDataInPublicKey) { … }

TEST_F(CTLogVerifierTest, VerifiesConsistencyProofEdgeCases_EmptyProof) { … }

TEST_F(CTLogVerifierTest, VerifiesConsistencyProofEdgeCases_MismatchingRoots) { … }

TEST_F(CTLogVerifierTest,
       VerifiesConsistencyProofEdgeCases_MatchingRootsNonEmptyProof) { … }

class CTLogVerifierConsistencyProofTest
    : public CTLogVerifierTest,
      public ::testing::WithParamInterface<size_t /* proof index */> { … };

// Checks that a sample set of valid consistency proofs verify successfully.
TEST_P(CTLogVerifierConsistencyProofTest, VerifiesValidConsistencyProof) { … }

INSTANTIATE_TEST_SUITE_P(…);

class CTLogVerifierAuditProofTest
    : public CTLogVerifierTest,
      public ::testing::WithParamInterface<size_t /* proof index */> { … };

// Checks that a sample set of valid audit proofs verify successfully.
TEST_P(CTLogVerifierAuditProofTest, VerifiesValidAuditProofs) { … }

INSTANTIATE_TEST_SUITE_P(…);

TEST_F(CTLogVerifierTest, VerifiesAuditProofEdgeCases_InvalidLeafIndex) { … }

// Functions that implement algorithms from RFC6962 necessary for constructing
// Merkle trees and proofs. This allows tests to generate a variety of trees
// for exhaustive testing.
namespace rfc6962 {

// Calculates the hash of a leaf in a Merkle tree, given its content.
// See RFC6962, section 2.1.
std::string HashLeaf(const std::string& leaf) { … }

// Calculates the root hash of a Merkle tree, given its leaf data and size.
// See RFC6962, section 2.1.
std::string HashTree(std::string leaves[], size_t tree_size) { … }

// Returns a Merkle audit proof for the leaf with index |leaf_index|.
// The tree consists of |leaves[0]| to |leaves[tree_size-1]|.
// If |leaf_index| is >= |tree_size|, an empty proof will be returned.
// See RFC6962, section 2.1.1, for more details.
std::vector<std::string> CreateAuditProof(std::string leaves[],
                                          size_t tree_size,
                                          size_t leaf_index) { … }

// Returns a Merkle consistency proof between two Merkle trees.
// The old tree contains |leaves[0]| to |leaves[old_tree_size-1]|.
// The new tree contains |leaves[0]| to |leaves[new_tree_size-1]|.
// Call with |contains_old_tree| = true.
// See RFC6962, section 2.1.2, for more details.
std::vector<std::string> CreateConsistencyProof(std::string leaves[],
                                                size_t new_tree_size,
                                                size_t old_tree_size,
                                                bool contains_old_tree = true) { … }

}  // namespace rfc6962

class CTLogVerifierTestUsingGenerator
    : public CTLogVerifierTest,
      public ::testing::WithParamInterface<size_t /* tree_size */> { … };

// Checks that valid consistency proofs for a range of generated Merkle trees
// verify successfully.
TEST_P(CTLogVerifierTestUsingGenerator, VerifiesValidConsistencyProof) { … }

// Checks that valid audit proofs for a range of generated Merkle trees verify
// successfully.
TEST_P(CTLogVerifierTestUsingGenerator, VerifiesValidAuditProofs) { … }

// Test verification of consistency proofs and audit proofs for all tree sizes
// from 0 to 128.
INSTANTIATE_TEST_SUITE_P(…);

}  // namespace

}  // namespace net
chromium/net/cert/ct_log_verifier_unittest.cc
