RAPPOR implementation

components/rappor/byte_vector_utils.cc

+// 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());
+}
+
+// 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)
+// See: http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf
+// "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
+  // See: http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf
+  // 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.
+// See: http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf
+const size_t HmacByteVectorGenerator::kEntropyInputSize = (256 / 8) * 3 / 2;
+
+// static
+std::string HmacByteVectorGenerator::GenerateEntropyInput() {
+  return base::RandBytesAsString(kEntropyInputSize);
+}
+
+ByteVector HmacByteVectorGenerator::GetRandomByteVector() {
+  // Streams bytes from HMAC_DRBG_Generate
+  // See: http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf
+  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