blob: 823d1250148c71d524dd4cbe2e418de761442978 [file] [log] [blame]
[email protected]67f92bc32012-01-26 01:56:191// Copyright (c) 2012 The Chromium Authors. All rights reserved.
[email protected]c6e584c2011-05-18 11:58:442// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "chrome/browser/internal_auth.h"
6
7#include <algorithm>
8#include <deque>
9
10#include "base/base64.h"
11#include "base/lazy_instance.h"
12#include "base/rand_util.h"
[email protected]c6e584c2011-05-18 11:58:4413#include "base/string_number_conversions.h"
14#include "base/string_split.h"
15#include "base/string_util.h"
[email protected]c38831a12011-10-28 12:44:4916#include "base/synchronization/lock.h"
[email protected]c6e584c2011-05-18 11:58:4417#include "base/threading/thread_checker.h"
18#include "base/time.h"
[email protected]c6e584c2011-05-18 11:58:4419#include "base/values.h"
[email protected]c6e584c2011-05-18 11:58:4420#include "crypto/hmac.h"
21
22namespace {
23
24typedef std::map<std::string, std::string> VarValueMap;
25
26// Size of a tick in microseconds. This determines upper bound for average
27// number of passports generated per time unit. This bound equals to
28// (kMicrosecondsPerSecond / TickUs) calls per second.
29const int64 kTickUs = 10000;
30
31// Verification window size in ticks; that means any passport expires in
32// (kVerificationWindowTicks * TickUs / kMicrosecondsPerSecond) seconds.
33const int kVerificationWindowTicks = 2000;
34
35// Generation window determines how well we are able to cope with bursts of
36// GeneratePassport calls those exceed upper bound on average speed.
37const int kGenerationWindowTicks = 20;
38
39// Makes no sense to compare other way round.
40COMPILE_ASSERT(kGenerationWindowTicks <= kVerificationWindowTicks,
41 makes_no_sense_to_have_generation_window_larger_than_verification_one);
42// We are not optimized for high value of kGenerationWindowTicks.
43COMPILE_ASSERT(kGenerationWindowTicks < 30, too_large_generation_window);
44
45// Regenerate key after this number of ticks.
46const int kKeyRegenerationSoftTicks = 500000;
47// Reject passports if key has not been regenerated in that number of ticks.
48const int kKeyRegenerationHardTicks = kKeyRegenerationSoftTicks * 2;
49
50// Limit for number of accepted var=value pairs. Feel free to bump this limit
51// higher once needed.
52const size_t kVarsLimit = 16;
53
54// Limit for length of caller-supplied strings. Feel free to bump this limit
55// higher once needed.
56const size_t kStringLengthLimit = 512;
57
58// Character used as a separator for construction of message to take HMAC of.
59// It is critical to validate all caller-supplied data (used to construct
60// message) to be clear of this separator because it could allow attacks.
61const char kItemSeparator = '\n';
62
63// Character used for var=value separation.
64const char kVarValueSeparator = '=';
65
66const size_t kKeySizeInBytes = 128 / 8;
[email protected]673266c42012-12-04 00:50:3567const size_t kHMACSizeInBytes = 256 / 8;
[email protected]c6e584c2011-05-18 11:58:4468
69// Length of base64 string required to encode given number of raw octets.
70#define BASE64_PER_RAW(X) (X > 0 ? ((X - 1) / 3 + 1) * 4 : 0)
71
72// Size of decimal string representing 64-bit tick.
73const size_t kTickStringLength = 20;
74
75// A passport consists of 2 parts: HMAC and tick.
76const size_t kPassportSize =
77 BASE64_PER_RAW(kHMACSizeInBytes) + kTickStringLength;
78
79int64 GetCurrentTick() {
80 int64 tick = base::Time::Now().ToInternalValue() / kTickUs;
81 if (tick < kVerificationWindowTicks ||
82 tick < kKeyRegenerationHardTicks ||
83 tick > kint64max - kKeyRegenerationHardTicks) {
84 return 0;
85 }
86 return tick;
87}
88
89bool IsDomainSane(const std::string& domain) {
90 return !domain.empty() &&
91 domain.size() <= kStringLengthLimit &&
92 IsStringUTF8(domain) &&
93 domain.find_first_of(kItemSeparator) == std::string::npos;
94}
95
96bool IsVarSane(const std::string& var) {
97 static const char kAllowedChars[] =
98 "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
99 "abcdefghijklmnopqrstuvwxyz"
100 "0123456789"
101 "_";
102 COMPILE_ASSERT(
103 sizeof(kAllowedChars) == 26 + 26 + 10 + 1 + 1, some_mess_with_chars);
104 // We must not allow kItemSeparator in anything used as an input to construct
105 // message to sign.
106 DCHECK(std::find(kAllowedChars, kAllowedChars + arraysize(kAllowedChars),
107 kItemSeparator) == kAllowedChars + arraysize(kAllowedChars));
108 DCHECK(std::find(kAllowedChars, kAllowedChars + arraysize(kAllowedChars),
109 kVarValueSeparator) == kAllowedChars + arraysize(kAllowedChars));
110 return !var.empty() &&
111 var.size() <= kStringLengthLimit &&
112 IsStringASCII(var) &&
113 var.find_first_not_of(kAllowedChars) == std::string::npos &&
114 !IsAsciiDigit(var[0]);
115}
116
117bool IsValueSane(const std::string& value) {
118 return value.size() <= kStringLengthLimit &&
119 IsStringUTF8(value) &&
120 value.find_first_of(kItemSeparator) == std::string::npos;
121}
122
123bool IsVarValueMapSane(const VarValueMap& map) {
124 if (map.size() > kVarsLimit)
125 return false;
126 for (VarValueMap::const_iterator it = map.begin(); it != map.end(); ++it) {
127 const std::string& var = it->first;
128 const std::string& value = it->second;
129 if (!IsVarSane(var) || !IsValueSane(value))
130 return false;
131 }
132 return true;
133}
134
135void ConvertVarValueMapToBlob(const VarValueMap& map, std::string* out) {
136 out->clear();
137 DCHECK(IsVarValueMapSane(map));
138 for (VarValueMap::const_iterator it = map.begin(); it != map.end(); ++it)
139 *out += it->first + kVarValueSeparator + it->second + kItemSeparator;
140}
141
[email protected]08b14a52012-07-02 23:30:36142void CreatePassport(const std::string& domain,
143 const VarValueMap& map,
144 int64 tick,
145 const crypto::HMAC* engine,
146 std::string* out) {
[email protected]c6e584c2011-05-18 11:58:44147 DCHECK(engine);
148 DCHECK(out);
149 DCHECK(IsDomainSane(domain));
150 DCHECK(IsVarValueMapSane(map));
151
152 out->clear();
153 std::string result(kPassportSize, '0');
154
155 std::string blob;
156 blob = domain + kItemSeparator;
157 std::string tmp;
158 ConvertVarValueMapToBlob(map, &tmp);
159 blob += tmp + kItemSeparator + base::Uint64ToString(tick);
160
161 std::string hmac;
162 unsigned char* hmac_data = reinterpret_cast<unsigned char*>(
163 WriteInto(&hmac, kHMACSizeInBytes + 1));
164 if (!engine->Sign(blob, hmac_data, kHMACSizeInBytes)) {
165 NOTREACHED();
166 return;
167 }
168 std::string hmac_base64;
169 if (!base::Base64Encode(hmac, &hmac_base64)) {
170 NOTREACHED();
171 return;
172 }
173 if (hmac_base64.size() != BASE64_PER_RAW(kHMACSizeInBytes)) {
174 NOTREACHED();
175 return;
176 }
177 DCHECK(hmac_base64.size() < result.size());
178 std::copy(hmac_base64.begin(), hmac_base64.end(), result.begin());
179
180 std::string tick_decimal = base::Uint64ToString(tick);
181 DCHECK(tick_decimal.size() <= kTickStringLength);
182 std::copy(
183 tick_decimal.begin(),
184 tick_decimal.end(),
185 result.begin() + kPassportSize - tick_decimal.size());
186
187 out->swap(result);
188}
189
190} // namespace
191
[email protected]08b14a52012-07-02 23:30:36192namespace chrome {
[email protected]c6e584c2011-05-18 11:58:44193
194class InternalAuthVerificationService {
195 public:
196 InternalAuthVerificationService()
197 : key_change_tick_(0),
198 dark_tick_(0) {
199 }
200
201 bool VerifyPassport(
202 const std::string& passport,
203 const std::string& domain,
204 const VarValueMap& map) {
205 int64 current_tick = GetCurrentTick();
206 int64 tick = PreVerifyPassport(passport, domain, current_tick);
207 if (tick == 0)
208 return false;
209 if (!IsVarValueMapSane(map))
210 return false;
211 std::string reference_passport;
212 CreatePassport(domain, map, tick, engine_.get(), &reference_passport);
213 if (passport != reference_passport) {
214 // Consider old key.
215 if (key_change_tick_ + get_verification_window_ticks() < tick) {
216 return false;
217 }
218 if (old_key_.empty() || old_engine_ == NULL)
219 return false;
220 CreatePassport(domain, map, tick, old_engine_.get(), &reference_passport);
221 if (passport != reference_passport)
222 return false;
223 }
224
225 // Record used tick to prevent reuse.
226 std::deque<int64>::iterator it = std::lower_bound(
227 used_ticks_.begin(), used_ticks_.end(), tick);
228 DCHECK(it == used_ticks_.end() || *it != tick);
229 used_ticks_.insert(it, tick);
230
231 // Consider pruning |used_ticks_|.
232 if (used_ticks_.size() > 50) {
233 dark_tick_ = std::max(dark_tick_,
234 current_tick - get_verification_window_ticks());
235 used_ticks_.erase(
236 used_ticks_.begin(),
237 std::lower_bound(used_ticks_.begin(), used_ticks_.end(),
238 dark_tick_ + 1));
239 }
240 return true;
241 }
242
243 void ChangeKey(const std::string& key) {
244 old_key_.swap(key_);
245 key_.clear();
246 old_engine_.swap(engine_);
247 engine_.reset(NULL);
248
249 if (key.size() != kKeySizeInBytes)
250 return;
[email protected]6df5b9e2011-07-30 05:18:01251 scoped_ptr<crypto::HMAC> new_engine(
252 new crypto::HMAC(crypto::HMAC::SHA256));
253 if (!new_engine->Init(key))
254 return;
255 engine_.swap(new_engine);
[email protected]c6e584c2011-05-18 11:58:44256 key_ = key;
257 key_change_tick_ = GetCurrentTick();
258 }
259
260 private:
261 static int get_verification_window_ticks() {
262 return InternalAuthVerification::get_verification_window_ticks();
263 }
264
265 // Returns tick bound to given passport on success or zero on failure.
266 int64 PreVerifyPassport(
267 const std::string& passport,
268 const std::string& domain,
269 int64 current_tick) {
270 if (passport.size() != kPassportSize ||
271 !IsStringASCII(passport) ||
272 !IsDomainSane(domain) ||
273 current_tick <= dark_tick_ ||
274 current_tick > key_change_tick_ + kKeyRegenerationHardTicks ||
275 key_.empty() ||
276 engine_ == NULL) {
277 return 0;
278 }
279
280 // Passport consists of 2 parts: first hmac and then tick.
281 std::string tick_decimal =
282 passport.substr(BASE64_PER_RAW(kHMACSizeInBytes));
283 DCHECK(tick_decimal.size() == kTickStringLength);
284 int64 tick = 0;
285 if (!base::StringToInt64(tick_decimal, &tick) ||
286 tick <= dark_tick_ ||
287 tick > key_change_tick_ + kKeyRegenerationHardTicks ||
288 tick < current_tick - get_verification_window_ticks() ||
289 std::binary_search(used_ticks_.begin(), used_ticks_.end(), tick)) {
290 return 0;
291 }
292 return tick;
293 }
294
295 // Current key.
296 std::string key_;
297
298 // We keep previous key in order to be able to verify passports during
299 // regeneration time. Keys are regenerated on a regular basis.
300 std::string old_key_;
301
302 // Corresponding HMAC engines.
303 scoped_ptr<crypto::HMAC> engine_;
304 scoped_ptr<crypto::HMAC> old_engine_;
305
306 // Tick at a time of recent key regeneration.
307 int64 key_change_tick_;
308
309 // Keeps track of ticks of successfully verified passports to prevent their
310 // reuse. Size of this container is kept reasonably low by purging outdated
311 // ticks.
312 std::deque<int64> used_ticks_;
313
314 // Some ticks before |dark_tick_| were purged from |used_ticks_| container.
315 // That means that we must not trust any tick less than or equal to dark tick.
316 int64 dark_tick_;
317
318 DISALLOW_COPY_AND_ASSIGN(InternalAuthVerificationService);
319};
320
[email protected]08b14a52012-07-02 23:30:36321} // namespace chrome
[email protected]c6e584c2011-05-18 11:58:44322
323namespace {
324
[email protected]08b14a52012-07-02 23:30:36325static base::LazyInstance<chrome::InternalAuthVerificationService>
[email protected]6de0fd1d2011-11-15 13:31:49326 g_verification_service = LAZY_INSTANCE_INITIALIZER;
[email protected]67f92bc32012-01-26 01:56:19327static base::LazyInstance<base::Lock>::Leaky
[email protected]6de0fd1d2011-11-15 13:31:49328 g_verification_service_lock = LAZY_INSTANCE_INITIALIZER;
[email protected]c6e584c2011-05-18 11:58:44329
330} // namespace
331
[email protected]08b14a52012-07-02 23:30:36332namespace chrome {
[email protected]c6e584c2011-05-18 11:58:44333
334class InternalAuthGenerationService : public base::ThreadChecker {
335 public:
336 InternalAuthGenerationService() : key_regeneration_tick_(0) {
337 GenerateNewKey();
338 }
339
340 void GenerateNewKey() {
341 DCHECK(CalledOnValidThread());
[email protected]e234b112011-09-13 10:10:29342 scoped_ptr<crypto::HMAC> new_engine(new crypto::HMAC(crypto::HMAC::SHA256));
[email protected]c6e584c2011-05-18 11:58:44343 std::string key = base::RandBytesAsString(kKeySizeInBytes);
[email protected]6df5b9e2011-07-30 05:18:01344 if (!new_engine->Init(key))
345 return;
346 engine_.swap(new_engine);
[email protected]c6e584c2011-05-18 11:58:44347 key_regeneration_tick_ = GetCurrentTick();
348 g_verification_service.Get().ChangeKey(key);
349 std::fill(key.begin(), key.end(), 0);
350 }
351
352 // Returns zero on failure.
353 int64 GetUnusedTick(const std::string& domain) {
354 DCHECK(CalledOnValidThread());
355 if (engine_ == NULL) {
356 NOTREACHED();
357 return 0;
358 }
359 if (!IsDomainSane(domain))
360 return 0;
361
362 int64 current_tick = GetCurrentTick();
363 if (!used_ticks_.empty() && used_ticks_.back() > current_tick)
364 current_tick = used_ticks_.back();
[email protected]e234b112011-09-13 10:10:29365 for (bool first_iteration = true;; first_iteration = false) {
366 if (current_tick < key_regeneration_tick_ + kKeyRegenerationHardTicks)
367 break;
368 if (!first_iteration)
369 return 0;
370 GenerateNewKey();
371 }
[email protected]c6e584c2011-05-18 11:58:44372
373 // Forget outdated ticks if any.
374 used_ticks_.erase(
375 used_ticks_.begin(),
376 std::lower_bound(used_ticks_.begin(), used_ticks_.end(),
377 current_tick - kGenerationWindowTicks + 1));
378 DCHECK(used_ticks_.size() <= kGenerationWindowTicks + 0u);
379 if (used_ticks_.size() >= kGenerationWindowTicks + 0u) {
380 // Average speed of GeneratePassport calls exceeds limit.
381 return 0;
382 }
383 for (int64 tick = current_tick;
384 tick > current_tick - kGenerationWindowTicks;
385 --tick) {
386 int idx = static_cast<int>(used_ticks_.size()) -
387 static_cast<int>(current_tick - tick + 1);
388 if (idx < 0 || used_ticks_[idx] != tick) {
389 DCHECK(used_ticks_.end() ==
390 std::find(used_ticks_.begin(), used_ticks_.end(), tick));
391 return tick;
392 }
393 }
394 NOTREACHED();
395 return 0;
396 }
397
398 std::string GeneratePassport(
399 const std::string& domain, const VarValueMap& map, int64 tick) {
400 DCHECK(CalledOnValidThread());
401 if (tick == 0) {
402 tick = GetUnusedTick(domain);
403 if (tick == 0)
404 return std::string();
405 }
406 if (!IsVarValueMapSane(map))
407 return std::string();
408
409 std::string result;
410 CreatePassport(domain, map, tick, engine_.get(), &result);
411 used_ticks_.insert(
412 std::lower_bound(used_ticks_.begin(), used_ticks_.end(), tick), tick);
413 return result;
414 }
415
416 private:
417 static int get_verification_window_ticks() {
418 return InternalAuthVerification::get_verification_window_ticks();
419 }
420
421 scoped_ptr<crypto::HMAC> engine_;
[email protected]c6e584c2011-05-18 11:58:44422 int64 key_regeneration_tick_;
423 std::deque<int64> used_ticks_;
424
425 DISALLOW_COPY_AND_ASSIGN(InternalAuthGenerationService);
426};
427
[email protected]08b14a52012-07-02 23:30:36428} // namespace chrome
[email protected]c6e584c2011-05-18 11:58:44429
430namespace {
431
[email protected]08b14a52012-07-02 23:30:36432static base::LazyInstance<chrome::InternalAuthGenerationService>
[email protected]6de0fd1d2011-11-15 13:31:49433 g_generation_service = LAZY_INSTANCE_INITIALIZER;
[email protected]c6e584c2011-05-18 11:58:44434
435} // namespace
436
[email protected]08b14a52012-07-02 23:30:36437namespace chrome {
[email protected]c6e584c2011-05-18 11:58:44438
439// static
440bool InternalAuthVerification::VerifyPassport(
441 const std::string& passport,
442 const std::string& domain,
443 const VarValueMap& var_value_map) {
444 base::AutoLock alk(g_verification_service_lock.Get());
445 return g_verification_service.Get().VerifyPassport(
446 passport, domain, var_value_map);
447}
448
449// static
450void InternalAuthVerification::ChangeKey(const std::string& key) {
451 base::AutoLock alk(g_verification_service_lock.Get());
452 g_verification_service.Get().ChangeKey(key);
453};
454
455// static
456int InternalAuthVerification::get_verification_window_ticks() {
457 int candidate = kVerificationWindowTicks;
458 if (verification_window_seconds_ > 0)
459 candidate = verification_window_seconds_ *
460 base::Time::kMicrosecondsPerSecond / kTickUs;
461 return std::max(1, std::min(candidate, kVerificationWindowTicks));
462}
463
464int InternalAuthVerification::verification_window_seconds_ = 0;
465
466// static
467std::string InternalAuthGeneration::GeneratePassport(
468 const std::string& domain, const VarValueMap& var_value_map) {
469 return g_generation_service.Get().GeneratePassport(domain, var_value_map, 0);
470}
471
472// static
473void InternalAuthGeneration::GenerateNewKey() {
474 g_generation_service.Get().GenerateNewKey();
475}
476
[email protected]08b14a52012-07-02 23:30:36477} // namespace chrome