src/net/quic/crypto/strike_register.h

   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_