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..1b540bf23d92ed87ad9e27a0fea604f780037e55
--- /dev/null
+++ b/components/rappor/byte_vector_utils.cc
@@ -0,0 +1,210 @@
+// 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 {
+
+// Reinterpets a ByteVector as a StringPiece.
+base::StringPiece ByteVectorAsStringPiece(const ByteVector& lhs) {
+  return base::StringPiece(reinterpret_cast<const char *>(&lhs[0]), lhs.size());

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

So, reinterpret_cast is generally not safe.  The only guarantee is that if you
reinterpret_cast from type A to type B and then back to type A again, you get
the same result as you started with.  The state after casting to type B is
undefined.

In contrast, I think the explicit call to the std::string constructor on line 25
is safe.  Can you use a similar safe pattern here as well?  (FWIW, I think that
std::string safely implicitly converts to base::StringPiece -- in fact, I think
that's the whole point of base::StringPiece -- so you can safely return an
std::string from this method rather than a base::StringPiece.)

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

The whole point of making this function was to avoid the extra copy involved
when creating a std::string, w.  From a practical standpoint, I think
reinterpeting an unsigned char* to a signed char* is pretty safe.  According to
http://stackoverflow.com/questions/15078638/can-i-turn-unsigned-char-into-cha...
the standard says that this doesn't violate strict-aliasing rules, but we aren't
gauranteed about the interpretation of the value being the "same".  If this
actually occurred, we should get test failures, at least from the
HmacByteVectorGenerator and HmacNist tests.

[Ilya Sherman, 2014/02/14 05:23:09]

Hmm, alright, I'm convinced.  Seems I need to brush up on my C++ miscellany :)

+}
+
+// Concatenates parameters together as a string.
+std::string Concat(const ByteVector& value, char c, const std::string& data) {
+  return std::string(value.begin(), value.end()) + c + data;
+}
+
+// Performs the operation: K = HMAC(K, data)
+// The input "K" is passed by initializing |hmac| with it.
+// The output "K" is returned by initializing |result| with it.
+// Returns false on an error.
+bool HMAC_Rotate(const crypto::HMAC& hmac,
+                 const std::string& data,
+                 crypto::HMAC* result) {
+  ByteVector key(hmac.DigestLength());
+  if (!hmac.Sign(data, &key[0], key.size()))
+    return false;
+  return result->Init(ByteVectorAsStringPiece(key));
+}
+
+// Performs the operation: V = HMAC(K, V)
+// The input "K" is passed by initializing |hmac| with it.
+// "V" is read from and written to |value|.
+// Returns false on an error.
+bool HMAC_Rehash(const crypto::HMAC& hmac, ByteVector* value) {
+  return hmac.Sign(ByteVectorAsStringPiece(*value),
+                   &(*value)[0], value->size());
+}
+
+// Implements (Key, V) = HMAC_DRBG_Update(provided_data, Key, V)
+// "V" is read from and written to |value|.
+// The input "Key" is passed by initializing |hmac1| with it.
+// The output "Key" is returned by initializing |out_hmac| with it.
+// Returns false on an error.
+bool HMAC_DRBG_Update(const std::string& provided_data,
+                      const crypto::HMAC& hmac1,
+                      ByteVector* value,
+                      crypto::HMAC* out_hmac) {
+  // HMAC_DRBG Update Process
+  crypto::HMAC temp_hmac(crypto::HMAC::SHA256);
+  crypto::HMAC* hmac2 = provided_data.size() > 0 ? &temp_hmac : out_hmac;
+  // 1. K = HMAC(K, V || 0x00 || provided_data)
+  if (!HMAC_Rotate(hmac1, Concat(*value, 0x00, provided_data), hmac2))
+    return false;
+  // 2. V = HMAC(K, V)
+  if (!HMAC_Rehash(*hmac2, value))
+    return false;
+  // 3. If (provided_data = Null), then return K and V.
+  if (hmac2 == out_hmac)
+    return true;
+  // 4. K = HMAC(K, V || 0x01 || provided_data)
+  if (!HMAC_Rotate(*hmac2, Concat(*value, 0x01, provided_data), out_hmac))
+    return false;
+  // 5. V = HMAC(K, V)
+  return HMAC_Rehash(*out_hmac, value);
+}
+
+}  // 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
+  crypto::HMAC hmac1(crypto::HMAC::SHA256);
+  if (!hmac1.Init(std::string(hmac_.DigestLength(), 0x00)))
+    NOTREACHED();
+  // 3. V = 0x01 01...01
+  // (value_ in initializer list)
+
+  // 4. (Key, V) = HMAC_DRBG_Update(seed_material, Key, V)
+  if (!HMAC_DRBG_Update(seed_material, hmac1, &value_, &hmac_))
+    NOTREACHED();
+}
+
+HmacByteVectorGenerator::~HmacByteVectorGenerator() {}
+
+HmacByteVectorGenerator::HmacByteVectorGenerator(
+    const HmacByteVectorGenerator& prev_request)
+    : ByteVectorGenerator(prev_request.byte_count()),
+      hmac_(crypto::HMAC::SHA256),
+      value_(prev_request.value_),
+      generated_bytes_(0) {
+  if (!HMAC_DRBG_Update("", prev_request.hmac_, &value_, &hmac_))
+    NOTREACHED();
+}
+
+// HMAC_DRBG requires entropy input to be security_strength bits long,
+// and nonce to be at least 1/2 security_strength bits long.  We
+// generate them both as a single "extra strong" entropy input.
+// max_security_strength for SHA256 is 256 bits.
+const size_t HmacByteVectorGenerator::kEntropyInputSize = (256 / 8) * 3 / 2;
+
+// static
+std::string HmacByteVectorGenerator::GenerateEntropyInput() {
+  return base::RandBytesAsString(kEntropyInputSize);
+}
+
+ByteVector HmacByteVectorGenerator::GetRandomByteVector() {
+  const size_t digest_length = hmac_.DigestLength();
+  DCHECK_EQ(value_.size(), digest_length);
+  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_Rehash(hmac_, &value_))
+        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
+    // max_number_of_bits_per_request == 2^19 bits == 2^16 bytes
+    DCHECK_LT(generated_bytes_, 1U << 16);
+  }
+  return bytes;
+}
+
+}  // namespace rappor