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