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.
4
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"
17
18namespace net {
19
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
22// data.
23static bool DecompressZlib(uint8* out, int out_len, base::StringPiece in) {
24  z_stream z;
25  memset(&z, 0, sizeof(z));
26
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;
31
32  if (inflateInit(&z) != Z_OK)
33    return false;
34  bool ret = false;
35  int r = inflate(&z, Z_FINISH);
36  if (r != Z_STREAM_END)
37    goto err;
38  if (z.avail_in || z.avail_out)
39    goto err;
40  ret = true;
41
42 err:
43  inflateEnd(&z);
44  return ret;
45}
46
47CRLSet::CRLSet()
48    : sequence_(0),
49      not_after_(0) {
50}
51
52CRLSet::~CRLSet() {
53}
54
55// CRLSet format:
56//
57// uint16le header_len
58// byte[header_len] header_bytes
59// repeated {
60//   byte[32] parent_spki_sha256
61//   uint32le num_serials
62//   [num_serials] {
63//     uint8 serial_length;
64//     byte[serial_length] serial;
65//   }
66//
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.
73//
74// A delta CRLSet is similar to a CRLSet:
75//
76// struct CompressedChanges {
77//    uint32le uncompressed_size
78//    uint32le compressed_size
79//    byte[compressed_size] zlib_data
80// }
81//
82// uint16le header_len
83// byte[header_len] header_bytes
84// CompressedChanges crl_changes
85// [crl_changes.uncompressed_size] {
86//   switch (crl_changes[i]) {
87//   case 0:
88//     // CRL is the same
89//   case 1:
90//     // New CRL inserted
91//     // See CRL structure from the non-delta format
92//   case 2:
93//     // CRL deleted
94//   case 3:
95//     // CRL changed
96//     CompressedChanges serials_changes
97//     [serials_changes.uncompressed_size] {
98//       switch (serials_changes[i]) {
99//       case 0:
100//         // the serial is the same
101//       case 1:
102//         // serial inserted
103//         uint8 serial_length
104//         byte[serial_length] serial
105//       case 2:
106//         // serial deleted
107//       }
108//     }
109//   }
110// }
111//
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.
119
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
122// returned pointer.
123static base::DictionaryValue* ReadHeader(base::StringPiece* data) {
124  if (data->size() < 2)
125    return NULL;
126  uint16 header_len;
127  memcpy(&header_len, data->data(), 2);  // assumes little-endian.
128  data->remove_prefix(2);
129
130  if (data->size() < header_len)
131    return NULL;
132
133  const base::StringPiece header_bytes(data->data(), header_len);
134  data->remove_prefix(header_len);
135
136  scoped_ptr<base::Value> header(base::JSONReader::Read(
137      header_bytes, base::JSON_ALLOW_TRAILING_COMMAS));
138  if (header.get() == NULL)
139    return NULL;
140
141  if (!header->IsType(base::Value::TYPE_DICTIONARY))
142    return NULL;
143  return reinterpret_cast<base::DictionaryValue*>(header.release());
144}
145
146// kCurrentFileVersion is the version of the CRLSet file format that we
147// currently implement.
148static const int kCurrentFileVersion = 0;
149
150static bool ReadCRL(base::StringPiece* data, std::string* out_parent_spki_hash,
151                    std::vector<std::string>* out_serials) {
152  if (data->size() < crypto::kSHA256Length)
153    return false;
154  *out_parent_spki_hash = std::string(data->data(), crypto::kSHA256Length);
155  data->remove_prefix(crypto::kSHA256Length);
156
157  if (data->size() < sizeof(uint32))
158    return false;
159  uint32 num_serials;
160  memcpy(&num_serials, data->data(), sizeof(uint32));  // assumes little endian
161  data->remove_prefix(sizeof(uint32));
162
163  for (uint32 i = 0; i < num_serials; ++i) {
164    uint8 serial_length;
165    if (data->size() < sizeof(uint8))
166      return false;
167    memcpy(&serial_length, data->data(), sizeof(uint8));
168    data->remove_prefix(sizeof(uint8));
169
170    if (data->size() < serial_length)
171      return false;
172    std::string serial(data->data(), serial_length);
173    data->remove_prefix(serial_length);
174    out_serials->push_back(serial);
175  }
176
177  return true;
178}
179
180bool 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.
184    return true;
185  }
186
187  blocked_spkis_.clear();
188
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))
192      return false;
193    if (!base::Base64Decode(spki_sha256_base64, &spki_sha256))
194      return false;
195    blocked_spkis_.push_back(spki_sha256);
196  }
197
198  return true;
199}
200
201// static
202bool 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)
206  // Linux check
207  COMPILE_ASSERT(__BYTE_ORDER == __LITTLE_ENDIAN, assumes_little_endian);
208#elif defined(__BIG_ENDIAN__)
209  // Mac check
210  #error assumes little endian
211#endif
212
213  scoped_ptr<base::DictionaryValue> header_dict(ReadHeader(&data));
214  if (!header_dict.get())
215    return false;
216
217  std::string contents;
218  if (!header_dict->GetString("ContentType", &contents))
219    return false;
220  if (contents != "CRLSet")
221    return false;
222
223  int version;
224  if (!header_dict->GetInteger("Version", &version) ||
225      version != kCurrentFileVersion) {
226    return false;
227  }
228
229  int sequence;
230  if (!header_dict->GetInteger("Sequence", &sequence))
231    return false;
232
233  double not_after;
234  if (!header_dict->GetDouble("NotAfter", &not_after)) {
235    // NotAfter is optional for now.
236    not_after = 0;
237  }
238  if (not_after < 0)
239    return false;
240
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);
244
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))
249      return false;
250
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;
253  }
254
255  if (!crl_set->CopyBlockedSPKIsFromHeader(header_dict.get()))
256    return false;
257
258  *out_crl_set = crl_set;
259  return true;
260}
261
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.
265static const unsigned kMaxUncompressedChangesLength = 1024 * 1024;
266
267static bool ReadChanges(base::StringPiece* data,
268                        std::vector<uint8>* out_changes) {
269  uint32 uncompressed_size, compressed_size;
270  if (data->size() < 2 * sizeof(uint32))
271    return false;
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);
277
278  if (uncompressed_size > kMaxUncompressedChangesLength)
279    return false;
280  if (data->size() < compressed_size)
281    return false;
282
283  out_changes->clear();
284  if (uncompressed_size == 0)
285    return true;
286
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);
291}
292
293// These are the range coder symbols used in delta updates.
294enum {
295  SYMBOL_SAME = 0,
296  SYMBOL_INSERT = 1,
297  SYMBOL_DELETE = 2,
298  SYMBOL_CHANGED = 3,
299};
300
301bool 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))
306    return false;
307
308  size_t i = 0;
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())
313        return false;
314      out_serials->push_back(old_serials[i]);
315      i++;
316    } else if (*k == SYMBOL_INSERT) {
317      uint8 serial_length;
318      if (data->size() < sizeof(uint8))
319        return false;
320      memcpy(&serial_length, data->data(), sizeof(uint8));
321      data->remove_prefix(sizeof(uint8));
322
323      if (data->size() < serial_length)
324        return false;
325      const std::string serial(data->data(), serial_length);
326      data->remove_prefix(serial_length);
327
328      out_serials->push_back(serial);
329    } else if (*k == SYMBOL_DELETE) {
330      if (i >= old_serials.size())
331        return false;
332      i++;
333    } else {
334      NOTREACHED();
335      return false;
336    }
337  }
338
339  if (i != old_serials.size())
340    return false;
341  return true;
342}
343
344bool 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())
349    return false;
350
351  std::string contents;
352  if (!header_dict->GetString("ContentType", &contents))
353    return false;
354  if (contents != "CRLSetDelta")
355    return false;
356
357  int version;
358  if (!header_dict->GetInteger("Version", &version) ||
359      version != kCurrentFileVersion) {
360    return false;
361  }
362
363  int sequence, delta_from;
364  if (!header_dict->GetInteger("Sequence", &sequence) ||
365      !header_dict->GetInteger("DeltaFrom", &delta_from) ||
366      delta_from < 0 ||
367      static_cast<uint32>(delta_from) != sequence_) {
368    return false;
369  }
370
371  double not_after;
372  if (!header_dict->GetDouble("NotAfter", &not_after)) {
373    // NotAfter is optional for now.
374    not_after = 0;
375  }
376  if (not_after < 0)
377    return false;
378
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);
382
383  if (!crl_set->CopyBlockedSPKIsFromHeader(header_dict.get()))
384    return false;
385
386  std::vector<uint8> crl_changes;
387
388  if (!ReadChanges(&data, &crl_changes))
389    return false;
390
391  size_t i = 0, j = 0;
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())
396        return false;
397      crl_set->crls_.push_back(crls_[i]);
398      crl_set->crls_index_by_issuer_[crls_[i].first] = j;
399      i++;
400      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))
405        return false;
406      crl_set->crls_.push_back(std::make_pair(parent_spki_hash, serials));
407      crl_set->crls_index_by_issuer_[parent_spki_hash] = j;
408      j++;
409    } else if (*k == SYMBOL_DELETE) {
410      if (i >= crls_.size())
411        return false;
412      i++;
413    } else if (*k == SYMBOL_CHANGED) {
414      if (i >= crls_.size())
415        return false;
416      std::vector<std::string> serials;
417      if (!ReadDeltaCRL(&data, crls_[i].second, &serials))
418        return false;
419      crl_set->crls_.push_back(std::make_pair(crls_[i].first, serials));
420      crl_set->crls_index_by_issuer_[crls_[i].first] = j;
421      i++;
422      j++;
423    } else {
424      NOTREACHED();
425      return false;
426    }
427  }
428
429  if (!data.empty())
430    return false;
431  if (i != crls_.size())
432    return false;
433
434  *out_crl_set = crl_set;
435  return true;
436}
437
438// static
439bool CRLSet::GetIsDeltaUpdate(const base::StringPiece& in_data,
440                              bool* is_delta) {
441  base::StringPiece data(in_data);
442  scoped_ptr<base::DictionaryValue> header_dict(ReadHeader(&data));
443  if (!header_dict.get())
444    return false;
445
446  std::string contents;
447  if (!header_dict->GetString("ContentType", &contents))
448    return false;
449
450  if (contents == "CRLSet") {
451    *is_delta = false;
452  } else if (contents == "CRLSetDelta") {
453    *is_delta = true;
454  } else {
455    return false;
456  }
457
458  return true;
459}
460
461std::string CRLSet::Serialize() const {
462  std::string header = base::StringPrintf(
463      "{"
464      "\"Version\":0,"
465      "\"ContentType\":\"CRLSet\","
466      "\"Sequence\":%u,"
467      "\"DeltaFrom\":0,"
468      "\"NumParents\":%u,"
469      "\"BlockedSPKIs\":[",
470      static_cast<unsigned>(sequence_),
471      static_cast<unsigned>(crls_.size()));
472
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);
477
478    if (i != blocked_spkis_.begin())
479      header += ",";
480    header += "\"" + spki_hash_base64 + "\"";
481  }
482  header += "]";
483  if (not_after_ != 0)
484    header += base::StringPrintf(",\"NotAfter\":%" PRIu64, not_after_);
485  header += "}";
486
487  size_t len = 2 /* header len */ + header.size();
488
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();
494    }
495  }
496
497  std::string ret;
498  char* out = WriteInto(&ret, len + 1 /* to include final NUL */);
499  size_t off = 0;
500  out[off++] = header.size();
501  out[off++] = header.size() >> 8;
502  memcpy(out + off, header.data(), header.size());
503  off += header.size();
504
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);
511
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());
516      off += j->size();
517    }
518  }
519
520  CHECK_EQ(off, len);
521  return ret;
522}
523
524CRLSet::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) {
529      return REVOKED;
530    }
531  }
532
533  return GOOD;
534}
535
536CRLSet::Result CRLSet::CheckSerial(
537    const base::StringPiece& serial_number,
538    const base::StringPiece& issuer_spki_hash) const {
539  base::StringPiece serial(serial_number);
540
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.
544    return UNKNOWN;
545  }
546
547  // Remove any leading zero bytes.
548  while (serial.size() > 1 && serial[0] == 0x00)
549    serial.remove_prefix(1);
550
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())
554    return UNKNOWN;
555  const std::vector<std::string>& serials = crls_[i->second].second;
556
557  for (std::vector<std::string>::const_iterator i = serials.begin();
558       i != serials.end(); ++i) {
559    if (base::StringPiece(*i) == serial)
560      return REVOKED;
561  }
562
563  return GOOD;
564}
565
566bool CRLSet::IsExpired() const {
567  if (not_after_ == 0)
568    return false;
569
570  uint64 now = base::Time::Now().ToTimeT();
571  return now > not_after_;
572}
573
574uint32 CRLSet::sequence() const {
575  return sequence_;
576}
577
578const CRLSet::CRLList& CRLSet::crls() const {
579  return crls_;
580}
581
582// static
583CRLSet* CRLSet::EmptyCRLSetForTesting() {
584  return ForTesting(false, NULL, "");
585}
586
587CRLSet* CRLSet::ExpiredCRLSetForTesting() {
588  return ForTesting(true, NULL, "");
589}
590
591// static
592CRLSet* CRLSet::ForTesting(bool is_expired,
593                           const SHA256HashValue* issuer_spki,
594                           const std::string& serial_number) {
595  CRLSet* crl_set = new CRLSet;
596  if (is_expired)
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;
603  }
604
605  if (!serial_number.empty())
606    crl_set->crls_[0].second.push_back(serial_number);
607
608  return crl_set;
609}
610
611}  // namespace net
612