RAPPOR implementation

components/rappor/byte_vector_utils_unittest.cc

Index: components/rappor/byte_vector_utils_unittest.cc
diff --git a/components/rappor/byte_vector_utils_unittest.cc b/components/rappor/byte_vector_utils_unittest.cc
new file mode 100644
index 0000000000000000000000000000000000000000..c0dc831d017b56e443145e00b8cab2f55898dcf4
--- /dev/null
+++ b/components/rappor/byte_vector_utils_unittest.cc
@@ -0,0 +1,89 @@
+// 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 "base/rand_util.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace rappor {
+
+TEST(ByteVectorTest, ByteVectorOr) {
+  ByteVector lhs(2);
+  lhs[1] = 0x12;
+  ByteVector rhs(2);
+  rhs[1] = 0x03;
+
+  EXPECT_EQ(0x13, (*ByteVectorOr(lhs, &rhs))[1]);
+}
+
+TEST(ByteVectorTest, ByteVectorMerge) {
+  ByteVector lhs(2);
+  lhs[1] = 0x33;
+  ByteVector rhs(2);
+  rhs[1] = 0x55;
+  ByteVector mask(2);
+  mask[1] = 0x0f;
+
+  EXPECT_EQ(0x35, (*ByteVectorMerge(mask, lhs, &rhs))[1]);
+}
+
+TEST(ByteVectorTest, ByteVectorGenerator) {
+  ByteVectorGenerator generator(2u);
+  ByteVector random_50 = generator.GetWeightedRandomByteVector(PROBABILITY_50);
+  EXPECT_EQ(random_50.size(), 2u);
+  ByteVector random_75 = generator.GetWeightedRandomByteVector(PROBABILITY_75);
+  EXPECT_EQ(random_75.size(), 2u);
+}
+
+TEST(ByteVectorTest, HmacByteVectorGenerator) {
+  HmacByteVectorGenerator generator(1u,
+      std::string(HmacByteVectorGenerator::kEntropyInputSize, 0x00), "");
+  ByteVector random_50 = generator.GetWeightedRandomByteVector(PROBABILITY_50);
+  EXPECT_EQ(random_50.size(), 1u);
+  EXPECT_EQ(random_50[0], 0x26);
+  ByteVector random_75 = generator.GetWeightedRandomByteVector(PROBABILITY_75);
+  EXPECT_EQ(random_75.size(), 1u);
+  EXPECT_EQ(random_75[0], 0xdf);
+}
+
+TEST(ByteVectorTest, WeightedRandomStatistics50) {
+  ByteVectorGenerator generator(50u);
+  ByteVector random = generator.GetWeightedRandomByteVector(PROBABILITY_50);
+  int bit_count = CountBits(random);
+  // Check bounds on bit counts that are true with 99.999% probability.
+  EXPECT_GT(bit_count, 155); // Binomial(400, .5) CDF(155) ~= 0.000004
+  EXPECT_LE(bit_count, 244); // Binomial(400, .5) CDF(244) ~= 0.999996
+}
+
+TEST(ByteVectorTest, WeightedRandomStatistics75) {
+  ByteVectorGenerator generator(50u);
+  ByteVector random = generator.GetWeightedRandomByteVector(PROBABILITY_75);
+  int bit_count = CountBits(random);
+  // Check bounds on bit counts that are true with 99.999% probability.
+  EXPECT_GT(bit_count, 259); // Binomial(400, .75) CDF(259) ~= 0.000003
+  EXPECT_LE(bit_count, 337); // Binomial(400, .75) CDF(337) ~= 0.999997
+}
+
+TEST(ByteVectorTest, HmacWeightedRandomStatistics50) {
+  HmacByteVectorGenerator generator(50u,
+      HmacByteVectorGenerator::GenerateEntropyInput(), "");
+  ByteVector random = generator.GetWeightedRandomByteVector(PROBABILITY_50);
+  int bit_count = CountBits(random);
+  // Check bounds on bit counts that are true with 99.999% probability.
+  EXPECT_GT(bit_count, 155); // Binomial(400, .5) CDF(155) ~= 0.000004
+  EXPECT_LE(bit_count, 244); // Binomial(400, .5) CDF(244) ~= 0.999996
+}
+
+TEST(ByteVectorTest, HmacWeightedRandomStatistics75) {
+  HmacByteVectorGenerator generator(50u,
+      HmacByteVectorGenerator::GenerateEntropyInput(), "");
+  ByteVector random = generator.GetWeightedRandomByteVector(PROBABILITY_75);
+  int bit_count = CountBits(random);
+  // Check bounds on bit counts that are true with 99.999% probability.
+  EXPECT_GT(bit_count, 259); // Binomial(400, .75) CDF(259) ~= 0.000003
+  EXPECT_LE(bit_count, 337); // Binomial(400, .75) CDF(337) ~= 0.999997
+}
+

[edknapp, 2014/02/12 23:09:17]

Could you include the relevant sample test vectors from
http://csrc.nist.gov/groups/STM/cavp/

[Steven Holte, 2014/02/13 21:13:45]

As Ed discovered in another thread, the test vectors NIST provides are generated
from the second request.  Since this HMAC_DRBG implementation only supports one
request, testing against those vectors is a bit problematic.  To mitigate this a
bit, I've modified the code to make the Update function more reusable and moved
it into the anonymous namespace as HMAC_DRBG_Update().

Then I did some manual testing by applying this patch, which makes the
constructor generate and discard a first request, and streams output from the
second, and then tests that against an NIST vector, and the test passed.  Not
sure what a better way to support this kind of testing would be.

diff --git a/components/rappor/byte_vector_utils.cc
b/components/rappor/byte_vector_utils.cc
index 7fb5554..e0571b9 100644
--- a/components/rappor/byte_vector_utils.cc
+++ b/components/rappor/byte_vector_utils.cc
@@ -153,7 +153,18 @@ HmacByteVectorGenerator::HmacByteVectorGenerator(
   // (value_ in initializer list)
 
   // 4. (Key, V) = HMAC_DRBG_Update(seed_material, Key, V)
-  if (!HMAC_DRBG_Update(seed_material, hmac1, &value_, &hmac_))
+  crypto::HMAC hmacZ(crypto::HMAC::SHA256);
+  if (!HMAC_DRBG_Update(seed_material, hmac1, &value_, &hmacZ))
+    NOTREACHED();
+  if (!HMAC_Rehash(hmacZ, &value_))
+    NOTREACHED();
+  if (!HMAC_Rehash(hmacZ, &value_))
+    NOTREACHED();
+  if (!HMAC_Rehash(hmacZ, &value_))
+    NOTREACHED();
+  if (!HMAC_Rehash(hmacZ, &value_))
+    NOTREACHED();
+  if (!HMAC_DRBG_Update("", hmacZ, &value_, &hmac_))
     NOTREACHED();
 }
 
diff --git a/components/rappor/byte_vector_utils_unittest.cc
b/components/rappor/byte_vector_utils_unittest.cc
index cb55317..4e3474b 100644
--- a/components/rappor/byte_vector_utils_unittest.cc
+++ b/components/rappor/byte_vector_utils_unittest.cc
@@ -5,6 +5,7 @@
 #include "components/rappor/byte_vector_utils.h"
 
 #include "base/rand_util.h"
+#include "base/strings/string_number_conversions.h"
 #include "testing/gtest/include/gtest/gtest.h"
 
 namespace rappor {
@@ -37,6 +38,16 @@ TEST(ByteVectorTest, ByteVectorGenerator) {
   EXPECT_EQ(random_75.size(), 2u);
 }
 
+const char entropy[] =
"ca851911349384bffe89de1cbdc46e6831e44d34a4fb935ee285dd14b71a7488";
+const char nonce[] = "659ba96c601dc69fc902940805ec0ca8";
+const char expected[] =
"e528e9abf2dece54d47c7e75e5fe302149f817ea9fb4bee6f4199697d04d5b89d54fbb978a15b5c443c9ec21036d2460b6f73ebad0dc2aba6e624abf07745bc107694bb7547bb0995f70de25d6b29e2d3011bb19d27676c07162c8b5ccde0668961df86803482cb37ed6d5c0bb8d50cf1f50d476aa0458bdaba806f48be9dcb8";
+
+std::string HexToString(const char* hex) {
+  ByteVector bv;
+  base::HexStringToBytes(hex, &bv);
+  return std::string(bv.begin(), bv.end());
+}
+
 TEST(ByteVectorTest, HmacByteVectorGenerator) {
   HmacByteVectorGenerator generator(1u,
       std::string(HmacByteVectorGenerator::kEntropyInputSize, 0x00), "");
@@ -48,6 +59,15 @@ TEST(ByteVectorTest, HmacByteVectorGenerator) {
   EXPECT_EQ(random_75[0], 0xdf);
 }
 
+TEST(ByteVectorTest, HmacNist) {
+  std::string entropy_input = HexToString(entropy) + HexToString(nonce);
+  HmacByteVectorGenerator generator(1024u / 8, entropy_input, "");
+  ByteVector random_50 = generator.GetWeightedRandomByteVector(PROBABILITY_50);
+
+  EXPECT_EQ(HexToString(expected),
+      std::string(random_50.begin(), random_50.end()));
+}
+
 TEST(ByteVectorTest, WeightedRandomStatistics50) {
   ByteVectorGenerator generator(50u);
   ByteVector random = generator.GetWeightedRandomByteVector(PROBABILITY_50);

[Alexei Svitkine (slow), 2014/02/13 21:25:39]

If you need to test a function that's in the anon namespace, one way you can do
this is to put it inside an "internal" namespace and declare it in the header.
So then the test code can still access it for testing.

For example:

https://code.google.com/p/chromium/codesearch#chromium/src/components/variati...

[edknapp, 2014/02/13 21:55:41]

What do you think of having each call to our GetRandomByteVector() correspond to
a call to the standard's HMAC_DRBG_Generate_algorithm? 

On 2014/02/13 21:13:45, Steven Holte wrote:

[Steven Holte, 2014/02/13 22:01:54]

Actually, after thinking about it a bit more, I figured out a reasonable way of
supporting the second request by adding a second constructor.  Since that's not
our normal behaviour, I've made that protected, but it does allow running
against the NIST vectors in tests.

+}  // namespace rappor