security/ct/BTVerifier.cpp

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
   3 /* This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 #include "BTVerifier.h"
   8
   9 #include <stdint.h>
  10
  11 #include "CTUtils.h"
  12 #include "SignedCertificateTimestamp.h"
  13 #include "hasht.h"
  14 #include "mozpkix/pkixnss.h"
  15 #include "mozpkix/pkixutil.h"
  16
  17 namespace mozilla {
  18 namespace ct {
  19
  20 using namespace mozilla::pkix;
  21
  22 typedef mozilla::pkix::Result Result;
  23
  24 // Common prefix lengths
  25 static const size_t kLogIdPrefixLengthBytes = 1;
  26 static const size_t kBTTreeSizeLength = 8;
  27 static const size_t kNodeHashPrefixLengthBytes = 1;
  28
  29 // Members of a SignedTreeHeadDataV2 struct
  30 static const size_t kSTHTimestampLength = 8;
  31 static const size_t kSTHExtensionsLengthBytes = 2;
  32 static const size_t kSTHSignatureLengthBytes = 2;
  33
  34 // Members of a Inclusion Proof struct
  35 static const size_t kLeafIndexLength = 8;
  36 static const size_t kInclusionPathLengthBytes = 2;
  37
  38 static Result GetDigestAlgorithmLengthAndIdentifier(
  39     DigestAlgorithm digestAlgorithm,
  40     /* out */ size_t& digestAlgorithmLength,
  41     /* out */ SECOidTag& digestAlgorithmId) {
  42   switch (digestAlgorithm) {
  43     case DigestAlgorithm::sha512:
  44       digestAlgorithmLength = SHA512_LENGTH;
  45       digestAlgorithmId = SEC_OID_SHA512;
  46       return Success;
  47     case DigestAlgorithm::sha256:
  48       digestAlgorithmLength = SHA256_LENGTH;
  49       digestAlgorithmId = SEC_OID_SHA256;
  50       return Success;
  51     default:
  52       return pkix::Result::FATAL_ERROR_INVALID_ARGS;
  53   }
  54 }
  55
  56 Result DecodeAndVerifySignedTreeHead(
  57     Input signerSubjectPublicKeyInfo, DigestAlgorithm digestAlgorithm,
  58     der::PublicKeyAlgorithm publicKeyAlgorithm, Input signedTreeHeadInput,
  59     /* out */ SignedTreeHeadDataV2& signedTreeHead) {
  60   SignedTreeHeadDataV2 result;
  61   Reader reader(signedTreeHeadInput);
  62
  63   Input logId;
  64   Result rv = ReadVariableBytes<kLogIdPrefixLengthBytes>(reader, logId);
  65   if (rv != Success) {
  66     return rv;
  67   }
  68   InputToBuffer(logId, result.logId);
  69
  70   // This is the beginning of the data covered by the signature.
  71   Reader::Mark signedDataMark = reader.GetMark();
  72
  73   rv = ReadUint<kSTHTimestampLength>(reader, result.timestamp);
  74   if (rv != Success) {
  75     return rv;
  76   }
  77
  78   rv = ReadUint<kBTTreeSizeLength>(reader, result.treeSize);
  79   if (rv != Success) {
  80     return rv;
  81   }
  82
  83   Input hash;
  84   rv = ReadVariableBytes<kNodeHashPrefixLengthBytes>(reader, hash);
  85   if (rv != Success) {
  86     return rv;
  87   }
  88   InputToBuffer(hash, result.rootHash);
  89
  90   // We ignore any extensions, but we have to read them.
  91   Input extensionsInput;
  92   rv = ReadVariableBytes<kSTHExtensionsLengthBytes>(reader, extensionsInput);
  93   if (rv != Success) {
  94     return rv;
  95   }
  96
  97   Input signedDataInput;
  98   rv = reader.GetInput(signedDataMark, signedDataInput);
  99   if (rv != Success) {
 100     return rv;
 101   }
 102
 103   SECOidTag unusedDigestAlgorithmId;
 104   size_t digestAlgorithmLength;
 105   rv = GetDigestAlgorithmLengthAndIdentifier(
 106       digestAlgorithm, digestAlgorithmLength, unusedDigestAlgorithmId);
 107   if (rv != Success) {
 108     return rv;
 109   }
 110
 111   uint8_t digestBuf[MAX_DIGEST_SIZE_IN_BYTES];
 112   rv = DigestBufNSS(signedDataInput, digestAlgorithm, digestBuf,
 113                     digestAlgorithmLength);
 114   if (rv != Success) {
 115     return rv;
 116   }
 117
 118   Input digestInput;
 119   rv = digestInput.Init(digestBuf, digestAlgorithmLength);
 120   if (rv != Success) {
 121     return rv;
 122   }
 123
 124   Input signatureInput;
 125   rv = ReadVariableBytes<kSTHSignatureLengthBytes>(reader, signatureInput);
 126   if (rv != Success) {
 127     return rv;
 128   }
 129
 130   SignedDigest signedDigest = {digestInput, digestAlgorithm, signatureInput};
 131   switch (publicKeyAlgorithm) {
 132     case der::PublicKeyAlgorithm::ECDSA:
 133       rv = VerifyECDSASignedDigestNSS(signedDigest, signerSubjectPublicKeyInfo,
 134                                       nullptr);
 135       break;
 136     case der::PublicKeyAlgorithm::RSA_PKCS1:
 137     case der::PublicKeyAlgorithm::Uninitialized:
 138     default:
 139       return Result::FATAL_ERROR_INVALID_ARGS;
 140   }
 141   if (rv != Success) {
 142     // VerifyECDSASignedDigestNSS eventually calls VFY_VerifyDigestDirect, which
 143     // can set the PR error code to SEC_ERROR_PKCS7_KEYALG_MISMATCH if the type
 144     // of key decoded from the SPKI does not match the given signature
 145     // algorithm. mozilla::pkix does not have a corresponding Result value and
 146     // turns this error code into Result::ERROR_UNKNOWN_ERROR. Since this is
 147     // uninformative, we'll turn that result into a bad signature error.
 148     if (rv == Result::ERROR_UNKNOWN_ERROR) {
 149       return Result::ERROR_BAD_SIGNATURE;
 150     }
 151     return rv;
 152   }
 153
 154   if (!reader.AtEnd()) {
 155     return pkix::Result::ERROR_BAD_DER;
 156   }
 157
 158   signedTreeHead = std::move(result);
 159   return Success;
 160 }
 161
 162 Result DecodeInclusionProof(Input input, InclusionProofDataV2& output) {
 163   InclusionProofDataV2 result;
 164   Reader reader(input);
 165
 166   Input logId;
 167   Result rv = ReadVariableBytes<kLogIdPrefixLengthBytes>(reader, logId);
 168   if (rv != Success) {
 169     return rv;
 170   }
 171
 172   rv = ReadUint<kBTTreeSizeLength>(reader, result.treeSize);
 173   if (rv != Success) {
 174     return rv;
 175   }
 176
 177   if (result.treeSize < 1) {
 178     return pkix::Result::ERROR_BAD_DER;
 179   }
 180
 181   rv = ReadUint<kLeafIndexLength>(reader, result.leafIndex);
 182   if (rv != Success) {
 183     return rv;
 184   }
 185
 186   if (result.leafIndex >= result.treeSize) {
 187     return pkix::Result::ERROR_BAD_DER;
 188   }
 189
 190   Input pathInput;
 191   rv = ReadVariableBytes<kInclusionPathLengthBytes>(reader, pathInput);
 192   if (rv != Success) {
 193     return rv;
 194   }
 195
 196   if (pathInput.GetLength() < 1) {
 197     return pkix::Result::ERROR_BAD_DER;
 198   }
 199
 200   Reader pathReader(pathInput);
 201   std::vector<Buffer> inclusionPath;
 202
 203   while (!pathReader.AtEnd()) {
 204     Input hash;
 205     rv = ReadVariableBytes<kNodeHashPrefixLengthBytes>(pathReader, hash);
 206     if (rv != Success) {
 207       return rv;
 208     }
 209
 210     Buffer hashBuffer;
 211     InputToBuffer(hash, hashBuffer);
 212
 213     inclusionPath.push_back(std::move(hashBuffer));
 214   }
 215
 216   if (!reader.AtEnd()) {
 217     return pkix::Result::ERROR_BAD_DER;
 218   }
 219
 220   InputToBuffer(logId, result.logId);
 221
 222   result.inclusionPath = std::move(inclusionPath);
 223
 224   output = std::move(result);
 225   return Success;
 226 }
 227
 228 static Result CommonFinishDigest(UniquePK11Context& context,
 229                                  size_t digestAlgorithmLength,
 230                                  /* out */ Buffer& outputBuffer) {
 231   uint32_t outLen = 0;
 232   outputBuffer.assign(digestAlgorithmLength, 0);
 233   if (PK11_DigestFinal(context.get(), outputBuffer.data(), &outLen,
 234                        digestAlgorithmLength) != SECSuccess) {
 235     return Result::FATAL_ERROR_LIBRARY_FAILURE;
 236   }
 237   if (outLen != digestAlgorithmLength) {
 238     return Result::FATAL_ERROR_LIBRARY_FAILURE;
 239   }
 240   return Success;
 241 }
 242
 243 static Result LeafHash(Input leafEntry, size_t digestAlgorithmLength,
 244                        SECOidTag digestAlgorithmId,
 245                        /* out */ Buffer& calculatedHash) {
 246   UniquePK11Context context(PK11_CreateDigestContext(digestAlgorithmId));
 247   if (!context) {
 248     return Result::FATAL_ERROR_LIBRARY_FAILURE;
 249   }
 250   const unsigned char zero = 0;
 251   if (PK11_DigestOp(context.get(), &zero, 1u) != SECSuccess) {
 252     return Result::FATAL_ERROR_LIBRARY_FAILURE;
 253   }
 254   SECItem leafEntryItem = UnsafeMapInputToSECItem(leafEntry);
 255   if (PK11_DigestOp(context.get(), leafEntryItem.data, leafEntryItem.len) !=
 256       SECSuccess) {
 257     return Result::FATAL_ERROR_LIBRARY_FAILURE;
 258   }
 259   return CommonFinishDigest(context, digestAlgorithmLength, calculatedHash);
 260 }
 261
 262 static Result NodeHash(const Buffer& left, const Buffer& right,
 263                        size_t digestAlgorithmLength,
 264                        SECOidTag digestAlgorithmId,
 265                        /* out */ Buffer& calculatedHash) {
 266   UniquePK11Context context(PK11_CreateDigestContext(digestAlgorithmId));
 267   if (!context) {
 268     return Result::FATAL_ERROR_LIBRARY_FAILURE;
 269   }
 270   const unsigned char one = 1;
 271   if (PK11_DigestOp(context.get(), &one, 1u) != SECSuccess) {
 272     return Result::FATAL_ERROR_LIBRARY_FAILURE;
 273   }
 274   if (PK11_DigestOp(context.get(), left.data(), left.size()) != SECSuccess) {
 275     return Result::FATAL_ERROR_LIBRARY_FAILURE;
 276   }
 277   if (PK11_DigestOp(context.get(), right.data(), right.size()) != SECSuccess) {
 278     return Result::FATAL_ERROR_LIBRARY_FAILURE;
 279   }
 280   return CommonFinishDigest(context, digestAlgorithmLength, calculatedHash);
 281 }
 282
 283 // This algorithm is specified by:
 284 // https://tools.ietf.org/html/draft-ietf-trans-rfc6962-bis-28#section-2.1.3.2
 285 Result VerifyInclusionProof(const InclusionProofDataV2& proof, Input leafEntry,
 286                             Input expectedRootHash,
 287                             DigestAlgorithm digestAlgorithm) {
 288   if (proof.treeSize == 0) {
 289     return pkix::Result::ERROR_BAD_SIGNATURE;
 290   }
 291   size_t digestAlgorithmLength;
 292   SECOidTag digestAlgorithmId;
 293   Result rv = GetDigestAlgorithmLengthAndIdentifier(
 294       digestAlgorithm, digestAlgorithmLength, digestAlgorithmId);
 295   if (rv != Success) {
 296     return rv;
 297   }
 298   if (proof.leafIndex >= proof.treeSize) {
 299     return pkix::Result::ERROR_BAD_SIGNATURE;
 300   }
 301   if (expectedRootHash.GetLength() != digestAlgorithmLength) {
 302     return pkix::Result::ERROR_BAD_SIGNATURE;
 303   }
 304   uint64_t leafIndex = proof.leafIndex;
 305   uint64_t lastNodeIndex = proof.treeSize - 1;
 306   Buffer calculatedHash;
 307   rv = LeafHash(leafEntry, digestAlgorithmLength, digestAlgorithmId,
 308                 calculatedHash);
 309   if (rv != Success) {
 310     return rv;
 311   }
 312   for (const auto& hash : proof.inclusionPath) {
 313     if (lastNodeIndex == 0) {
 314       return pkix::Result::ERROR_BAD_SIGNATURE;
 315     }
 316     if (leafIndex % 2 == 1 || leafIndex == lastNodeIndex) {
 317       rv = NodeHash(hash, calculatedHash, digestAlgorithmLength,
 318                     digestAlgorithmId, calculatedHash);
 319       if (rv != Success) {
 320         return rv;
 321       }
 322       if (leafIndex % 2 == 0) {
 323         while (leafIndex % 2 == 0 && lastNodeIndex > 0) {
 324           leafIndex >>= 1;
 325           lastNodeIndex >>= 1;
 326         }
 327       }
 328     } else {
 329       rv = NodeHash(calculatedHash, hash, digestAlgorithmLength,
 330                     digestAlgorithmId, calculatedHash);
 331       if (rv != Success) {
 332         return rv;
 333       }
 334     }
 335     leafIndex >>= 1;
 336     lastNodeIndex >>= 1;
 337   }
 338   if (lastNodeIndex != 0) {
 339     return pkix::Result::ERROR_BAD_SIGNATURE;
 340   }
 341   assert(calculatedHash.size() == digestAlgorithmLength);
 342   if (calculatedHash.size() != digestAlgorithmLength) {
 343     return pkix::Result::FATAL_ERROR_LIBRARY_FAILURE;
 344   }
 345   if (memcmp(calculatedHash.data(), expectedRootHash.UnsafeGetData(),
 346              digestAlgorithmLength) != 0) {
 347     return pkix::Result::ERROR_BAD_SIGNATURE;
 348   }
 349   return Success;
 350 }
 351
 352 }  // namespace ct
 353 }  // namespace mozilla