Home | History | Annotate | Download | only in crypto
      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_
    221