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   Input signatureInput;
 104   rv = ReadVariableBytes<kSTHSignatureLengthBytes>(reader, signatureInput);
 105   if (rv != Success) {
 106     return rv;
 107   }
 108
 109   switch (publicKeyAlgorithm) {
 110     case der::PublicKeyAlgorithm::ECDSA:
 111       rv = VerifyECDSASignedDataNSS(signedDataInput, digestAlgorithm,
 112                                     signatureInput, signerSubjectPublicKeyInfo,
 113                                     nullptr);
 114       break;
 115     case der::PublicKeyAlgorithm::RSA_PKCS1:
 116     default:
 117       return Result::FATAL_ERROR_INVALID_ARGS;
 118   }
 119   if (rv != Success) {
 120     return rv;
 121   }
 122
 123   if (!reader.AtEnd()) {
 124     return pkix::Result::ERROR_BAD_DER;
 125   }
 126
 127   signedTreeHead = std::move(result);
 128   return Success;
 129 }
 130
 131 Result DecodeInclusionProof(Input input, InclusionProofDataV2& output) {
 132   InclusionProofDataV2 result;
 133   Reader reader(input);
 134
 135   Input logId;
 136   Result rv = ReadVariableBytes<kLogIdPrefixLengthBytes>(reader, logId);
 137   if (rv != Success) {
 138     return rv;
 139   }
 140
 141   rv = ReadUint<kBTTreeSizeLength>(reader, result.treeSize);
 142   if (rv != Success) {
 143     return rv;
 144   }
 145
 146   if (result.treeSize < 1) {
 147     return pkix::Result::ERROR_BAD_DER;
 148   }
 149
 150   rv = ReadUint<kLeafIndexLength>(reader, result.leafIndex);
 151   if (rv != Success) {
 152     return rv;
 153   }
 154
 155   if (result.leafIndex >= result.treeSize) {
 156     return pkix::Result::ERROR_BAD_DER;
 157   }
 158
 159   Input pathInput;
 160   rv = ReadVariableBytes<kInclusionPathLengthBytes>(reader, pathInput);
 161   if (rv != Success) {
 162     return rv;
 163   }
 164
 165   if (pathInput.GetLength() < 1) {
 166     return pkix::Result::ERROR_BAD_DER;
 167   }
 168
 169   Reader pathReader(pathInput);
 170   std::vector<Buffer> inclusionPath;
 171
 172   while (!pathReader.AtEnd()) {
 173     Input hash;
 174     rv = ReadVariableBytes<kNodeHashPrefixLengthBytes>(pathReader, hash);
 175     if (rv != Success) {
 176       return rv;
 177     }
 178
 179     Buffer hashBuffer;
 180     InputToBuffer(hash, hashBuffer);
 181
 182     inclusionPath.push_back(std::move(hashBuffer));
 183   }
 184
 185   if (!reader.AtEnd()) {
 186     return pkix::Result::ERROR_BAD_DER;
 187   }
 188
 189   InputToBuffer(logId, result.logId);
 190
 191   result.inclusionPath = std::move(inclusionPath);
 192
 193   output = std::move(result);
 194   return Success;
 195 }
 196
 197 static Result CommonFinishDigest(UniquePK11Context& context,
 198                                  size_t digestAlgorithmLength,
 199                                  /* out */ Buffer& outputBuffer) {
 200   uint32_t outLen = 0;
 201   outputBuffer.assign(digestAlgorithmLength, 0);
 202   if (PK11_DigestFinal(context.get(), outputBuffer.data(), &outLen,
 203                        digestAlgorithmLength) != SECSuccess) {
 204     return Result::FATAL_ERROR_LIBRARY_FAILURE;
 205   }
 206   if (outLen != digestAlgorithmLength) {
 207     return Result::FATAL_ERROR_LIBRARY_FAILURE;
 208   }
 209   return Success;
 210 }
 211
 212 static Result LeafHash(Input leafEntry, size_t digestAlgorithmLength,
 213                        SECOidTag digestAlgorithmId,
 214                        /* out */ Buffer& calculatedHash) {
 215   UniquePK11Context context(PK11_CreateDigestContext(digestAlgorithmId));
 216   if (!context) {
 217     return Result::FATAL_ERROR_LIBRARY_FAILURE;
 218   }
 219   const unsigned char zero = 0;
 220   if (PK11_DigestOp(context.get(), &zero, 1u) != SECSuccess) {
 221     return Result::FATAL_ERROR_LIBRARY_FAILURE;
 222   }
 223   SECItem leafEntryItem = UnsafeMapInputToSECItem(leafEntry);
 224   if (PK11_DigestOp(context.get(), leafEntryItem.data, leafEntryItem.len) !=
 225       SECSuccess) {
 226     return Result::FATAL_ERROR_LIBRARY_FAILURE;
 227   }
 228   return CommonFinishDigest(context, digestAlgorithmLength, calculatedHash);
 229 }
 230
 231 static Result NodeHash(const Buffer& left, const Buffer& right,
 232                        size_t digestAlgorithmLength,
 233                        SECOidTag digestAlgorithmId,
 234                        /* out */ Buffer& calculatedHash) {
 235   UniquePK11Context context(PK11_CreateDigestContext(digestAlgorithmId));
 236   if (!context) {
 237     return Result::FATAL_ERROR_LIBRARY_FAILURE;
 238   }
 239   const unsigned char one = 1;
 240   if (PK11_DigestOp(context.get(), &one, 1u) != SECSuccess) {
 241     return Result::FATAL_ERROR_LIBRARY_FAILURE;
 242   }
 243   if (PK11_DigestOp(context.get(), left.data(), left.size()) != SECSuccess) {
 244     return Result::FATAL_ERROR_LIBRARY_FAILURE;
 245   }
 246   if (PK11_DigestOp(context.get(), right.data(), right.size()) != SECSuccess) {
 247     return Result::FATAL_ERROR_LIBRARY_FAILURE;
 248   }
 249   return CommonFinishDigest(context, digestAlgorithmLength, calculatedHash);
 250 }
 251
 252 // This algorithm is specified by:
 253 // https://tools.ietf.org/html/draft-ietf-trans-rfc6962-bis-28#section-2.1.3.2
 254 Result VerifyInclusionProof(const InclusionProofDataV2& proof, Input leafEntry,
 255                             Input expectedRootHash,
 256                             DigestAlgorithm digestAlgorithm) {
 257   if (proof.treeSize == 0) {
 258     return pkix::Result::ERROR_BAD_SIGNATURE;
 259   }
 260   size_t digestAlgorithmLength;
 261   SECOidTag digestAlgorithmId;
 262   Result rv = GetDigestAlgorithmLengthAndIdentifier(
 263       digestAlgorithm, digestAlgorithmLength, digestAlgorithmId);
 264   if (rv != Success) {
 265     return rv;
 266   }
 267   if (proof.leafIndex >= proof.treeSize) {
 268     return pkix::Result::ERROR_BAD_SIGNATURE;
 269   }
 270   if (expectedRootHash.GetLength() != digestAlgorithmLength) {
 271     return pkix::Result::ERROR_BAD_SIGNATURE;
 272   }
 273   uint64_t leafIndex = proof.leafIndex;
 274   uint64_t lastNodeIndex = proof.treeSize - 1;
 275   Buffer calculatedHash;
 276   rv = LeafHash(leafEntry, digestAlgorithmLength, digestAlgorithmId,
 277                 calculatedHash);
 278   if (rv != Success) {
 279     return rv;
 280   }
 281   for (const auto& hash : proof.inclusionPath) {
 282     if (lastNodeIndex == 0) {
 283       return pkix::Result::ERROR_BAD_SIGNATURE;
 284     }
 285     if (leafIndex % 2 == 1 || leafIndex == lastNodeIndex) {
 286       rv = NodeHash(hash, calculatedHash, digestAlgorithmLength,
 287                     digestAlgorithmId, calculatedHash);
 288       if (rv != Success) {
 289         return rv;
 290       }
 291       if (leafIndex % 2 == 0) {
 292         while (leafIndex % 2 == 0 && lastNodeIndex > 0) {
 293           leafIndex >>= 1;
 294           lastNodeIndex >>= 1;
 295         }
 296       }
 297     } else {
 298       rv = NodeHash(calculatedHash, hash, digestAlgorithmLength,
 299                     digestAlgorithmId, calculatedHash);
 300       if (rv != Success) {
 301         return rv;
 302       }
 303     }
 304     leafIndex >>= 1;
 305     lastNodeIndex >>= 1;
 306   }
 307   if (lastNodeIndex != 0) {
 308     return pkix::Result::ERROR_BAD_SIGNATURE;
 309   }
 310   assert(calculatedHash.size() == digestAlgorithmLength);
 311   if (calculatedHash.size() != digestAlgorithmLength) {
 312     return pkix::Result::FATAL_ERROR_LIBRARY_FAILURE;
 313   }
 314   if (memcmp(calculatedHash.data(), expectedRootHash.UnsafeGetData(),
 315              digestAlgorithmLength) != 0) {
 316     return pkix::Result::ERROR_BAD_SIGNATURE;
 317   }
 318   return Success;
 319 }
 320
 321 }  // namespace ct
 322 }  // namespace mozilla