net/cert/crl_set.cc

   1 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "base/base64.h"
   6 #include "base/format_macros.h"
   7 #include "base/json/json_reader.h"
   8 #include "base/logging.h"
   9 #include "base/stl_util.h"
  10 #include "base/strings/string_util.h"
  11 #include "base/strings/stringprintf.h"
  12 #include "base/time/time.h"
  13 #include "base/values.h"
  14 #include "crypto/sha2.h"
  15 #include "net/cert/crl_set.h"
  16 #include "third_party/zlib/zlib.h"
  17
  18 namespace net {
  19
  20 // Decompress zlib decompressed |in| into |out|. |out_len| is the number of
  21 // bytes at |out| and must be exactly equal to the size of the decompressed
  22 // data.
  23 static bool DecompressZlib(uint8* out, int out_len, base::StringPiece in) {
  24   z_stream z;
  25   memset(&z, 0, sizeof(z));
  26
  27   z.next_in = reinterpret_cast<Bytef*>(const_cast<char*>(in.data()));
  28   z.avail_in = in.size();
  29   z.next_out = reinterpret_cast<Bytef*>(out);
  30   z.avail_out = out_len;
  31
  32   if (inflateInit(&z) != Z_OK)
  33     return false;
  34   bool ret = false;
  35   int r = inflate(&z, Z_FINISH);
  36   if (r != Z_STREAM_END)
  37     goto err;
  38   if (z.avail_in || z.avail_out)
  39     goto err;
  40   ret = true;
  41
  42  err:
  43   inflateEnd(&z);
  44   return ret;
  45 }
  46
  47 CRLSet::CRLSet()
  48     : sequence_(0),
  49       not_after_(0) {
  50 }
  51
  52 CRLSet::~CRLSet() {
  53 }
  54
  55 // CRLSet format:
  56 //
  57 // uint16le header_len
  58 // byte[header_len] header_bytes
  59 // repeated {
  60 //   byte[32] parent_spki_sha256
  61 //   uint32le num_serials
  62 //   [num_serials] {
  63 //     uint8 serial_length;
  64 //     byte[serial_length] serial;
  65 //   }
  66 //
  67 // header_bytes consists of a JSON dictionary with the following keys:
  68 //   Version (int): currently 0
  69 //   ContentType (string): "CRLSet" or "CRLSetDelta" (magic value)
  70 //   DeltaFrom (int32): if this is a delta update (see below), then this
  71 //       contains the sequence number of the base CRLSet.
  72 //   Sequence (int32): the monotonic sequence number of this CRL set.
  73 //
  74 // A delta CRLSet is similar to a CRLSet:
  75 //
  76 // struct CompressedChanges {
  77 //    uint32le uncompressed_size
  78 //    uint32le compressed_size
  79 //    byte[compressed_size] zlib_data
  80 // }
  81 //
  82 // uint16le header_len
  83 // byte[header_len] header_bytes
  84 // CompressedChanges crl_changes
  85 // [crl_changes.uncompressed_size] {
  86 //   switch (crl_changes[i]) {
  87 //   case 0:
  88 //     // CRL is the same
  89 //   case 1:
  90 //     // New CRL inserted
  91 //     // See CRL structure from the non-delta format
  92 //   case 2:
  93 //     // CRL deleted
  94 //   case 3:
  95 //     // CRL changed
  96 //     CompressedChanges serials_changes
  97 //     [serials_changes.uncompressed_size] {
  98 //       switch (serials_changes[i]) {
  99 //       case 0:
 100 //         // the serial is the same
 101 //       case 1:
 102 //         // serial inserted
 103 //         uint8 serial_length
 104 //         byte[serial_length] serial
 105 //       case 2:
 106 //         // serial deleted
 107 //       }
 108 //     }
 109 //   }
 110 // }
 111 //
 112 // A delta CRLSet applies to a specific CRL set as given in the
 113 // header's "DeltaFrom" value. The delta describes the changes to each CRL
 114 // in turn with a zlib compressed array of options: either the CRL is the same,
 115 // a new CRL is inserted, the CRL is deleted or the CRL is updated. In the case
 116 // of an update, the serials in the CRL are considered in the same fashion
 117 // except there is no delta update of a serial number: they are either
 118 // inserted, deleted or left the same.
 119
 120 // ReadHeader reads the header (including length prefix) from |data| and
 121 // updates |data| to remove the header on return. Caller takes ownership of the
 122 // returned pointer.
 123 static base::DictionaryValue* ReadHeader(base::StringPiece* data) {
 124   if (data->size() < 2)
 125     return NULL;
 126   uint16 header_len;
 127   memcpy(&header_len, data->data(), 2);  // assumes little-endian.
 128   data->remove_prefix(2);
 129
 130   if (data->size() < header_len)
 131     return NULL;
 132
 133   const base::StringPiece header_bytes(data->data(), header_len);
 134   data->remove_prefix(header_len);
 135
 136   scoped_ptr<base::Value> header(base::JSONReader::Read(
 137       header_bytes, base::JSON_ALLOW_TRAILING_COMMAS));
 138   if (header.get() == NULL)
 139     return NULL;
 140
 141   if (!header->IsType(base::Value::TYPE_DICTIONARY))
 142     return NULL;
 143   return reinterpret_cast<base::DictionaryValue*>(header.release());
 144 }
 145
 146 // kCurrentFileVersion is the version of the CRLSet file format that we
 147 // currently implement.
 148 static const int kCurrentFileVersion = 0;
 149
 150 static bool ReadCRL(base::StringPiece* data, std::string* out_parent_spki_hash,
 151                     std::vector<std::string>* out_serials) {
 152   if (data->size() < crypto::kSHA256Length)
 153     return false;
 154   *out_parent_spki_hash = std::string(data->data(), crypto::kSHA256Length);
 155   data->remove_prefix(crypto::kSHA256Length);
 156
 157   if (data->size() < sizeof(uint32))
 158     return false;
 159   uint32 num_serials;
 160   memcpy(&num_serials, data->data(), sizeof(uint32));  // assumes little endian
 161   data->remove_prefix(sizeof(uint32));
 162
 163   for (uint32 i = 0; i < num_serials; ++i) {
 164     uint8 serial_length;
 165     if (data->size() < sizeof(uint8))
 166       return false;
 167     memcpy(&serial_length, data->data(), sizeof(uint8));
 168     data->remove_prefix(sizeof(uint8));
 169
 170     if (data->size() < serial_length)
 171       return false;
 172     std::string serial(data->data(), serial_length);
 173     data->remove_prefix(serial_length);
 174     out_serials->push_back(serial);
 175   }
 176
 177   return true;
 178 }
 179
 180 bool CRLSet::CopyBlockedSPKIsFromHeader(base::DictionaryValue* header_dict) {
 181   base::ListValue* blocked_spkis_list = NULL;
 182   if (!header_dict->GetList("BlockedSPKIs", &blocked_spkis_list)) {
 183     // BlockedSPKIs is optional, so it's fine if we don't find it.
 184     return true;
 185   }
 186
 187   blocked_spkis_.clear();
 188
 189   for (size_t i = 0; i < blocked_spkis_list->GetSize(); ++i) {
 190     std::string spki_sha256_base64, spki_sha256;
 191     if (!blocked_spkis_list->GetString(i, &spki_sha256_base64))
 192       return false;
 193     if (!base::Base64Decode(spki_sha256_base64, &spki_sha256))
 194       return false;
 195     blocked_spkis_.push_back(spki_sha256);
 196   }
 197
 198   return true;
 199 }
 200
 201 // static
 202 bool CRLSet::Parse(base::StringPiece data, scoped_refptr<CRLSet>* out_crl_set) {
 203   // Other parts of Chrome assume that we're little endian, so we don't lose
 204   // anything by doing this.
 205 #if defined(__BYTE_ORDER)
 206   // Linux check
 207   COMPILE_ASSERT(__BYTE_ORDER == __LITTLE_ENDIAN, assumes_little_endian);
 208 #elif defined(__BIG_ENDIAN__)
 209   // Mac check
 210   #error assumes little endian
 211 #endif
 212
 213   scoped_ptr<base::DictionaryValue> header_dict(ReadHeader(&data));
 214   if (!header_dict.get())
 215     return false;
 216
 217   std::string contents;
 218   if (!header_dict->GetString("ContentType", &contents))
 219     return false;
 220   if (contents != "CRLSet")
 221     return false;
 222
 223   int version;
 224   if (!header_dict->GetInteger("Version", &version) ||
 225       version != kCurrentFileVersion) {
 226     return false;
 227   }
 228
 229   int sequence;
 230   if (!header_dict->GetInteger("Sequence", &sequence))
 231     return false;
 232
 233   double not_after;
 234   if (!header_dict->GetDouble("NotAfter", &not_after)) {
 235     // NotAfter is optional for now.
 236     not_after = 0;
 237   }
 238   if (not_after < 0)
 239     return false;
 240
 241   scoped_refptr<CRLSet> crl_set(new CRLSet);
 242   crl_set->sequence_ = static_cast<uint32>(sequence);
 243   crl_set->not_after_ = static_cast<uint64>(not_after);
 244
 245   for (size_t crl_index = 0; !data.empty(); crl_index++) {
 246     std::string parent_spki_sha256;
 247     std::vector<std::string> serials;
 248     if (!ReadCRL(&data, &parent_spki_sha256, &serials))
 249       return false;
 250
 251     crl_set->crls_.push_back(std::make_pair(parent_spki_sha256, serials));
 252     crl_set->crls_index_by_issuer_[parent_spki_sha256] = crl_index;
 253   }
 254
 255   if (!crl_set->CopyBlockedSPKIsFromHeader(header_dict.get()))
 256     return false;
 257
 258   *out_crl_set = crl_set;
 259   return true;
 260 }
 261
 262 // kMaxUncompressedChangesLength is the largest changes array that we'll
 263 // accept. This bounds the number of CRLs in the CRLSet as well as the number
 264 // of serial numbers in a given CRL.
 265 static const unsigned kMaxUncompressedChangesLength = 1024 * 1024;
 266
 267 static bool ReadChanges(base::StringPiece* data,
 268                         std::vector<uint8>* out_changes) {
 269   uint32 uncompressed_size, compressed_size;
 270   if (data->size() < 2 * sizeof(uint32))
 271     return false;
 272   // assumes little endian.
 273   memcpy(&uncompressed_size, data->data(), sizeof(uint32));
 274   data->remove_prefix(4);
 275   memcpy(&compressed_size, data->data(), sizeof(uint32));
 276   data->remove_prefix(4);
 277
 278   if (uncompressed_size > kMaxUncompressedChangesLength)
 279     return false;
 280   if (data->size() < compressed_size)
 281     return false;
 282
 283   out_changes->clear();
 284   if (uncompressed_size == 0)
 285     return true;
 286
 287   out_changes->resize(uncompressed_size);
 288   base::StringPiece compressed(data->data(), compressed_size);
 289   data->remove_prefix(compressed_size);
 290   return DecompressZlib(&(*out_changes)[0], uncompressed_size, compressed);
 291 }
 292
 293 // These are the range coder symbols used in delta updates.
 294 enum {
 295   SYMBOL_SAME = 0,
 296   SYMBOL_INSERT = 1,
 297   SYMBOL_DELETE = 2,
 298   SYMBOL_CHANGED = 3,
 299 };
 300
 301 bool ReadDeltaCRL(base::StringPiece* data,
 302                   const std::vector<std::string>& old_serials,
 303                   std::vector<std::string>* out_serials) {
 304   std::vector<uint8> changes;
 305   if (!ReadChanges(data, &changes))
 306     return false;
 307
 308   size_t i = 0;
 309   for (std::vector<uint8>::const_iterator k = changes.begin();
 310        k != changes.end(); ++k) {
 311     if (*k == SYMBOL_SAME) {
 312       if (i >= old_serials.size())
 313         return false;
 314       out_serials->push_back(old_serials[i]);
 315       i++;
 316     } else if (*k == SYMBOL_INSERT) {
 317       uint8 serial_length;
 318       if (data->size() < sizeof(uint8))
 319         return false;
 320       memcpy(&serial_length, data->data(), sizeof(uint8));
 321       data->remove_prefix(sizeof(uint8));
 322
 323       if (data->size() < serial_length)
 324         return false;
 325       const std::string serial(data->data(), serial_length);
 326       data->remove_prefix(serial_length);
 327
 328       out_serials->push_back(serial);
 329     } else if (*k == SYMBOL_DELETE) {
 330       if (i >= old_serials.size())
 331         return false;
 332       i++;
 333     } else {
 334       NOTREACHED();
 335       return false;
 336     }
 337   }
 338
 339   if (i != old_serials.size())
 340     return false;
 341   return true;
 342 }
 343
 344 bool CRLSet::ApplyDelta(const base::StringPiece& in_data,
 345                         scoped_refptr<CRLSet>* out_crl_set) {
 346   base::StringPiece data(in_data);
 347   scoped_ptr<base::DictionaryValue> header_dict(ReadHeader(&data));
 348   if (!header_dict.get())
 349     return false;
 350
 351   std::string contents;
 352   if (!header_dict->GetString("ContentType", &contents))
 353     return false;
 354   if (contents != "CRLSetDelta")
 355     return false;
 356
 357   int version;
 358   if (!header_dict->GetInteger("Version", &version) ||
 359       version != kCurrentFileVersion) {
 360     return false;
 361   }
 362
 363   int sequence, delta_from;
 364   if (!header_dict->GetInteger("Sequence", &sequence) ||
 365       !header_dict->GetInteger("DeltaFrom", &delta_from) ||
 366       delta_from < 0 ||
 367       static_cast<uint32>(delta_from) != sequence_) {
 368     return false;
 369   }
 370
 371   double not_after;
 372   if (!header_dict->GetDouble("NotAfter", &not_after)) {
 373     // NotAfter is optional for now.
 374     not_after = 0;
 375   }
 376   if (not_after < 0)
 377     return false;
 378
 379   scoped_refptr<CRLSet> crl_set(new CRLSet);
 380   crl_set->sequence_ = static_cast<uint32>(sequence);
 381   crl_set->not_after_ = static_cast<uint64>(not_after);
 382
 383   if (!crl_set->CopyBlockedSPKIsFromHeader(header_dict.get()))
 384     return false;
 385
 386   std::vector<uint8> crl_changes;
 387
 388   if (!ReadChanges(&data, &crl_changes))
 389     return false;
 390
 391   size_t i = 0, j = 0;
 392   for (std::vector<uint8>::const_iterator k = crl_changes.begin();
 393        k != crl_changes.end(); ++k) {
 394     if (*k == SYMBOL_SAME) {
 395       if (i >= crls_.size())
 396         return false;
 397       crl_set->crls_.push_back(crls_[i]);
 398       crl_set->crls_index_by_issuer_[crls_[i].first] = j;
 399       i++;
 400       j++;
 401     } else if (*k == SYMBOL_INSERT) {
 402       std::string parent_spki_hash;
 403       std::vector<std::string> serials;
 404       if (!ReadCRL(&data, &parent_spki_hash, &serials))
 405         return false;
 406       crl_set->crls_.push_back(std::make_pair(parent_spki_hash, serials));
 407       crl_set->crls_index_by_issuer_[parent_spki_hash] = j;
 408       j++;
 409     } else if (*k == SYMBOL_DELETE) {
 410       if (i >= crls_.size())
 411         return false;
 412       i++;
 413     } else if (*k == SYMBOL_CHANGED) {
 414       if (i >= crls_.size())
 415         return false;
 416       std::vector<std::string> serials;
 417       if (!ReadDeltaCRL(&data, crls_[i].second, &serials))
 418         return false;
 419       crl_set->crls_.push_back(std::make_pair(crls_[i].first, serials));
 420       crl_set->crls_index_by_issuer_[crls_[i].first] = j;
 421       i++;
 422       j++;
 423     } else {
 424       NOTREACHED();
 425       return false;
 426     }
 427   }
 428
 429   if (!data.empty())
 430     return false;
 431   if (i != crls_.size())
 432     return false;
 433
 434   *out_crl_set = crl_set;
 435   return true;
 436 }
 437
 438 // static
 439 bool CRLSet::GetIsDeltaUpdate(const base::StringPiece& in_data,
 440                               bool* is_delta) {
 441   base::StringPiece data(in_data);
 442   scoped_ptr<base::DictionaryValue> header_dict(ReadHeader(&data));
 443   if (!header_dict.get())
 444     return false;
 445
 446   std::string contents;
 447   if (!header_dict->GetString("ContentType", &contents))
 448     return false;
 449
 450   if (contents == "CRLSet") {
 451     *is_delta = false;
 452   } else if (contents == "CRLSetDelta") {
 453     *is_delta = true;
 454   } else {
 455     return false;
 456   }
 457
 458   return true;
 459 }
 460
 461 std::string CRLSet::Serialize() const {
 462   std::string header = base::StringPrintf(
 463       "{"
 464       "\"Version\":0,"
 465       "\"ContentType\":\"CRLSet\","
 466       "\"Sequence\":%u,"
 467       "\"DeltaFrom\":0,"
 468       "\"NumParents\":%u,"
 469       "\"BlockedSPKIs\":[",
 470       static_cast<unsigned>(sequence_),
 471       static_cast<unsigned>(crls_.size()));
 472
 473   for (std::vector<std::string>::const_iterator i = blocked_spkis_.begin();
 474        i != blocked_spkis_.end(); ++i) {
 475     std::string spki_hash_base64;
 476     base::Base64Encode(*i, &spki_hash_base64);
 477
 478     if (i != blocked_spkis_.begin())
 479       header += ",";
 480     header += "\"" + spki_hash_base64 + "\"";
 481   }
 482   header += "]";
 483   if (not_after_ != 0)
 484     header += base::StringPrintf(",\"NotAfter\":%" PRIu64, not_after_);
 485   header += "}";
 486
 487   size_t len = 2 /* header len */ + header.size();
 488
 489   for (CRLList::const_iterator i = crls_.begin(); i != crls_.end(); ++i) {
 490     len += i->first.size() + 4 /* num serials */;
 491     for (std::vector<std::string>::const_iterator j = i->second.begin();
 492          j != i->second.end(); ++j) {
 493       len += 1 /* serial length */ + j->size();
 494     }
 495   }
 496
 497   std::string ret;
 498   char* out = WriteInto(&ret, len + 1 /* to include final NUL */);
 499   size_t off = 0;
 500   out[off++] = header.size();
 501   out[off++] = header.size() >> 8;
 502   memcpy(out + off, header.data(), header.size());
 503   off += header.size();
 504
 505   for (CRLList::const_iterator i = crls_.begin(); i != crls_.end(); ++i) {
 506     memcpy(out + off, i->first.data(), i->first.size());
 507     off += i->first.size();
 508     const uint32 num_serials = i->second.size();
 509     memcpy(out + off, &num_serials, sizeof(num_serials));
 510     off += sizeof(num_serials);
 511
 512     for (std::vector<std::string>::const_iterator j = i->second.begin();
 513          j != i->second.end(); ++j) {
 514       out[off++] = j->size();
 515       memcpy(out + off, j->data(), j->size());
 516       off += j->size();
 517     }
 518   }
 519
 520   CHECK_EQ(off, len);
 521   return ret;
 522 }
 523
 524 CRLSet::Result CRLSet::CheckSPKI(const base::StringPiece& spki_hash) const {
 525   for (std::vector<std::string>::const_iterator i = blocked_spkis_.begin();
 526        i != blocked_spkis_.end(); ++i) {
 527     if (spki_hash.size() == i->size() &&
 528         memcmp(spki_hash.data(), i->data(), i->size()) == 0) {
 529       return REVOKED;
 530     }
 531   }
 532
 533   return GOOD;
 534 }
 535
 536 CRLSet::Result CRLSet::CheckSerial(
 537     const base::StringPiece& serial_number,
 538     const base::StringPiece& issuer_spki_hash) const {
 539   base::StringPiece serial(serial_number);
 540
 541   if (!serial.empty() && (serial[0] & 0x80) != 0) {
 542     // This serial number is negative but the process which generates CRL sets
 543     // will reject any certificates with negative serial numbers as invalid.
 544     return UNKNOWN;
 545   }
 546
 547   // Remove any leading zero bytes.
 548   while (serial.size() > 1 && serial[0] == 0x00)
 549     serial.remove_prefix(1);
 550
 551   std::map<std::string, size_t>::const_iterator i =
 552       crls_index_by_issuer_.find(issuer_spki_hash.as_string());
 553   if (i == crls_index_by_issuer_.end())
 554     return UNKNOWN;
 555   const std::vector<std::string>& serials = crls_[i->second].second;
 556
 557   for (std::vector<std::string>::const_iterator i = serials.begin();
 558        i != serials.end(); ++i) {
 559     if (base::StringPiece(*i) == serial)
 560       return REVOKED;
 561   }
 562
 563   return GOOD;
 564 }
 565
 566 bool CRLSet::IsExpired() const {
 567   if (not_after_ == 0)
 568     return false;
 569
 570   uint64 now = base::Time::Now().ToTimeT();
 571   return now > not_after_;
 572 }
 573
 574 uint32 CRLSet::sequence() const {
 575   return sequence_;
 576 }
 577
 578 const CRLSet::CRLList& CRLSet::crls() const {
 579   return crls_;
 580 }
 581
 582 // static
 583 CRLSet* CRLSet::EmptyCRLSetForTesting() {
 584   return ForTesting(false, NULL, "");
 585 }
 586
 587 CRLSet* CRLSet::ExpiredCRLSetForTesting() {
 588   return ForTesting(true, NULL, "");
 589 }
 590
 591 // static
 592 CRLSet* CRLSet::ForTesting(bool is_expired,
 593                            const SHA256HashValue* issuer_spki,
 594                            const std::string& serial_number) {
 595   CRLSet* crl_set = new CRLSet;
 596   if (is_expired)
 597     crl_set->not_after_ = 1;
 598   if (issuer_spki != NULL) {
 599     const std::string spki(reinterpret_cast<const char*>(issuer_spki->data),
 600                            sizeof(issuer_spki->data));
 601     crl_set->crls_.push_back(make_pair(spki, std::vector<std::string>()));
 602     crl_set->crls_index_by_issuer_[spki] = 0;
 603   }
 604
 605   if (!serial_number.empty())
 606     crl_set->crls_[0].second.push_back(serial_number);
 607
 608   return crl_set;
 609 }
 610
 611 }  // namespace net