CT: First step towards supporting Certificate Transparency in Chrome.

net/cert/ct_serialization.cc

Index: net/cert/ct_serialization.cc
diff --git a/net/cert/ct_serialization.cc b/net/cert/ct_serialization.cc
new file mode 100644
index 0000000000000000000000000000000000000000..fa3453e79dca608d21c219de1421f326b2011fd3
--- /dev/null
+++ b/net/cert/ct_serialization.cc
@@ -0,0 +1,387 @@
+// Copyright (c) 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_serialization.h"
+
+#include "base/basictypes.h"
+#include "base/logging.h"
+
+namespace net {
+
+namespace ct {
+
+namespace {
+
+// SCT Version length

[wtc, 2013/10/24 23:14:23]

Nit: define "SCT".

[Eran M. (Google), 2013/10/30 18:00:08]

Done.

+const size_t kVersionLengthInBytes = 1;

[wtc, 2013/10/24 23:14:23]

Since all of the lengths in this file are in bytes, "InBytes" can be omitted
from the names.

[Eran M. (Google), 2013/10/30 18:00:08]

Done.

+
+// Members of a V1 SCT
+const size_t kLogIdLengthInBytes = 32;
+const size_t kTimestampLengthInBytes = 8;
+const size_t kMaxExtensionsLengthInBytes = (1 << 16) - 1;
+const size_t kHashAlgorithmLengthInBytes = 1;
+const size_t kSigAlgorithmLengthInBytes = 1;
+const size_t kMaxSignatureLengthInBytes = (1 << 16) - 1;
+
+// Members of the digitally-signed struct of a V1 SCT
+const size_t kSignatureTypeLengthInBytes = 1;
+const size_t kLogEntryTypeLengthInBytes = 2;
+const size_t kMaxAsn1CertificateLengthInBytes = (1 << 24) - 1;
+const size_t kMaxTbsCertificateLengthInBytes = (1 << 24) - 1;
+
+const size_t kMaxSCTListLengthInBytes = (1 << 16) - 1;
+const size_t kMaxSerializedSCTLengthInBytes = (1 << 16) - 1;
+
+enum SignatureType {
+  SIGNATURE_TYPE_CERTIFICATE_TIMESTAMP = 0,

[wtc, 2013/10/24 23:14:23]

Nit: I suggest also include "tree_hash(1)" for completeness.

[Eran M. (Google), 2013/10/30 18:00:08]

Done.

+};
+
+// Returns the size, in bytes, of the length prefix needed for a field
+// capable of being |max_field_length| long. For example, a field that can
+// be 2^16 - 1 bytes needs 2 bytes to encode the length.
+// This is essentially log2(max_field_length)

[wtc, 2013/10/24 23:14:23]

It should be (log2(max_field_length) + 7)/8 because log2(max_field_length) is a
length in bits.

Also, it may be a good idea to just use constants instead of computing the
prefix lengths every time. All of the kMax***LengthInBytes constants are 2^n -
1, so their lengths are naturally bounded. More on this in ReadLength(). Note:
you can choose to not make this change. I just wanted you to consider this
alternative.

[Eran M. (Google), 2013/10/30 18:00:08]

Good idea - switched the constants to the number of bytes needed to store the
values, rather than the maximal value.

+size_t PrefixLength(size_t max_field_length) {
+  CHECK_GT(max_field_length, 0U);
+  size_t prefix_length = 0;
+
+  for (; max_field_length > 0; max_field_length >>= 8)
+    ++prefix_length;
+
+  return prefix_length;
+}
+
+// Reads a TLS-encoded variable length unsigned integer from |in|.
+// |length| indicates the size (in bytes) of the integer. On success, returns
+// true and stores the result in |*out|.

[wtc, 2013/10/24 23:14:23]

Document how |in| is updated. You may want to point out TLS encodes integers in
big-endian order.

[Eran M. (Google), 2013/10/30 18:00:08]

Done, also added the description of the modification to |in| to other relevant
methods.

+template <typename T>
+bool ReadUint(size_t length, base::StringPiece* in, T* out) {

[wtc, 2013/10/24 23:14:23]

It would be nice to assert that length <= sizeof(T). Otherwise |*out| may
receive a truncated value.

You have such an assertion in WriteUint.

[Eran M. (Google), 2013/10/30 18:00:08]

Done.

+  if (in->size() < length)
+    return false;
+  T result = 0;
+  for (size_t i = 0; i < length; ++i) {
+    result = (result << 8) | static_cast<unsigned char>((*in)[i]);
+  }

[wtc, 2013/10/24 23:14:23]

Nit: omit curly braces.

[Eran M. (Google), 2013/10/30 18:00:08]

I prefer to keep them in this context, as the body of the for loop is
non-trivial.

+  in->remove_prefix(length);
+  *out = result;
+  return true;
+}
+
+// Reads a TLS-encoded field length from |in|.
+// |max_length| indicates the maximum length supported (eg: 2^24 - 1). On
+// success, returns true and stores the result in |*out|.

[wtc, 2013/10/24 23:14:23]

Document how |in| is updated.

[Eran M. (Google), 2013/10/30 18:00:08]

Done.

+bool ReadLength(size_t max_length, base::StringPiece* in, size_t* out) {
+  size_t prefix_length = PrefixLength(max_length);
+  size_t length;
+  if (!ReadUint(prefix_length, in, &length) || length > max_length)

[wtc, 2013/10/24 23:14:23]

Since we only pass constants of the form 2^n - 1 (where n is 8, 16, or 24) as
|max_length| to ReadLength(), |length > max_length| will never be false.

I suggest we just pass |prefix_length| directly to ReadLength(). 

[Eran M. (Google), 2013/10/30 18:00:08]

Done.

+    return false;
+  *out = length;
+  return true;
+}
+
+// Reads |length| bytes from |*in|. If |*in| is too small, returns false.
+bool ReadFixedBytes(size_t length,
+                    base::StringPiece* in,
+                    base::StringPiece* out) {
+  if (in->length() < length)
+    return false;
+  out->set(in->data(), length);
+  in->remove_prefix(length);
+  return true;
+}
+
+// Reads a length-prefixed variable amount of bytes from |in|, updating |out|
+// on success. |max_length| indicates the maximum length of the field.
+bool ReadVariableBytes(size_t max_length,
+                       base::StringPiece* in,
+                       base::StringPiece* out) {
+  size_t length;
+  if (!ReadLength(max_length, in, &length))
+    return false;
+  return ReadFixedBytes(length, in, out);
+}
+
+// Reads a variable-length list that has been TLS encoded.
+// |max_list_length| contains the overall length of the encoded list.
+// |max_item_length| contains the maximum length of a single item.
+// On success, returns true and updates |*out| with the encoded list.
+bool ReadList(size_t max_list_length,
+              size_t max_item_length,
+              base::StringPiece* in,
+              std::vector<base::StringPiece>* out) {
+  std::vector<base::StringPiece> result;
+
+  base::StringPiece list_data;
+  if (!ReadVariableBytes(max_list_length, in, &list_data))
+    return false;
+
+  while (!list_data.empty()) {
+    base::StringPiece list_item;
+    if (!ReadVariableBytes(max_item_length, &list_data, &list_item)) {
+      return false;
+    }

[wtc, 2013/10/24 23:14:23]

Nit: omit curly braces.

[Eran M. (Google), 2013/10/30 18:00:08]

Added a DVLOG statement, so keeping them (to be consistent with the following
if).

+    if (list_item.empty()) {

[wtc, 2013/10/24 23:14:23]

Some types may be zero-length. But I agree it doesn't make sense for a list item
to be empty.

[Eran M. (Google), 2013/10/30 18:00:08]

This specifically is used to parse SCT lists, an SCT should definitely not have
zero length. 

Overall I think we'd want to detect (and warn about) every SCT parsing failure.
SCTs, when present, should always be verifiable.

+      DVLOG(1) << "Empty item in list";
+      return false;
+    }
+    result.push_back(list_item);
+  }
+
+  result.swap(*out);
+  return true;
+}
+
+// Checks and converts a hash algorithm.
+// |in| is the numeric representation of the algorithm.
+// If the hash algorithm value is in a set of known values, fills in |out| and
+// returns true. Otherwise, returns false.
+bool ConvertHashAlgorithm(int in, DigitallySigned::HashAlgorithm* out) {
+  switch (in) {
+    case DigitallySigned::HASH_ALGO_NONE:
+    case DigitallySigned::HASH_ALGO_MD5:
+    case DigitallySigned::HASH_ALGO_SHA1:
+    case DigitallySigned::HASH_ALGO_SHA224:
+    case DigitallySigned::HASH_ALGO_SHA256:
+    case DigitallySigned::HASH_ALGO_SHA384:
+    case DigitallySigned::HASH_ALGO_SHA512:
+      break;
+    default:
+      return false;
+  }
+  *out = static_cast<DigitallySigned::HashAlgorithm>(in);
+  return true;
+}
+
+// Checks and converts a signing algorithm.
+// |in| is the numeric representation of the algorithm.
+// If the signing algorithm value is in a set of known values, fills in |out|
+// and returns true. Otherwise, returns false.
+bool ConvertSigAlgorithm(int in, DigitallySigned::SignatureAlgorithm* out) {

[wtc, 2013/10/24 23:14:23]

Nit: Sig => Signature

[Eran M. (Google), 2013/10/30 18:00:08]

Done.

+  switch (in) {
+    case DigitallySigned::SIG_ALGO_ANONYMOUS:
+    case DigitallySigned::SIG_ALGO_RSA:
+    case DigitallySigned::SIG_ALGO_DSA:
+    case DigitallySigned::SIG_ALGO_ECDSA:
+      break;
+    default:
+      return false;
+  }
+  *out = static_cast<DigitallySigned::SignatureAlgorithm>(in);
+  return true;
+}
+
+// Checks and converts a log entry type.
+// |in| the numeric representation of the log type.
+// If the log type is 0 (X509 cert) or 1 (PreCertificate), fills in |out| and
+// returns true. Otherwise, returns false.
+bool ConvertLogEntryType(int in, LogEntry::Type* out) {
+  switch (in) {
+    case LogEntry::LOG_ENTRY_TYPE_X509:
+    case LogEntry::LOG_ENTRY_TYPE_PRECERT:
+      break;
+    default:
+      return false;
+  }
+  *out = static_cast<LogEntry::Type>(in);
+  return true;
+}
+
+// Writes a TLS-encoded variable length unsigned integer to |output|.
+// |max_length| indicates the size (in bytes) of the integer.
+// |value| the value itself to be written.
+template <typename T>
+void WriteUint(size_t max_length, T value, std::string* output) {

[wtc, 2013/10/24 23:14:23]

"max_length" is a poor parameter name because it has a different meaning in
other functions. This parameter should be named "length".

[Eran M. (Google), 2013/10/30 18:00:08]

Done.

+  DCHECK_LE(max_length, sizeof(T));
+  DCHECK(max_length == sizeof(T) || value >> (max_length * 8) == 0);
+
+  for (; max_length > 0; --max_length) {
+    output->push_back(
+        ((value & (static_cast<T>(0xFF) << ((max_length - 1) * 8)))
+        >> ((max_length - 1) * 8)));

[wtc, 2013/10/24 23:14:23]

You don't need the left shift of 0xFF. You can do this:

  (value >> ((max_length - 1) * 8))) & 0xFF

[Eran M. (Google), 2013/10/30 18:00:08]

Done.

+  }
+}
+
+// Writes a fixed-length array to |output| from |input|.
+void WriteFixedBytes(const base::StringPiece& input, std::string* output) {
+  input.AppendToString(output);
+}
+
+// Writes a variable-length array to |output|.
+// |max_field_length| indicates the length (in bytes) of the array.
+// |input| is the array itself.
+// If the size of |input| is less than |max_field_length|, encode the
+// length and data and return true. Otherwise, return false.
+bool WriteVariableBytes(size_t max_field_length,

[wtc, 2013/10/24 23:14:23]

Nit: this parameter's name should ideally match the equivalent parameter name in
ReadVariableBytes.

[Eran M. (Google), 2013/10/30 18:00:08]

Done.

+                        const base::StringPiece& input,
+                        std::string* output) {
+  if (input.size() > max_field_length)
+    return false;
+
+  size_t prefix_length = PrefixLength(max_field_length);
+  WriteUint(prefix_length, input.size(), output);
+  WriteFixedBytes(input, output);
+
+  return true;
+}
+
+// Writes a LogEntry of type X509 cert to |output|.

[wtc, 2013/10/24 23:14:23]

Nit: X509 => X.509

[Eran M. (Google), 2013/10/30 18:00:08]

Done.

+// |input| is the LogEntry containing the certificate.
+// Returns true if the leaf_cert in the LogEntry does not exceed
+// kMaxAsn1CertificateLengthInBytes and so can be written to |output|.
+bool EncodeAsn1CertLogEntry(const LogEntry& input, std::string* output) {
+  return WriteVariableBytes(kMaxAsn1CertificateLengthInBytes,
+                            input.leaf_cert, output);
+}
+
+// Writes a LogEntry of type PreCertificate to |output|.
+// |input| is the LogEntry containing the TBSCertificate and issuer key hash.
+// Returns true if the TBSCertificate component in the LogEntry does not
+// exceed kMaxTbsCertificateLengthInBytes and so can be written to |output|.
+bool EncodePrecertLogEntry(const LogEntry& input, std::string* output) {
+  WriteFixedBytes(
+      base::StringPiece(
+          reinterpret_cast<const char*>(input.issuer_key_hash.data),
+          kLogIdLengthInBytes),
+      output);
+  return WriteVariableBytes(kMaxTbsCertificateLengthInBytes,
+                            input.tbs_certificate, output);
+}
+
+}  // namespace
+
+// If |input| is less than kMaxSignatureLengthInBytes, encodes the |input|

[wtc, 2013/10/24 23:14:23]

Nit: If |input| is => If |input.signature_data| is 

[Eran M. (Google), 2013/10/30 18:00:08]

Done.

+// to |output and returns true. Otherwise, returns false.
+bool EncodeDigitallySigned(const DigitallySigned& input,
+                           std::string* output) {
+  WriteUint(kHashAlgorithmLengthInBytes, input.hash_algorithm, output);
+  WriteUint(kSigAlgorithmLengthInBytes, input.signature_algorithm,
+            output);
+  return WriteVariableBytes(kMaxSignatureLengthInBytes, input.signature_data,
+                            output);
+}
+
+// Reads and decodes a DigitallySigned object from |input|.
+// Returns true and fills |output| if all fields can be read, false otherwise.
+bool DecodeDigitallySigned(base::StringPiece* input,
+                           DigitallySigned* output) {
+  int hash_algo;
+  int sig_algo;
+  base::StringPiece sig_data;
+
+  if (!ReadUint(kHashAlgorithmLengthInBytes, input, &hash_algo) ||
+      !ReadUint(kSigAlgorithmLengthInBytes, input, &sig_algo) ||

[wtc, 2013/10/24 23:14:23]

The third argument of ReadUint (as the function name suggests) should point to
an unsigned type, but hash_algo and sig_algo are signed int.

[Eran M. (Google), 2013/10/30 18:00:08]

Done - changed to unsigned.

+      !ReadVariableBytes(kMaxSignatureLengthInBytes, input, &sig_data)) {
+    return false;
+  }
+
+  DigitallySigned result;
+  if (!ConvertHashAlgorithm(hash_algo, &result.hash_algorithm)) {
+    DVLOG(1) << "Invalid hash algorithm " << hash_algo;
+    return false;
+  }
+  if (!ConvertSigAlgorithm(sig_algo, &result.signature_algorithm)) {
+    DVLOG(1) << "Invalid signature algorithm " << sig_algo;
+    return false;
+  }
+  sig_data.CopyToString(&result.signature_data);
+
+  // XXX(rsleevi): Declare a swap specialization to avoid the extra copy
+  // of |result.signature|.

[wtc, 2013/10/24 23:14:23]

Nit: |result.signature| => |result.signature_data|

[Eran M. (Google), 2013/10/30 18:00:08]

Done.

+  *output = result;
+  return true;
+}
+
+// Encodes the |input| LogEntry to |output|. Returns true if the entry size
+// does not exceed allowed size in RFC6962, false otherwise.
+bool EncodeLogEntry(const LogEntry& input, std::string* output) {
+  WriteUint(kLogEntryTypeLengthInBytes, input.type, output);
+  switch (input.type) {
+    case LogEntry::LOG_ENTRY_TYPE_X509:
+      return EncodeAsn1CertLogEntry(input, output);
+    case LogEntry::LOG_ENTRY_TYPE_PRECERT:
+      return EncodePrecertLogEntry(input, output);
+  }
+  return false;
+}
+
+// Encodes the data signed by an SCT into |output|. The signature included in
+// the SCT is then verified over these bytes.
+// |timestamp| timestamp from the SCT.
+// |serialized_log_entry| the log entry signed by the SCT.
+// |extensions| CT extensions.
+// Returns true if the extensions' length does not exceed
+// kMaxExtensionsLengthInBytes, false otherwise.
+bool EncodeV1SCTSignedData(const base::Time& timestamp,
+                           const std::string& serialized_log_entry,
+                           const std::string& extensions,
+                           std::string* output) {
+  WriteUint(kVersionLengthInBytes, SignedCertificateTimestamp::SCT_VERSION_1,
+            output);
+  WriteUint(kSignatureTypeLengthInBytes, SIGNATURE_TYPE_CERTIFICATE_TIMESTAMP,
+            output);
+  base::TimeDelta time_since_epoch = timestamp - base::Time::UnixEpoch();
+  WriteUint(kTimestampLengthInBytes, time_since_epoch.InMilliseconds(),
+            output);
+  WriteFixedBytes(serialized_log_entry, output);

[wtc, 2013/10/24 23:14:23]

Using the function name "WriteFixedBytes" is a little misleading here because
WriteFixedBytes is documented as "Writes a fixed-length array" but
serialized_log_entry is not fixed-length.

We can use WriteFixedBytes because serialized_log_entry is already encoded.

Maybe WriteFixedBytes can be renamed WriteBytes or WriteEncodedBytes, and its
comments updated accordingly.

[Eran M. (Google), 2013/10/30 18:00:08]

Done - renamed to WriteEncodedBytes (and updated the documentation).

+  return WriteVariableBytes(kMaxExtensionsLengthInBytes, extensions, output);
+}
+
+// Decode a list of SCTs: from a single string in |input| to a vector of
+// individually-encoded SCTs |output|. This list is typically obtained
+// from the CT extension in a certificate.
+// Returns true if the list could be read and decoded successfully, false
+// otherwise (note that the validity of each individual SCT should be checked
+// separately).
+bool DecodeSCTList(base::StringPiece* input,
+                   std::vector<base::StringPiece>* output) {
+  std::vector<base::StringPiece> result;
+  if (!ReadList(kMaxSCTListLengthInBytes, kMaxSerializedSCTLengthInBytes,
+                input, &result)) {
+    return false;
+  }
+
+  if (!input->empty() || result.empty())
+    return false;
+  output->swap(result);
+  return true;
+}
+
+// Decodes a single SCT from |input| to |output|.
+// Returns true if all fields in the SCT could be read and decoded, false
+// otherwise.
+bool DecodeSignedCertificateTimestamp(base::StringPiece* input,
+                                      SignedCertificateTimestamp* output) {
+  SignedCertificateTimestamp result;
+  int version;
+  if (!ReadUint(kVersionLengthInBytes, input, &version))

[wtc, 2013/10/24 23:14:23]

|version| is a signed int, but ReadUint implies we're reading an unsigned
integer.

[Eran M. (Google), 2013/10/30 18:00:08]

Done.

+    return false;
+  if (version != SignedCertificateTimestamp::SCT_VERSION_1) {
+    DVLOG(1) << "Unsupported/invalid version " << version;
+    return false;
+  }
+
+  result.version = SignedCertificateTimestamp::SCT_VERSION_1;
+  uint64 timestamp;
+  base::StringPiece log_id;
+  base::StringPiece extensions;
+  if (!ReadFixedBytes(kLogIdLengthInBytes, input, &log_id) ||
+      !ReadUint(kTimestampLengthInBytes, input, &timestamp) ||
+      !ReadVariableBytes(kMaxExtensionsLengthInBytes, input,
+                         &extensions) ||
+      !DecodeDigitallySigned(input, &result.signature)) {
+    return false;
+  }
+  log_id.CopyToString(&result.log_id);
+  extensions.CopyToString(&result.extensions);
+  result.timestamp =
+      base::Time::UnixEpoch() +
+      base::TimeDelta::FromMilliseconds(static_cast<int64>(timestamp));

[wtc, 2013/10/24 23:14:23]

Should we validate |timestamp| before casting it to a signed type and adding it
to base::Time::UnixEpoch()?

[Eran M. (Google), 2013/10/30 18:00:08]

Done - verified that the value does not exceed max_int64.

+
+  // XXX(rsleevi): Declare a swap specialization to avoid the extra copy.
+  *output = result;
+  return true;
+}
+
+}  // namespace ct
+
+}  // namespace net