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