chrome/browser/internal_auth.cc

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