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/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"
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
22 static bool DecompressZlib(uint8
* out
, int out_len
, base::StringPiece in
) {
24 memset(&z
, 0, sizeof(z
));
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
;
31 if (inflateInit(&z
) != Z_OK
)
34 int r
= inflate(&z
, Z_FINISH
);
35 if (r
!= Z_STREAM_END
)
37 if (z
.avail_in
|| z
.avail_out
)
48 // uint16le header_len
49 // byte[header_len] header_bytes
51 // byte[32] parent_spki_sha256
52 // uint32le num_serials
54 // uint8 serial_length;
55 // byte[serial_length] serial;
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): if this is a delta update (see below), then this
62 // contains the sequence number of the base CRLSet.
63 // Sequence (int32): the monotonic sequence number of this CRL set.
65 // A delta CRLSet is similar to a CRLSet:
67 // struct CompressedChanges {
68 // uint32le uncompressed_size
69 // uint32le compressed_size
70 // byte[compressed_size] zlib_data
73 // uint16le header_len
74 // byte[header_len] header_bytes
75 // CompressedChanges crl_changes
76 // [crl_changes.uncompressed_size] {
77 // switch (crl_changes[i]) {
81 // // New CRL inserted
82 // // See CRL structure from the non-delta format
87 // CompressedChanges serials_changes
88 // [serials_changes.uncompressed_size] {
89 // switch (serials_changes[i]) {
91 // // the serial is the same
94 // uint8 serial_length
95 // byte[serial_length] serial
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.
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
114 static base::DictionaryValue
* ReadHeader(base::StringPiece
* data
) {
115 if (data
->size() < 2)
118 memcpy(&header_len
, data
->data(), 2); // assumes little-endian.
119 data
->remove_prefix(2);
121 if (data
->size() < header_len
)
124 const base::StringPiece
header_bytes(data
->data(), header_len
);
125 data
->remove_prefix(header_len
);
127 scoped_ptr
<base::Value
> header(base::JSONReader::Read(
128 header_bytes
, base::JSON_ALLOW_TRAILING_COMMAS
));
129 if (header
.get() == NULL
)
132 if (!header
->IsType(base::Value::TYPE_DICTIONARY
))
134 return reinterpret_cast<base::DictionaryValue
*>(header
.release());
137 // kCurrentFileVersion is the version of the CRLSet file format that we
138 // currently implement.
139 static const int kCurrentFileVersion
= 0;
141 static bool ReadCRL(base::StringPiece
* data
, std::string
* out_parent_spki_hash
,
142 std::vector
<std::string
>* out_serials
) {
143 if (data
->size() < crypto::kSHA256Length
)
145 out_parent_spki_hash
->assign(data
->data(), crypto::kSHA256Length
);
146 data
->remove_prefix(crypto::kSHA256Length
);
148 if (data
->size() < sizeof(uint32
))
151 memcpy(&num_serials
, data
->data(), sizeof(uint32
)); // assumes little endian
152 if (num_serials
> 32 * 1024 * 1024) // Sanity check.
155 out_serials
->reserve(num_serials
);
156 data
->remove_prefix(sizeof(uint32
));
158 for (uint32 i
= 0; i
< num_serials
; ++i
) {
159 if (data
->size() < sizeof(uint8
))
162 uint8 serial_length
= data
->data()[0];
163 data
->remove_prefix(sizeof(uint8
));
165 if (data
->size() < serial_length
)
168 out_serials
->push_back(std::string());
169 out_serials
->back().assign(data
->data(), serial_length
);
170 data
->remove_prefix(serial_length
);
177 bool CRLSetStorage::CopyBlockedSPKIsFromHeader(
179 base::DictionaryValue
* header_dict
) {
180 base::ListValue
* blocked_spkis_list
= NULL
;
181 if (!header_dict
->GetList("BlockedSPKIs", &blocked_spkis_list
)) {
182 // BlockedSPKIs is optional, so it's fine if we don't find it.
186 crl_set
->blocked_spkis_
.clear();
187 crl_set
->blocked_spkis_
.reserve(blocked_spkis_list
->GetSize());
189 std::string spki_sha256_base64
;
191 for (size_t i
= 0; i
< blocked_spkis_list
->GetSize(); ++i
) {
192 spki_sha256_base64
.clear();
194 if (!blocked_spkis_list
->GetString(i
, &spki_sha256_base64
))
197 crl_set
->blocked_spkis_
.push_back(std::string());
198 if (!base::Base64Decode(spki_sha256_base64
,
199 &crl_set
->blocked_spkis_
.back())) {
200 crl_set
->blocked_spkis_
.pop_back();
208 // kMaxUncompressedChangesLength is the largest changes array that we'll
209 // accept. This bounds the number of CRLs in the CRLSet as well as the number
210 // of serial numbers in a given CRL.
211 static const unsigned kMaxUncompressedChangesLength
= 1024 * 1024;
213 static bool ReadChanges(base::StringPiece
* data
,
214 std::vector
<uint8
>* out_changes
) {
215 uint32 uncompressed_size
, compressed_size
;
216 if (data
->size() < 2 * sizeof(uint32
))
218 // assumes little endian.
219 memcpy(&uncompressed_size
, data
->data(), sizeof(uint32
));
220 data
->remove_prefix(4);
221 memcpy(&compressed_size
, data
->data(), sizeof(uint32
));
222 data
->remove_prefix(4);
224 if (uncompressed_size
> kMaxUncompressedChangesLength
)
226 if (data
->size() < compressed_size
)
229 out_changes
->clear();
230 if (uncompressed_size
== 0)
233 out_changes
->resize(uncompressed_size
);
234 base::StringPiece
compressed(data
->data(), compressed_size
);
235 data
->remove_prefix(compressed_size
);
236 return DecompressZlib(&(*out_changes
)[0], uncompressed_size
, compressed
);
239 // These are the range coder symbols used in delta updates.
247 static bool ReadDeltaCRL(base::StringPiece
* data
,
248 const std::vector
<std::string
>& old_serials
,
249 std::vector
<std::string
>* out_serials
) {
250 std::vector
<uint8
> changes
;
251 if (!ReadChanges(data
, &changes
))
255 for (std::vector
<uint8
>::const_iterator k
= changes
.begin();
256 k
!= changes
.end(); ++k
) {
257 if (*k
== SYMBOL_SAME
) {
258 if (i
>= old_serials
.size())
260 out_serials
->push_back(old_serials
[i
]);
262 } else if (*k
== SYMBOL_INSERT
) {
264 if (data
->size() < sizeof(uint8
))
266 memcpy(&serial_length
, data
->data(), sizeof(uint8
));
267 data
->remove_prefix(sizeof(uint8
));
269 if (data
->size() < serial_length
)
271 const std::string
serial(data
->data(), serial_length
);
272 data
->remove_prefix(serial_length
);
274 out_serials
->push_back(serial
);
275 } else if (*k
== SYMBOL_DELETE
) {
276 if (i
>= old_serials
.size())
285 if (i
!= old_serials
.size())
291 bool CRLSetStorage::Parse(base::StringPiece data
,
292 scoped_refptr
<CRLSet
>* out_crl_set
) {
293 TRACE_EVENT0("CRLSet", "Parse");
294 // Other parts of Chrome assume that we're little endian, so we don't lose
295 // anything by doing this.
296 #if defined(__BYTE_ORDER)
298 static_assert(__BYTE_ORDER
== __LITTLE_ENDIAN
, "assumes little endian");
299 #elif defined(__BIG_ENDIAN__)
301 #error assumes little endian
304 scoped_ptr
<base::DictionaryValue
> header_dict(ReadHeader(&data
));
305 if (!header_dict
.get())
308 std::string contents
;
309 if (!header_dict
->GetString("ContentType", &contents
))
311 if (contents
!= "CRLSet")
315 if (!header_dict
->GetInteger("Version", &version
) ||
316 version
!= kCurrentFileVersion
) {
321 if (!header_dict
->GetInteger("Sequence", &sequence
))
325 if (!header_dict
->GetDouble("NotAfter", ¬_after
)) {
326 // NotAfter is optional for now.
332 scoped_refptr
<CRLSet
> crl_set(new CRLSet());
333 crl_set
->sequence_
= static_cast<uint32
>(sequence
);
334 crl_set
->not_after_
= static_cast<uint64
>(not_after
);
335 crl_set
->crls_
.reserve(64); // Value observed experimentally.
337 for (size_t crl_index
= 0; !data
.empty(); crl_index
++) {
338 // Speculatively push back a pair and pass it to ReadCRL() to avoid
339 // unnecessary copies.
340 crl_set
->crls_
.push_back(
341 std::make_pair(std::string(), std::vector
<std::string
>()));
342 std::pair
<std::string
, std::vector
<std::string
> >* const back_pair
=
343 &crl_set
->crls_
.back();
345 if (!ReadCRL(&data
, &back_pair
->first
, &back_pair
->second
)) {
346 // Undo the speculative push_back() performed above.
347 crl_set
->crls_
.pop_back();
351 crl_set
->crls_index_by_issuer_
[back_pair
->first
] = crl_index
;
354 if (!CopyBlockedSPKIsFromHeader(crl_set
.get(), header_dict
.get()))
357 *out_crl_set
= crl_set
;
362 bool CRLSetStorage::ApplyDelta(const CRLSet
* in_crl_set
,
363 const base::StringPiece
& delta_bytes
,
364 scoped_refptr
<CRLSet
>* out_crl_set
) {
365 base::StringPiece
data(delta_bytes
);
366 scoped_ptr
<base::DictionaryValue
> header_dict(ReadHeader(&data
));
367 if (!header_dict
.get())
370 std::string contents
;
371 if (!header_dict
->GetString("ContentType", &contents
))
373 if (contents
!= "CRLSetDelta")
377 if (!header_dict
->GetInteger("Version", &version
) ||
378 version
!= kCurrentFileVersion
) {
382 int sequence
, delta_from
;
383 if (!header_dict
->GetInteger("Sequence", &sequence
) ||
384 !header_dict
->GetInteger("DeltaFrom", &delta_from
) ||
386 static_cast<uint32
>(delta_from
) != in_crl_set
->sequence_
) {
391 if (!header_dict
->GetDouble("NotAfter", ¬_after
)) {
392 // NotAfter is optional for now.
398 scoped_refptr
<CRLSet
> crl_set(new CRLSet
);
399 crl_set
->sequence_
= static_cast<uint32
>(sequence
);
400 crl_set
->not_after_
= static_cast<uint64
>(not_after
);
402 if (!CopyBlockedSPKIsFromHeader(crl_set
.get(), header_dict
.get()))
405 std::vector
<uint8
> crl_changes
;
407 if (!ReadChanges(&data
, &crl_changes
))
411 for (std::vector
<uint8
>::const_iterator k
= crl_changes
.begin();
412 k
!= crl_changes
.end(); ++k
) {
413 if (*k
== SYMBOL_SAME
) {
414 if (i
>= in_crl_set
->crls_
.size())
416 crl_set
->crls_
.push_back(in_crl_set
->crls_
[i
]);
417 crl_set
->crls_index_by_issuer_
[in_crl_set
->crls_
[i
].first
] = j
;
420 } else if (*k
== SYMBOL_INSERT
) {
421 std::string parent_spki_hash
;
422 std::vector
<std::string
> serials
;
423 if (!ReadCRL(&data
, &parent_spki_hash
, &serials
))
425 crl_set
->crls_
.push_back(std::make_pair(parent_spki_hash
, serials
));
426 crl_set
->crls_index_by_issuer_
[parent_spki_hash
] = j
;
428 } else if (*k
== SYMBOL_DELETE
) {
429 if (i
>= in_crl_set
->crls_
.size())
432 } else if (*k
== SYMBOL_CHANGED
) {
433 if (i
>= in_crl_set
->crls_
.size())
435 std::vector
<std::string
> serials
;
436 if (!ReadDeltaCRL(&data
, in_crl_set
->crls_
[i
].second
, &serials
))
438 crl_set
->crls_
.push_back(
439 std::make_pair(in_crl_set
->crls_
[i
].first
, serials
));
440 crl_set
->crls_index_by_issuer_
[in_crl_set
->crls_
[i
].first
] = j
;
451 if (i
!= in_crl_set
->crls_
.size())
454 *out_crl_set
= crl_set
;
459 bool CRLSetStorage::GetIsDeltaUpdate(const base::StringPiece
& bytes
,
461 base::StringPiece
data(bytes
);
462 scoped_ptr
<base::DictionaryValue
> header_dict(ReadHeader(&data
));
463 if (!header_dict
.get())
466 std::string contents
;
467 if (!header_dict
->GetString("ContentType", &contents
))
470 if (contents
== "CRLSet") {
472 } else if (contents
== "CRLSetDelta") {
482 std::string
CRLSetStorage::Serialize(const CRLSet
* crl_set
) {
483 std::string header
= base::StringPrintf(
486 "\"ContentType\":\"CRLSet\","
490 "\"BlockedSPKIs\":[",
491 static_cast<unsigned>(crl_set
->sequence_
),
492 static_cast<unsigned>(crl_set
->crls_
.size()));
494 for (std::vector
<std::string
>::const_iterator i
=
495 crl_set
->blocked_spkis_
.begin();
496 i
!= crl_set
->blocked_spkis_
.end(); ++i
) {
497 std::string spki_hash_base64
;
498 base::Base64Encode(*i
, &spki_hash_base64
);
500 if (i
!= crl_set
->blocked_spkis_
.begin())
502 header
+= "\"" + spki_hash_base64
+ "\"";
505 if (crl_set
->not_after_
!= 0)
506 header
+= base::StringPrintf(",\"NotAfter\":%" PRIu64
, crl_set
->not_after_
);
509 size_t len
= 2 /* header len */ + header
.size();
511 for (CRLSet::CRLList::const_iterator i
= crl_set
->crls_
.begin();
512 i
!= crl_set
->crls_
.end(); ++i
) {
513 len
+= i
->first
.size() + 4 /* num serials */;
514 for (std::vector
<std::string
>::const_iterator j
= i
->second
.begin();
515 j
!= i
->second
.end(); ++j
) {
516 len
+= 1 /* serial length */ + j
->size();
521 uint8_t* out
= reinterpret_cast<uint8_t*>(
522 WriteInto(&ret
, len
+ 1 /* to include final NUL */));
524 CHECK(base::IsValueInRangeForNumericType
<uint16
>(header
.size()));
525 out
[off
++] = static_cast<uint8_t>(header
.size());
526 out
[off
++] = static_cast<uint8_t>(header
.size() >> 8);
527 memcpy(out
+ off
, header
.data(), header
.size());
528 off
+= header
.size();
530 for (CRLSet::CRLList::const_iterator i
= crl_set
->crls_
.begin();
531 i
!= crl_set
->crls_
.end(); ++i
) {
532 memcpy(out
+ off
, i
->first
.data(), i
->first
.size());
533 off
+= i
->first
.size();
534 const uint32 num_serials
= i
->second
.size();
535 memcpy(out
+ off
, &num_serials
, sizeof(num_serials
));
536 off
+= sizeof(num_serials
);
538 for (std::vector
<std::string
>::const_iterator j
= i
->second
.begin();
539 j
!= i
->second
.end(); ++j
) {
540 CHECK(base::IsValueInRangeForNumericType
<uint8_t>(j
->size()));
541 out
[off
++] = static_cast<uint8_t>(j
->size());
542 memcpy(out
+ off
, j
->data(), j
->size());