| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright (c) 2013 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 #ifndef NET_QUIC_CRYPTO_STRIKE_REGISTER_H_ | |
| 6 #define NET_QUIC_CRYPTO_STRIKE_REGISTER_H_ | |
| 7 | |
| 8 #include <set> | |
| 9 #include <utility> | |
| 10 #include <vector> | |
| 11 | |
| 12 #include "base/basictypes.h" | |
| 13 #include "base/memory/scoped_ptr.h" | |
| 14 #include "net/base/net_export.h" | |
| 15 | |
| 16 namespace net { | |
| 17 | |
| 18 // InsertStatus enum values cannot be changed, they need to be stable. | |
| 19 enum InsertStatus { | |
| 20 NONCE_OK = 0, | |
| 21 // The default error value for nonce verification failures from strike | |
| 22 // register (covers old strike registers and unknown failures). | |
| 23 NONCE_UNKNOWN_FAILURE = 1, | |
| 24 // Decrypted nonce had incorrect length. | |
| 25 NONCE_INVALID_FAILURE = 2, | |
| 26 // Nonce is not unique. | |
| 27 NONCE_NOT_UNIQUE_FAILURE = 3, | |
| 28 // Nonce's orbit is invalid or incorrect. | |
| 29 NONCE_INVALID_ORBIT_FAILURE = 4, | |
| 30 // Nonce's timestamp is not in the strike register's valid time range. | |
| 31 NONCE_INVALID_TIME_FAILURE = 5, | |
| 32 // Strike register's RPC call timed out, nonce couldn't be verified. | |
| 33 STRIKE_REGISTER_TIMEOUT = 6, | |
| 34 // Strike register is down, nonce couldn't be verified. | |
| 35 STRIKE_REGISTER_FAILURE = 7, | |
| 36 }; | |
| 37 | |
| 38 // A StrikeRegister is critbit tree which stores a set of observed nonces. | |
| 39 // We use a critbit tree because: | |
| 40 // 1) It's immune to algorithmic complexity attacks. If we had used a hash | |
| 41 // tree, an attacker could send us a series of values which stretch out one | |
| 42 // of the hash chains, causing us to do much more work than normal. | |
| 43 // 2) We can write it to use a fixed block of memory: avoiding fragmentation | |
| 44 // issues and so forth. (We might be able to do that with the STL | |
| 45 // algorithms and a custom allocator, but I don't want to go there.) | |
| 46 // 3) It's simple (compared to balanced binary trees) and doesn't involve | |
| 47 // bouncing nearly as many cache lines around. | |
| 48 // 4) It allows us to query for the oldest element in log(n) time. | |
| 49 // | |
| 50 // This code is based on djb's public domain critbit tree from qhasm. | |
| 51 // | |
| 52 // A critbit tree has external and internal nodes. External nodes are just the | |
| 53 // nonce values (which are stored with internal times, see below, and without | |
| 54 // the orbit values included). Internal nodes contain the bit number at which | |
| 55 // the tree is branching and exactly two children. The critical bit is stored | |
| 56 // as a byte number and a byte (|otherbits|) which has all the bits set | |
| 57 // /except/ the one in question. | |
| 58 // | |
| 59 // Internal nodes have exactly two children: an internal node with only a | |
| 60 // single child would be useless. | |
| 61 // | |
| 62 // The branching bit number (considering the MSB to be the 1st bit) is | |
| 63 // monotonically increasing as you go down the tree. | |
| 64 // | |
| 65 // There are two distinct time representations used. External times are those | |
| 66 // which are exposed to the users of this class. They are expected to be a | |
| 67 // count of the number of seconds since the UNIX epoch. Internal times are a | |
| 68 // count of the number of seconds since a point in time a couple of years | |
| 69 // before the creation time given to the constructor. (See | |
| 70 // |ExternalTimeToInternal|) This avoids having to worry about overflow since | |
| 71 // we assume that no process will run for 130 years. | |
| 72 class NET_EXPORT_PRIVATE StrikeRegister { | |
| 73 public: | |
| 74 enum StartupType { | |
| 75 // DENY_REQUESTS_AT_STARTUP is the typical mode for a strike register. | |
| 76 // Because servers can crash and the strike-register memory-based, the | |
| 77 // state of the strike-register may be lost at any time. Thus the previous | |
| 78 // instance of the server may have accepted an nonce with time | |
| 79 // now+window_secs, which was forgotten in the crash. Therefore | |
| 80 // DENY_REQUESTS_AT_STARTUP causes the strike-register to reject all | |
| 81 // requests timestampped before window_secs + the creation time (the | |
| 82 // quiescent period). | |
| 83 DENY_REQUESTS_AT_STARTUP, | |
| 84 // NO_STARTUP_PERIOD_NEEDED indicates that no quiescent period is required. | |
| 85 // This may be because the strike-register is using an orbit randomly | |
| 86 // generated at startup and therefore nonces accepted by the previous | |
| 87 // instance of the strike-register are invalid for that reason. | |
| 88 NO_STARTUP_PERIOD_NEEDED, | |
| 89 }; | |
| 90 | |
| 91 // An external node takes 24 bytes as we don't record the orbit. | |
| 92 static const uint32 kExternalNodeSize; | |
| 93 | |
| 94 // We address the nodes by their index in the array. This means that 0 is a | |
| 95 // valid index. Therefore this is our invalid index. It also has a one bit | |
| 96 // in the LSB position because we tend to store indexes shifted up 8 bits | |
| 97 // and this distinguishes kNil from (kExternalFlag | 0) << 8. | |
| 98 static const uint32 kNil; | |
| 99 | |
| 100 // Our pointers from internal nodes can either point to an internal or | |
| 101 // external node. We flag the 24th bit to mark a pointer as external. | |
| 102 static const uint32 kExternalFlag; | |
| 103 | |
| 104 // Allows early validation before a strike register is created. | |
| 105 static void ValidateStrikeRegisterConfig(unsigned max_entries); | |
| 106 | |
| 107 // Construct a new set which can hold, at most, |max_entries| (which must be | |
| 108 // less than 2**23). See the comments around StartupType about initial | |
| 109 // behaviour. Otherwise, all nonces that are outside +/- |window_secs| from | |
| 110 // the current time will be rejected. Additionally, all nonces that have an | |
| 111 // orbit value other than |orbit| will be rejected. | |
| 112 // | |
| 113 // (Note that this code is independent of the actual units of time used, but | |
| 114 // you should use seconds.) | |
| 115 StrikeRegister(unsigned max_entries, | |
| 116 uint32 current_time_external, | |
| 117 uint32 window_secs, | |
| 118 const uint8 orbit[8], | |
| 119 StartupType startup); | |
| 120 | |
| 121 ~StrikeRegister(); | |
| 122 | |
| 123 void Reset(); | |
| 124 | |
| 125 // |Insert| queries to see if |nonce| is | |
| 126 // a) for the wrong orbit | |
| 127 // b) before the current horizon | |
| 128 // c) outside of the valid time window | |
| 129 // d) already in the set of observed nonces | |
| 130 // and returns the failure reason if any of these are true. It is also free to | |
| 131 // return failure reason for other reasons as it's always safe to reject an | |
| 132 // nonce. | |
| 133 // | |
| 134 // nonces are: | |
| 135 // 4 bytes of timestamp (UNIX epoch seconds) | |
| 136 // 8 bytes of orbit value (a cluster id) | |
| 137 // 20 bytes of random data | |
| 138 // | |
| 139 // Otherwise, it inserts |nonce| into the observed set and returns NONCE_OK. | |
| 140 InsertStatus Insert(const uint8 nonce[32], uint32 current_time); | |
| 141 | |
| 142 // orbit returns a pointer to the 8-byte orbit value for this | |
| 143 // strike-register. | |
| 144 const uint8* orbit() const; | |
| 145 | |
| 146 // Time window for which the strike register has complete information. | |
| 147 uint32 GetCurrentValidWindowSecs(uint32 current_time_external) const; | |
| 148 | |
| 149 // This is a debugging aid which checks the tree for sanity. | |
| 150 void Validate(); | |
| 151 | |
| 152 private: | |
| 153 class InternalNode; | |
| 154 | |
| 155 // TimeFromBytes returns a big-endian uint32 from |d|. | |
| 156 static uint32 TimeFromBytes(const uint8 d[4]); | |
| 157 | |
| 158 // Range of internal times for which the strike register has | |
| 159 // complete information. A nonce is within the valid range of the | |
| 160 // strike register if: | |
| 161 // valid_range.first <= nonce_time_internal <= valid_range.second | |
| 162 std::pair<uint32, uint32> GetValidRange(uint32 current_time_internal) const; | |
| 163 | |
| 164 // ExternalTimeToInternal converts an external time value into an internal | |
| 165 // time value using |internal_epoch_|. | |
| 166 uint32 ExternalTimeToInternal(uint32 external_time) const; | |
| 167 | |
| 168 // BestMatch returns either kNil, or an external node index which could | |
| 169 // possibly match |v|. | |
| 170 uint32 BestMatch(const uint8 v[24]) const; | |
| 171 | |
| 172 // external_node_next_ptr returns the 'next' pointer embedded in external | |
| 173 // node |i|. This is used to thread a free list through the external nodes. | |
| 174 uint32& external_node_next_ptr(unsigned i); | |
| 175 | |
| 176 uint8* external_node(unsigned i); | |
| 177 | |
| 178 uint32 GetFreeExternalNode(); | |
| 179 | |
| 180 uint32 GetFreeInternalNode(); | |
| 181 | |
| 182 // DropOldestNode removes the oldest node in the tree and updates |horizon_| | |
| 183 // accordingly. | |
| 184 void DropOldestNode(); | |
| 185 | |
| 186 void FreeExternalNode(uint32 index); | |
| 187 | |
| 188 void FreeInternalNode(uint32 index); | |
| 189 | |
| 190 void ValidateTree(uint32 internal_node, | |
| 191 int last_bit, | |
| 192 const std::vector<std::pair<unsigned, bool> >& bits, | |
| 193 const std::set<uint32>& free_internal_nodes, | |
| 194 const std::set<uint32>& free_external_nodes, | |
| 195 std::set<uint32>* used_internal_nodes, | |
| 196 std::set<uint32>* used_external_nodes); | |
| 197 | |
| 198 const uint32 max_entries_; | |
| 199 const uint32 window_secs_; | |
| 200 // internal_epoch_ contains the external time value of the start of internal | |
| 201 // time. | |
| 202 const uint32 internal_epoch_; | |
| 203 uint8 orbit_[8]; | |
| 204 // The strike register will reject nonces with internal times < |horizon_| . | |
| 205 uint32 horizon_; | |
| 206 | |
| 207 uint32 internal_node_free_head_; | |
| 208 uint32 external_node_free_head_; | |
| 209 uint32 internal_node_head_; | |
| 210 // internal_nodes_ can't be a scoped_ptr because the type isn't defined in | |
| 211 // this header. | |
| 212 InternalNode* internal_nodes_; | |
| 213 scoped_ptr<uint8[]> external_nodes_; | |
| 214 | |
| 215 DISALLOW_COPY_AND_ASSIGN(StrikeRegister); | |
| 216 }; | |
| 217 | |
| 218 } // namespace net | |
| 219 | |
| 220 #endif // NET_QUIC_CRYPTO_STRIKE_REGISTER_H_ | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 992733002:
Remove //net (except for Android test stuff) and sdch (Closed)
Base URL: git@github.com:domokit/mojo.git@master