Home | History | Annotate | Download | only in cert
      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 
     18 namespace 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.
     23 static 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 
     47 CRLSet::CRLSet()
     48     : sequence_(0),
     49       not_after_(0) {
     50 }
     51 
     52 CRLSet::~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.
    123 static 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.
    148 static const int kCurrentFileVersion = 0;
    149 
    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)
    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 
    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.
    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
    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)
    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.
    265 static const unsigned kMaxUncompressedChangesLength = 1024 * 1024;
    266 
    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))
    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.
    294 enum {
    295   SYMBOL_SAME = 0,
    296   SYMBOL_INSERT = 1,
    297   SYMBOL_DELETE = 2,
    298   SYMBOL_CHANGED = 3,
    299 };
    300 
    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))
    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 
    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())
    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
    439 bool 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 
    461 std::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 
    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) {
    529       return REVOKED;
    530     }
    531   }
    532 
    533   return GOOD;
    534 }
    535 
    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);
    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 
    566 bool 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 
    574 uint32 CRLSet::sequence() const {
    575   return sequence_;
    576 }
    577 
    578 const CRLSet::CRLList& CRLSet::crls() const {
    579   return crls_;
    580 }
    581 
    582 // static
    583 CRLSet* CRLSet::EmptyCRLSetForTesting() {
    584   return ForTesting(false, NULL, "");
    585 }
    586 
    587 CRLSet* CRLSet::ExpiredCRLSetForTesting() {
    588   return ForTesting(true, NULL, "");
    589 }
    590 
    591 // static
    592 CRLSet* 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