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 16namespace 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. 21static 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. 113static 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. 138static const int kCurrentFileVersion = 0; 139 140static 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 176bool 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. 210static const unsigned kMaxUncompressedChangesLength = 1024 * 1024; 211 212static 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. 239enum { 240 SYMBOL_SAME = 0, 241 SYMBOL_INSERT = 1, 242 SYMBOL_DELETE = 2, 243 SYMBOL_CHANGED = 3, 244}; 245 246static 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 290bool 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 361bool 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 458bool 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 481std::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