// 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 <stdint.h>

#include <string>

#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_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.
uint64_t CalculateNearestPowerOfTwo(uint64_t n) {
  DCHECK_GT(n, 1u);

  uint64_t ret = UINT64_C(1) << 63;
  while (ret >= n)
    ret >>= 1;

  return ret;
}

// The following structures, TestVector and ProofTestVector are used for
// definining test proofs later on.

// A single hash node.
struct TestVector {
  const char* const str;
  size_t length_bytes;
};

// A single consistency proof. Contains the old and new tree sizes
// (snapshot1 and snapshot2), the length of the proof (proof_length) and
// at most 3 proof nodes (all test proofs will be for a tree of size 8).
struct ProofTestVector {
  uint64_t snapshot1;
  uint64_t snapshot2;
  size_t proof_length;
  TestVector proof[3];
};

// All test data replicated from
// https://github.com/google/certificate-transparency/blob/c41b090ecc14ddd6b3531dc7e5ce36b21e253fdd/cpp/merkletree/merkle_tree_test.cc
// A hash of the empty string.
const TestVector kSHA256EmptyTreeHash = {
    "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855", 32};

// Node hashes for a sample tree of size 8 (each element in this array is
// a node hash, not leaf data; order represents order of the nodes in the tree).
const TestVector kSHA256Roots[8] = {
    {"6e340b9cffb37a989ca544e6bb780a2c78901d3fb33738768511a30617afa01d", 32},
    {"fac54203e7cc696cf0dfcb42c92a1d9dbaf70ad9e621f4bd8d98662f00e3c125", 32},
    {"aeb6bcfe274b70a14fb067a5e5578264db0fa9b51af5e0ba159158f329e06e77", 32},
    {"d37ee418976dd95753c1c73862b9398fa2a2cf9b4ff0fdfe8b30cd95209614b7", 32},
    {"4e3bbb1f7b478dcfe71fb631631519a3bca12c9aefca1612bfce4c13a86264d4", 32},
    {"76e67dadbcdf1e10e1b74ddc608abd2f98dfb16fbce75277b5232a127f2087ef", 32},
    {"ddb89be403809e325750d3d263cd78929c2942b7942a34b77e122c9594a74c8c", 32},
    {"5dc9da79a70659a9ad559cb701ded9a2ab9d823aad2f4960cfe370eff4604328", 32}};

// A collection of consistency proofs between various sub-trees of the tree
// defined by |kSHA256Roots|.
const ProofTestVector kSHA256Proofs[4] = {
    // Empty consistency proof between trees of the same size (1).
    {1, 1, 0, {{"", 0}, {"", 0}, {"", 0}}},
    // Consistency proof between tree of size 1 and tree of size 8, with 3
    // nodes in the proof.
    {1,
     8,
     3,
     {{"96a296d224f285c67bee93c30f8a309157f0daa35dc5b87e410b78630a09cfc7", 32},
      {"5f083f0a1a33ca076a95279832580db3e0ef4584bdff1f54c8a360f50de3031e", 32},
      {"6b47aaf29ee3c2af9af889bc1fb9254dabd31177f16232dd6aab035ca39bf6e4",
       32}}},
    // Consistency proof between tree of size 6 and tree of size 8, with 3
    // nodes in the proof.
    {6,
     8,
     3,
     {{"0ebc5d3437fbe2db158b9f126a1d118e308181031d0a949f8dededebc558ef6a", 32},
      {"ca854ea128ed050b41b35ffc1b87b8eb2bde461e9e3b5596ece6b9d5975a0ae0", 32},
      {"d37ee418976dd95753c1c73862b9398fa2a2cf9b4ff0fdfe8b30cd95209614b7",
       32}}},
    // Consistency proof between tree of size 2 and tree of size 5, with 2
    // nodes in the proof.
    {2,
     5,
     2,
     {{"5f083f0a1a33ca076a95279832580db3e0ef4584bdff1f54c8a360f50de3031e", 32},
      {"bc1a0643b12e4d2d7c77918f44e0f4f79a838b6cf9ec5b5c283e1f4d88599e6b", 32},
      {"", 0}}}};

// Decodes a hexadecimal string into the binary data it represents.
std::string HexToBytes(const char* hex_data, size_t hex_data_length) {
  std::vector<uint8_t> output;
  std::string result;
  std::string hex_data_input(hex_data, hex_data_length);
  if (base::HexStringToBytes(hex_data, &output))
    result.assign(reinterpret_cast<const char*>(&output[0]), output.size());
  return result;
}

std::string GetEmptyTreeHash() {
  return HexToBytes(kSHA256EmptyTreeHash.str,
                    kSHA256EmptyTreeHash.length_bytes);
}

// Creates a ct::MerkleConsistencyProof and returns the result of
// calling log->VerifyConsistencyProof with that proof and snapshots.
bool VerifyConsistencyProof(scoped_refptr<const CTLogVerifier> log,
                            uint64_t old_tree_size,
                            const std::string& old_tree_root,
                            uint64_t new_tree_size,
                            const std::string& new_tree_root,
                            const std::vector<std::string>& proof) {
  return log->VerifyConsistencyProof(
      ct::MerkleConsistencyProof(log->key_id(), proof, old_tree_size,
                                 new_tree_size),
      old_tree_root, new_tree_root);
}

class CTLogVerifierTest : public ::testing::Test {
 public:
  CTLogVerifierTest() {}

  void SetUp() override {
    log_ = CTLogVerifier::Create(ct::GetTestPublicKey(), "testlog",
                                 "https://ct.example.com");

    ASSERT_TRUE(log_);
    ASSERT_EQ(log_->key_id(), ct::GetTestPublicKeyId());
  }

  // Given a consistency proof between two snapshots of the tree, asserts that
  // it verifies and no other combination of snapshots and proof nodes verifies.
  void VerifierConsistencyCheck(int snapshot1,
                                int snapshot2,
                                const std::string& root1,
                                const std::string& root2,
                                const std::vector<std::string>& proof) {
    // Verify the original consistency proof.
    EXPECT_TRUE(
        VerifyConsistencyProof(log_, snapshot1, root1, snapshot2, root2, proof))
        << " " << snapshot1 << " " << snapshot2;

    if (proof.empty()) {
      // For simplicity test only non-trivial proofs that have root1 != root2
      // snapshot1 != 0 and snapshot1 != snapshot2.
      return;
    }

    // Wrong snapshot index: The proof checking code should not accept
    // as a valid proof a proof for a tree size different than the original
    // size it was produced for.
    // Test that this is not the case for off-by-one changes.
    EXPECT_FALSE(VerifyConsistencyProof(log_, snapshot1 - 1, root1, snapshot2,
                                        root2, proof));
    EXPECT_FALSE(VerifyConsistencyProof(log_, snapshot1 + 1, root1, snapshot2,
                                        root2, proof));
    EXPECT_FALSE(VerifyConsistencyProof(log_, snapshot1 ^ 2, root1, snapshot2,
                                        root2, proof));

    // Test that the proof is not accepted for trees with wrong tree height.
    EXPECT_FALSE(VerifyConsistencyProof(log_, snapshot1, root1, snapshot2 * 2,
                                        root2, proof));
    EXPECT_FALSE(VerifyConsistencyProof(log_, snapshot1, root1, snapshot2 / 2,
                                        root2, proof));

    // Test that providing the wrong input root fails checking an
    // otherwise-valid proof.
    const std::string wrong_root("WrongRoot");
    EXPECT_FALSE(VerifyConsistencyProof(log_, snapshot1, root1, snapshot2,
                                        wrong_root, proof));
    EXPECT_FALSE(VerifyConsistencyProof(log_, snapshot1, wrong_root, snapshot2,
                                        root2, proof));
    // Test that swapping roots fails checking an otherwise-valid proof (that
    // the right root is used for each calculation).
    EXPECT_FALSE(VerifyConsistencyProof(log_, snapshot1, root2, snapshot2,
                                        root1, proof));

    // Variations of wrong proofs, all of which should be rejected.
    std::vector<std::string> wrong_proof;
    // Empty proof.
    EXPECT_FALSE(VerifyConsistencyProof(log_, snapshot1, root1, snapshot2,
                                        root2, wrong_proof));

    // Modify a single element in the proof.
    for (size_t j = 0; j < proof.size(); ++j) {
      wrong_proof = proof;
      wrong_proof[j] = GetEmptyTreeHash();
      EXPECT_FALSE(VerifyConsistencyProof(log_, snapshot1, root1, snapshot2,
                                          root2, wrong_proof));
    }

    // Add garbage at the end of the proof.
    wrong_proof = proof;
    wrong_proof.push_back(std::string());
    EXPECT_FALSE(VerifyConsistencyProof(log_, snapshot1, root1, snapshot2,
                                        root2, wrong_proof));
    wrong_proof.pop_back();

    wrong_proof.push_back(proof.back());
    EXPECT_FALSE(VerifyConsistencyProof(log_, snapshot1, root1, snapshot2,
                                        root2, wrong_proof));
    wrong_proof.pop_back();

    // Remove a node from the end.
    wrong_proof.pop_back();
    EXPECT_FALSE(VerifyConsistencyProof(log_, snapshot1, root1, snapshot2,
                                        root2, wrong_proof));

    // Add garbage in the beginning of the proof.
    wrong_proof.clear();
    wrong_proof.push_back(std::string());
    wrong_proof.insert(wrong_proof.end(), proof.begin(), proof.end());
    EXPECT_FALSE(VerifyConsistencyProof(log_, snapshot1, root1, snapshot2,
                                        root2, wrong_proof));

    wrong_proof[0] = proof[0];
    EXPECT_FALSE(VerifyConsistencyProof(log_, snapshot1, root1, snapshot2,
                                        root2, wrong_proof));
  }

 protected:
  scoped_refptr<const CTLogVerifier> log_;
};

TEST_F(CTLogVerifierTest, VerifiesCertSCT) {
  ct::LogEntry cert_entry;
  ct::GetX509CertLogEntry(&cert_entry);

  scoped_refptr<ct::SignedCertificateTimestamp> cert_sct;
  ct::GetX509CertSCT(&cert_sct);

  EXPECT_TRUE(log_->Verify(cert_entry, *cert_sct.get()));
}

TEST_F(CTLogVerifierTest, VerifiesPrecertSCT) {
  ct::LogEntry precert_entry;
  ct::GetPrecertLogEntry(&precert_entry);

  scoped_refptr<ct::SignedCertificateTimestamp> precert_sct;
  ct::GetPrecertSCT(&precert_sct);

  EXPECT_TRUE(log_->Verify(precert_entry, *precert_sct.get()));
}

TEST_F(CTLogVerifierTest, FailsInvalidTimestamp) {
  ct::LogEntry cert_entry;
  ct::GetX509CertLogEntry(&cert_entry);

  scoped_refptr<ct::SignedCertificateTimestamp> cert_sct;
  ct::GetX509CertSCT(&cert_sct);

  // Mangle the timestamp, so that it should fail signature validation.
  cert_sct->timestamp = base::Time::Now();

  EXPECT_FALSE(log_->Verify(cert_entry, *cert_sct.get()));
}

TEST_F(CTLogVerifierTest, FailsInvalidLogID) {
  ct::LogEntry cert_entry;
  ct::GetX509CertLogEntry(&cert_entry);

  scoped_refptr<ct::SignedCertificateTimestamp> cert_sct;
  ct::GetX509CertSCT(&cert_sct);

  // Mangle the log ID, which should cause it to match a different log before
  // attempting signature validation.
  cert_sct->log_id.assign(cert_sct->log_id.size(), '\0');

  EXPECT_FALSE(log_->Verify(cert_entry, *cert_sct.get()));
}

TEST_F(CTLogVerifierTest, VerifiesValidSTH) {
  ct::SignedTreeHead sth;
  ASSERT_TRUE(ct::GetSampleSignedTreeHead(&sth));
  EXPECT_TRUE(log_->VerifySignedTreeHead(sth));
}

TEST_F(CTLogVerifierTest, DoesNotVerifyInvalidSTH) {
  ct::SignedTreeHead sth;
  ASSERT_TRUE(ct::GetSampleSignedTreeHead(&sth));
  sth.sha256_root_hash[0] = '\x0';
  EXPECT_FALSE(log_->VerifySignedTreeHead(sth));
}

TEST_F(CTLogVerifierTest, VerifiesValidEmptySTH) {
  ct::SignedTreeHead sth;
  ASSERT_TRUE(ct::GetSampleEmptySignedTreeHead(&sth));
  EXPECT_TRUE(log_->VerifySignedTreeHead(sth));
}

TEST_F(CTLogVerifierTest, DoesNotVerifyInvalidEmptySTH) {
  ct::SignedTreeHead sth;
  ASSERT_TRUE(ct::GetBadEmptySignedTreeHead(&sth));
  EXPECT_FALSE(log_->VerifySignedTreeHead(sth));
}

// Test that excess data after the public key is rejected.
TEST_F(CTLogVerifierTest, ExcessDataInPublicKey) {
  std::string key = ct::GetTestPublicKey();
  key += "extra";

  scoped_refptr<const CTLogVerifier> log =
      CTLogVerifier::Create(key, "testlog", "https://ct.example.com");
  EXPECT_FALSE(log);
}

TEST_F(CTLogVerifierTest, VerifiesConsistencyProofEdgeCases_EmptyProof) {
  std::vector<std::string> empty_proof;
  std::string root1(GetEmptyTreeHash()), root2(GetEmptyTreeHash());

  // Snapshots that are always consistent, because they are either
  // from an empty tree to a non-empty one or for trees of the same
  // size.
  EXPECT_TRUE(VerifyConsistencyProof(log_, 0, root1, 0, root2, empty_proof));
  EXPECT_TRUE(VerifyConsistencyProof(log_, 0, root1, 1, root2, empty_proof));
  EXPECT_TRUE(VerifyConsistencyProof(log_, 1, root1, 1, root2, empty_proof));

  // Invalid consistency proofs.
  // Time travel to the past.
  EXPECT_FALSE(VerifyConsistencyProof(log_, 1, root1, 0, root2, empty_proof));
  EXPECT_FALSE(VerifyConsistencyProof(log_, 2, root1, 1, root2, empty_proof));
  // Proof between two trees of different size can never be empty.
  EXPECT_FALSE(VerifyConsistencyProof(log_, 1, root1, 2, root2, empty_proof));
}

TEST_F(CTLogVerifierTest, VerifiesConsistencyProofEdgeCases_MismatchingRoots) {
  std::vector<std::string> empty_proof;
  std::string root2;
  const std::string empty_tree_hash(GetEmptyTreeHash());

  // Roots don't match.
  EXPECT_FALSE(
      VerifyConsistencyProof(log_, 0, empty_tree_hash, 0, root2, empty_proof));
  EXPECT_FALSE(
      VerifyConsistencyProof(log_, 1, empty_tree_hash, 1, root2, empty_proof));
}

TEST_F(CTLogVerifierTest,
       VerifiesConsistencyProofEdgeCases_MatchingRootsNonEmptyProof) {
  const std::string empty_tree_hash(GetEmptyTreeHash());

  std::vector<std::string> proof;
  proof.push_back(empty_tree_hash);

  // Roots match and the tree size is either the same or the old tree size is 0,
  // but the proof is not empty (the verification code should not accept
  // proofs with redundant nodes in this case).
  proof.push_back(empty_tree_hash);
  EXPECT_FALSE(VerifyConsistencyProof(log_, 0, empty_tree_hash, 0,
                                      empty_tree_hash, proof));
  EXPECT_FALSE(VerifyConsistencyProof(log_, 0, empty_tree_hash, 1,
                                      empty_tree_hash, proof));
  EXPECT_FALSE(VerifyConsistencyProof(log_, 1, empty_tree_hash, 1,
                                      empty_tree_hash, proof));
}

TEST_F(CTLogVerifierTest, VerifiesValidConsistencyProofs) {
  std::vector<std::string> proof;
  std::string root1, root2;

  // Known good proofs.
  for (size_t i = 0; i < arraysize(kSHA256Proofs); ++i) {
    proof.clear();
    for (size_t j = 0; j < kSHA256Proofs[i].proof_length; ++j) {
      const TestVector& v = kSHA256Proofs[i].proof[j];
      proof.push_back(HexToBytes(v.str, v.length_bytes));
    }
    const uint64_t snapshot1 = kSHA256Proofs[i].snapshot1;
    const uint64_t snapshot2 = kSHA256Proofs[i].snapshot2;
    const TestVector& old_root = kSHA256Roots[snapshot1 - 1];
    const TestVector& new_root = kSHA256Roots[snapshot2 - 1];
    VerifierConsistencyCheck(
        snapshot1, snapshot2, HexToBytes(old_root.str, old_root.length_bytes),
        HexToBytes(new_root.str, new_root.length_bytes), proof);
  }
}

const char kLeafPrefix[] = {'\x00'};

// Reference implementation of RFC6962.
// This allows generation of arbitrary-sized Merkle trees and consistency
// proofs between them for testing the consistency proof validation
// code.
class TreeHasher {
 public:
  static std::string HashEmpty() {
    return HexToBytes(kSHA256EmptyTreeHash.str,
                      kSHA256EmptyTreeHash.length_bytes);
  }

  static std::string HashLeaf(const std::string& leaf) {
    SHA256HashValue sha256;
    memset(sha256.data, 0, sizeof(sha256.data));

    scoped_ptr<crypto::SecureHash> hash(
        crypto::SecureHash::Create(crypto::SecureHash::SHA256));
    hash->Update(kLeafPrefix, 1);
    hash->Update(leaf.data(), leaf.size());
    hash->Finish(sha256.data, sizeof(sha256.data));

    return std::string(reinterpret_cast<const char*>(sha256.data),
                       sizeof(sha256.data));
  }
};

// Reference implementation of Merkle hash, for cross-checking.
// Recursively calculates the hash of the root given the leaf data
// specified in |inputs|.
std::string ReferenceMerkleTreeHash(std::string* inputs, uint64_t input_size) {
  if (!input_size)
    return TreeHasher::HashEmpty();
  if (input_size == 1)
    return TreeHasher::HashLeaf(inputs[0]);

  const uint64_t split = CalculateNearestPowerOfTwo(input_size);

  return ct::internal::HashNodes(
      ReferenceMerkleTreeHash(&inputs[0], split),
      ReferenceMerkleTreeHash(&inputs[split], input_size - split));
}

// Reference implementation of snapshot consistency. Returns a
// consistency proof between two snapshots of the tree designated
// by |inputs|.
// Call with have_root1 = true.
std::vector<std::string> ReferenceSnapshotConsistency(std::string* inputs,
                                                      uint64_t snapshot2,
                                                      uint64_t snapshot1,
                                                      bool have_root1) {
  std::vector<std::string> proof;
  if (snapshot1 == 0 || snapshot1 > snapshot2)
    return proof;
  if (snapshot1 == snapshot2) {
    // Consistency proof for two equal subtrees is empty.
    if (!have_root1) {
      // Record the hash of this subtree unless it's the root for which
      // the proof was originally requested. (This happens when the snapshot1
      // tree is balanced.)
      proof.push_back(ReferenceMerkleTreeHash(inputs, snapshot1));
    }
    return proof;
  }

  // 0 < snapshot1 < snapshot2
  const uint64_t split = CalculateNearestPowerOfTwo(snapshot2);

  std::vector<std::string> subproof;
  if (snapshot1 <= split) {
    // Root of snapshot1 is in the left subtree of snapshot2.
    // Prove that the left subtrees are consistent.
    subproof =
        ReferenceSnapshotConsistency(inputs, split, snapshot1, have_root1);
    proof.insert(proof.end(), subproof.begin(), subproof.end());
    // Record the hash of the right subtree (only present in snapshot2).
    proof.push_back(ReferenceMerkleTreeHash(&inputs[split], snapshot2 - split));
  } else {
    // Snapshot1 root is at the same level as snapshot2 root.
    // Prove that the right subtrees are consistent. The right subtree
    // doesn't contain the root of snapshot1, so set have_root1 = false.
    subproof = ReferenceSnapshotConsistency(&inputs[split], snapshot2 - split,
                                            snapshot1 - split, false);
    proof.insert(proof.end(), subproof.begin(), subproof.end());
    // Record the hash of the left subtree (equal in both trees).
    proof.push_back(ReferenceMerkleTreeHash(&inputs[0], split));
  }
  return proof;
}

// "brute-force" test generating a tree of 256 entries, generating
// a consistency proof for each snapshot of each sub-tree up to that
// size and making sure it verifies.
TEST_F(CTLogVerifierTest,
       VerifiesValidConsistencyProofsFromReferenceGenerator) {
  std::vector<std::string> data;
  for (int i = 0; i < 256; ++i)
    data.push_back(std::string(1, i));

  std::vector<std::string> proof;
  std::string root1, root2;
  // More tests with reference proof generator.
  for (size_t tree_size = 1; tree_size <= data.size() / 2; ++tree_size) {
    root2 = ReferenceMerkleTreeHash(data.data(), tree_size);
    // Repeat for each snapshot in range.
    for (size_t snapshot = 1; snapshot <= tree_size; ++snapshot) {
      proof =
          ReferenceSnapshotConsistency(data.data(), tree_size, snapshot, true);
      root1 = ReferenceMerkleTreeHash(data.data(), snapshot);
      VerifierConsistencyCheck(snapshot, tree_size, root1, root2, proof);
    }
  }
}

}  // namespace

}  // namespace net