RAPPOR implementation

components/rappor/byte_vector_utils.cc

Index: components/rappor/byte_vector_utils.cc
diff --git a/components/rappor/byte_vector_utils.cc b/components/rappor/byte_vector_utils.cc
new file mode 100644
index 0000000000000000000000000000000000000000..10e91046d5b7fb49702f9ff898b2858675d9d8b8
--- /dev/null
+++ b/components/rappor/byte_vector_utils.cc
@@ -0,0 +1,124 @@
+// 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.
+
+#include "components/rappor/byte_vector_utils.h"
+
+#include <string>
+
+#include "base/logging.h"
+#include "base/strings/string_number_conversions.h"
+#include "crypto/random.h"
+
+namespace rappor {
+
+ByteVector* ByteVectorOr(const ByteVector& lhs, ByteVector* rhs) {
+  DCHECK_EQ(lhs.size(), rhs->size());
+  for (size_t i = 0, len = lhs.size(); i < len; ++i) {
+    (*rhs)[i] = lhs[i] | (*rhs)[i];
+  }
+  return rhs;
+}
+
+ByteVector* ByteVectorMerge(const ByteVector& mask,
+                            const ByteVector& lhs,
+                            ByteVector* rhs) {
+  DCHECK_EQ(lhs.size(), rhs->size());
+  for (size_t i = 0, len = lhs.size(); i < len; ++i) {
+    (*rhs)[i] = (lhs[i] & ~mask[i]) | ((*rhs)[i] & mask[i]);
+  }
+  return rhs;
+}
+
+int CountBits(const ByteVector& vector) {

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

This operation is called "population count" or "popcount" in the literature.
There are clever tricks in the books "Hacker's Delight" and vol. 4 of the Art of
Computer Programming if you are interested in this.

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

Since I'm only using this function for testing, I'm not really worried about
optimizing it.

+  int bit_count = 0;
+  for(size_t i = 0; i < vector.size(); ++i) {
+    uint8_t byte = vector[i];
+    for (int j = 0; j < 8 ; ++j) {
+      if (byte & (1 << j))
+        bit_count++;
+    }
+  }
+  return bit_count;
+}
+
+ByteVectorGenerator::ByteVectorGenerator(size_t byte_count)
+    : byte_count_(byte_count) {}
+
+ByteVectorGenerator::~ByteVectorGenerator() {}
+
+uint8_t ByteVectorGenerator::RandByte() {

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

Requesting only one byte at a time from the PRNG can be very inefficient. I
suggest you make this function request a specified number of bytes from the
PRNG, for example:

  void ByteVectorGenerator::RandBytes(uint8_t*out, size_t len);

Then ByteVectorGenerator::GetRandomByteVector() can simply do:

ByteVector ByteVectorGenerator::GetRandomByteVector() {
  ByteVector bytes(byte_count_);
  RandBytes(&bytes[0], byte_count_);
  return bytes;
}

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

Done.

+  uint8_t random_bits;
+  crypto::RandBytes(&random_bits, sizeof(uint8_t));
+  return random_bits;
+}
+
+ByteVector ByteVectorGenerator::GetRandomByteVector() {
+  ByteVector bytes(byte_count_);
+  for (size_t i = 0; i < byte_count_; ++i) {
+    bytes[i] = RandByte();
+  }
+  return bytes;
+}
+
+ByteVector ByteVectorGenerator::GetWeightedRandomByteVector(
+    Probability probability) {
+  ByteVector bytes = GetRandomByteVector();
+  switch (probability) {
+    case PROBABILITY_75:
+      return *ByteVectorOr(GetRandomByteVector(), &bytes);
+    case PROBABILITY_50:
+      return bytes;
+  }
+  NOTREACHED();

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

This error probably needs to be detected in release builds also.

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

This should be prevented by compiler errors due to missing enum values/invalid
conversions.

If we remove the PROBABILITY_50 case:
../../components/rappor/byte_vector_utils.cc:59:10: error: enumeration value
‘PROBABILITY_50’ not handled in switch [-Werror=switch]

If we tried to pass a number directly like GetWeightedRandomByteVector(3)
../../components/rappor/byte_vector_utils_unittest.cc:34:65: error: invalid
conversion from ‘int’ to ‘rappor::Probability’ [-fpermissive]

+  return bytes;
+}
+
+HmacByteVectorGenerator::HmacByteVectorGenerator(size_t byte_count,
+                                                 const std::string& secret)
+    : ByteVectorGenerator(byte_count),
+      hmac_(crypto::HMAC::SHA256),
+      value_(hmac_.DigestLength(), 0x01),
+      requested_bytes_(0) {
+  // HMAC_DRBG Instantiate Process
+  // 2. Key = 0x00 00...00
+  // 3. V = 0x01 01...01
+  ByteVector key(hmac_.DigestLength(), 0x00);
+  std::string initial_value(value_.begin(), value_.end());
+
+  // 4. (Key, V) = HMAC_DRBG_Update(seed_material, Key, V)
+  // HMAC_DRBG Update Process inlined
+  // 1. K = HMAC(K, V || 0x00 || provided_data)
+  crypto::HMAC keygen_hmac(crypto::HMAC::SHA256);
+  if (!keygen_hmac.Init(std::string(key.begin(), key.end())))
+    NOTREACHED();
+  if (!keygen_hmac.Sign(initial_value + char(0x00) + secret,
+      key.data(), key.size()))
+    NOTREACHED();
+  // 2. V = HMAC(K, V)
+  if (!hmac_.Init(std::string(key.begin(), key.end())))
+    NOTREACHED();
+  if (!hmac_.Sign(initial_value, value_.data(), value_.size()))
+    NOTREACHED();
+}
+
+HmacByteVectorGenerator::~HmacByteVectorGenerator() {}
+
+uint8_t HmacByteVectorGenerator::RandByte() {
+  size_t requested_byte_in_digest = requested_bytes_ % hmac_.DigestLength();
+  if (requested_byte_in_digest == 0) {
+    // Do step 4.1 of the HMAC_DRBG Generate Process for more bits.
+    // V = HMAC(Key, V)
+    if(!hmac_.Sign(std::string(value_.begin(), value_.end()),
+        value_.data(), value_.size()))
+      NOTREACHED();
+  }
+  uint8_t result = value_[requested_byte_in_digest];
+  requested_bytes_++;
+  // Check max_number_of_bits_per_request from 10.1 Table 2
+  // max_number_of_bits_per_request == 2^19 bits == 2^16 bytes
+  DCHECK_LT(requested_bytes_, 1U << 16);
+  return result;
+}
+
+}  // namespace rappor