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