RAPPOR implementation

components/rappor/byte_vector_utils.h

+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef COMPONENTS_RAPPOR_BYTE_VECTOR_UTILS_H_
+#define COMPONENTS_RAPPOR_BYTE_VECTOR_UTILS_H_
+
+#include <stddef.h>
+#include <stdint.h>
+#include <vector>
+
+#include "components/rappor/rappor_parameters.h"
+#include "crypto/hmac.h"
+
+namespace rappor {
+
+// A vector of 8-bit integers used to store a set of binary bits.
+typedef std::vector<uint8_t> ByteVector;
+
+// Computes a bitwise OR of byte vectors and stores the result in rhs.
+ByteVector* ByteVectorOr(const ByteVector& lhs, ByteVector* rhs);
+
+// Merges the contents of lhs and rhs  vectors according to a mask vector.
+// Equivalent to (lhs & ~mask) | (rhs & mask).  Stores the result in rhs.
+ByteVector* ByteVectorMerge(const ByteVector& mask,
+                            const ByteVector& lhs,
+                            ByteVector* rhs);
+
+// Counts the number of bits set in the byte vector.
+int CountBits(const ByteVector& vector);
+
+// A utility object for generating random binary data with different
+// likelihood of bits being true, using entropy from crypto::RandBytes().
+class ByteVectorGenerator {
+ public:
+  explicit ByteVectorGenerator(size_t byte_count);
+
+  ~ByteVectorGenerator();
+
+  // Generates a random byte vector where the bits are an independent random
+  // variables which are true with the given |probability|.
+  ByteVector GetWeightedRandomByteVector(Probability probability);
+
+ protected:
+  // Generates a random byte from a uniform distribution.
+  virtual uint8_t RandByte();
+
+ private:
+  // Generates a random vector of bytes from a uniform distribution.
+  ByteVector GetRandomByteVector();
+
+  size_t byte_count_;
+
+  DISALLOW_COPY_AND_ASSIGN(ByteVectorGenerator);
+};
+
+// A ByteVectorGenerator that uses a psuedo-random function to generate
+// deterministicly random bits.  The implementation is equivalent to the

[wtc, 2014/02/10 20:12:54]

Nit: deterministicly => deterministically

Also, you can just say "pseudo-random" instead of "deterministically random".

[Steven Holte, 2014/02/10 22:50:54]

Done.

+// HMAC_DRBG algorithm from NIST, assuming that all of the bytes can
+// be generated from one request.  Therefore, this one instance of this class
+// should not be used to generate more than 2^19 bits
+// Ref: http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf

[wtc, 2014/02/10 20:12:54]

IMPORTANT: sometimes we need to audit the Chromium source tree for correct use
of crypto. So the mention of "HMAC_DRBG" in this class is likely to cause this
class to be scrutinized in a crypto audit.

It would be nice if you could document why you need your own pseudo-random
number generator (PRNG). Here I asked two possible questions. But there are
other ways to document this.

1. Is HmacByteVectorGenerator used for cryptographic purposes? In other words,
do you just need the bits to be uniformly distributed, or do you also need them
to be unpredictable? The latter is a must for crypto applications.

2. If HmacByteVectorGenerator is used for non-crypto purposes, why do you use a
cryptographically secure pseudo-random number generator? The answer could be
"although a cryptographic PRNG exceeds my requirements, it saves me the time to
research a good non-cryptographic PRNG." But if that was the case, why couldn't
you just use crypto::RandomBytes?

[Steven Holte, 2014/02/10 22:50:54]

Added a longer comment explaining the rationale of using HMAC_DRBG instead of
crypto::RandBytes

+class HmacByteVectorGenerator : public ByteVectorGenerator {
+ public:
+  // Constructor takes the size of the vector to generate, along with a
+  // secret value to seed the pseudo-random number generator.  |secret| is
+  // treated as an array of bytes.
+  HmacByteVectorGenerator(size_t byte_count, const std::string& secret);
+
+  ~HmacByteVectorGenerator();
+
+ protected:
+  virtual uint8_t RandByte() OVERRIDE;
+
+ private:
+  crypto::HMAC hmac_;
+  ByteVector value_;
+  size_t requested_bytes_;
+
+  DISALLOW_COPY_AND_ASSIGN(HmacByteVectorGenerator);
+};
+
+}  // namespace rappor
+
+#endif  // COMPONENTS_RAPPOR_BYTE_VECTOR_UTILS_H_