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         num_bits_used_(8) {}
  48
  49   // Next sets |*out| to the next bit from the input. It returns false if no
  50   // more bits are available or true otherwise.
  51   bool Next(bool* out) {
  52     if (num_bits_used_ == 8) {
  53       if (current_byte_index_ >= num_bytes_) {
  54         return false;
  55       }
  56       current_byte_ = bytes_[current_byte_index_++];
  57       num_bits_used_ = 0;
  58     }
  59
  60     *out = 1 & (current_byte_ >> (7 - num_bits_used_));
  61     num_bits_used_++;
  62     return true;
  63   }
  64
  65   // Read sets the |num_bits| least-significant bits of |*out| to the value of
  66   // the next |num_bits| bits from the input. It returns false if there are
  67   // insufficient bits in the input or true otherwise.
  68   bool Read(unsigned num_bits, uint32* out) {
  69     DCHECK_LE(num_bits, 32u);
  70
  71     uint32 ret = 0;
  72     for (unsigned i = 0; i < num_bits; ++i) {
  73       bool bit;
  74       if (!Next(&bit)) {
  75         return false;
  76       }
  77       ret |= static_cast<uint32>(bit) << (num_bits - 1 - i);
  78     }
  79
  80     *out = ret;
  81     return true;
  82   }
  83
  84   // Unary sets |*out| to the result of decoding a unary value from the input.
  85   // It returns false if there were insufficient bits in the input and true
  86   // otherwise.
  87   bool Unary(size_t* out) {
  88     size_t ret = 0;
  89
  90     for (;;) {
  91       bool bit;
  92       if (!Next(&bit)) {
  93         return false;
  94       }
  95       if (!bit) {
  96         break;
  97       }
  98       ret++;
  99     }
 100
 101     *out = ret;
 102     return true;
 103   }
 104
 105   // Seek sets the current offest in the input to bit number |offset|. It
 106   // returns true if |offset| is within the range of the input and false
 107   // otherwise.
 108   bool Seek(size_t offset) {
 109     if (offset >= num_bits_) {
 110       return false;
 111     }
 112     current_byte_index_ = offset / 8;
 113     current_byte_ = bytes_[current_byte_index_++];
 114     num_bits_used_ = offset % 8;
 115     return true;
 116   }
 117
 118  private:
 119   const uint8* const bytes_;
 120   const size_t num_bits_;
 121   const size_t num_bytes_;
 122   // current_byte_index_ contains the current byte offset in |bytes_|.
 123   size_t current_byte_index_;
 124   // current_byte_ contains the current byte of the input.
 125   uint8 current_byte_;
 126   // num_bits_used_ contains the number of bits of |current_byte_| that have
 127   // been read.
 128   unsigned num_bits_used_;
 129 };
 130
 131 // HuffmanDecoder is a very simple Huffman reader. The input Huffman tree is
 132 // simply encoded as a series of two-byte structures. The first byte determines
 133 // the "0" pointer for that node and the second the "1" pointer. Each byte
 134 // either has the MSB set, in which case the bottom 7 bits are the value for
 135 // that position, or else the bottom seven bits contain the index of a node.
 136 //
 137 // The tree is decoded by walking rather than a table-driven approach.
 138 class HuffmanDecoder {
 139  public:
 140   HuffmanDecoder(const uint8* tree, size_t tree_bytes)
 141       : tree_(tree),
 142         tree_bytes_(tree_bytes) {}
 143
 144   bool Decode(BitReader* reader, char* out) {
 145     const uint8* current = &tree_[tree_bytes_-2];
 146
 147     for (;;) {
 148       bool bit;
 149       if (!reader->Next(&bit)) {
 150         return false;
 151       }
 152
 153       uint8 b = current[bit];
 154       if (b & 0x80) {
 155         *out = static_cast<char>(b & 0x7f);
 156         return true;
 157       }
 158
 159       unsigned offset = static_cast<unsigned>(b) * 2;
 160       DCHECK_LT(offset, tree_bytes_);
 161       if (offset >= tree_bytes_) {
 162         return false;
 163       }
 164
 165       current = &tree_[offset];
 166     }
 167   }
 168
 169  private:
 170   const uint8* const tree_;
 171   const size_t tree_bytes_;
 172 };
 173
 174 } // namespace anonymous
 175
 176 namespace net {
 177
 178 // DecodeHSTSPreloadRaw resolves |hostname| in the preloaded data. It returns
 179 // false on internal error and true otherwise. After a successful return,
 180 // |*out_found| is true iff a relevant entry has been found. If so, |*out|
 181 // contains the details.
 182 //
 183 // Don't call this function, call DecodeHSTSPreload, below.
 184 //
 185 // Although this code should be robust, it never processes attacker-controlled
 186 // data -- it only operates on the preloaded data built into the binary.
 187 //
 188 // The preloaded data is represented as a trie and matches the hostname
 189 // backwards. Each node in the trie starts with a number of characters, which
 190 // must match exactly. After that is a dispatch table which maps the next
 191 // character in the hostname to another node in the trie.
 192 //
 193 // In the dispatch table, the zero character represents the "end of string"
 194 // (which is the *beginning* of a hostname since we process it backwards). The
 195 // value in that case is special -- rather than an offset to another trie node,
 196 // it contains the HSTS information: whether subdomains are included, pinsets
 197 // etc. If an "end of string" matches a period in the hostname then the
 198 // information is remembered because, if no more specific node is found, then
 199 // that information applies to the hostname.
 200 //
 201 // Dispatch tables are always given in order, but the "end of string" (zero)
 202 // value always comes before an entry for '.'.
 203 bool DecodeHSTSPreloadRaw(const std::string& hostname,
 204                           bool* out_found,
 205                           PreloadResult* out) {
 206   HuffmanDecoder huffman(kHSTSHuffmanTree, sizeof(kHSTSHuffmanTree));
 207   BitReader reader(kPreloadedHSTSData, kPreloadedHSTSBits);
 208   size_t bit_offset = kHSTSRootPosition;
 209   static const char kEndOfString = 0;
 210   static const char kEndOfTable = 127;
 211
 212   *out_found = false;
 213
 214   if (hostname.empty()) {
 215     return true;
 216   }
 217   // hostname_offset contains one more than the index of the current character
 218   // in the hostname that is being considered. It's one greater so that we can
 219   // represent the position just before the beginning (with zero).
 220   size_t hostname_offset = hostname.size();
 221
 222   for (;;) {
 223     // Seek to the desired location.
 224     if (!reader.Seek(bit_offset)) {
 225       return false;
 226     }
 227
 228     // Decode the unary length of the common prefix.
 229     size_t prefix_length;
 230     if (!reader.Unary(&prefix_length)) {
 231       return false;
 232     }
 233
 234     // Match each character in the prefix.
 235     for (size_t i = 0; i < prefix_length; ++i) {
 236       if (hostname_offset == 0) {
 237         // We can't match the terminator with a prefix string.
 238         return true;
 239       }
 240
 241       char c;
 242       if (!huffman.Decode(&reader, &c)) {
 243         return false;
 244       }
 245       if (hostname[hostname_offset - 1] != c) {
 246         return true;
 247       }
 248       hostname_offset--;
 249     }
 250
 251     bool is_first_offset = true;
 252     size_t current_offset = 0;
 253
 254     // Next is the dispatch table.
 255     for (;;) {
 256       char c;
 257       if (!huffman.Decode(&reader, &c)) {
 258         return false;
 259       }
 260       if (c == kEndOfTable) {
 261         // No exact match.
 262         return true;
 263       }
 264
 265       if (c == kEndOfString) {
 266         PreloadResult tmp;
 267         if (!reader.Next(&tmp.sts_include_subdomains) ||
 268             !reader.Next(&tmp.force_https) ||
 269             !reader.Next(&tmp.has_pins)) {
 270           return false;
 271         }
 272
 273         tmp.pkp_include_subdomains = tmp.sts_include_subdomains;
 274
 275         if (tmp.has_pins) {
 276           if (!reader.Read(4, &tmp.pinset_id) ||
 277               !reader.Read(9, &tmp.domain_id) ||
 278               (!tmp.sts_include_subdomains &&
 279                !reader.Next(&tmp.pkp_include_subdomains))) {
 280             return false;
 281           }
 282         }
 283
 284         tmp.hostname_offset = hostname_offset;
 285
 286         if (hostname_offset == 0 || hostname[hostname_offset - 1] == '.') {
 287           *out_found =
 288               tmp.sts_include_subdomains || tmp.pkp_include_subdomains;
 289           *out = tmp;
 290
 291           if (hostname_offset > 0) {
 292             out->force_https &= tmp.sts_include_subdomains;
 293           } else {
 294             *out_found = true;
 295             return true;
 296           }
 297         }
 298
 299         continue;
 300       }
 301
 302       // The entries in a dispatch table are in order thus we can tell if there
 303       // will be no match if the current character past the one that we want.
 304       if (hostname_offset == 0 || hostname[hostname_offset-1] < c) {
 305         return true;
 306       }
 307
 308       if (is_first_offset) {
 309         // The first offset is backwards from the current position.
 310         uint32 jump_delta_bits;
 311         uint32 jump_delta;
 312         if (!reader.Read(5, &jump_delta_bits) ||
 313             !reader.Read(jump_delta_bits, &jump_delta)) {
 314           return false;
 315         }
 316
 317         if (bit_offset < jump_delta) {
 318           return false;
 319         }
 320
 321         current_offset = bit_offset - jump_delta;
 322         is_first_offset = false;
 323       } else {
 324         // Subsequent offsets are forward from the target of the first offset.
 325         uint32 is_long_jump;
 326         if (!reader.Read(1, &is_long_jump)) {
 327           return false;
 328         }
 329
 330         uint32 jump_delta;
 331         if (!is_long_jump) {
 332           if (!reader.Read(7, &jump_delta)) {
 333             return false;
 334           }
 335         } else {
 336           uint32 jump_delta_bits;
 337           if (!reader.Read(4, &jump_delta_bits) ||
 338               !reader.Read(jump_delta_bits + 8, &jump_delta)) {
 339             return false;
 340           }
 341         }
 342
 343         current_offset += jump_delta;
 344         if (current_offset >= bit_offset) {
 345           return false;
 346         }
 347       }
 348
 349       DCHECK_LT(0u, hostname_offset);
 350       if (hostname[hostname_offset - 1] == c) {
 351         bit_offset = current_offset;
 352         hostname_offset--;
 353         break;
 354       }
 355     }
 356   }
 357 }
 358
 359 bool DecodeHSTSPreload(const std::string& hostname, PreloadResult* out)
 360 {
 361   bool found;
 362   if (!DecodeHSTSPreloadRaw(hostname, &found, out)) {
 363     DCHECK(false, "Internal error in DecodeHSTSPreloadRaw for hostname %s", hostname.c_str());
 364     return false;
 365   }
 366
 367   return found;
 368 }
 369
 370 } // namespace TPKP