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