net/cert/crl_set_storage.cc

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