components/rappor/byte_vector_utils.cc

   1 // Copyright 2014 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "components/rappor/byte_vector_utils.h"
   6
   7 #include <string>
   8
   9 #include "base/logging.h"
  10 #include "base/rand_util.h"
  11 #include "base/strings/string_number_conversions.h"
  12 #include "crypto/random.h"
  13
  14 namespace rappor {
  15
  16 namespace {
  17
  18 // Reinterpets a ByteVector as a StringPiece.
  19 base::StringPiece ByteVectorAsStringPiece(const ByteVector& lhs) {
  20   return base::StringPiece(reinterpret_cast<const char *>(&lhs[0]), lhs.size());
  21 }
  22
  23 // Concatenates parameters together as a string.
  24 std::string Concat(const ByteVector& value, char c, const std::string& data) {
  25   return std::string(value.begin(), value.end()) + c + data;
  26 }
  27
  28 // Performs the operation: K = HMAC(K, data)
  29 // The input "K" is passed by initializing |hmac| with it.
  30 // The output "K" is returned by initializing |result| with it.
  31 // Returns false on an error.
  32 bool HMAC_Rotate(const crypto::HMAC& hmac,
  33                  const std::string& data,
  34                  crypto::HMAC* result) {
  35   ByteVector key(hmac.DigestLength());
  36   if (!hmac.Sign(data, &key[0], key.size()))
  37     return false;
  38   return result->Init(ByteVectorAsStringPiece(key));
  39 }
  40
  41 // Performs the operation: V = HMAC(K, V)
  42 // The input "K" is passed by initializing |hmac| with it.
  43 // "V" is read from and written to |value|.
  44 // Returns false on an error.
  45 bool HMAC_Rehash(const crypto::HMAC& hmac, ByteVector* value) {
  46   return hmac.Sign(ByteVectorAsStringPiece(*value),
  47                    &(*value)[0], value->size());
  48 }
  49
  50 // Implements (Key, V) = HMAC_DRBG_Update(provided_data, Key, V)
  51 // See: http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf
  52 // "V" is read from and written to |value|.
  53 // The input "Key" is passed by initializing |hmac1| with it.
  54 // The output "Key" is returned by initializing |out_hmac| with it.
  55 // Returns false on an error.
  56 bool HMAC_DRBG_Update(const std::string& provided_data,
  57                       const crypto::HMAC& hmac1,
  58                       ByteVector* value,
  59                       crypto::HMAC* out_hmac) {
  60   // HMAC_DRBG Update Process
  61   crypto::HMAC temp_hmac(crypto::HMAC::SHA256);
  62   crypto::HMAC* hmac2 = provided_data.size() > 0 ? &temp_hmac : out_hmac;
  63   // 1. K = HMAC(K, V || 0x00 || provided_data)
  64   if (!HMAC_Rotate(hmac1, Concat(*value, 0x00, provided_data), hmac2))
  65     return false;
  66   // 2. V = HMAC(K, V)
  67   if (!HMAC_Rehash(*hmac2, value))
  68     return false;
  69   // 3. If (provided_data = Null), then return K and V.
  70   if (hmac2 == out_hmac)
  71     return true;
  72   // 4. K = HMAC(K, V || 0x01 || provided_data)
  73   if (!HMAC_Rotate(*hmac2, Concat(*value, 0x01, provided_data), out_hmac))
  74     return false;
  75   // 5. V = HMAC(K, V)
  76   return HMAC_Rehash(*out_hmac, value);
  77 }
  78
  79 }  // namespace
  80
  81 void Uint64ToByteVector(uint64_t value, size_t size, ByteVector* output) {
  82   DCHECK_LE(size, 8u);
  83   DCHECK_EQ(size, output->size());
  84   for (size_t i = 0; i < size; i++) {
  85     // Get the value of the i-th smallest byte and copy it to the byte vector.
  86     uint64_t shift = i * 8;
  87     uint64_t byte_mask = static_cast<uint64_t>(0xff) << shift;
  88     (*output)[i] = (value & byte_mask) >> shift;
  89   }
  90 }
  91
  92 ByteVector* ByteVectorAnd(const ByteVector& lhs, ByteVector* rhs) {
  93   DCHECK_EQ(lhs.size(), rhs->size());
  94   for (size_t i = 0; i < lhs.size(); ++i) {
  95     (*rhs)[i] = lhs[i] & (*rhs)[i];
  96   }
  97   return rhs;
  98 }
  99
 100 ByteVector* ByteVectorOr(const ByteVector& lhs, ByteVector* rhs) {
 101   DCHECK_EQ(lhs.size(), rhs->size());
 102   for (size_t i = 0; i < lhs.size(); ++i) {
 103     (*rhs)[i] = lhs[i] | (*rhs)[i];
 104   }
 105   return rhs;
 106 }
 107
 108 ByteVector* ByteVectorMerge(const ByteVector& mask,
 109                             const ByteVector& lhs,
 110                             ByteVector* rhs) {
 111   DCHECK_EQ(lhs.size(), rhs->size());
 112   for (size_t i = 0; i < lhs.size(); ++i) {
 113     (*rhs)[i] = (lhs[i] & ~mask[i]) | ((*rhs)[i] & mask[i]);
 114   }
 115   return rhs;
 116 }
 117
 118 int CountBits(const ByteVector& vector) {
 119   int bit_count = 0;
 120   for (size_t i = 0; i < vector.size(); ++i) {
 121     uint8_t byte = vector[i];
 122     for (int j = 0; j < 8 ; ++j) {
 123       if (byte & (1 << j))
 124         bit_count++;
 125     }
 126   }
 127   return bit_count;
 128 }
 129
 130 ByteVectorGenerator::ByteVectorGenerator(size_t byte_count)
 131     : byte_count_(byte_count) {}
 132
 133 ByteVectorGenerator::~ByteVectorGenerator() {}
 134
 135 ByteVector ByteVectorGenerator::GetRandomByteVector() {
 136   ByteVector bytes(byte_count_);
 137   crypto::RandBytes(&bytes[0], bytes.size());
 138   return bytes;
 139 }
 140
 141 ByteVector ByteVectorGenerator::GetWeightedRandomByteVector(
 142     Probability probability) {
 143   ByteVector bytes = GetRandomByteVector();
 144   switch (probability) {
 145     case PROBABILITY_75:
 146       return *ByteVectorOr(GetRandomByteVector(), &bytes);
 147     case PROBABILITY_50:
 148       return bytes;
 149     case PROBABILITY_25:
 150       return *ByteVectorAnd(GetRandomByteVector(), &bytes);
 151   }
 152   NOTREACHED();
 153   return bytes;
 154 }
 155
 156 HmacByteVectorGenerator::HmacByteVectorGenerator(
 157     size_t byte_count,
 158     const std::string& entropy_input,
 159     const std::string& personalization_string)
 160     : ByteVectorGenerator(byte_count),
 161       hmac_(crypto::HMAC::SHA256),
 162       value_(hmac_.DigestLength(), 0x01),
 163       generated_bytes_(0) {
 164   // HMAC_DRBG Instantiate Process
 165   // See: http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf
 166   // 1. seed_material = entropy_input + nonce + personalization_string
 167   // Note: We are using the 8.6.7 interpretation, where the entropy_input and
 168   // nonce are acquired at the same time from the same source.
 169   DCHECK_EQ(kEntropyInputSize, entropy_input.size());
 170   std::string seed_material(entropy_input + personalization_string);
 171   // 2. Key = 0x00 00...00
 172   crypto::HMAC hmac1(crypto::HMAC::SHA256);
 173   if (!hmac1.Init(std::string(hmac_.DigestLength(), 0x00)))
 174     NOTREACHED();
 175   // 3. V = 0x01 01...01
 176   // (value_ in initializer list)
 177
 178   // 4. (Key, V) = HMAC_DRBG_Update(seed_material, Key, V)
 179   if (!HMAC_DRBG_Update(seed_material, hmac1, &value_, &hmac_))
 180     NOTREACHED();
 181 }
 182
 183 HmacByteVectorGenerator::~HmacByteVectorGenerator() {}
 184
 185 HmacByteVectorGenerator::HmacByteVectorGenerator(
 186     const HmacByteVectorGenerator& prev_request)
 187     : ByteVectorGenerator(prev_request.byte_count()),
 188       hmac_(crypto::HMAC::SHA256),
 189       value_(prev_request.value_),
 190       generated_bytes_(0) {
 191   if (!HMAC_DRBG_Update("", prev_request.hmac_, &value_, &hmac_))
 192     NOTREACHED();
 193 }
 194
 195 // HMAC_DRBG requires entropy input to be security_strength bits long,
 196 // and nonce to be at least 1/2 security_strength bits long.  We
 197 // generate them both as a single "extra strong" entropy input.
 198 // max_security_strength for SHA256 is 256 bits.
 199 // See: http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf
 200 const size_t HmacByteVectorGenerator::kEntropyInputSize = (256 / 8) * 3 / 2;
 201
 202 // static
 203 std::string HmacByteVectorGenerator::GenerateEntropyInput() {
 204   return base::RandBytesAsString(kEntropyInputSize);
 205 }
 206
 207 ByteVector HmacByteVectorGenerator::GetRandomByteVector() {
 208   // Streams bytes from HMAC_DRBG_Generate
 209   // See: http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf
 210   const size_t digest_length = hmac_.DigestLength();
 211   DCHECK_EQ(value_.size(), digest_length);
 212   ByteVector bytes(byte_count());
 213   uint8_t* data = &bytes[0];
 214   size_t bytes_to_go = byte_count();
 215   while (bytes_to_go > 0) {
 216     size_t requested_byte_in_digest = generated_bytes_ % digest_length;
 217     if (requested_byte_in_digest == 0) {
 218       // Do step 4.1 of the HMAC_DRBG Generate Process for more bits.
 219       // V = HMAC(Key, V)
 220       if (!HMAC_Rehash(hmac_, &value_))
 221         NOTREACHED();
 222     }
 223     size_t n = std::min(bytes_to_go,
 224                         digest_length - requested_byte_in_digest);
 225     memcpy(data, &value_[requested_byte_in_digest], n);
 226     data += n;
 227     bytes_to_go -= n;
 228     generated_bytes_ += n;
 229     // Check max_number_of_bits_per_request from 10.1 Table 2
 230     // max_number_of_bits_per_request == 2^19 bits == 2^16 bytes
 231     DCHECK_LT(generated_bytes_, 1U << 16);
 232   }
 233   return bytes;
 234 }
 235
 236 }  // namespace rappor