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..4c5400dc315d4f8c60ca3308771aebcfb18eb2d2
--- /dev/null
+++ b/components/rappor/byte_vector_utils.cc
@@ -0,0 +1,125 @@
+// 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) {
+  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() {}
+
+ByteVector ByteVectorGenerator::GetRandomByteVector() {
+  ByteVector bytes(byte_count_);
+  crypto::RandBytes(&bytes[0], bytes.size());
+  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();
+  return bytes;
+}
+
+HmacByteVectorGenerator::HmacByteVectorGenerator(size_t byte_count,

[edknapp, 2014/02/11 17:28:00]

Please pass in entropy_input, nonce, and personalization_string separately. 

[Steven Holte, 2014/02/11 22:08:14]

Separated entropy_input, personalization_string, and referenced the part of
section 8.6.7 that allows acquiring entropy_input and nonce at the same time
from the same source.

+                                                 const std::string& secret)
+    : ByteVectorGenerator(byte_count),
+      hmac_(crypto::HMAC::SHA256),
+      value_(hmac_.DigestLength(), 0x01),
+      requested_bytes_(0) {

[Alexei Svitkine (slow), 2014/02/11 16:59:06]

Why does this need to be a class member, rather than a local var in the function
where it's used?

[wtc, 2014/02/11 20:55:29]

requested_bytes_ is the total number of bytes generated by this object. Although
it is only used in GetRandomByteVector, it needs to be a class member to count
the number of bytes across multiple calls.

[Steven Holte, 2014/02/11 22:08:14]

This is the number of bytes streamed from the HMAC_DRBG Generate process, so
it's cumulative over multiple calls to GetRandomByteVector.

+  // 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

[edknapp, 2014/02/11 17:28:00]

Please move this to a private function:
Update(provided_data)

[Steven Holte, 2014/02/11 22:08:14]

Done.

+  // 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[0], key.size()))

[Alexei Svitkine (slow), 2014/02/11 16:59:06]

Nit: Add {}'s. Align params.

Alternatively, make a local var for "initial_value + char(0x00) + secret" so
that this if fits into one line.

[Steven Holte, 2014/02/11 22:08:14]

Done.

+    NOTREACHED();
+  // 2. V = HMAC(K, V)
+  if (!hmac_.Init(std::string(key.begin(), key.end())))
+    NOTREACHED();
+  if (!hmac_.Sign(initial_value, &value_[0], value_.size()))
+    NOTREACHED();
+}
+
+HmacByteVectorGenerator::~HmacByteVectorGenerator() {}
+
+ByteVector HmacByteVectorGenerator::GetRandomByteVector() {
+  ByteVector bytes(byte_count_);
+  uint8_t* data = bytes.data();
+  size_t bytes_to_go = byte_count_;
+  while (bytes_to_go) {

[Alexei Svitkine (slow), 2014/02/11 16:59:06]

Nit: bytes_to_go > 0

[Steven Holte, 2014/02/11 22:08:14]

Done.

+    size_t requested_byte_in_digest = requested_bytes_ % hmac_.DigestLength();

[Alexei Svitkine (slow), 2014/02/11 16:59:06]

The digest length is constant between iterations, right? If so, I'd cache it in
a variable to avoid calling this every iteration. (You also use it below).

[Steven Holte, 2014/02/11 22:08:14]

Done.

+    if (requested_byte_in_digest == 0) {
+      // Do step 4.1 of the HMAC_DRBG Generate Process for more bits.

[Alexei Svitkine (slow), 2014/02/11 16:59:06]

This function is now pretty complex. Given it's implementing some spec (as far
as I can tell from this comment), are you sure we don't have a library
implementation somewhere that can be re-used?

Or perhaps this should be moved to the HMAC class?

[wtc, 2014/02/11 20:55:29]

I don't know of such a class in the Chromium source tree. The random number
generators in Chromium are all singletons and don't allow the seed to be
specified.
This thought also crossed my mind, but I'm afraid that people (including me)
will be tempted to ask for a more general interface to this class, and that will
make this code review drag on longer.

+      // V = HMAC(Key, V)
+      if (!hmac_.Sign(std::string(value_.begin(), value_.end()),

[Alexei Svitkine (slow), 2014/02/11 16:59:06]

Can the param be a StringPiece rather than a std::string()? That way, there
won't be any copying.. Or is it because you're using |value_| as the output too,
so the copy needs to happen - if so document this with a comment.

[Steven Holte, 2014/02/11 22:08:14]

value_ is a ByteVector, so StringPiece doesn't like it's iterators.

+          &value_[0], value_.size()))

[Alexei Svitkine (slow), 2014/02/11 16:59:06]

Nit: Same comment as above about {}'s and aligning params.

[Steven Holte, 2014/02/11 22:08:14]

Done.

+        NOTREACHED();
+    }
+    size_t n = std::min(bytes_to_go,
+                        hmac_.DigestLength() - requested_byte_in_digest);
+    memcpy(data, &value_[requested_byte_in_digest], n);
+    data += n;
+    bytes_to_go -= n;
+    requested_bytes_ += n;
+    // 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 bytes;
+}
+
+}  // namespace rappor