OLD | NEW |
(Empty) | |
| 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 ByteVector* ByteVectorOr(const ByteVector& lhs, ByteVector* rhs) { |
| 82 DCHECK_EQ(lhs.size(), rhs->size()); |
| 83 for (size_t i = 0, len = lhs.size(); i < len; ++i) { |
| 84 (*rhs)[i] = lhs[i] | (*rhs)[i]; |
| 85 } |
| 86 return rhs; |
| 87 } |
| 88 |
| 89 ByteVector* ByteVectorMerge(const ByteVector& mask, |
| 90 const ByteVector& lhs, |
| 91 ByteVector* rhs) { |
| 92 DCHECK_EQ(lhs.size(), rhs->size()); |
| 93 for (size_t i = 0, len = lhs.size(); i < len; ++i) { |
| 94 (*rhs)[i] = (lhs[i] & ~mask[i]) | ((*rhs)[i] & mask[i]); |
| 95 } |
| 96 return rhs; |
| 97 } |
| 98 |
| 99 int CountBits(const ByteVector& vector) { |
| 100 int bit_count = 0; |
| 101 for (size_t i = 0; i < vector.size(); ++i) { |
| 102 uint8_t byte = vector[i]; |
| 103 for (int j = 0; j < 8 ; ++j) { |
| 104 if (byte & (1 << j)) |
| 105 bit_count++; |
| 106 } |
| 107 } |
| 108 return bit_count; |
| 109 } |
| 110 |
| 111 ByteVectorGenerator::ByteVectorGenerator(size_t byte_count) |
| 112 : byte_count_(byte_count) {} |
| 113 |
| 114 ByteVectorGenerator::~ByteVectorGenerator() {} |
| 115 |
| 116 ByteVector ByteVectorGenerator::GetRandomByteVector() { |
| 117 ByteVector bytes(byte_count_); |
| 118 crypto::RandBytes(&bytes[0], bytes.size()); |
| 119 return bytes; |
| 120 } |
| 121 |
| 122 ByteVector ByteVectorGenerator::GetWeightedRandomByteVector( |
| 123 Probability probability) { |
| 124 ByteVector bytes = GetRandomByteVector(); |
| 125 switch (probability) { |
| 126 case PROBABILITY_75: |
| 127 return *ByteVectorOr(GetRandomByteVector(), &bytes); |
| 128 case PROBABILITY_50: |
| 129 return bytes; |
| 130 } |
| 131 NOTREACHED(); |
| 132 return bytes; |
| 133 } |
| 134 |
| 135 HmacByteVectorGenerator::HmacByteVectorGenerator( |
| 136 size_t byte_count, |
| 137 const std::string& entropy_input, |
| 138 const std::string& personalization_string) |
| 139 : ByteVectorGenerator(byte_count), |
| 140 hmac_(crypto::HMAC::SHA256), |
| 141 value_(hmac_.DigestLength(), 0x01), |
| 142 generated_bytes_(0) { |
| 143 // HMAC_DRBG Instantiate Process |
| 144 // See: http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf |
| 145 // 1. seed_material = entropy_input + nonce + personalization_string |
| 146 // Note: We are using the 8.6.7 interpretation, where the entropy_input and |
| 147 // nonce are acquired at the same time from the same source. |
| 148 DCHECK_EQ(kEntropyInputSize, entropy_input.size()); |
| 149 std::string seed_material(entropy_input + personalization_string); |
| 150 // 2. Key = 0x00 00...00 |
| 151 crypto::HMAC hmac1(crypto::HMAC::SHA256); |
| 152 if (!hmac1.Init(std::string(hmac_.DigestLength(), 0x00))) |
| 153 NOTREACHED(); |
| 154 // 3. V = 0x01 01...01 |
| 155 // (value_ in initializer list) |
| 156 |
| 157 // 4. (Key, V) = HMAC_DRBG_Update(seed_material, Key, V) |
| 158 if (!HMAC_DRBG_Update(seed_material, hmac1, &value_, &hmac_)) |
| 159 NOTREACHED(); |
| 160 } |
| 161 |
| 162 HmacByteVectorGenerator::~HmacByteVectorGenerator() {} |
| 163 |
| 164 HmacByteVectorGenerator::HmacByteVectorGenerator( |
| 165 const HmacByteVectorGenerator& prev_request) |
| 166 : ByteVectorGenerator(prev_request.byte_count()), |
| 167 hmac_(crypto::HMAC::SHA256), |
| 168 value_(prev_request.value_), |
| 169 generated_bytes_(0) { |
| 170 if (!HMAC_DRBG_Update("", prev_request.hmac_, &value_, &hmac_)) |
| 171 NOTREACHED(); |
| 172 } |
| 173 |
| 174 // HMAC_DRBG requires entropy input to be security_strength bits long, |
| 175 // and nonce to be at least 1/2 security_strength bits long. We |
| 176 // generate them both as a single "extra strong" entropy input. |
| 177 // max_security_strength for SHA256 is 256 bits. |
| 178 // See: http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf |
| 179 const size_t HmacByteVectorGenerator::kEntropyInputSize = (256 / 8) * 3 / 2; |
| 180 |
| 181 // static |
| 182 std::string HmacByteVectorGenerator::GenerateEntropyInput() { |
| 183 return base::RandBytesAsString(kEntropyInputSize); |
| 184 } |
| 185 |
| 186 ByteVector HmacByteVectorGenerator::GetRandomByteVector() { |
| 187 // Streams bytes from HMAC_DRBG_Generate |
| 188 // See: http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf |
| 189 const size_t digest_length = hmac_.DigestLength(); |
| 190 DCHECK_EQ(value_.size(), digest_length); |
| 191 ByteVector bytes(byte_count()); |
| 192 uint8_t* data = &bytes[0]; |
| 193 size_t bytes_to_go = byte_count(); |
| 194 while (bytes_to_go > 0) { |
| 195 size_t requested_byte_in_digest = generated_bytes_ % digest_length; |
| 196 if (requested_byte_in_digest == 0) { |
| 197 // Do step 4.1 of the HMAC_DRBG Generate Process for more bits. |
| 198 // V = HMAC(Key, V) |
| 199 if (!HMAC_Rehash(hmac_, &value_)) |
| 200 NOTREACHED(); |
| 201 } |
| 202 size_t n = std::min(bytes_to_go, |
| 203 digest_length - requested_byte_in_digest); |
| 204 memcpy(data, &value_[requested_byte_in_digest], n); |
| 205 data += n; |
| 206 bytes_to_go -= n; |
| 207 generated_bytes_ += n; |
| 208 // Check max_number_of_bits_per_request from 10.1 Table 2 |
| 209 // max_number_of_bits_per_request == 2^19 bits == 2^16 bytes |
| 210 DCHECK_LT(generated_bytes_, 1U << 16); |
| 211 } |
| 212 return bytes; |
| 213 } |
| 214 |
| 215 } // namespace rappor |
OLD | NEW |