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.
5 #include "net/cert/crl_set_storage.h"
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"
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
21 static bool DecompressZlib(uint8* out, int out_len, base::StringPiece in) {
23 memset(&z, 0, sizeof(z));
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;
30 if (inflateInit(&z) != Z_OK)
33 int r = inflate(&z, Z_FINISH);
34 if (r != Z_STREAM_END)
36 if (z.avail_in || z.avail_out)
47 // uint16le header_len
48 // byte[header_len] header_bytes
50 // byte[32] parent_spki_sha256
51 // uint32le num_serials
53 // uint8 serial_length;
54 // byte[serial_length] serial;
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.
64 // A delta CRLSet is similar to a CRLSet:
66 // struct CompressedChanges {
67 // uint32le uncompressed_size
68 // uint32le compressed_size
69 // byte[compressed_size] zlib_data
72 // uint16le header_len
73 // byte[header_len] header_bytes
74 // CompressedChanges crl_changes
75 // [crl_changes.uncompressed_size] {
76 // switch (crl_changes[i]) {
80 // // New CRL inserted
81 // // See CRL structure from the non-delta format
86 // CompressedChanges serials_changes
87 // [serials_changes.uncompressed_size] {
88 // switch (serials_changes[i]) {
90 // // the serial is the same
93 // uint8 serial_length
94 // byte[serial_length] serial
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.
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
113 static base::DictionaryValue* ReadHeader(base::StringPiece* data) {
114 if (data->size() < 2)
117 memcpy(&header_len, data->data(), 2); // assumes little-endian.
118 data->remove_prefix(2);
120 if (data->size() < header_len)
123 const base::StringPiece header_bytes(data->data(), header_len);
124 data->remove_prefix(header_len);
126 scoped_ptr<base::Value> header(base::JSONReader::Read(
127 header_bytes, base::JSON_ALLOW_TRAILING_COMMAS));
128 if (header.get() == NULL)
131 if (!header->IsType(base::Value::TYPE_DICTIONARY))
133 return reinterpret_cast<base::DictionaryValue*>(header.release());
136 // kCurrentFileVersion is the version of the CRLSet file format that we
137 // currently implement.
138 static const int kCurrentFileVersion = 0;
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)
144 out_parent_spki_hash->assign(data->data(), crypto::kSHA256Length);
145 data->remove_prefix(crypto::kSHA256Length);
147 if (data->size() < sizeof(uint32))
150 memcpy(&num_serials, data->data(), sizeof(uint32)); // assumes little endian
151 if (num_serials > 32 * 1024 * 1024) // Sanity check.
154 out_serials->reserve(num_serials);
155 data->remove_prefix(sizeof(uint32));
157 for (uint32 i = 0; i < num_serials; ++i) {
158 if (data->size() < sizeof(uint8))
161 uint8 serial_length = data->data()[0];
162 data->remove_prefix(sizeof(uint8));
164 if (data->size() < serial_length)
167 out_serials->push_back(std::string());
168 out_serials->back().assign(data->data(), serial_length);
169 data->remove_prefix(serial_length);
176 bool CRLSetStorage::CopyBlockedSPKIsFromHeader(
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.
185 crl_set->blocked_spkis_.clear();
186 crl_set->blocked_spkis_.reserve(blocked_spkis_list->GetSize());
188 std::string spki_sha256_base64;
190 for (size_t i = 0; i < blocked_spkis_list->GetSize(); ++i) {
191 spki_sha256_base64.clear();
193 if (!blocked_spkis_list->GetString(i, &spki_sha256_base64))
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();
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;
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))
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);
223 if (uncompressed_size > kMaxUncompressedChangesLength)
225 if (data->size() < compressed_size)
228 out_changes->clear();
229 if (uncompressed_size == 0)
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);
238 // These are the range coder symbols used in delta updates.
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))
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())
259 out_serials->push_back(old_serials[i]);
261 } else if (*k == SYMBOL_INSERT) {
263 if (data->size() < sizeof(uint8))
265 memcpy(&serial_length, data->data(), sizeof(uint8));
266 data->remove_prefix(sizeof(uint8));
268 if (data->size() < serial_length)
270 const std::string serial(data->data(), serial_length);
271 data->remove_prefix(serial_length);
273 out_serials->push_back(serial);
274 } else if (*k == SYMBOL_DELETE) {
275 if (i >= old_serials.size())
284 if (i != old_serials.size())
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)
297 COMPILE_ASSERT(__BYTE_ORDER == __LITTLE_ENDIAN, assumes_little_endian);
298 #elif defined(__BIG_ENDIAN__)
300 #error assumes little endian
303 scoped_ptr<base::DictionaryValue> header_dict(ReadHeader(&data));
304 if (!header_dict.get())
307 std::string contents;
308 if (!header_dict->GetString("ContentType", &contents))
310 if (contents != "CRLSet")
314 if (!header_dict->GetInteger("Version", &version) ||
315 version != kCurrentFileVersion) {
320 if (!header_dict->GetInteger("Sequence", &sequence))
324 if (!header_dict->GetDouble("NotAfter", ¬_after)) {
325 // NotAfter is optional for now.
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.
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();
344 if (!ReadCRL(&data, &back_pair->first, &back_pair->second)) {
345 // Undo the speculative push_back() performed above.
346 crl_set->crls_.pop_back();
350 crl_set->crls_index_by_issuer_[back_pair->first] = crl_index;
353 if (!CopyBlockedSPKIsFromHeader(crl_set, header_dict.get()))
356 *out_crl_set = crl_set;
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())
369 std::string contents;
370 if (!header_dict->GetString("ContentType", &contents))
372 if (contents != "CRLSetDelta")
376 if (!header_dict->GetInteger("Version", &version) ||
377 version != kCurrentFileVersion) {
381 int sequence, delta_from;
382 if (!header_dict->GetInteger("Sequence", &sequence) ||
383 !header_dict->GetInteger("DeltaFrom", &delta_from) ||
385 static_cast<uint32>(delta_from) != in_crl_set->sequence_) {
390 if (!header_dict->GetDouble("NotAfter", ¬_after)) {
391 // NotAfter is optional for now.
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);
401 if (!CopyBlockedSPKIsFromHeader(crl_set, header_dict.get()))
404 std::vector<uint8> crl_changes;
406 if (!ReadChanges(&data, &crl_changes))
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())
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;
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))
424 crl_set->crls_.push_back(std::make_pair(parent_spki_hash, serials));
425 crl_set->crls_index_by_issuer_[parent_spki_hash] = j;
427 } else if (*k == SYMBOL_DELETE) {
428 if (i >= in_crl_set->crls_.size())
431 } else if (*k == SYMBOL_CHANGED) {
432 if (i >= in_crl_set->crls_.size())
434 std::vector<std::string> serials;
435 if (!ReadDeltaCRL(&data, in_crl_set->crls_[i].second, &serials))
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;
450 if (i != in_crl_set->crls_.size())
453 *out_crl_set = crl_set;
458 bool CRLSetStorage::GetIsDeltaUpdate(const base::StringPiece& bytes,
460 base::StringPiece data(bytes);
461 scoped_ptr<base::DictionaryValue> header_dict(ReadHeader(&data));
462 if (!header_dict.get())
465 std::string contents;
466 if (!header_dict->GetString("ContentType", &contents))
469 if (contents == "CRLSet") {
471 } else if (contents == "CRLSetDelta") {
481 std::string CRLSetStorage::Serialize(const CRLSet* crl_set) {
482 std::string header = base::StringPrintf(
485 "\"ContentType\":\"CRLSet\","
489 "\"BlockedSPKIs\":[",
490 static_cast<unsigned>(crl_set->sequence_),
491 static_cast<unsigned>(crl_set->crls_.size()));
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);
499 if (i != crl_set->blocked_spkis_.begin())
501 header += "\"" + spki_hash_base64 + "\"";
504 if (crl_set->not_after_ != 0)
505 header += base::StringPrintf(",\"NotAfter\":%" PRIu64, crl_set->not_after_);
508 size_t len = 2 /* header len */ + header.size();
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();
520 char* out = WriteInto(&ret, len + 1 /* to include final NUL */);
522 out[off++] = header.size();
523 out[off++] = header.size() >> 8;
524 memcpy(out + off, header.data(), header.size());
525 off += header.size();
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);
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());