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