components/rappor/byte_vector_utils.h

   1 // Copyright 2014 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 COMPONENTS_RAPPOR_BYTE_VECTOR_UTILS_H_
   6 #define COMPONENTS_RAPPOR_BYTE_VECTOR_UTILS_H_
   7
   8 #include <vector>
   9
  10 #include "base/basictypes.h"
  11 #include "components/rappor/rappor_parameters.h"
  12 #include "crypto/hmac.h"
  13
  14 namespace rappor {
  15
  16 // A vector of 8-bit integers used to store a set of binary bits.
  17 typedef std::vector<uint8_t> ByteVector;
  18
  19 // Computes a bitwise OR of byte vectors and stores the result in rhs.
  20 // Returns rhs for chaining.
  21 ByteVector* ByteVectorOr(const ByteVector& lhs, ByteVector* rhs);
  22
  23 // Merges the contents of lhs and rhs  vectors according to a mask vector.
  24 // The i-th bit of the result vector will be the i-th bit of either the lhs
  25 // or rhs vector, based on the i-th bit of the mask vector.
  26 // Equivalent to (lhs & ~mask) | (rhs & mask).  Stores the result in rhs.
  27 // Returns rhs for chaining.
  28 ByteVector* ByteVectorMerge(const ByteVector& mask,
  29                             const ByteVector& lhs,
  30                             ByteVector* rhs);
  31
  32 // Counts the number of bits set in the byte vector.
  33 int CountBits(const ByteVector& vector);
  34
  35 // A utility object for generating random binary data with different
  36 // likelihood of bits being true, using entropy from crypto::RandBytes().
  37 class ByteVectorGenerator {
  38  public:
  39   explicit ByteVectorGenerator(size_t byte_count);
  40
  41   ~ByteVectorGenerator();
  42
  43   // Generates a random byte vector where the bits are independent random
  44   // variables which are true with the given |probability|.
  45   ByteVector GetWeightedRandomByteVector(Probability probability);
  46
  47  protected:
  48   // Size of vectors to be generated.
  49   size_t byte_count() const { return byte_count_; }
  50
  51   // Generates a random vector of bytes from a uniform distribution.
  52   virtual ByteVector GetRandomByteVector();
  53
  54  private:
  55   size_t byte_count_;
  56
  57   DISALLOW_COPY_AND_ASSIGN(ByteVectorGenerator);
  58 };
  59
  60 // A ByteVectorGenerator that uses a psuedo-random function to generate a
  61 // deterministically random bits.  This class only implements a single request
  62 // from HMAC_DRBG and streams up to 2^19 bits from that request.
  63 // Ref: http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf
  64 // We're using our own PRNG instead of crypto::RandBytes because we need to
  65 // generate a repeatable sequence of bits from the same seed. Conservatively,
  66 // we're choosing to use HMAC_DRBG here, as it is one of the best studied
  67 // and standardized ways of generating deterministic, unpredictable sequences
  68 // based on a secret seed.
  69 class HmacByteVectorGenerator : public ByteVectorGenerator {
  70  public:
  71   // Constructor takes the size of the vector to generate, along with a
  72   // |entropy_input| and |personalization_string| to seed the pseudo-random
  73   // number generator.  The string parameters are treated as byte arrays.
  74   HmacByteVectorGenerator(size_t byte_count,
  75                           const std::string& entropy_input,
  76                           const std::string& personalization_string);
  77
  78   ~HmacByteVectorGenerator();
  79
  80   // Generates a random string suitable for passing to the constructor as
  81   // |entropy_input|.
  82   static std::string GenerateEntropyInput();
  83
  84   // Key size required for 128-bit security strength (including nonce).
  85   static const size_t kEntropyInputSize;
  86
  87  protected:
  88   // Generate byte vector generator that streams from the next request instead
  89   // of the current one.  For testing against NIST test vectors only.
  90   explicit HmacByteVectorGenerator(const HmacByteVectorGenerator& prev_request);
  91
  92   // ByteVector implementation:
  93   virtual ByteVector GetRandomByteVector() OVERRIDE;
  94
  95  private:
  96   // HMAC initalized with the value of "Key" HMAC_DRBG_Initialize.
  97   crypto::HMAC hmac_;
  98
  99   // The "V" value from HMAC_DRBG.
 100   ByteVector value_;
 101
 102   // Total number of bytes streamed from the HMAC_DRBG Generate Process.
 103   size_t generated_bytes_;
 104
 105   DISALLOW_ASSIGN(HmacByteVectorGenerator);
 106 };
 107
 108 }  // namespace rappor
 109
 110 #endif  // COMPONENTS_RAPPOR_BYTE_VECTOR_UTILS_H_