| OLD | NEW |
| 1 // Copyright (c) 2013 The Chromium Authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
| 3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
| 4 | 4 |
| 5 #ifndef NET_QUIC_CRYPTO_STRIKE_REGISTER_H_ | 5 #ifndef NET_QUIC_CRYPTO_STRIKE_REGISTER_H_ |
| 6 #define NET_QUIC_CRYPTO_STRIKE_REGISTER_H_ | 6 #define NET_QUIC_CRYPTO_STRIKE_REGISTER_H_ |
| 7 | 7 |
| 8 #include <set> | 8 #include <set> |
| 9 #include <utility> | 9 #include <utility> |
| 10 #include <vector> | 10 #include <vector> |
| 11 | 11 |
| 12 #include "base/basictypes.h" | 12 #include "base/basictypes.h" |
| 13 #include "base/memory/scoped_ptr.h" | 13 #include "base/memory/scoped_ptr.h" |
| 14 #include "net/base/net_export.h" | 14 #include "net/base/net_export.h" |
| 15 | 15 |
| 16 namespace net { | 16 namespace net { |
| 17 | 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 |
| 18 // A StrikeRegister is critbit tree which stores a set of observed nonces. | 38 // A StrikeRegister is critbit tree which stores a set of observed nonces. |
| 19 // We use a critbit tree because: | 39 // We use a critbit tree because: |
| 20 // 1) It's immune to algorithmic complexity attacks. If we had used a hash | 40 // 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 | 41 // 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. | 42 // 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 | 43 // 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 | 44 // 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.) | 45 // 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 | 46 // 3) It's simple (compared to balanced binary trees) and doesn't involve |
| 27 // bouncing nearly as many cache lines around. | 47 // bouncing nearly as many cache lines around. |
| (...skipping 72 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 100 | 120 |
| 101 ~StrikeRegister(); | 121 ~StrikeRegister(); |
| 102 | 122 |
| 103 void Reset(); | 123 void Reset(); |
| 104 | 124 |
| 105 // |Insert| queries to see if |nonce| is | 125 // |Insert| queries to see if |nonce| is |
| 106 // a) for the wrong orbit | 126 // a) for the wrong orbit |
| 107 // b) before the current horizon | 127 // b) before the current horizon |
| 108 // c) outside of the valid time window | 128 // c) outside of the valid time window |
| 109 // d) already in the set of observed nonces | 129 // d) already in the set of observed nonces |
| 110 // and returns false if any of these are true. It is also free to return | 130 // and returns the failure reason if any of these are true. It is also free to |
| 111 // false for other reasons as it's always safe to reject an nonce. | 131 // return failure reason for other reasons as it's always safe to reject an |
| 132 // nonce. |
| 112 // | 133 // |
| 113 // nonces are: | 134 // nonces are: |
| 114 // 4 bytes of timestamp (UNIX epoch seconds) | 135 // 4 bytes of timestamp (UNIX epoch seconds) |
| 115 // 8 bytes of orbit value (a cluster id) | 136 // 8 bytes of orbit value (a cluster id) |
| 116 // 20 bytes of random data | 137 // 20 bytes of random data |
| 117 // | 138 // |
| 118 // Otherwise, it inserts |nonce| into the observed set and returns true. | 139 // Otherwise, it inserts |nonce| into the observed set and returns NONCE_OK. |
| 119 bool Insert(const uint8 nonce[32], uint32 current_time); | 140 InsertStatus Insert(const uint8 nonce[32], uint32 current_time); |
| 120 | 141 |
| 121 // orbit returns a pointer to the 8-byte orbit value for this | 142 // orbit returns a pointer to the 8-byte orbit value for this |
| 122 // strike-register. | 143 // strike-register. |
| 123 const uint8* orbit() const; | 144 const uint8* orbit() const; |
| 124 | 145 |
| 125 // Time window for which the strike register has complete information. | 146 // Time window for which the strike register has complete information. |
| 126 uint32 GetCurrentValidWindowSecs(uint32 current_time_external) const; | 147 uint32 GetCurrentValidWindowSecs(uint32 current_time_external) const; |
| 127 | 148 |
| 128 // This is a debugging aid which checks the tree for sanity. | 149 // This is a debugging aid which checks the tree for sanity. |
| 129 void Validate(); | 150 void Validate(); |
| (...skipping 60 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 190 // this header. | 211 // this header. |
| 191 InternalNode* internal_nodes_; | 212 InternalNode* internal_nodes_; |
| 192 scoped_ptr<uint8[]> external_nodes_; | 213 scoped_ptr<uint8[]> external_nodes_; |
| 193 | 214 |
| 194 DISALLOW_COPY_AND_ASSIGN(StrikeRegister); | 215 DISALLOW_COPY_AND_ASSIGN(StrikeRegister); |
| 195 }; | 216 }; |
| 196 | 217 |
| 197 } // namespace net | 218 } // namespace net |
| 198 | 219 |
| 199 #endif // NET_QUIC_CRYPTO_STRIKE_REGISTER_H_ | 220 #endif // NET_QUIC_CRYPTO_STRIKE_REGISTER_H_ |
| OLD | NEW |