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..ea72911f320b4bfbc379428516ab6126e2141d27
--- /dev/null
+++ b/components/rappor/byte_vector_utils.cc
@@ -0,0 +1,175 @@
+// 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/rand_util.h"
+#include "base/strings/string_number_conversions.h"
+#include "crypto/random.h"
+
+namespace rappor {
+
+namespace {
+
+base::StringPiece ByteVectorToStringPiece(const ByteVector& lhs) {

[Alexei Svitkine (slow), 2014/02/12 22:42:36]

Nit: I'd name this ByteVectorAsStringPiece(), since the string piece is just a
view over the existing byte vector rather than a conversion.

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

nit: Docs.

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

Done.

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

Done.

+  return base::StringPiece(reinterpret_cast<const char *>(&lhs[0]), lhs.size());

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

IMPORTANT: I don't think this is safe, as the byte vector might contain bytes
that evaluate to control characters or to the NUL byte.  I think you need to
actually make a copy, possibly base-64 encoded.

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

It should be perfectly valid for the StringPiece to contain NUL bytes/control
characters.  Since the length in included in the constructor, they shouldn't
terminate the string.

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

Yes, looks like you're right -- I didn't realize that std::strings supported
internal NUL bytes.  That said, I still think the reinterpret_cast is unsafe
(see my comment on the latest patch set, which goes into more detail).

+}
+
+std::string Concat(const ByteVector& value, char c, const std::string& data) {

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

nit: Docs.

+  return std::string(value.begin(), value.end()) + c + data;

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

IMPORTANT: One of the chars you pass to Concat is the Nul character, below. 
Does that really work?  It seems unlikely to do what you want.

[Alexei Svitkine (slow), 2014/02/13 04:22:33]

This CL is using the std::string type (and StringPiece above) as just a
container for arbitrary bytes (non-text data). We do something similar in
MetricsService to store serialized protos (which are also not text). I believe
this is safe to do (see:
http://stackoverflow.com/questions/2845769/can-a-stdstring-contain-embedded-n...)
as long as all the things the things these strings are being passed to don't
expect them to be actual text.

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

Yes, it does.  std::string may contain null characters.

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

Yeah, you guys are right.  My bad.

+}
+
+// K = HMAC(K, data)

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

nit: Please expand the documentation to be written in the form of a sentence or
sentences.

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

Done.

+bool HMAC_Rotate(const crypto::HMAC& hmac,
+                 const std::string& data,
+                 crypto::HMAC* out_hmac) {

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

Optional nit: "out_hmac" -> "result"

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

Done.

+  ByteVector key(hmac.DigestLength());
+  if (!hmac.Sign(data, &key[0], key.size()))
+    return false;
+  return out_hmac->Init(ByteVectorToStringPiece(key));
+}
+
+}  // namespace
+
+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,
+    const std::string& entropy_input,
+    const std::string& personalization_string)
+    : ByteVectorGenerator(byte_count),
+      hmac_(crypto::HMAC::SHA256),
+      value_(hmac_.DigestLength(), 0x01),
+      generated_bytes_(0) {
+  // HMAC_DRBG Instantiate Process
+  // 1. seed_material = entropy_input + nonce + personalization_string
+  // Note: We are using the 8.6.7 interpretation, where the entropy_input and
+  // nonce are acquired at the same time from the same source.
+  DCHECK_EQ(kEntropyInputSize, entropy_input.size());
+  std::string seed_material(entropy_input + personalization_string);
+  // 2. Key = 0x00 00...00
+  ByteVector key(hmac_.DigestLength(), 0x00);
+  // 3. V = 0x01 01...01
+  // (value_ in initializer list)
+
+  // 4. (Key, V) = HMAC_DRBG_Update(seed_material, Key, V)
+  Update(seed_material, key);
+}
+
+HmacByteVectorGenerator::~HmacByteVectorGenerator() {}
+
+const size_t HmacByteVectorGenerator::kEntropyInputSize = (128 / 8) * 3 / 2;

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

Please document what's happening in this computation.  Presumably the constants
+ computation are meant to be clearer than simply using 24, but it's not clear
to me what the semantics of this computation are.

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

Expanded, and also updated security_strength to match the examples from NIST.

+
+// static
+std::string HmacByteVectorGenerator::GenerateEntropyInput() {
+  return base::RandBytesAsString(kEntropyInputSize);
+}
+
+void HmacByteVectorGenerator::Update(const std::string& provided_data,
+                                     const ByteVector& key1) {
+  // HMAC_DRBG Update Process

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

It seems wrong for you to need to implement this within the rappor component.  I
would think this makes more sense in the crypto component.  Have you considered
moving the logic to there?

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

The logic in this method is not obviously correct to me, because I'm not super
familiar with HMACs.  I think that means it's a good idea to provide additional
documentation here, most likely in the form of a link to the algorithm
description that this is implementing.

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

This was discussed a bit earlier.  This isn't a general implementation of
HMAC_DRBG, so we don't want to encourage other components to start using it.

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

There is a link in the header file, along with some additional explanation of
the assumptions this is implemented with.

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

Please re-link to it in the implementation file, as that's where the intricate
logic is.

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

Added in several comments.

+  crypto::HMAC hmac1(crypto::HMAC::SHA256);
+  crypto::HMAC hmac2(crypto::HMAC::SHA256);
+  if (!hmac1.Init(ByteVectorToStringPiece(key1)))
+    NOTREACHED();
+  // 1. K = HMAC(K, V || 0x00 || provided_data)
+  if (!HMAC_Rotate(hmac1, Concat(value_, 0x00, provided_data), &hmac2))
+    NOTREACHED();
+  // 2. V = HMAC(K, V)
+  if (!hmac2.Sign(ByteVectorToStringPiece(value_), &value_[0], value_.size()))
+    NOTREACHED();
+  // 3. If (provided_data = Null), then return K and V.

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

This comment doesn't seem to match the code.

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

Added a comment to the fact that we are ignoring the NULL case explicitly.

+  DCHECK_GE(provided_data.size(), kEntropyInputSize);
+  // 4. K = HMAC(K, V || 0x01 || provided_data)
+  if (!HMAC_Rotate(hmac2, Concat(value_, 0x01, provided_data), &hmac_))
+    NOTREACHED();
+  // 5. V = HMAC(K, V)
+  if (!hmac_.Sign(ByteVectorToStringPiece(value_), &value_[0], value_.size()))
+    NOTREACHED();
+}
+
+ByteVector HmacByteVectorGenerator::GetRandomByteVector() {
+  const size_t digest_length = hmac_.DigestLength();

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

Is this expected to be equal to the size of |value_|?  If so, it would be nice
to DCHECK that.  If not, I'm not sure how line 164 is guaranteed to be safe.

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

Added DCHECK

+  ByteVector bytes(byte_count_);
+  uint8_t* data = &bytes[0];
+  size_t bytes_to_go = byte_count_;
+  while (bytes_to_go > 0) {
+    size_t requested_byte_in_digest = generated_bytes_ % digest_length;
+    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(ByteVectorToStringPiece(value_),
+                      &value_[0], value_.size())) {
+        NOTREACHED();
+      }
+    }
+    size_t n = std::min(bytes_to_go,
+                        digest_length - requested_byte_in_digest);
+    memcpy(data, &value_[requested_byte_in_digest], n);
+    data += n;
+    bytes_to_go -= n;
+    generated_bytes_ += n;
+    // Check max_number_of_bits_per_request from 10.1 Table 2

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

nit: Please provide a link to the reference that contains 10.1 Table 2.

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

See class declaration in header file.

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

Please include the link at each relevant location.  Someone reading through this
file a year from now won't necessarily know to look in the header file for the
reference.

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

Done.

+    // max_number_of_bits_per_request == 2^19 bits == 2^16 bytes
+    DCHECK_LT(generated_bytes_, 1U << 16);
+  }
+  return bytes;
+}
+
+}  // namespace rappor