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..17783960c1d08aef255c3dad986303e1ee3081fc
--- /dev/null
+++ b/components/rappor/byte_vector_utils.cc
@@ -0,0 +1,112 @@
+// Copyright (c) 2013 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/hmac.h"

[Ilya Sherman, 2014/01/10 11:00:32]

nit: This is already included in the header file.

[Steven Holte, 2014/01/14 00:47:54]

Done.

+#include "crypto/random.h"
+
+namespace rappor {
+
+// Computes a bitwise and of byte vectors and stores the result in rhs.

[Ilya Sherman, 2014/01/10 11:00:32]

nit: "bitwise and" -> "bitwise AND", though there's really no need to duplicate
this comment from the header file.  Ditto below.

[Steven Holte, 2014/01/14 00:47:54]

Done.

+ByteVector* ByteVectorAnd(const ByteVector& lhs, ByteVector* rhs) {
+  DCHECK_EQ(lhs.size(), rhs->size());
+  for (size_t i = 0, len = lhs.size(); i < len; i++) {

[Ilya Sherman, 2014/01/10 11:00:32]

nit: i++ -> ++i (applies throughout)

[Steven Holte, 2014/01/14 00:47:54]

Done.

+    (*rhs)[i] = lhs[i] & (*rhs)[i];
+  }
+  return rhs;
+}
+
+// Computes a bitwise or of byte vectors and stores the result in rhs.
+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;
+}
+
+ByteVectorGenerator::ByteVectorGenerator(size_t byte_count)
+    : byte_count_(byte_count) {}
+
+ByteVectorGenerator::~ByteVectorGenerator() {}
+
+uint8_t ByteVectorGenerator::RandByte() {
+  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_87_5:
+      return *ByteVectorOr(GetRandomByteVector(),
+                           ByteVectorOr(GetRandomByteVector(), &bytes));

[Ilya Sherman, 2014/01/10 11:00:32]

Hmm, this seems a little bit inefficient.  If the inefficiency is (arguably)
necessary, please document why this approach is used rather than something more
direct like flipping a biased coin for each bit.

[Steven Holte, 2014/01/15 04:53:44]

I'm not sure really what the more efficient way would be, or how I would flip
biased coins directly.  I've dropped the implementation of the probabilities
other than 75 and 50, because they aren't currently used anyway.

+    case PROBABILITY_75:
+      return *ByteVectorOr(GetRandomByteVector(), &bytes);
+    case PROBABILITY_50:
+      return bytes;
+    case PROBABILITY_25:
+      return *ByteVectorAnd(GetRandomByteVector(), &bytes);
+    case PROBABILITY_12_5:
+      return *ByteVectorAnd(GetRandomByteVector(),
+                            ByteVectorAnd(GetRandomByteVector(), &bytes));
+    default:
+      // Invalid probability for coin flips
+      NOTREACHED();

[Ilya Sherman, 2014/01/10 11:00:32]

nit: Are there any other values in the enum?  Can the default statement be
removed so that the compiler can enforce that all cases are covered?

[Steven Holte, 2014/01/14 00:47:54]

Done.

+  }
+  return bytes;
+}
+
+HmacByteVectorGenerator::HmacByteVectorGenerator(size_t byte_count,
+                                                 const std::string& secret)
+    : ByteVectorGenerator(byte_count), hmac_(crypto::HMAC::SHA256) {

[Ilya Sherman, 2014/01/10 11:00:32]

nit: The hmac_ initialization should be wrapped to the next line (one field per
line if any wrapping at all is necessary).

[Steven Holte, 2014/01/14 00:47:54]

Done.

+  // A completely arbitrary value for the initial value of an
+  // HmacByteVectorGenerator's state. The initial digits of pi.
+  const uint64_t kHmacInitialState = 3141592653589793;

[Ilya Sherman, 2014/01/10 11:00:32]

What's the advantage of having this be a constant rather than a random number? 
Also, if an arbitrary constant suffices, why not just pick 0?

[Steven Holte, 2014/01/15 04:53:44]

Basically, we don't want to use 0 just in case it has some exploitable property.
 We can't use a runtime-random number, since it needs to be deterministic, so a
random-ish number is a compromise.

+
+  if (!hmac_.Init(secret))
+    NOTREACHED();
+
+  DCHECK(hmac_.DigestLength() > sizeof(uint64_t));

[Ilya Sherman, 2014/01/10 11:00:32]

Why do you use uint64_t here, but uint8_t below?

[Steven Holte, 2014/01/14 00:47:54]

Done.

+  hmac_state_ = kHmacInitialState;

[Ilya Sherman, 2014/01/10 11:00:32]

nit: Why isn't this set as part of the initializer list?

[Steven Holte, 2014/01/15 04:53:44]

It seems more clear to put the constant in a local scope.

+}
+
+HmacByteVectorGenerator::~HmacByteVectorGenerator() {}
+
+uint8_t HmacByteVectorGenerator::RandByte() {
+  uint8_t random_bits;
+  std::string state = base::Uint64ToString(hmac_state_);
+  if (!hmac_.Sign(state, &random_bits, sizeof(uint8_t)))
+    NOTREACHED();
+
+  ++hmac_state_;
+  return random_bits;
+}
+
+}  // namespace rappor