src/common/net/http/transport_security_state.cpp

   1 /*
   2  * Copyright 2014 The Chromium Authors. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions are
   6  * met:
   7
   8  *    * Redistributions of source code must retain the above copyright
   9  * notice, this list of conditions and the following disclaimer.
  10  *    * Redistributions in binary form must reproduce the above
  11  * copyright notice, this list of conditions and the following disclaimer
  12  * in the documentation and/or other materials provided with the
  13  * distribution.
  14  *    * Neither the name of Google Inc. nor the names of its
  15  * contributors may be used to endorse or promote products derived from
  16  * this software without specific prior written permission.
  17
  18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  19  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  20  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  21  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  22  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  23  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  24  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  25  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  26  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29  */
  30
  31 // This file is subset of chromium-efl/net/http/transport_security_state.cc
  32
  33 #include "net/http/transport_security_state.h"
  34 #include "net/http/transport_security_state_static.h"
  35 #include "base/logging.h"
  36
  37 namespace {
  38
  39 // BitReader is a class that allows a bytestring to be read bit-by-bit.
  40 class BitReader {
  41  public:
  42   BitReader(const uint8* bytes, size_t num_bits)
  43       : bytes_(bytes),
  44         num_bits_(num_bits),
  45         num_bytes_((num_bits + 7) / 8),
  46         current_byte_index_(0),
  47         current_byte_(0),
  48         num_bits_used_(8) {}
  49
  50   // Next sets |*out| to the next bit from the input. It returns false if no
  51   // more bits are available or true otherwise.
  52   bool Next(bool* out) {
  53     if (num_bits_used_ == 8) {
  54       if (current_byte_index_ >= num_bytes_) {
  55         return false;
  56       }
  57       current_byte_ = bytes_[current_byte_index_++];
  58       num_bits_used_ = 0;
  59     }
  60
  61     *out = 1 & (current_byte_ >> (7 - num_bits_used_));
  62     num_bits_used_++;
  63     return true;
  64   }
  65
  66   // Read sets the |num_bits| least-significant bits of |*out| to the value of
  67   // the next |num_bits| bits from the input. It returns false if there are
  68   // insufficient bits in the input or true otherwise.
  69   bool Read(unsigned num_bits, uint32* out) {
  70     DCHECK_LE(num_bits, 32u);
  71
  72     uint32 ret = 0;
  73     for (unsigned i = 0; i < num_bits; ++i) {
  74       bool bit;
  75       if (!Next(&bit)) {
  76         return false;
  77       }
  78       ret |= static_cast<uint32>(bit) << (num_bits - 1 - i);
  79     }
  80
  81     *out = ret;
  82     return true;
  83   }
  84
  85   // Unary sets |*out| to the result of decoding a unary value from the input.
  86   // It returns false if there were insufficient bits in the input and true
  87   // otherwise.
  88   bool Unary(size_t* out) {
  89     size_t ret = 0;
  90
  91     for (;;) {
  92       bool bit;
  93       if (!Next(&bit)) {
  94         return false;
  95       }
  96       if (!bit) {
  97         break;
  98       }
  99       ret++;
 100     }
 101
 102     *out = ret;
 103     return true;
 104   }
 105
 106   // Seek sets the current offest in the input to bit number |offset|. It
 107   // returns true if |offset| is within the range of the input and false
 108   // otherwise.
 109   bool Seek(size_t offset) {
 110     if (offset >= num_bits_) {
 111       return false;
 112     }
 113     current_byte_index_ = offset / 8;
 114     current_byte_ = bytes_[current_byte_index_++];
 115     num_bits_used_ = offset % 8;
 116     return true;
 117   }
 118
 119  private:
 120   const uint8* const bytes_;
 121   const size_t num_bits_;
 122   const size_t num_bytes_;
 123   // current_byte_index_ contains the current byte offset in |bytes_|.
 124   size_t current_byte_index_;
 125   // current_byte_ contains the current byte of the input.
 126   uint8 current_byte_;
 127   // num_bits_used_ contains the number of bits of |current_byte_| that have
 128   // been read.
 129   unsigned num_bits_used_;
 130 };
 131
 132 // HuffmanDecoder is a very simple Huffman reader. The input Huffman tree is
 133 // simply encoded as a series of two-byte structures. The first byte determines
 134 // the "0" pointer for that node and the second the "1" pointer. Each byte
 135 // either has the MSB set, in which case the bottom 7 bits are the value for
 136 // that position, or else the bottom seven bits contain the index of a node.
 137 //
 138 // The tree is decoded by walking rather than a table-driven approach.
 139 class HuffmanDecoder {
 140  public:
 141   HuffmanDecoder(const uint8* tree, size_t tree_bytes)
 142       : tree_(tree),
 143         tree_bytes_(tree_bytes) {}
 144
 145   bool Decode(BitReader* reader, char* out) {
 146     const uint8* current = &tree_[tree_bytes_-2];
 147
 148     for (;;) {
 149       bool bit;
 150       if (!reader->Next(&bit)) {
 151         return false;
 152       }
 153
 154       uint8 b = current[bit];
 155       if (b & 0x80) {
 156         *out = static_cast<char>(b & 0x7f);
 157         return true;
 158       }
 159
 160       unsigned offset = static_cast<unsigned>(b) * 2;
 161       DCHECK_LT(offset, tree_bytes_);
 162       if (offset >= tree_bytes_) {
 163         return false;
 164       }
 165
 166       current = &tree_[offset];
 167     }
 168   }
 169
 170  private:
 171   const uint8* const tree_;
 172   const size_t tree_bytes_;
 173 };
 174
 175 } // namespace anonymous
 176
 177 namespace net {
 178
 179 // DecodeHSTSPreloadRaw resolves |hostname| in the preloaded data. It returns
 180 // false on internal error and true otherwise. After a successful return,
 181 // |*out_found| is true iff a relevant entry has been found. If so, |*out|
 182 // contains the details.
 183 //
 184 // Don't call this function, call DecodeHSTSPreload, below.
 185 //
 186 // Although this code should be robust, it never processes attacker-controlled
 187 // data -- it only operates on the preloaded data built into the binary.
 188 //
 189 // The preloaded data is represented as a trie and matches the hostname
 190 // backwards. Each node in the trie starts with a number of characters, which
 191 // must match exactly. After that is a dispatch table which maps the next
 192 // character in the hostname to another node in the trie.
 193 //
 194 // In the dispatch table, the zero character represents the "end of string"
 195 // (which is the *beginning* of a hostname since we process it backwards). The
 196 // value in that case is special -- rather than an offset to another trie node,
 197 // it contains the HSTS information: whether subdomains are included, pinsets
 198 // etc. If an "end of string" matches a period in the hostname then the
 199 // information is remembered because, if no more specific node is found, then
 200 // that information applies to the hostname.
 201 //
 202 // Dispatch tables are always given in order, but the "end of string" (zero)
 203 // value always comes before an entry for '.'.
 204 bool DecodeHSTSPreloadRaw(const std::string& hostname,
 205                           bool* out_found,
 206                           PreloadResult* out) {
 207   HuffmanDecoder huffman(kHSTSHuffmanTree, sizeof(kHSTSHuffmanTree));
 208   BitReader reader(kPreloadedHSTSData, kPreloadedHSTSBits);
 209   size_t bit_offset = kHSTSRootPosition;
 210   static const char kEndOfString = 0;
 211   static const char kEndOfTable = 127;
 212
 213   *out_found = false;
 214
 215   if (hostname.empty()) {
 216     return true;
 217   }
 218   // hostname_offset contains one more than the index of the current character
 219   // in the hostname that is being considered. It's one greater so that we can
 220   // represent the position just before the beginning (with zero).
 221   size_t hostname_offset = hostname.size();
 222
 223   for (;;) {
 224     // Seek to the desired location.
 225     if (!reader.Seek(bit_offset)) {
 226       return false;
 227     }
 228
 229     // Decode the unary length of the common prefix.
 230     size_t prefix_length;
 231     if (!reader.Unary(&prefix_length)) {
 232       return false;
 233     }
 234
 235     // Match each character in the prefix.
 236     for (size_t i = 0; i < prefix_length; ++i) {
 237       if (hostname_offset == 0) {
 238         // We can't match the terminator with a prefix string.
 239         return true;
 240       }
 241
 242       char c;
 243       if (!huffman.Decode(&reader, &c)) {
 244         return false;
 245       }
 246       if (hostname[hostname_offset - 1] != c) {
 247         return true;
 248       }
 249       hostname_offset--;
 250     }
 251
 252     bool is_first_offset = true;
 253     size_t current_offset = 0;
 254
 255     // Next is the dispatch table.
 256     for (;;) {
 257       char c;
 258       if (!huffman.Decode(&reader, &c)) {
 259         return false;
 260       }
 261       if (c == kEndOfTable) {
 262         // No exact match.
 263         return true;
 264       }
 265
 266       if (c == kEndOfString) {
 267         PreloadResult tmp;
 268         if (!reader.Next(&tmp.sts_include_subdomains) ||
 269             !reader.Next(&tmp.force_https) ||
 270             !reader.Next(&tmp.has_pins)) {
 271           return false;
 272         }
 273
 274         tmp.pkp_include_subdomains = tmp.sts_include_subdomains;
 275
 276         if (tmp.has_pins) {
 277           if (!reader.Read(4, &tmp.pinset_id) ||
 278               !reader.Read(9, &tmp.domain_id) ||
 279               (!tmp.sts_include_subdomains &&
 280                !reader.Next(&tmp.pkp_include_subdomains))) {
 281             return false;
 282           }
 283         }
 284
 285         tmp.hostname_offset = hostname_offset;
 286
 287         if (hostname_offset == 0 || hostname[hostname_offset - 1] == '.') {
 288           *out_found =
 289               tmp.sts_include_subdomains || tmp.pkp_include_subdomains;
 290           *out = tmp;
 291
 292           if (hostname_offset > 0) {
 293             out->force_https &= tmp.sts_include_subdomains;
 294           } else {
 295             *out_found = true;
 296             return true;
 297           }
 298         }
 299
 300         continue;
 301       }
 302
 303       // The entries in a dispatch table are in order thus we can tell if there
 304       // will be no match if the current character past the one that we want.
 305       if (hostname_offset == 0 || hostname[hostname_offset-1] < c) {
 306         return true;
 307       }
 308
 309       if (is_first_offset) {
 310         // The first offset is backwards from the current position.
 311         uint32 jump_delta_bits;
 312         uint32 jump_delta;
 313         if (!reader.Read(5, &jump_delta_bits) ||
 314             !reader.Read(jump_delta_bits, &jump_delta)) {
 315           return false;
 316         }
 317
 318         if (bit_offset < jump_delta) {
 319           return false;
 320         }
 321
 322         current_offset = bit_offset - jump_delta;
 323         is_first_offset = false;
 324       } else {
 325         // Subsequent offsets are forward from the target of the first offset.
 326         uint32 is_long_jump;
 327         if (!reader.Read(1, &is_long_jump)) {
 328           return false;
 329         }
 330
 331         uint32 jump_delta;
 332         if (!is_long_jump) {
 333           if (!reader.Read(7, &jump_delta)) {
 334             return false;
 335           }
 336         } else {
 337           uint32 jump_delta_bits;
 338           if (!reader.Read(4, &jump_delta_bits) ||
 339               !reader.Read(jump_delta_bits + 8, &jump_delta)) {
 340             return false;
 341           }
 342         }
 343
 344         current_offset += jump_delta;
 345         if (current_offset >= bit_offset) {
 346           return false;
 347         }
 348       }
 349
 350       DCHECK_LT(0u, hostname_offset);
 351       if (hostname[hostname_offset - 1] == c) {
 352         bit_offset = current_offset;
 353         hostname_offset--;
 354         break;
 355       }
 356     }
 357   }
 358 }
 359
 360 bool DecodeHSTSPreload(const std::string& hostname, PreloadResult* out)
 361 {
 362   bool found;
 363   if (!DecodeHSTSPreloadRaw(hostname, &found, out)) {
 364     DCHECK(false, "Internal error in DecodeHSTSPreloadRaw for hostname %s", hostname.c_str());
 365     return false;
 366   }
 367
 368   return found;
 369 }
 370
 371 } // namespace TPKP