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/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
  22 namespace {
  23
  24 typedef 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.
  29 const int64 kTickUs = 10000;
  30
  31 // Verification window size in ticks; that means any passport expires in
  32 // (kVerificationWindowTicks * TickUs / kMicrosecondsPerSecond) seconds.
  33 const 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.
  37 const int kGenerationWindowTicks = 20;
  38
  39 // Makes no sense to compare other way round.
  40 static_assert(kGenerationWindowTicks <= kVerificationWindowTicks,
  41     "generation window should not be larger than the verification window");
  42 // We are not optimized for high value of kGenerationWindowTicks.
  43 static_assert(kGenerationWindowTicks < 30,
  44     "generation window should not be too large");
  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 size_t 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       base::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   static_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       base::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       base::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   base::Base64Encode(hmac, &hmac_base64);
 171   if (hmac_base64.size() != BASE64_PER_RAW(kHMACSizeInBytes)) {
 172     NOTREACHED();
 173     return;
 174   }
 175   DCHECK(hmac_base64.size() < result.size());
 176   std::copy(hmac_base64.begin(), hmac_base64.end(), result.begin());
 177
 178   std::string tick_decimal = base::Uint64ToString(tick);
 179   DCHECK(tick_decimal.size() <= kTickStringLength);
 180   std::copy(
 181       tick_decimal.begin(),
 182       tick_decimal.end(),
 183       result.begin() + kPassportSize - tick_decimal.size());
 184
 185   out->swap(result);
 186 }
 187
 188 }  // namespace
 189
 190 namespace chrome {
 191
 192 class InternalAuthVerificationService {
 193  public:
 194   InternalAuthVerificationService()
 195       : key_change_tick_(0),
 196         dark_tick_(0) {
 197   }
 198
 199   bool VerifyPassport(
 200       const std::string& passport,
 201       const std::string& domain,
 202       const VarValueMap& map) {
 203     int64 current_tick = GetCurrentTick();
 204     int64 tick = PreVerifyPassport(passport, domain, current_tick);
 205     if (tick == 0)
 206       return false;
 207     if (!IsVarValueMapSane(map))
 208       return false;
 209     std::string reference_passport;
 210     CreatePassport(domain, map, tick, engine_.get(), &reference_passport);
 211     if (passport != reference_passport) {
 212       // Consider old key.
 213       if (key_change_tick_ + get_verification_window_ticks() < tick) {
 214         return false;
 215       }
 216       if (old_key_.empty() || old_engine_ == NULL)
 217         return false;
 218       CreatePassport(domain, map, tick, old_engine_.get(), &reference_passport);
 219       if (passport != reference_passport)
 220         return false;
 221     }
 222
 223     // Record used tick to prevent reuse.
 224     std::deque<int64>::iterator it = std::lower_bound(
 225         used_ticks_.begin(), used_ticks_.end(), tick);
 226     DCHECK(it == used_ticks_.end() || *it != tick);
 227     used_ticks_.insert(it, tick);
 228
 229     // Consider pruning |used_ticks_|.
 230     if (used_ticks_.size() > 50) {
 231       dark_tick_ = std::max(dark_tick_,
 232           current_tick - get_verification_window_ticks());
 233       used_ticks_.erase(
 234           used_ticks_.begin(),
 235           std::lower_bound(used_ticks_.begin(), used_ticks_.end(),
 236                            dark_tick_ + 1));
 237     }
 238     return true;
 239   }
 240
 241   void ChangeKey(const std::string& key) {
 242     old_key_.swap(key_);
 243     key_.clear();
 244     old_engine_.swap(engine_);
 245     engine_.reset(NULL);
 246
 247     if (key.size() != kKeySizeInBytes)
 248       return;
 249     scoped_ptr<crypto::HMAC> new_engine(
 250         new crypto::HMAC(crypto::HMAC::SHA256));
 251     if (!new_engine->Init(key))
 252       return;
 253     engine_.swap(new_engine);
 254     key_ = key;
 255     key_change_tick_ = GetCurrentTick();
 256   }
 257
 258  private:
 259   static int get_verification_window_ticks() {
 260     return InternalAuthVerification::get_verification_window_ticks();
 261   }
 262
 263   // Returns tick bound to given passport on success or zero on failure.
 264   int64 PreVerifyPassport(
 265     const std::string& passport,
 266     const std::string& domain,
 267     int64 current_tick) {
 268     if (passport.size() != kPassportSize ||
 269         !base::IsStringASCII(passport) ||
 270         !IsDomainSane(domain) ||
 271         current_tick <= dark_tick_ ||
 272         current_tick > key_change_tick_  + kKeyRegenerationHardTicks ||
 273         key_.empty() ||
 274         engine_ == NULL) {
 275       return 0;
 276     }
 277
 278     // Passport consists of 2 parts: first hmac and then tick.
 279     std::string tick_decimal =
 280         passport.substr(BASE64_PER_RAW(kHMACSizeInBytes));
 281     DCHECK(tick_decimal.size() == kTickStringLength);
 282     int64 tick = 0;
 283     if (!base::StringToInt64(tick_decimal, &tick) ||
 284         tick <= dark_tick_ ||
 285         tick > key_change_tick_ + kKeyRegenerationHardTicks ||
 286         tick < current_tick - get_verification_window_ticks() ||
 287         std::binary_search(used_ticks_.begin(), used_ticks_.end(), tick)) {
 288       return 0;
 289     }
 290     return tick;
 291   }
 292
 293   // Current key.
 294   std::string key_;
 295
 296   // We keep previous key in order to be able to verify passports during
 297   // regeneration time.  Keys are regenerated on a regular basis.
 298   std::string old_key_;
 299
 300   // Corresponding HMAC engines.
 301   scoped_ptr<crypto::HMAC> engine_;
 302   scoped_ptr<crypto::HMAC> old_engine_;
 303
 304   // Tick at a time of recent key regeneration.
 305   int64 key_change_tick_;
 306
 307   // 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   // ticks.
 310   std::deque<int64> used_ticks_;
 311
 312   // 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   int64 dark_tick_;
 315
 316   DISALLOW_COPY_AND_ASSIGN(InternalAuthVerificationService);
 317 };
 318
 319 }  // namespace chrome
 320
 321 namespace {
 322
 323 static base::LazyInstance<chrome::InternalAuthVerificationService>
 324     g_verification_service = LAZY_INSTANCE_INITIALIZER;
 325 static base::LazyInstance<base::Lock>::Leaky
 326     g_verification_service_lock = LAZY_INSTANCE_INITIALIZER;
 327
 328 }  // namespace
 329
 330 namespace chrome {
 331
 332 class InternalAuthGenerationService : public base::ThreadChecker {
 333  public:
 334   InternalAuthGenerationService() : key_regeneration_tick_(0) {
 335     GenerateNewKey();
 336   }
 337
 338   void GenerateNewKey() {
 339     DCHECK(CalledOnValidThread());
 340     scoped_ptr<crypto::HMAC> new_engine(new crypto::HMAC(crypto::HMAC::SHA256));
 341     std::string key = base::RandBytesAsString(kKeySizeInBytes);
 342     if (!new_engine->Init(key))
 343       return;
 344     engine_.swap(new_engine);
 345     key_regeneration_tick_ = GetCurrentTick();
 346     g_verification_service.Get().ChangeKey(key);
 347     std::fill(key.begin(), key.end(), 0);
 348   }
 349
 350   // Returns zero on failure.
 351   int64 GetUnusedTick(const std::string& domain) {
 352     DCHECK(CalledOnValidThread());
 353     if (engine_ == NULL) {
 354       NOTREACHED();
 355       return 0;
 356     }
 357     if (!IsDomainSane(domain))
 358       return 0;
 359
 360     int64 current_tick = GetCurrentTick();
 361     if (!used_ticks_.empty() && used_ticks_.back() > current_tick)
 362       current_tick = used_ticks_.back();
 363     for (bool first_iteration = true;; first_iteration = false) {
 364       if (current_tick < key_regeneration_tick_ + kKeyRegenerationHardTicks)
 365         break;
 366       if (!first_iteration)
 367         return 0;
 368       GenerateNewKey();
 369     }
 370
 371     // Forget outdated ticks if any.
 372     used_ticks_.erase(
 373         used_ticks_.begin(),
 374         std::lower_bound(used_ticks_.begin(), used_ticks_.end(),
 375                          current_tick - kGenerationWindowTicks + 1));
 376     DCHECK(used_ticks_.size() <= kGenerationWindowTicks + 0u);
 377     if (used_ticks_.size() >= kGenerationWindowTicks + 0u) {
 378       // Average speed of GeneratePassport calls exceeds limit.
 379       return 0;
 380     }
 381     for (int64 tick = current_tick;
 382         tick > current_tick - kGenerationWindowTicks;
 383         --tick) {
 384       int idx = static_cast<int>(used_ticks_.size()) -
 385           static_cast<int>(current_tick - tick + 1);
 386       if (idx < 0 || used_ticks_[idx] != tick) {
 387         DCHECK(used_ticks_.end() ==
 388             std::find(used_ticks_.begin(), used_ticks_.end(), tick));
 389         return tick;
 390       }
 391     }
 392     NOTREACHED();
 393     return 0;
 394   }
 395
 396   std::string GeneratePassport(
 397       const std::string& domain, const VarValueMap& map, int64 tick) {
 398     DCHECK(CalledOnValidThread());
 399     if (tick == 0) {
 400       tick = GetUnusedTick(domain);
 401       if (tick == 0)
 402         return std::string();
 403     }
 404     if (!IsVarValueMapSane(map))
 405       return std::string();
 406
 407     std::string result;
 408     CreatePassport(domain, map, tick, engine_.get(), &result);
 409     used_ticks_.insert(
 410         std::lower_bound(used_ticks_.begin(), used_ticks_.end(), tick), tick);
 411     return result;
 412   }
 413
 414  private:
 415   static int get_verification_window_ticks() {
 416     return InternalAuthVerification::get_verification_window_ticks();
 417   }
 418
 419   scoped_ptr<crypto::HMAC> engine_;
 420   int64 key_regeneration_tick_;
 421   std::deque<int64> used_ticks_;
 422
 423   DISALLOW_COPY_AND_ASSIGN(InternalAuthGenerationService);
 424 };
 425
 426 }  // namespace chrome
 427
 428 namespace {
 429
 430 static base::LazyInstance<chrome::InternalAuthGenerationService>
 431     g_generation_service = LAZY_INSTANCE_INITIALIZER;
 432
 433 }  // namespace
 434
 435 namespace chrome {
 436
 437 // static
 438 bool InternalAuthVerification::VerifyPassport(
 439     const std::string& passport,
 440     const std::string& domain,
 441     const VarValueMap& var_value_map) {
 442   base::AutoLock alk(g_verification_service_lock.Get());
 443   return g_verification_service.Get().VerifyPassport(
 444       passport, domain, var_value_map);
 445 }
 446
 447 // static
 448 void InternalAuthVerification::ChangeKey(const std::string& key) {
 449   base::AutoLock alk(g_verification_service_lock.Get());
 450   g_verification_service.Get().ChangeKey(key);
 451 };
 452
 453 // static
 454 int InternalAuthVerification::get_verification_window_ticks() {
 455   int candidate = kVerificationWindowTicks;
 456   if (verification_window_seconds_ > 0)
 457     candidate = verification_window_seconds_ *
 458         base::Time::kMicrosecondsPerSecond / kTickUs;
 459   return std::max(1, std::min(candidate, kVerificationWindowTicks));
 460 }
 461
 462 int InternalAuthVerification::verification_window_seconds_ = 0;
 463
 464 // static
 465 std::string InternalAuthGeneration::GeneratePassport(
 466     const std::string& domain, const VarValueMap& var_value_map) {
 467   return g_generation_service.Get().GeneratePassport(domain, var_value_map, 0);
 468 }
 469
 470 // static
 471 void InternalAuthGeneration::GenerateNewKey() {
 472   g_generation_service.Get().GenerateNewKey();
 473 }
 474
 475 }  // namespace chrome