OLD | NEW |
1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. | 1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "chrome/browser/internal_auth.h" | 5 #include "chrome/browser/internal_auth.h" |
6 | 6 |
| 7 #include <stdint.h> |
| 8 |
7 #include <algorithm> | 9 #include <algorithm> |
8 #include <deque> | 10 #include <deque> |
| 11 #include <limits> |
9 | 12 |
10 #include "base/base64.h" | 13 #include "base/base64.h" |
11 #include "base/lazy_instance.h" | 14 #include "base/lazy_instance.h" |
12 #include "base/rand_util.h" | 15 #include "base/rand_util.h" |
13 #include "base/strings/string_number_conversions.h" | 16 #include "base/strings/string_number_conversions.h" |
14 #include "base/strings/string_split.h" | 17 #include "base/strings/string_split.h" |
15 #include "base/strings/string_util.h" | 18 #include "base/strings/string_util.h" |
16 #include "base/synchronization/lock.h" | 19 #include "base/synchronization/lock.h" |
17 #include "base/threading/thread_checker.h" | 20 #include "base/threading/thread_checker.h" |
18 #include "base/time/time.h" | 21 #include "base/time/time.h" |
19 #include "base/values.h" | 22 #include "base/values.h" |
20 #include "crypto/hmac.h" | 23 #include "crypto/hmac.h" |
21 | 24 |
22 namespace { | 25 namespace { |
23 | 26 |
24 typedef std::map<std::string, std::string> VarValueMap; | 27 typedef std::map<std::string, std::string> VarValueMap; |
25 | 28 |
26 // Size of a tick in microseconds. This determines upper bound for average | 29 // Size of a tick in microseconds. This determines upper bound for average |
27 // number of passports generated per time unit. This bound equals to | 30 // number of passports generated per time unit. This bound equals to |
28 // (kMicrosecondsPerSecond / TickUs) calls per second. | 31 // (kMicrosecondsPerSecond / TickUs) calls per second. |
29 const int64 kTickUs = 10000; | 32 const int64_t kTickUs = 10000; |
30 | 33 |
31 // Verification window size in ticks; that means any passport expires in | 34 // Verification window size in ticks; that means any passport expires in |
32 // (kVerificationWindowTicks * TickUs / kMicrosecondsPerSecond) seconds. | 35 // (kVerificationWindowTicks * TickUs / kMicrosecondsPerSecond) seconds. |
33 const int kVerificationWindowTicks = 2000; | 36 const int kVerificationWindowTicks = 2000; |
34 | 37 |
35 // Generation window determines how well we are able to cope with bursts of | 38 // Generation window determines how well we are able to cope with bursts of |
36 // GeneratePassport calls those exceed upper bound on average speed. | 39 // GeneratePassport calls those exceed upper bound on average speed. |
37 const int kGenerationWindowTicks = 20; | 40 const int kGenerationWindowTicks = 20; |
38 | 41 |
39 // Makes no sense to compare other way round. | 42 // Makes no sense to compare other way round. |
(...skipping 30 matching lines...) Expand all Loading... |
70 // Length of base64 string required to encode given number of raw octets. | 73 // Length of base64 string required to encode given number of raw octets. |
71 #define BASE64_PER_RAW(X) (X > 0 ? ((X - 1) / 3 + 1) * 4 : 0) | 74 #define BASE64_PER_RAW(X) (X > 0 ? ((X - 1) / 3 + 1) * 4 : 0) |
72 | 75 |
73 // Size of decimal string representing 64-bit tick. | 76 // Size of decimal string representing 64-bit tick. |
74 const size_t kTickStringLength = 20; | 77 const size_t kTickStringLength = 20; |
75 | 78 |
76 // A passport consists of 2 parts: HMAC and tick. | 79 // A passport consists of 2 parts: HMAC and tick. |
77 const size_t kPassportSize = | 80 const size_t kPassportSize = |
78 BASE64_PER_RAW(kHMACSizeInBytes) + kTickStringLength; | 81 BASE64_PER_RAW(kHMACSizeInBytes) + kTickStringLength; |
79 | 82 |
80 int64 GetCurrentTick() { | 83 int64_t GetCurrentTick() { |
81 int64 tick = base::Time::Now().ToInternalValue() / kTickUs; | 84 int64_t tick = base::Time::Now().ToInternalValue() / kTickUs; |
82 if (tick < kVerificationWindowTicks || | 85 if (tick < kVerificationWindowTicks || tick < kKeyRegenerationHardTicks || |
83 tick < kKeyRegenerationHardTicks || | 86 tick > std::numeric_limits<int64_t>::max() - kKeyRegenerationHardTicks) { |
84 tick > kint64max - kKeyRegenerationHardTicks) { | |
85 return 0; | 87 return 0; |
86 } | 88 } |
87 return tick; | 89 return tick; |
88 } | 90 } |
89 | 91 |
90 bool IsDomainSane(const std::string& domain) { | 92 bool IsDomainSane(const std::string& domain) { |
91 return !domain.empty() && | 93 return !domain.empty() && |
92 domain.size() <= kStringLengthLimit && | 94 domain.size() <= kStringLengthLimit && |
93 base::IsStringUTF8(domain) && | 95 base::IsStringUTF8(domain) && |
94 domain.find_first_of(kItemSeparator) == std::string::npos; | 96 domain.find_first_of(kItemSeparator) == std::string::npos; |
(...skipping 40 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
135 | 137 |
136 void ConvertVarValueMapToBlob(const VarValueMap& map, std::string* out) { | 138 void ConvertVarValueMapToBlob(const VarValueMap& map, std::string* out) { |
137 out->clear(); | 139 out->clear(); |
138 DCHECK(IsVarValueMapSane(map)); | 140 DCHECK(IsVarValueMapSane(map)); |
139 for (VarValueMap::const_iterator it = map.begin(); it != map.end(); ++it) | 141 for (VarValueMap::const_iterator it = map.begin(); it != map.end(); ++it) |
140 *out += it->first + kVarValueSeparator + it->second + kItemSeparator; | 142 *out += it->first + kVarValueSeparator + it->second + kItemSeparator; |
141 } | 143 } |
142 | 144 |
143 void CreatePassport(const std::string& domain, | 145 void CreatePassport(const std::string& domain, |
144 const VarValueMap& map, | 146 const VarValueMap& map, |
145 int64 tick, | 147 int64_t tick, |
146 const crypto::HMAC* engine, | 148 const crypto::HMAC* engine, |
147 std::string* out) { | 149 std::string* out) { |
148 DCHECK(engine); | 150 DCHECK(engine); |
149 DCHECK(out); | 151 DCHECK(out); |
150 DCHECK(IsDomainSane(domain)); | 152 DCHECK(IsDomainSane(domain)); |
151 DCHECK(IsVarValueMapSane(map)); | 153 DCHECK(IsVarValueMapSane(map)); |
152 | 154 |
153 out->clear(); | 155 out->clear(); |
154 std::string result(kPassportSize, '0'); | 156 std::string result(kPassportSize, '0'); |
155 | 157 |
(...skipping 37 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
193 public: | 195 public: |
194 InternalAuthVerificationService() | 196 InternalAuthVerificationService() |
195 : key_change_tick_(0), | 197 : key_change_tick_(0), |
196 dark_tick_(0) { | 198 dark_tick_(0) { |
197 } | 199 } |
198 | 200 |
199 bool VerifyPassport( | 201 bool VerifyPassport( |
200 const std::string& passport, | 202 const std::string& passport, |
201 const std::string& domain, | 203 const std::string& domain, |
202 const VarValueMap& map) { | 204 const VarValueMap& map) { |
203 int64 current_tick = GetCurrentTick(); | 205 int64_t current_tick = GetCurrentTick(); |
204 int64 tick = PreVerifyPassport(passport, domain, current_tick); | 206 int64_t tick = PreVerifyPassport(passport, domain, current_tick); |
205 if (tick == 0) | 207 if (tick == 0) |
206 return false; | 208 return false; |
207 if (!IsVarValueMapSane(map)) | 209 if (!IsVarValueMapSane(map)) |
208 return false; | 210 return false; |
209 std::string reference_passport; | 211 std::string reference_passport; |
210 CreatePassport(domain, map, tick, engine_.get(), &reference_passport); | 212 CreatePassport(domain, map, tick, engine_.get(), &reference_passport); |
211 if (passport != reference_passport) { | 213 if (passport != reference_passport) { |
212 // Consider old key. | 214 // Consider old key. |
213 if (key_change_tick_ + get_verification_window_ticks() < tick) { | 215 if (key_change_tick_ + get_verification_window_ticks() < tick) { |
214 return false; | 216 return false; |
215 } | 217 } |
216 if (old_key_.empty() || old_engine_ == NULL) | 218 if (old_key_.empty() || old_engine_ == NULL) |
217 return false; | 219 return false; |
218 CreatePassport(domain, map, tick, old_engine_.get(), &reference_passport); | 220 CreatePassport(domain, map, tick, old_engine_.get(), &reference_passport); |
219 if (passport != reference_passport) | 221 if (passport != reference_passport) |
220 return false; | 222 return false; |
221 } | 223 } |
222 | 224 |
223 // Record used tick to prevent reuse. | 225 // Record used tick to prevent reuse. |
224 std::deque<int64>::iterator it = std::lower_bound( | 226 std::deque<int64_t>::iterator it = |
225 used_ticks_.begin(), used_ticks_.end(), tick); | 227 std::lower_bound(used_ticks_.begin(), used_ticks_.end(), tick); |
226 DCHECK(it == used_ticks_.end() || *it != tick); | 228 DCHECK(it == used_ticks_.end() || *it != tick); |
227 used_ticks_.insert(it, tick); | 229 used_ticks_.insert(it, tick); |
228 | 230 |
229 // Consider pruning |used_ticks_|. | 231 // Consider pruning |used_ticks_|. |
230 if (used_ticks_.size() > 50) { | 232 if (used_ticks_.size() > 50) { |
231 dark_tick_ = std::max(dark_tick_, | 233 dark_tick_ = std::max(dark_tick_, |
232 current_tick - get_verification_window_ticks()); | 234 current_tick - get_verification_window_ticks()); |
233 used_ticks_.erase( | 235 used_ticks_.erase( |
234 used_ticks_.begin(), | 236 used_ticks_.begin(), |
235 std::lower_bound(used_ticks_.begin(), used_ticks_.end(), | 237 std::lower_bound(used_ticks_.begin(), used_ticks_.end(), |
(...skipping 18 matching lines...) Expand all Loading... |
254 key_ = key; | 256 key_ = key; |
255 key_change_tick_ = GetCurrentTick(); | 257 key_change_tick_ = GetCurrentTick(); |
256 } | 258 } |
257 | 259 |
258 private: | 260 private: |
259 static int get_verification_window_ticks() { | 261 static int get_verification_window_ticks() { |
260 return InternalAuthVerification::get_verification_window_ticks(); | 262 return InternalAuthVerification::get_verification_window_ticks(); |
261 } | 263 } |
262 | 264 |
263 // Returns tick bound to given passport on success or zero on failure. | 265 // Returns tick bound to given passport on success or zero on failure. |
264 int64 PreVerifyPassport( | 266 int64_t PreVerifyPassport(const std::string& passport, |
265 const std::string& passport, | 267 const std::string& domain, |
266 const std::string& domain, | 268 int64_t current_tick) { |
267 int64 current_tick) { | |
268 if (passport.size() != kPassportSize || | 269 if (passport.size() != kPassportSize || |
269 !base::IsStringASCII(passport) || | 270 !base::IsStringASCII(passport) || |
270 !IsDomainSane(domain) || | 271 !IsDomainSane(domain) || |
271 current_tick <= dark_tick_ || | 272 current_tick <= dark_tick_ || |
272 current_tick > key_change_tick_ + kKeyRegenerationHardTicks || | 273 current_tick > key_change_tick_ + kKeyRegenerationHardTicks || |
273 key_.empty() || | 274 key_.empty() || |
274 engine_ == NULL) { | 275 engine_ == NULL) { |
275 return 0; | 276 return 0; |
276 } | 277 } |
277 | 278 |
278 // Passport consists of 2 parts: first hmac and then tick. | 279 // Passport consists of 2 parts: first hmac and then tick. |
279 std::string tick_decimal = | 280 std::string tick_decimal = |
280 passport.substr(BASE64_PER_RAW(kHMACSizeInBytes)); | 281 passport.substr(BASE64_PER_RAW(kHMACSizeInBytes)); |
281 DCHECK(tick_decimal.size() == kTickStringLength); | 282 DCHECK(tick_decimal.size() == kTickStringLength); |
282 int64 tick = 0; | 283 int64_t tick = 0; |
283 if (!base::StringToInt64(tick_decimal, &tick) || | 284 if (!base::StringToInt64(tick_decimal, &tick) || |
284 tick <= dark_tick_ || | 285 tick <= dark_tick_ || |
285 tick > key_change_tick_ + kKeyRegenerationHardTicks || | 286 tick > key_change_tick_ + kKeyRegenerationHardTicks || |
286 tick < current_tick - get_verification_window_ticks() || | 287 tick < current_tick - get_verification_window_ticks() || |
287 std::binary_search(used_ticks_.begin(), used_ticks_.end(), tick)) { | 288 std::binary_search(used_ticks_.begin(), used_ticks_.end(), tick)) { |
288 return 0; | 289 return 0; |
289 } | 290 } |
290 return tick; | 291 return tick; |
291 } | 292 } |
292 | 293 |
293 // Current key. | 294 // Current key. |
294 std::string key_; | 295 std::string key_; |
295 | 296 |
296 // We keep previous key in order to be able to verify passports during | 297 // We keep previous key in order to be able to verify passports during |
297 // regeneration time. Keys are regenerated on a regular basis. | 298 // regeneration time. Keys are regenerated on a regular basis. |
298 std::string old_key_; | 299 std::string old_key_; |
299 | 300 |
300 // Corresponding HMAC engines. | 301 // Corresponding HMAC engines. |
301 scoped_ptr<crypto::HMAC> engine_; | 302 scoped_ptr<crypto::HMAC> engine_; |
302 scoped_ptr<crypto::HMAC> old_engine_; | 303 scoped_ptr<crypto::HMAC> old_engine_; |
303 | 304 |
304 // Tick at a time of recent key regeneration. | 305 // Tick at a time of recent key regeneration. |
305 int64 key_change_tick_; | 306 int64_t key_change_tick_; |
306 | 307 |
307 // Keeps track of ticks of successfully verified passports to prevent their | 308 // Keeps track of ticks of successfully verified passports to prevent their |
308 // reuse. Size of this container is kept reasonably low by purging outdated | 309 // reuse. Size of this container is kept reasonably low by purging outdated |
309 // ticks. | 310 // ticks. |
310 std::deque<int64> used_ticks_; | 311 std::deque<int64_t> used_ticks_; |
311 | 312 |
312 // Some ticks before |dark_tick_| were purged from |used_ticks_| container. | 313 // Some ticks before |dark_tick_| were purged from |used_ticks_| container. |
313 // That means that we must not trust any tick less than or equal to dark tick. | 314 // That means that we must not trust any tick less than or equal to dark tick. |
314 int64 dark_tick_; | 315 int64_t dark_tick_; |
315 | 316 |
316 DISALLOW_COPY_AND_ASSIGN(InternalAuthVerificationService); | 317 DISALLOW_COPY_AND_ASSIGN(InternalAuthVerificationService); |
317 }; | 318 }; |
318 | 319 |
319 } // namespace chrome | 320 } // namespace chrome |
320 | 321 |
321 namespace { | 322 namespace { |
322 | 323 |
323 static base::LazyInstance<chrome::InternalAuthVerificationService> | 324 static base::LazyInstance<chrome::InternalAuthVerificationService> |
324 g_verification_service = LAZY_INSTANCE_INITIALIZER; | 325 g_verification_service = LAZY_INSTANCE_INITIALIZER; |
(...skipping 16 matching lines...) Expand all Loading... |
341 std::string key = base::RandBytesAsString(kKeySizeInBytes); | 342 std::string key = base::RandBytesAsString(kKeySizeInBytes); |
342 if (!new_engine->Init(key)) | 343 if (!new_engine->Init(key)) |
343 return; | 344 return; |
344 engine_.swap(new_engine); | 345 engine_.swap(new_engine); |
345 key_regeneration_tick_ = GetCurrentTick(); | 346 key_regeneration_tick_ = GetCurrentTick(); |
346 g_verification_service.Get().ChangeKey(key); | 347 g_verification_service.Get().ChangeKey(key); |
347 std::fill(key.begin(), key.end(), 0); | 348 std::fill(key.begin(), key.end(), 0); |
348 } | 349 } |
349 | 350 |
350 // Returns zero on failure. | 351 // Returns zero on failure. |
351 int64 GetUnusedTick(const std::string& domain) { | 352 int64_t GetUnusedTick(const std::string& domain) { |
352 DCHECK(CalledOnValidThread()); | 353 DCHECK(CalledOnValidThread()); |
353 if (engine_ == NULL) { | 354 if (engine_ == NULL) { |
354 NOTREACHED(); | 355 NOTREACHED(); |
355 return 0; | 356 return 0; |
356 } | 357 } |
357 if (!IsDomainSane(domain)) | 358 if (!IsDomainSane(domain)) |
358 return 0; | 359 return 0; |
359 | 360 |
360 int64 current_tick = GetCurrentTick(); | 361 int64_t current_tick = GetCurrentTick(); |
361 if (!used_ticks_.empty() && used_ticks_.back() > current_tick) | 362 if (!used_ticks_.empty() && used_ticks_.back() > current_tick) |
362 current_tick = used_ticks_.back(); | 363 current_tick = used_ticks_.back(); |
363 for (bool first_iteration = true;; first_iteration = false) { | 364 for (bool first_iteration = true;; first_iteration = false) { |
364 if (current_tick < key_regeneration_tick_ + kKeyRegenerationHardTicks) | 365 if (current_tick < key_regeneration_tick_ + kKeyRegenerationHardTicks) |
365 break; | 366 break; |
366 if (!first_iteration) | 367 if (!first_iteration) |
367 return 0; | 368 return 0; |
368 GenerateNewKey(); | 369 GenerateNewKey(); |
369 } | 370 } |
370 | 371 |
371 // Forget outdated ticks if any. | 372 // Forget outdated ticks if any. |
372 used_ticks_.erase( | 373 used_ticks_.erase( |
373 used_ticks_.begin(), | 374 used_ticks_.begin(), |
374 std::lower_bound(used_ticks_.begin(), used_ticks_.end(), | 375 std::lower_bound(used_ticks_.begin(), used_ticks_.end(), |
375 current_tick - kGenerationWindowTicks + 1)); | 376 current_tick - kGenerationWindowTicks + 1)); |
376 DCHECK(used_ticks_.size() <= kGenerationWindowTicks + 0u); | 377 DCHECK(used_ticks_.size() <= kGenerationWindowTicks + 0u); |
377 if (used_ticks_.size() >= kGenerationWindowTicks + 0u) { | 378 if (used_ticks_.size() >= kGenerationWindowTicks + 0u) { |
378 // Average speed of GeneratePassport calls exceeds limit. | 379 // Average speed of GeneratePassport calls exceeds limit. |
379 return 0; | 380 return 0; |
380 } | 381 } |
381 for (int64 tick = current_tick; | 382 for (int64_t tick = current_tick; |
382 tick > current_tick - kGenerationWindowTicks; | 383 tick > current_tick - kGenerationWindowTicks; --tick) { |
383 --tick) { | |
384 int idx = static_cast<int>(used_ticks_.size()) - | 384 int idx = static_cast<int>(used_ticks_.size()) - |
385 static_cast<int>(current_tick - tick + 1); | 385 static_cast<int>(current_tick - tick + 1); |
386 if (idx < 0 || used_ticks_[idx] != tick) { | 386 if (idx < 0 || used_ticks_[idx] != tick) { |
387 DCHECK(used_ticks_.end() == | 387 DCHECK(used_ticks_.end() == |
388 std::find(used_ticks_.begin(), used_ticks_.end(), tick)); | 388 std::find(used_ticks_.begin(), used_ticks_.end(), tick)); |
389 return tick; | 389 return tick; |
390 } | 390 } |
391 } | 391 } |
392 NOTREACHED(); | 392 NOTREACHED(); |
393 return 0; | 393 return 0; |
394 } | 394 } |
395 | 395 |
396 std::string GeneratePassport( | 396 std::string GeneratePassport(const std::string& domain, |
397 const std::string& domain, const VarValueMap& map, int64 tick) { | 397 const VarValueMap& map, |
| 398 int64_t tick) { |
398 DCHECK(CalledOnValidThread()); | 399 DCHECK(CalledOnValidThread()); |
399 if (tick == 0) { | 400 if (tick == 0) { |
400 tick = GetUnusedTick(domain); | 401 tick = GetUnusedTick(domain); |
401 if (tick == 0) | 402 if (tick == 0) |
402 return std::string(); | 403 return std::string(); |
403 } | 404 } |
404 if (!IsVarValueMapSane(map)) | 405 if (!IsVarValueMapSane(map)) |
405 return std::string(); | 406 return std::string(); |
406 | 407 |
407 std::string result; | 408 std::string result; |
408 CreatePassport(domain, map, tick, engine_.get(), &result); | 409 CreatePassport(domain, map, tick, engine_.get(), &result); |
409 used_ticks_.insert( | 410 used_ticks_.insert( |
410 std::lower_bound(used_ticks_.begin(), used_ticks_.end(), tick), tick); | 411 std::lower_bound(used_ticks_.begin(), used_ticks_.end(), tick), tick); |
411 return result; | 412 return result; |
412 } | 413 } |
413 | 414 |
414 private: | 415 private: |
415 static int get_verification_window_ticks() { | 416 static int get_verification_window_ticks() { |
416 return InternalAuthVerification::get_verification_window_ticks(); | 417 return InternalAuthVerification::get_verification_window_ticks(); |
417 } | 418 } |
418 | 419 |
419 scoped_ptr<crypto::HMAC> engine_; | 420 scoped_ptr<crypto::HMAC> engine_; |
420 int64 key_regeneration_tick_; | 421 int64_t key_regeneration_tick_; |
421 std::deque<int64> used_ticks_; | 422 std::deque<int64_t> used_ticks_; |
422 | 423 |
423 DISALLOW_COPY_AND_ASSIGN(InternalAuthGenerationService); | 424 DISALLOW_COPY_AND_ASSIGN(InternalAuthGenerationService); |
424 }; | 425 }; |
425 | 426 |
426 } // namespace chrome | 427 } // namespace chrome |
427 | 428 |
428 namespace { | 429 namespace { |
429 | 430 |
430 static base::LazyInstance<chrome::InternalAuthGenerationService> | 431 static base::LazyInstance<chrome::InternalAuthGenerationService> |
431 g_generation_service = LAZY_INSTANCE_INITIALIZER; | 432 g_generation_service = LAZY_INSTANCE_INITIALIZER; |
(...skipping 34 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
466 const std::string& domain, const VarValueMap& var_value_map) { | 467 const std::string& domain, const VarValueMap& var_value_map) { |
467 return g_generation_service.Get().GeneratePassport(domain, var_value_map, 0); | 468 return g_generation_service.Get().GeneratePassport(domain, var_value_map, 0); |
468 } | 469 } |
469 | 470 |
470 // static | 471 // static |
471 void InternalAuthGeneration::GenerateNewKey() { | 472 void InternalAuthGeneration::GenerateNewKey() { |
472 g_generation_service.Get().GenerateNewKey(); | 473 g_generation_service.Get().GenerateNewKey(); |
473 } | 474 } |
474 | 475 |
475 } // namespace chrome | 476 } // namespace chrome |
OLD | NEW |