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", ¬_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", ¬_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 548