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 // Allows early validation before a strike register is created. 85 static void ValidateStrikeRegisterConfig(unsigned max_entries); 86 87 // Construct a new set which can hold, at most, |max_entries| (which must be 88 // less than 2**23). See the comments around StartupType about initial 89 // behaviour. Otherwise, all nonces that are outside +/- |window_secs| from 90 // the current time will be rejected. Additionally, all nonces that have an 91 // orbit value other than |orbit| will be rejected. 92 // 93 // (Note that this code is independent of the actual units of time used, but 94 // you should use seconds.) 95 StrikeRegister(unsigned max_entries, 96 uint32 current_time_external, 97 uint32 window_secs, 98 const uint8 orbit[8], 99 StartupType startup); 100 101 ~StrikeRegister(); 102 103 void Reset(); 104 105 // |Insert| queries to see if |nonce| is 106 // a) for the wrong orbit 107 // b) before the current horizon 108 // c) outside of the valid time window 109 // d) already in the set of observed nonces 110 // and returns false if any of these are true. It is also free to return 111 // false for other reasons as it's always safe to reject an nonce. 112 // 113 // nonces are: 114 // 4 bytes of timestamp (UNIX epoch seconds) 115 // 8 bytes of orbit value (a cluster id) 116 // 20 bytes of random data 117 // 118 // Otherwise, it inserts |nonce| into the observed set and returns true. 119 bool Insert(const uint8 nonce[32], const uint32 current_time); 120 121 // orbit returns a pointer to the 8-byte orbit value for this 122 // strike-register. 123 const uint8* orbit() const; 124 125 // This is a debugging aid which checks the tree for sanity. 126 void Validate(); 127 128 private: 129 class InternalNode; 130 131 // TimeFromBytes returns a big-endian uint32 from |d|. 132 static uint32 TimeFromBytes(const uint8 d[4]); 133 134 // ExternalTimeToInternal converts an external time value into an internal 135 // time value using |internal_epoch_|. 136 uint32 ExternalTimeToInternal(uint32 external_time); 137 138 // BestMatch returns either kNil, or an external node index which could 139 // possibly match |v|. 140 uint32 BestMatch(const uint8 v[24]) const; 141 142 // external_node_next_ptr returns the 'next' pointer embedded in external 143 // node |i|. This is used to thread a free list through the external nodes. 144 uint32& external_node_next_ptr(unsigned i); 145 146 uint8* external_node(unsigned i); 147 148 uint32 GetFreeExternalNode(); 149 150 uint32 GetFreeInternalNode(); 151 152 // DropNode removes the oldest node in the tree and updates |horizon_| 153 // accordingly. 154 void DropNode(); 155 156 void FreeExternalNode(uint32 index); 157 158 void FreeInternalNode(uint32 index); 159 160 void ValidateTree(uint32 internal_node, 161 int last_bit, 162 const std::vector<std::pair<unsigned, bool> >& bits, 163 const std::set<uint32>& free_internal_nodes, 164 const std::set<uint32>& free_external_nodes, 165 std::set<uint32>* used_internal_nodes, 166 std::set<uint32>* used_external_nodes); 167 168 const uint32 max_entries_; 169 const uint32 window_secs_; 170 // internal_epoch_ contains the external time value of the start of internal 171 // time. 172 const uint32 internal_epoch_; 173 uint8 orbit_[8]; 174 uint32 horizon_; 175 bool horizon_valid_; 176 177 uint32 internal_node_free_head_; 178 uint32 external_node_free_head_; 179 uint32 internal_node_head_; 180 // internal_nodes_ can't be a scoped_ptr because the type isn't defined in 181 // this header. 182 InternalNode* internal_nodes_; 183 scoped_ptr<uint8[]> external_nodes_; 184 185 DISALLOW_COPY_AND_ASSIGN(StrikeRegister); 186 }; 187 188 } // namespace net 189 190 #endif // NET_QUIC_CRYPTO_STRIKE_REGISTER_H_ 191
