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 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" 13#include "base/strings/string_number_conversions.h" 14#include "base/strings/string_split.h" 15#include "base/strings/string_util.h" 16#include "base/synchronization/lock.h" 17#include "base/threading/thread_checker.h" 18#include "base/time/time.h" 19#include "base/values.h" 20#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; 67const size_t kHMACSizeInBytes = 256 / 8; 68 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 142void CreatePassport(const std::string& domain, 143 const VarValueMap& map, 144 int64 tick, 145 const crypto::HMAC* engine, 146 std::string* out) { 147 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 192namespace chrome { 193 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; 251 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); 256 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 321} // namespace chrome 322 323namespace { 324 325static base::LazyInstance<chrome::InternalAuthVerificationService> 326 g_verification_service = LAZY_INSTANCE_INITIALIZER; 327static base::LazyInstance<base::Lock>::Leaky 328 g_verification_service_lock = LAZY_INSTANCE_INITIALIZER; 329 330} // namespace 331 332namespace chrome { 333 334class InternalAuthGenerationService : public base::ThreadChecker { 335 public: 336 InternalAuthGenerationService() : key_regeneration_tick_(0) { 337 GenerateNewKey(); 338 } 339 340 void GenerateNewKey() { 341 DCHECK(CalledOnValidThread()); 342 scoped_ptr<crypto::HMAC> new_engine(new crypto::HMAC(crypto::HMAC::SHA256)); 343 std::string key = base::RandBytesAsString(kKeySizeInBytes); 344 if (!new_engine->Init(key)) 345 return; 346 engine_.swap(new_engine); 347 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(); 365 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 } 372 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_; 422 int64 key_regeneration_tick_; 423 std::deque<int64> used_ticks_; 424 425 DISALLOW_COPY_AND_ASSIGN(InternalAuthGenerationService); 426}; 427 428} // namespace chrome 429 430namespace { 431 432static base::LazyInstance<chrome::InternalAuthGenerationService> 433 g_generation_service = LAZY_INSTANCE_INITIALIZER; 434 435} // namespace 436 437namespace chrome { 438 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 477} // namespace chrome 478