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/format_macros.h"
   9 #include "base/json/json_reader.h"
  10 #include "base/numerics/safe_conversions.h"
  11 #include "base/strings/stringprintf.h"
  12 #include "base/trace_event/trace_event.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_t* 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_t 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_t): if this is a delta update (see below), then this
  62 //       contains the sequence number of the base CRLSet.
  63 //   Sequence (int32_t): 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_t 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   uint16_t header_len;
 116   if (data->size() < sizeof(header_len))
 117     return NULL;
 118   // Assumes little-endian.
 119   memcpy(&header_len, data->data(), sizeof(header_len));
 120   data->remove_prefix(sizeof(header_len));
 121
 122   if (data->size() < header_len)
 123     return NULL;
 124
 125   const base::StringPiece header_bytes(data->data(), header_len);
 126   data->remove_prefix(header_len);
 127
 128   scoped_ptr<base::Value> header =
 129       base::JSONReader::Read(header_bytes, base::JSON_ALLOW_TRAILING_COMMAS);
 130   if (header.get() == NULL)
 131     return NULL;
 132
 133   if (!header->IsType(base::Value::TYPE_DICTIONARY))
 134     return NULL;
 135   return reinterpret_cast<base::DictionaryValue*>(header.release());
 136 }
 137
 138 // kCurrentFileVersion is the version of the CRLSet file format that we
 139 // currently implement.
 140 static const int kCurrentFileVersion = 0;
 141
 142 static bool ReadCRL(base::StringPiece* data, std::string* out_parent_spki_hash,
 143                     std::vector<std::string>* out_serials) {
 144   if (data->size() < crypto::kSHA256Length)
 145     return false;
 146   out_parent_spki_hash->assign(data->data(), crypto::kSHA256Length);
 147   data->remove_prefix(crypto::kSHA256Length);
 148
 149   uint32_t num_serials;
 150   if (data->size() < sizeof(num_serials))
 151     return false;
 152   // Assumes little endian.
 153   memcpy(&num_serials, data->data(), sizeof(num_serials));
 154   data->remove_prefix(sizeof(num_serials));
 155
 156   if (num_serials > 32 * 1024 * 1024)  // Sanity check.
 157     return false;
 158
 159   out_serials->reserve(num_serials);
 160
 161   for (uint32_t i = 0; i < num_serials; ++i) {
 162     if (data->size() < sizeof(uint8_t))
 163       return false;
 164
 165     uint8_t serial_length = data->data()[0];
 166     data->remove_prefix(sizeof(uint8_t));
 167
 168     if (data->size() < serial_length)
 169       return false;
 170
 171     out_serials->push_back(std::string());
 172     out_serials->back().assign(data->data(), serial_length);
 173     data->remove_prefix(serial_length);
 174   }
 175
 176   return true;
 177 }
 178
 179 // static
 180 bool CRLSetStorage::CopyBlockedSPKIsFromHeader(
 181     CRLSet* crl_set,
 182     base::DictionaryValue* header_dict) {
 183   base::ListValue* blocked_spkis_list = NULL;
 184   if (!header_dict->GetList("BlockedSPKIs", &blocked_spkis_list)) {
 185     // BlockedSPKIs is optional, so it's fine if we don't find it.
 186     return true;
 187   }
 188
 189   crl_set->blocked_spkis_.clear();
 190   crl_set->blocked_spkis_.reserve(blocked_spkis_list->GetSize());
 191
 192   std::string spki_sha256_base64;
 193
 194   for (size_t i = 0; i < blocked_spkis_list->GetSize(); ++i) {
 195     spki_sha256_base64.clear();
 196
 197     if (!blocked_spkis_list->GetString(i, &spki_sha256_base64))
 198       return false;
 199
 200     crl_set->blocked_spkis_.push_back(std::string());
 201     if (!base::Base64Decode(spki_sha256_base64,
 202                             &crl_set->blocked_spkis_.back())) {
 203       crl_set->blocked_spkis_.pop_back();
 204       return false;
 205     }
 206   }
 207
 208   return true;
 209 }
 210
 211 // kMaxUncompressedChangesLength is the largest changes array that we'll
 212 // accept. This bounds the number of CRLs in the CRLSet as well as the number
 213 // of serial numbers in a given CRL.
 214 static const unsigned kMaxUncompressedChangesLength = 1024 * 1024;
 215
 216 static bool ReadChanges(base::StringPiece* data,
 217                         std::vector<uint8_t>* out_changes) {
 218   uint32_t uncompressed_size, compressed_size;
 219   if (data->size() < sizeof(uncompressed_size) + sizeof(compressed_size))
 220     return false;
 221   // Assumes little endian.
 222   memcpy(&uncompressed_size, data->data(), sizeof(uncompressed_size));
 223   data->remove_prefix(sizeof(uncompressed_size));
 224   memcpy(&compressed_size, data->data(), sizeof(compressed_size));
 225   data->remove_prefix(sizeof(compressed_size));
 226
 227   if (uncompressed_size > kMaxUncompressedChangesLength)
 228     return false;
 229   if (data->size() < compressed_size)
 230     return false;
 231
 232   out_changes->clear();
 233   if (uncompressed_size == 0)
 234     return true;
 235
 236   out_changes->resize(uncompressed_size);
 237   base::StringPiece compressed(data->data(), compressed_size);
 238   data->remove_prefix(compressed_size);
 239   return DecompressZlib(&(*out_changes)[0], uncompressed_size, compressed);
 240 }
 241
 242 // These are the range coder symbols used in delta updates.
 243 enum {
 244   SYMBOL_SAME = 0,
 245   SYMBOL_INSERT = 1,
 246   SYMBOL_DELETE = 2,
 247   SYMBOL_CHANGED = 3,
 248 };
 249
 250 static bool ReadDeltaCRL(base::StringPiece* data,
 251                          const std::vector<std::string>& old_serials,
 252                          std::vector<std::string>* out_serials) {
 253   std::vector<uint8_t> changes;
 254   if (!ReadChanges(data, &changes))
 255     return false;
 256
 257   size_t i = 0;
 258   for (std::vector<uint8_t>::const_iterator k = changes.begin();
 259        k != changes.end(); ++k) {
 260     if (*k == SYMBOL_SAME) {
 261       if (i >= old_serials.size())
 262         return false;
 263       out_serials->push_back(old_serials[i]);
 264       i++;
 265     } else if (*k == SYMBOL_INSERT) {
 266       if (data->size() < sizeof(uint8_t))
 267         return false;
 268       uint8_t serial_length = data->data()[0];
 269       data->remove_prefix(sizeof(uint8_t));
 270
 271       if (data->size() < serial_length)
 272         return false;
 273       const std::string serial(data->data(), serial_length);
 274       data->remove_prefix(serial_length);
 275
 276       out_serials->push_back(serial);
 277     } else if (*k == SYMBOL_DELETE) {
 278       if (i >= old_serials.size())
 279         return false;
 280       i++;
 281     } else {
 282       NOTREACHED();
 283       return false;
 284     }
 285   }
 286
 287   if (i != old_serials.size())
 288     return false;
 289   return true;
 290 }
 291
 292 // static
 293 bool CRLSetStorage::Parse(base::StringPiece data,
 294                           scoped_refptr<CRLSet>* out_crl_set) {
 295   TRACE_EVENT0("CRLSet", "Parse");
 296   // Other parts of Chrome assume that we're little endian, so we don't lose
 297   // anything by doing this.
 298 #if defined(__BYTE_ORDER)
 299   // Linux check
 300   static_assert(__BYTE_ORDER == __LITTLE_ENDIAN, "assumes little endian");
 301 #elif defined(__BIG_ENDIAN__)
 302   // Mac check
 303   #error assumes little endian
 304 #endif
 305
 306   scoped_ptr<base::DictionaryValue> header_dict(ReadHeader(&data));
 307   if (!header_dict.get())
 308     return false;
 309
 310   std::string contents;
 311   if (!header_dict->GetString("ContentType", &contents))
 312     return false;
 313   if (contents != "CRLSet")
 314     return false;
 315
 316   int version;
 317   if (!header_dict->GetInteger("Version", &version) ||
 318       version != kCurrentFileVersion) {
 319     return false;
 320   }
 321
 322   int sequence;
 323   if (!header_dict->GetInteger("Sequence", &sequence))
 324     return false;
 325
 326   double not_after;
 327   if (!header_dict->GetDouble("NotAfter", &not_after)) {
 328     // NotAfter is optional for now.
 329     not_after = 0;
 330   }
 331   if (not_after < 0)
 332     return false;
 333
 334   scoped_refptr<CRLSet> crl_set(new CRLSet());
 335   crl_set->sequence_ = static_cast<uint32_t>(sequence);
 336   crl_set->not_after_ = static_cast<uint64_t>(not_after);
 337   crl_set->crls_.reserve(64);  // Value observed experimentally.
 338
 339   for (size_t crl_index = 0; !data.empty(); crl_index++) {
 340     // Speculatively push back a pair and pass it to ReadCRL() to avoid
 341     // unnecessary copies.
 342     crl_set->crls_.push_back(
 343         std::make_pair(std::string(), std::vector<std::string>()));
 344     std::pair<std::string, std::vector<std::string> >* const back_pair =
 345         &crl_set->crls_.back();
 346
 347     if (!ReadCRL(&data, &back_pair->first, &back_pair->second)) {
 348       // Undo the speculative push_back() performed above.
 349       crl_set->crls_.pop_back();
 350       return false;
 351     }
 352
 353     crl_set->crls_index_by_issuer_[back_pair->first] = crl_index;
 354   }
 355
 356   if (!CopyBlockedSPKIsFromHeader(crl_set.get(), header_dict.get()))
 357     return false;
 358
 359   *out_crl_set = crl_set;
 360   return true;
 361 }
 362
 363 // static
 364 bool CRLSetStorage::ApplyDelta(const CRLSet* in_crl_set,
 365                                const base::StringPiece& delta_bytes,
 366                                scoped_refptr<CRLSet>* out_crl_set) {
 367   base::StringPiece data(delta_bytes);
 368   scoped_ptr<base::DictionaryValue> header_dict(ReadHeader(&data));
 369   if (!header_dict.get())
 370     return false;
 371
 372   std::string contents;
 373   if (!header_dict->GetString("ContentType", &contents))
 374     return false;
 375   if (contents != "CRLSetDelta")
 376     return false;
 377
 378   int version;
 379   if (!header_dict->GetInteger("Version", &version) ||
 380       version != kCurrentFileVersion) {
 381     return false;
 382   }
 383
 384   int sequence, delta_from;
 385   if (!header_dict->GetInteger("Sequence", &sequence) ||
 386       !header_dict->GetInteger("DeltaFrom", &delta_from) || delta_from < 0 ||
 387       static_cast<uint32_t>(delta_from) != in_crl_set->sequence_) {
 388     return false;
 389   }
 390
 391   double not_after;
 392   if (!header_dict->GetDouble("NotAfter", &not_after)) {
 393     // NotAfter is optional for now.
 394     not_after = 0;
 395   }
 396   if (not_after < 0)
 397     return false;
 398
 399   scoped_refptr<CRLSet> crl_set(new CRLSet);
 400   crl_set->sequence_ = static_cast<uint32_t>(sequence);
 401   crl_set->not_after_ = static_cast<uint64_t>(not_after);
 402
 403   if (!CopyBlockedSPKIsFromHeader(crl_set.get(), header_dict.get()))
 404     return false;
 405
 406   std::vector<uint8_t> crl_changes;
 407
 408   if (!ReadChanges(&data, &crl_changes))
 409     return false;
 410
 411   size_t i = 0, j = 0;
 412   for (std::vector<uint8_t>::const_iterator k = crl_changes.begin();
 413        k != crl_changes.end(); ++k) {
 414     if (*k == SYMBOL_SAME) {
 415       if (i >= in_crl_set->crls_.size())
 416         return false;
 417       crl_set->crls_.push_back(in_crl_set->crls_[i]);
 418       crl_set->crls_index_by_issuer_[in_crl_set->crls_[i].first] = j;
 419       i++;
 420       j++;
 421     } else if (*k == SYMBOL_INSERT) {
 422       std::string parent_spki_hash;
 423       std::vector<std::string> serials;
 424       if (!ReadCRL(&data, &parent_spki_hash, &serials))
 425         return false;
 426       crl_set->crls_.push_back(std::make_pair(parent_spki_hash, serials));
 427       crl_set->crls_index_by_issuer_[parent_spki_hash] = j;
 428       j++;
 429     } else if (*k == SYMBOL_DELETE) {
 430       if (i >= in_crl_set->crls_.size())
 431         return false;
 432       i++;
 433     } else if (*k == SYMBOL_CHANGED) {
 434       if (i >= in_crl_set->crls_.size())
 435         return false;
 436       std::vector<std::string> serials;
 437       if (!ReadDeltaCRL(&data, in_crl_set->crls_[i].second, &serials))
 438         return false;
 439       crl_set->crls_.push_back(
 440           std::make_pair(in_crl_set->crls_[i].first, serials));
 441       crl_set->crls_index_by_issuer_[in_crl_set->crls_[i].first] = j;
 442       i++;
 443       j++;
 444     } else {
 445       NOTREACHED();
 446       return false;
 447     }
 448   }
 449
 450   if (!data.empty())
 451     return false;
 452   if (i != in_crl_set->crls_.size())
 453     return false;
 454
 455   *out_crl_set = crl_set;
 456   return true;
 457 }
 458
 459 // static
 460 bool CRLSetStorage::GetIsDeltaUpdate(const base::StringPiece& bytes,
 461                                      bool* is_delta) {
 462   base::StringPiece data(bytes);
 463   scoped_ptr<base::DictionaryValue> header_dict(ReadHeader(&data));
 464   if (!header_dict.get())
 465     return false;
 466
 467   std::string contents;
 468   if (!header_dict->GetString("ContentType", &contents))
 469     return false;
 470
 471   if (contents == "CRLSet") {
 472     *is_delta = false;
 473   } else if (contents == "CRLSetDelta") {
 474     *is_delta = true;
 475   } else {
 476     return false;
 477   }
 478
 479   return true;
 480 }
 481
 482 // static
 483 std::string CRLSetStorage::Serialize(const CRLSet* crl_set) {
 484   std::string header = base::StringPrintf(
 485       "{"
 486       "\"Version\":0,"
 487       "\"ContentType\":\"CRLSet\","
 488       "\"Sequence\":%u,"
 489       "\"DeltaFrom\":0,"
 490       "\"NumParents\":%u,"
 491       "\"BlockedSPKIs\":[",
 492       static_cast<unsigned>(crl_set->sequence_),
 493       static_cast<unsigned>(crl_set->crls_.size()));
 494
 495   for (std::vector<std::string>::const_iterator i =
 496            crl_set->blocked_spkis_.begin();
 497        i != crl_set->blocked_spkis_.end(); ++i) {
 498     std::string spki_hash_base64;
 499     base::Base64Encode(*i, &spki_hash_base64);
 500
 501     if (i != crl_set->blocked_spkis_.begin())
 502       header += ",";
 503     header += "\"" + spki_hash_base64 + "\"";
 504   }
 505   header += "]";
 506   if (crl_set->not_after_ != 0)
 507     header += base::StringPrintf(",\"NotAfter\":%" PRIu64, crl_set->not_after_);
 508   header += "}";
 509
 510   size_t len = 2 /* header len */ + header.size();
 511
 512   for (CRLSet::CRLList::const_iterator i = crl_set->crls_.begin();
 513        i != crl_set->crls_.end(); ++i) {
 514     len += i->first.size() + 4 /* num serials */;
 515     for (std::vector<std::string>::const_iterator j = i->second.begin();
 516          j != i->second.end(); ++j) {
 517       len += 1 /* serial length */ + j->size();
 518     }
 519   }
 520
 521   std::string ret;
 522   uint8_t* out = reinterpret_cast<uint8_t*>(
 523       base::WriteInto(&ret, len + 1 /* to include final NUL */));
 524   size_t off = 0;
 525   CHECK(base::IsValueInRangeForNumericType<uint16_t>(header.size()));
 526   out[off++] = static_cast<uint8_t>(header.size());
 527   out[off++] = static_cast<uint8_t>(header.size() >> 8);
 528   memcpy(out + off, header.data(), header.size());
 529   off += header.size();
 530
 531   for (CRLSet::CRLList::const_iterator i = crl_set->crls_.begin();
 532        i != crl_set->crls_.end(); ++i) {
 533     memcpy(out + off, i->first.data(), i->first.size());
 534     off += i->first.size();
 535     const uint32_t num_serials = i->second.size();
 536     memcpy(out + off, &num_serials, sizeof(num_serials));
 537     off += sizeof(num_serials);
 538
 539     for (std::vector<std::string>::const_iterator j = i->second.begin();
 540          j != i->second.end(); ++j) {
 541       CHECK(base::IsValueInRangeForNumericType<uint8_t>(j->size()));
 542       out[off++] = static_cast<uint8_t>(j->size());
 543       memcpy(out + off, j->data(), j->size());
 544       off += j->size();
 545     }
 546   }
 547
 548   CHECK_EQ(off, len);
 549   return ret;
 550 }
 551
 552 }  // namespace net