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