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 "base/logging.h"
#include "net/cert/ct_log_verifier_util.h"
#include "net/cert/ct_serialization.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,
    0xc8, 0x99, 0x6f, 0xb9, 0x24, 0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b,
    0x93, 0x4c, 0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55};

bool IsPowerOfTwo(uint64_t n) {
  return n != 0 && (n & (n - 1)) == 0;
}

}  // namespace

// static
scoped_refptr<const CTLogVerifier> CTLogVerifier::Create(
    const base::StringPiece& public_key,
    const base::StringPiece& description,
    const base::StringPiece& url) {
  GURL log_url(url.as_string());
  if (!log_url.is_valid())
    return nullptr;
  scoped_refptr<CTLogVerifier> result(new CTLogVerifier(description, log_url));
  if (!result->Init(public_key))
    return nullptr;
  return result;
}

CTLogVerifier::CTLogVerifier(const base::StringPiece& description,
                             const GURL& url)
    : description_(description.as_string()),
      url_(url),
      hash_algorithm_(ct::DigitallySigned::HASH_ALGO_NONE),
      signature_algorithm_(ct::DigitallySigned::SIG_ALGO_ANONYMOUS),
      public_key_(NULL) {
  DCHECK(url_.is_valid());
}

bool CTLogVerifier::Verify(const ct::LogEntry& entry,
                           const ct::SignedCertificateTimestamp& sct) const {
  if (sct.log_id != key_id()) {
    DVLOG(1) << "SCT is not signed by this log.";
    return false;
  }

  if (!SignatureParametersMatch(sct.signature))
    return false;

  std::string serialized_log_entry;
  if (!ct::EncodeLogEntry(entry, &serialized_log_entry)) {
    DVLOG(1) << "Unable to serialize entry.";
    return false;
  }
  std::string serialized_data;
  if (!ct::EncodeV1SCTSignedData(sct.timestamp, serialized_log_entry,
                                 sct.extensions, &serialized_data)) {
    DVLOG(1) << "Unable to create SCT to verify.";
    return false;
  }

  return VerifySignature(serialized_data, sct.signature.signature_data);
}

bool CTLogVerifier::VerifySignedTreeHead(
    const ct::SignedTreeHead& signed_tree_head) const {
  if (!SignatureParametersMatch(signed_tree_head.signature))
    return false;

  std::string serialized_data;
  ct::EncodeTreeHeadSignature(signed_tree_head, &serialized_data);
  if (VerifySignature(serialized_data,
                      signed_tree_head.signature.signature_data)) {
    if (signed_tree_head.tree_size == 0) {
      // Root hash must equate SHA256 hash of the empty string.
      return (memcmp(signed_tree_head.sha256_root_hash, kSHA256EmptyStringHash,
                     ct::kSthRootHashLength) == 0);
    }
    return true;
  }
  return false;
}

bool CTLogVerifier::SignatureParametersMatch(
    const ct::DigitallySigned& signature) const {
  if (!signature.SignatureParametersMatch(hash_algorithm_,
                                          signature_algorithm_)) {
    DVLOG(1) << "Mismatched hash or signature algorithm. Hash: "
             << hash_algorithm_ << " vs " << signature.hash_algorithm
             << " Signature: " << signature_algorithm_ << " vs "
             << signature.signature_algorithm << ".";
    return false;
  }

  return true;
}

bool CTLogVerifier::VerifyConsistencyProof(
    const ct::MerkleConsistencyProof& proof,
    const std::string& old_tree_hash,
    const std::string& new_tree_hash) const {
  // Proof does not originate from this log.
  if (key_id_ != proof.log_id)
    return false;

  // Cannot prove consistency from a tree of a certain size to a tree smaller
  // than that - only the other way around.
  if (proof.first_tree_size > proof.second_tree_size)
    return false;

  // If the proof is between trees of the same size, then the 'proof'
  // is really just a statement that the tree hasn't changed. If this
  // is the case, there should be no proof nodes, and both the old
  // and new hash should be equivalent.
  if (proof.first_tree_size == proof.second_tree_size)
    return proof.nodes.empty() && old_tree_hash == new_tree_hash;

  // It is possible to call this method to prove consistency between the
  // initial state of a log (i.e. an empty tree) and a later root. In that
  // case, the only valid proof is an empty proof.
  if (proof.first_tree_size == 0)
    return proof.nodes.empty();

  // Implement the algorithm described in
  // https://tools.ietf.org/html/draft-ietf-trans-rfc6962-bis-11#section-9.4.2
  //
  // It maintains a pair of hashes |fr| and |sr|, initialized to the same
  // value. Each node in |proof| will be hashed to the left of both |fr| and
  // |sr| or to the right of only |sr|. The proof is then valid if |fr| is
  // |old_tree_hash| and |sr| is |new_tree_hash|, proving that tree nodes which
  // make up |old_tree_hash| are a prefix of |new_tree_hash|.

  // At this point, the algorithm's preconditions must be satisfied.
  DCHECK_LT(0u, proof.first_tree_size);
  DCHECK_LT(proof.first_tree_size, proof.second_tree_size);

  // 1. If "first" is an exact power of 2, then prepend "first_hash" to the
  // "consistency_path" array.
  base::StringPiece first_proof_node = old_tree_hash;
  std::vector<std::string>::const_iterator iter = proof.nodes.begin();
  if (!IsPowerOfTwo(proof.first_tree_size)) {
    if (iter == proof.nodes.end())
      return false;
    first_proof_node = *iter;
    ++iter;
  }
  // iter now points to the second node in the modified proof.nodes.

  // 2. Set "fn" to "first - 1" and "sn" to "second - 1".
  uint64_t fn = proof.first_tree_size - 1;
  uint64_t sn = proof.second_tree_size - 1;

  // 3. If "LSB(fn)" is set, then right-shift both "fn" and "sn" equally until
  // "LSB(fn)" is not set.
  while (fn & 1) {
    fn >>= 1;
    sn >>= 1;
  }

  // 4. Set both "fr" and "sr" to the first value in the "consistency_path"
  // array.
  std::string fr = first_proof_node.as_string();
  std::string sr = first_proof_node.as_string();

  // 5. For each subsequent value "c" in the "consistency_path" array:
  for (; iter != proof.nodes.end(); ++iter) {
    // The proof should end exactly when |sn| becomes zero. This check is
    // missing from the draft specification. It and the additional check below
    // ensure the proof is consistent with the tree sizes but is not necessary
    // to ensure |old_tree_hash| is a prefix of |new_tree_hash|.
    if (sn == 0)
      return false;
    // If "LSB(fn)" is set, or if "fn" is equal to "sn", then:
    if ((fn & 1) || fn == sn) {
      // 1. Set "fr" to "HASH(0x01 || c || fr)"
      //    Set "sr" to "HASH(0x01 || c || sr)"
      fr = ct::internal::HashNodes(*iter, fr);
      sr = ct::internal::HashNodes(*iter, sr);

      // 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 "sr" to "HASH(0x01 || sr || c)"
      sr = ct::internal::HashNodes(sr, *iter);
    }

    // Finally, right-shift both "fn" and "sn" one time.
    fn >>= 1;
    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 and that the "sr" calculated is equal to the
  // "second_hash" supplied.
  //
  // The proof should also end exactly when |sn| becomes zero. This check is
  // missing from the draft specification. It and the additional check above
  // ensure the proof is consistent with the tree sizes but is not necessary to
  // ensure |old_tree_hash| is a prefix of |new_tree_hash|.
  return fr == old_tree_hash && sr == new_tree_hash && sn == 0;
}

}  // namespace net