RAPPOR implementation

components/rappor/byte_vector_utils.h

Index: components/rappor/byte_vector_utils.h
diff --git a/components/rappor/byte_vector_utils.h b/components/rappor/byte_vector_utils.h
new file mode 100644
index 0000000000000000000000000000000000000000..5fffd0ce1ecb7ab99b54bf6832525d2914923b3d
--- /dev/null
+++ b/components/rappor/byte_vector_utils.h
@@ -0,0 +1,99 @@
+// 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.

[Ilya Sherman, 2014/02/13 01:39:03]

nit: Please document the return value as well.

+ByteVector* ByteVectorOr(const ByteVector& lhs, ByteVector* rhs);
+
+// Merges the contents of lhs and rhs  vectors according to a mask vector.

[Ilya Sherman, 2014/02/13 01:39:03]

nit: I think it would be helpful to spell out, in English, that bit i in the
resulting vector is set to bit i from either the lhs or the rhs vector,
depending on whether bit i of the mask vector is 0 (lhs) or 1 (rhs).

[Ilya Sherman, 2014/02/13 23:23:08]

^^^

[Steven Holte, 2014/02/14 02:53:28]

Done.

+// Equivalent to (lhs & ~mask) | (rhs & mask).  Stores the result in rhs.

[Ilya Sherman, 2014/02/13 01:39:03]

nit: Please document the return value as well.

[Ilya Sherman, 2014/02/13 23:23:08]

^^^

[Steven Holte, 2014/02/14 02:53:28]

Done.

+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 independent random
+  // variables which are true with the given |probability|.
+  ByteVector GetWeightedRandomByteVector(Probability probability);
+
+ protected:
+  // Generates a random vector of bytes from a uniform distribution.
+  virtual ByteVector GetRandomByteVector();
+
+  size_t byte_count_;

[Ilya Sherman, 2014/02/13 01:39:03]

nit: This and the DISALLOW_COPY_AND_ASSIGN lines should have private visibility,
not protected.

[Steven Holte, 2014/02/13 05:11:12]

Done.

+
+  DISALLOW_COPY_AND_ASSIGN(ByteVectorGenerator);
+};
+
+// A ByteVectorGenerator that uses a psuedo-random function to generate a
+// deterministically random bits.  This class only implements a single request
+// from HMAC_DRBG and streams up to 2^19 bits from that request.
+// Ref: http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf
+// We're using our own PRNG instead of crypto::RandBytes because we need to
+// generate a repeatable sequence of bits from the same seed. Conservatively,
+// we're choosing to use HMAC_DRBG here, as it is one of the best studied
+// and standardized ways of generating deterministic, unpredictable sequences
+// based on a secret seed.
+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

[Ilya Sherman, 2014/02/13 01:39:03]

nit: There is no parameter named |secret| below.  Has this been replaced by one
or both of the two string variables?  Please update the documentation.

[Steven Holte, 2014/02/13 05:11:12]

Done.

+  // treated as an array of bytes.
+  HmacByteVectorGenerator(size_t byte_count,
+                          const std::string& entropy_input,
+                          const std::string& personalization_string);
+
+  ~HmacByteVectorGenerator();
+
+  static std::string GenerateEntropyInput();

[Ilya Sherman, 2014/02/13 01:39:03]

nit: Docs, please.

[Steven Holte, 2014/02/13 05:11:12]

Done.

+
+  // Key size required for 128-bit security strength (including nonce).
+  static const size_t kEntropyInputSize;
+
+ protected:
+  virtual ByteVector GetRandomByteVector() OVERRIDE;

[Ilya Sherman, 2014/02/13 01:39:03]

nit: Please add the comment "// ByteVector implementation:" above this line.

[Steven Holte, 2014/02/13 05:11:12]

Done.

+
+ private:
+  // Implements (Key, V) = HMAC_DRBG_Update(provided_data, Key, V)

[Ilya Sherman, 2014/02/13 01:39:03]

nit: IMO, you should probably use either (Key, Value) or (K, V); but not (Key,
V).

[Steven Holte, 2014/02/13 05:11:12]

This is what the NIST spec uses.

+  // V is read from and written to value_

[Ilya Sherman, 2014/02/13 01:39:03]

nit: Please end the sentence with a period.

[Steven Holte, 2014/02/13 05:11:12]

Done.

+  // Key is output by passing it to hmac_.Init

[Ilya Sherman, 2014/02/13 01:39:03]

nit: Ditto.

[Steven Holte, 2014/02/13 05:11:12]

Done.

+  void Update(const std::string& provided_data, const ByteVector& key);
+
+  // HMAC initalized with the value of "Key" HMAC_DRBG_Initialize.
+  crypto::HMAC hmac_;
+  // The "V" value from HMAC_DRBG.
+  ByteVector value_;
+  // Total number of bytes streamed from the HMAC_DRBG Generate Process.
+  size_t generated_bytes_;

[Ilya Sherman, 2014/02/13 01:39:03]

nit: Please leave blank lines between documented member variables.

[Steven Holte, 2014/02/13 05:11:12]

Done.

+
+  DISALLOW_COPY_AND_ASSIGN(HmacByteVectorGenerator);
+};
+
+}  // namespace rappor
+
+#endif  // COMPONENTS_RAPPOR_BYTE_VECTOR_UTILS_H_