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.
5 #ifndef NET_QUIC_CRYPTO_STRIKE_REGISTER_H_
6 #define NET_QUIC_CRYPTO_STRIKE_REGISTER_H_
12 #include "base/basictypes.h"
13 #include "base/memory/scoped_ptr.h"
14 #include "net/base/net_export.h"
18 // InsertStatus enum values cannot be changed, they need to be stable.
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,
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.
50 // This code is based on djb's public domain critbit tree from qhasm.
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.
59 // Internal nodes have exactly two children: an internal node with only a
60 // single child would be useless.
62 // The branching bit number (considering the MSB to be the 1st bit) is
63 // monotonically increasing as you go down the tree.
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
{
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
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
,
91 // An external node takes 24 bytes as we don't record the orbit.
92 static const uint32 kExternalNodeSize
;
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
;
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
;
104 // Allows early validation before a strike register is created.
105 static void ValidateStrikeRegisterConfig(unsigned max_entries
);
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.
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
,
118 const uint8 orbit
[8],
119 StartupType startup
);
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
135 // 4 bytes of timestamp (UNIX epoch seconds)
136 // 8 bytes of orbit value (a cluster id)
137 // 20 bytes of random data
139 // Otherwise, it inserts |nonce| into the observed set and returns NONCE_OK.
140 InsertStatus
Insert(const uint8 nonce
[32], uint32 current_time
);
142 // orbit returns a pointer to the 8-byte orbit value for this
144 const uint8
* orbit() const;
146 // Time window for which the strike register has complete information.
147 uint32
GetCurrentValidWindowSecs(uint32 current_time_external
) const;
149 // This is a debugging aid which checks the tree for sanity.
155 // TimeFromBytes returns a big-endian uint32 from |d|.
156 static uint32
TimeFromBytes(const uint8 d
[4]);
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;
164 // ExternalTimeToInternal converts an external time value into an internal
165 // time value using |internal_epoch_|.
166 uint32
ExternalTimeToInternal(uint32 external_time
) const;
168 // BestMatch returns either kNil, or an external node index which could
169 // possibly match |v|.
170 uint32
BestMatch(const uint8 v
[24]) const;
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
);
176 uint8
* external_node(unsigned i
);
178 uint32
GetFreeExternalNode();
180 uint32
GetFreeInternalNode();
182 // DropOldestNode removes the oldest node in the tree and updates |horizon_|
184 void DropOldestNode();
186 void FreeExternalNode(uint32 index
);
188 void FreeInternalNode(uint32 index
);
190 void ValidateTree(uint32 internal_node
,
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
);
198 const uint32 max_entries_
;
199 const uint32 window_secs_
;
200 // internal_epoch_ contains the external time value of the start of internal
202 const uint32 internal_epoch_
;
204 // The strike register will reject nonces with internal times < |horizon_| .
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
212 InternalNode
* internal_nodes_
;
213 scoped_ptr
<uint8
[]> external_nodes_
;
215 DISALLOW_COPY_AND_ASSIGN(StrikeRegister
);
220 #endif // NET_QUIC_CRYPTO_STRIKE_REGISTER_H_