1 // Copyright (c) 2012 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.
5 #include "base/base64.h"
6 #include "base/format_macros.h"
7 #include "base/json/json_reader.h"
8 #include "base/logging.h"
9 #include "base/stl_util.h"
10 #include "base/strings/string_util.h"
11 #include "base/strings/stringprintf.h"
12 #include "base/time/time.h"
13 #include "base/values.h"
14 #include "crypto/sha2.h"
15 #include "net/cert/crl_set.h"
16 #include "third_party/zlib/zlib.h"
20 // Decompress zlib decompressed |in| into |out|. |out_len| is the number of
21 // bytes at |out| and must be exactly equal to the size of the decompressed
23 static bool DecompressZlib(uint8* out, int out_len, base::StringPiece in) {
25 memset(&z, 0, sizeof(z));
27 z.next_in = reinterpret_cast<Bytef*>(const_cast<char*>(in.data()));
28 z.avail_in = in.size();
29 z.next_out = reinterpret_cast<Bytef*>(out);
30 z.avail_out = out_len;
32 if (inflateInit(&z) != Z_OK)
35 int r = inflate(&z, Z_FINISH);
36 if (r != Z_STREAM_END)
38 if (z.avail_in || z.avail_out)
57 // uint16le header_len
58 // byte[header_len] header_bytes
60 // byte[32] parent_spki_sha256
61 // uint32le num_serials
63 // uint8 serial_length;
64 // byte[serial_length] serial;
67 // header_bytes consists of a JSON dictionary with the following keys:
68 // Version (int): currently 0
69 // ContentType (string): "CRLSet" or "CRLSetDelta" (magic value)
70 // DeltaFrom (int32): if this is a delta update (see below), then this
71 // contains the sequence number of the base CRLSet.
72 // Sequence (int32): the monotonic sequence number of this CRL set.
74 // A delta CRLSet is similar to a CRLSet:
76 // struct CompressedChanges {
77 // uint32le uncompressed_size
78 // uint32le compressed_size
79 // byte[compressed_size] zlib_data
82 // uint16le header_len
83 // byte[header_len] header_bytes
84 // CompressedChanges crl_changes
85 // [crl_changes.uncompressed_size] {
86 // switch (crl_changes[i]) {
90 // // New CRL inserted
91 // // See CRL structure from the non-delta format
96 // CompressedChanges serials_changes
97 // [serials_changes.uncompressed_size] {
98 // switch (serials_changes[i]) {
100 // // the serial is the same
102 // // serial inserted
103 // uint8 serial_length
104 // byte[serial_length] serial
112 // A delta CRLSet applies to a specific CRL set as given in the
113 // header's "DeltaFrom" value. The delta describes the changes to each CRL
114 // in turn with a zlib compressed array of options: either the CRL is the same,
115 // a new CRL is inserted, the CRL is deleted or the CRL is updated. In the case
116 // of an update, the serials in the CRL are considered in the same fashion
117 // except there is no delta update of a serial number: they are either
118 // inserted, deleted or left the same.
120 // ReadHeader reads the header (including length prefix) from |data| and
121 // updates |data| to remove the header on return. Caller takes ownership of the
123 static base::DictionaryValue* ReadHeader(base::StringPiece* data) {
124 if (data->size() < 2)
127 memcpy(&header_len, data->data(), 2); // assumes little-endian.
128 data->remove_prefix(2);
130 if (data->size() < header_len)
133 const base::StringPiece header_bytes(data->data(), header_len);
134 data->remove_prefix(header_len);
136 scoped_ptr<base::Value> header(base::JSONReader::Read(
137 header_bytes, base::JSON_ALLOW_TRAILING_COMMAS));
138 if (header.get() == NULL)
141 if (!header->IsType(base::Value::TYPE_DICTIONARY))
143 return reinterpret_cast<base::DictionaryValue*>(header.release());
146 // kCurrentFileVersion is the version of the CRLSet file format that we
147 // currently implement.
148 static const int kCurrentFileVersion = 0;
150 static bool ReadCRL(base::StringPiece* data, std::string* out_parent_spki_hash,
151 std::vector<std::string>* out_serials) {
152 if (data->size() < crypto::kSHA256Length)
154 *out_parent_spki_hash = std::string(data->data(), crypto::kSHA256Length);
155 data->remove_prefix(crypto::kSHA256Length);
157 if (data->size() < sizeof(uint32))
160 memcpy(&num_serials, data->data(), sizeof(uint32)); // assumes little endian
161 data->remove_prefix(sizeof(uint32));
163 for (uint32 i = 0; i < num_serials; ++i) {
165 if (data->size() < sizeof(uint8))
167 memcpy(&serial_length, data->data(), sizeof(uint8));
168 data->remove_prefix(sizeof(uint8));
170 if (data->size() < serial_length)
172 std::string serial(data->data(), serial_length);
173 data->remove_prefix(serial_length);
174 out_serials->push_back(serial);
180 bool CRLSet::CopyBlockedSPKIsFromHeader(base::DictionaryValue* header_dict) {
181 base::ListValue* blocked_spkis_list = NULL;
182 if (!header_dict->GetList("BlockedSPKIs", &blocked_spkis_list)) {
183 // BlockedSPKIs is optional, so it's fine if we don't find it.
187 blocked_spkis_.clear();
189 for (size_t i = 0; i < blocked_spkis_list->GetSize(); ++i) {
190 std::string spki_sha256_base64, spki_sha256;
191 if (!blocked_spkis_list->GetString(i, &spki_sha256_base64))
193 if (!base::Base64Decode(spki_sha256_base64, &spki_sha256))
195 blocked_spkis_.push_back(spki_sha256);
202 bool CRLSet::Parse(base::StringPiece data, scoped_refptr<CRLSet>* out_crl_set) {
203 // Other parts of Chrome assume that we're little endian, so we don't lose
204 // anything by doing this.
205 #if defined(__BYTE_ORDER)
207 COMPILE_ASSERT(__BYTE_ORDER == __LITTLE_ENDIAN, assumes_little_endian);
208 #elif defined(__BIG_ENDIAN__)
210 #error assumes little endian
213 scoped_ptr<base::DictionaryValue> header_dict(ReadHeader(&data));
214 if (!header_dict.get())
217 std::string contents;
218 if (!header_dict->GetString("ContentType", &contents))
220 if (contents != "CRLSet")
224 if (!header_dict->GetInteger("Version", &version) ||
225 version != kCurrentFileVersion) {
230 if (!header_dict->GetInteger("Sequence", &sequence))
234 if (!header_dict->GetDouble("NotAfter", ¬_after)) {
235 // NotAfter is optional for now.
241 scoped_refptr<CRLSet> crl_set(new CRLSet);
242 crl_set->sequence_ = static_cast<uint32>(sequence);
243 crl_set->not_after_ = static_cast<uint64>(not_after);
245 for (size_t crl_index = 0; !data.empty(); crl_index++) {
246 std::string parent_spki_sha256;
247 std::vector<std::string> serials;
248 if (!ReadCRL(&data, &parent_spki_sha256, &serials))
251 crl_set->crls_.push_back(std::make_pair(parent_spki_sha256, serials));
252 crl_set->crls_index_by_issuer_[parent_spki_sha256] = crl_index;
255 if (!crl_set->CopyBlockedSPKIsFromHeader(header_dict.get()))
258 *out_crl_set = crl_set;
262 // kMaxUncompressedChangesLength is the largest changes array that we'll
263 // accept. This bounds the number of CRLs in the CRLSet as well as the number
264 // of serial numbers in a given CRL.
265 static const unsigned kMaxUncompressedChangesLength = 1024 * 1024;
267 static bool ReadChanges(base::StringPiece* data,
268 std::vector<uint8>* out_changes) {
269 uint32 uncompressed_size, compressed_size;
270 if (data->size() < 2 * sizeof(uint32))
272 // assumes little endian.
273 memcpy(&uncompressed_size, data->data(), sizeof(uint32));
274 data->remove_prefix(4);
275 memcpy(&compressed_size, data->data(), sizeof(uint32));
276 data->remove_prefix(4);
278 if (uncompressed_size > kMaxUncompressedChangesLength)
280 if (data->size() < compressed_size)
283 out_changes->clear();
284 if (uncompressed_size == 0)
287 out_changes->resize(uncompressed_size);
288 base::StringPiece compressed(data->data(), compressed_size);
289 data->remove_prefix(compressed_size);
290 return DecompressZlib(&(*out_changes)[0], uncompressed_size, compressed);
293 // These are the range coder symbols used in delta updates.
301 bool ReadDeltaCRL(base::StringPiece* data,
302 const std::vector<std::string>& old_serials,
303 std::vector<std::string>* out_serials) {
304 std::vector<uint8> changes;
305 if (!ReadChanges(data, &changes))
309 for (std::vector<uint8>::const_iterator k = changes.begin();
310 k != changes.end(); ++k) {
311 if (*k == SYMBOL_SAME) {
312 if (i >= old_serials.size())
314 out_serials->push_back(old_serials[i]);
316 } else if (*k == SYMBOL_INSERT) {
318 if (data->size() < sizeof(uint8))
320 memcpy(&serial_length, data->data(), sizeof(uint8));
321 data->remove_prefix(sizeof(uint8));
323 if (data->size() < serial_length)
325 const std::string serial(data->data(), serial_length);
326 data->remove_prefix(serial_length);
328 out_serials->push_back(serial);
329 } else if (*k == SYMBOL_DELETE) {
330 if (i >= old_serials.size())
339 if (i != old_serials.size())
344 bool CRLSet::ApplyDelta(const base::StringPiece& in_data,
345 scoped_refptr<CRLSet>* out_crl_set) {
346 base::StringPiece data(in_data);
347 scoped_ptr<base::DictionaryValue> header_dict(ReadHeader(&data));
348 if (!header_dict.get())
351 std::string contents;
352 if (!header_dict->GetString("ContentType", &contents))
354 if (contents != "CRLSetDelta")
358 if (!header_dict->GetInteger("Version", &version) ||
359 version != kCurrentFileVersion) {
363 int sequence, delta_from;
364 if (!header_dict->GetInteger("Sequence", &sequence) ||
365 !header_dict->GetInteger("DeltaFrom", &delta_from) ||
367 static_cast<uint32>(delta_from) != sequence_) {
372 if (!header_dict->GetDouble("NotAfter", ¬_after)) {
373 // NotAfter is optional for now.
379 scoped_refptr<CRLSet> crl_set(new CRLSet);
380 crl_set->sequence_ = static_cast<uint32>(sequence);
381 crl_set->not_after_ = static_cast<uint64>(not_after);
383 if (!crl_set->CopyBlockedSPKIsFromHeader(header_dict.get()))
386 std::vector<uint8> crl_changes;
388 if (!ReadChanges(&data, &crl_changes))
392 for (std::vector<uint8>::const_iterator k = crl_changes.begin();
393 k != crl_changes.end(); ++k) {
394 if (*k == SYMBOL_SAME) {
395 if (i >= crls_.size())
397 crl_set->crls_.push_back(crls_[i]);
398 crl_set->crls_index_by_issuer_[crls_[i].first] = j;
401 } else if (*k == SYMBOL_INSERT) {
402 std::string parent_spki_hash;
403 std::vector<std::string> serials;
404 if (!ReadCRL(&data, &parent_spki_hash, &serials))
406 crl_set->crls_.push_back(std::make_pair(parent_spki_hash, serials));
407 crl_set->crls_index_by_issuer_[parent_spki_hash] = j;
409 } else if (*k == SYMBOL_DELETE) {
410 if (i >= crls_.size())
413 } else if (*k == SYMBOL_CHANGED) {
414 if (i >= crls_.size())
416 std::vector<std::string> serials;
417 if (!ReadDeltaCRL(&data, crls_[i].second, &serials))
419 crl_set->crls_.push_back(std::make_pair(crls_[i].first, serials));
420 crl_set->crls_index_by_issuer_[crls_[i].first] = j;
431 if (i != crls_.size())
434 *out_crl_set = crl_set;
439 bool CRLSet::GetIsDeltaUpdate(const base::StringPiece& in_data,
441 base::StringPiece data(in_data);
442 scoped_ptr<base::DictionaryValue> header_dict(ReadHeader(&data));
443 if (!header_dict.get())
446 std::string contents;
447 if (!header_dict->GetString("ContentType", &contents))
450 if (contents == "CRLSet") {
452 } else if (contents == "CRLSetDelta") {
461 std::string CRLSet::Serialize() const {
462 std::string header = base::StringPrintf(
465 "\"ContentType\":\"CRLSet\","
469 "\"BlockedSPKIs\":[",
470 static_cast<unsigned>(sequence_),
471 static_cast<unsigned>(crls_.size()));
473 for (std::vector<std::string>::const_iterator i = blocked_spkis_.begin();
474 i != blocked_spkis_.end(); ++i) {
475 std::string spki_hash_base64;
476 base::Base64Encode(*i, &spki_hash_base64);
478 if (i != blocked_spkis_.begin())
480 header += "\"" + spki_hash_base64 + "\"";
484 header += base::StringPrintf(",\"NotAfter\":%" PRIu64, not_after_);
487 size_t len = 2 /* header len */ + header.size();
489 for (CRLList::const_iterator i = crls_.begin(); i != crls_.end(); ++i) {
490 len += i->first.size() + 4 /* num serials */;
491 for (std::vector<std::string>::const_iterator j = i->second.begin();
492 j != i->second.end(); ++j) {
493 len += 1 /* serial length */ + j->size();
498 char* out = WriteInto(&ret, len + 1 /* to include final NUL */);
500 out[off++] = header.size();
501 out[off++] = header.size() >> 8;
502 memcpy(out + off, header.data(), header.size());
503 off += header.size();
505 for (CRLList::const_iterator i = crls_.begin(); i != crls_.end(); ++i) {
506 memcpy(out + off, i->first.data(), i->first.size());
507 off += i->first.size();
508 const uint32 num_serials = i->second.size();
509 memcpy(out + off, &num_serials, sizeof(num_serials));
510 off += sizeof(num_serials);
512 for (std::vector<std::string>::const_iterator j = i->second.begin();
513 j != i->second.end(); ++j) {
514 out[off++] = j->size();
515 memcpy(out + off, j->data(), j->size());
524 CRLSet::Result CRLSet::CheckSPKI(const base::StringPiece& spki_hash) const {
525 for (std::vector<std::string>::const_iterator i = blocked_spkis_.begin();
526 i != blocked_spkis_.end(); ++i) {
527 if (spki_hash.size() == i->size() &&
528 memcmp(spki_hash.data(), i->data(), i->size()) == 0) {
536 CRLSet::Result CRLSet::CheckSerial(
537 const base::StringPiece& serial_number,
538 const base::StringPiece& issuer_spki_hash) const {
539 base::StringPiece serial(serial_number);
541 if (!serial.empty() && (serial[0] & 0x80) != 0) {
542 // This serial number is negative but the process which generates CRL sets
543 // will reject any certificates with negative serial numbers as invalid.
547 // Remove any leading zero bytes.
548 while (serial.size() > 1 && serial[0] == 0x00)
549 serial.remove_prefix(1);
551 std::map<std::string, size_t>::const_iterator i =
552 crls_index_by_issuer_.find(issuer_spki_hash.as_string());
553 if (i == crls_index_by_issuer_.end())
555 const std::vector<std::string>& serials = crls_[i->second].second;
557 for (std::vector<std::string>::const_iterator i = serials.begin();
558 i != serials.end(); ++i) {
559 if (base::StringPiece(*i) == serial)
566 bool CRLSet::IsExpired() const {
570 uint64 now = base::Time::Now().ToTimeT();
571 return now > not_after_;
574 uint32 CRLSet::sequence() const {
578 const CRLSet::CRLList& CRLSet::crls() const {
583 CRLSet* CRLSet::EmptyCRLSetForTesting() {
584 return ForTesting(false, NULL, "");
587 CRLSet* CRLSet::ExpiredCRLSetForTesting() {
588 return ForTesting(true, NULL, "");
592 CRLSet* CRLSet::ForTesting(bool is_expired,
593 const SHA256HashValue* issuer_spki,
594 const std::string& serial_number) {
595 CRLSet* crl_set = new CRLSet;
597 crl_set->not_after_ = 1;
598 if (issuer_spki != NULL) {
599 const std::string spki(reinterpret_cast<const char*>(issuer_spki->data),
600 sizeof(issuer_spki->data));
601 crl_set->crls_.push_back(make_pair(spki, std::vector<std::string>()));
602 crl_set->crls_index_by_issuer_[spki] = 0;
605 if (!serial_number.empty())
606 crl_set->crls_[0].second.push_back(serial_number);