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 COMPILE_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.
  43 COMPILE_ASSERT(kGenerationWindowTicks < 30, too_large_generation_window);
  44
  45 // Regenerate key after this number of ticks.
  46 const int kKeyRegenerationSoftTicks = 500000;
  47 // Reject passports if key has not been regenerated in that number of ticks.
  48 const int kKeyRegenerationHardTicks = kKeyRegenerationSoftTicks * 2;
  49
  50 // Limit for number of accepted var=value pairs. Feel free to bump this limit
  51 // higher once needed.
  52 const size_t kVarsLimit = 16;
  53
  54 // Limit for length of caller-supplied strings. Feel free to bump this limit
  55 // higher once needed.
  56 const 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.
  61 const char kItemSeparator = '\n';
  62
  63 // Character used for var=value separation.
  64 const char kVarValueSeparator = '=';
  65
  66 const size_t kKeySizeInBytes = 128 / 8;
  67 const 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.
  73 const size_t kTickStringLength = 20;
  74
  75 // A passport consists of 2 parts: HMAC and tick.
  76 const size_t kPassportSize =
  77     BASE64_PER_RAW(kHMACSizeInBytes) + kTickStringLength;
  78
  79 int64 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
  89 bool IsDomainSane(const std::string& domain) {
  90   return !domain.empty() &&
  91       domain.size() <= kStringLengthLimit &&
  92       base::IsStringUTF8(domain) &&
  93       domain.find_first_of(kItemSeparator) == std::string::npos;
  94 }
  95
  96 bool 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       base::IsStringASCII(var) &&
 113       var.find_first_not_of(kAllowedChars) == std::string::npos &&
 114       !IsAsciiDigit(var[0]);
 115 }
 116
 117 bool IsValueSane(const std::string& value) {
 118   return value.size() <= kStringLengthLimit &&
 119       base::IsStringUTF8(value) &&
 120       value.find_first_of(kItemSeparator) == std::string::npos;
 121 }
 122
 123 bool 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
 135 void 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
 142 void 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   base::Base64Encode(hmac, &hmac_base64);
 170   if (hmac_base64.size() != BASE64_PER_RAW(kHMACSizeInBytes)) {
 171     NOTREACHED();
 172     return;
 173   }
 174   DCHECK(hmac_base64.size() < result.size());
 175   std::copy(hmac_base64.begin(), hmac_base64.end(), result.begin());
 176
 177   std::string tick_decimal = base::Uint64ToString(tick);
 178   DCHECK(tick_decimal.size() <= kTickStringLength);
 179   std::copy(
 180       tick_decimal.begin(),
 181       tick_decimal.end(),
 182       result.begin() + kPassportSize - tick_decimal.size());
 183
 184   out->swap(result);
 185 }
 186
 187 }  // namespace
 188
 189 namespace chrome {
 190
 191 class InternalAuthVerificationService {
 192  public:
 193   InternalAuthVerificationService()
 194       : key_change_tick_(0),
 195         dark_tick_(0) {
 196   }
 197
 198   bool VerifyPassport(
 199       const std::string& passport,
 200       const std::string& domain,
 201       const VarValueMap& map) {
 202     int64 current_tick = GetCurrentTick();
 203     int64 tick = PreVerifyPassport(passport, domain, current_tick);
 204     if (tick == 0)
 205       return false;
 206     if (!IsVarValueMapSane(map))
 207       return false;
 208     std::string reference_passport;
 209     CreatePassport(domain, map, tick, engine_.get(), &reference_passport);
 210     if (passport != reference_passport) {
 211       // Consider old key.
 212       if (key_change_tick_ + get_verification_window_ticks() < tick) {
 213         return false;
 214       }
 215       if (old_key_.empty() || old_engine_ == NULL)
 216         return false;
 217       CreatePassport(domain, map, tick, old_engine_.get(), &reference_passport);
 218       if (passport != reference_passport)
 219         return false;
 220     }
 221
 222     // Record used tick to prevent reuse.
 223     std::deque<int64>::iterator it = std::lower_bound(
 224         used_ticks_.begin(), used_ticks_.end(), tick);
 225     DCHECK(it == used_ticks_.end() || *it != tick);
 226     used_ticks_.insert(it, tick);
 227
 228     // Consider pruning |used_ticks_|.
 229     if (used_ticks_.size() > 50) {
 230       dark_tick_ = std::max(dark_tick_,
 231           current_tick - get_verification_window_ticks());
 232       used_ticks_.erase(
 233           used_ticks_.begin(),
 234           std::lower_bound(used_ticks_.begin(), used_ticks_.end(),
 235                            dark_tick_ + 1));
 236     }
 237     return true;
 238   }
 239
 240   void ChangeKey(const std::string& key) {
 241     old_key_.swap(key_);
 242     key_.clear();
 243     old_engine_.swap(engine_);
 244     engine_.reset(NULL);
 245
 246     if (key.size() != kKeySizeInBytes)
 247       return;
 248     scoped_ptr<crypto::HMAC> new_engine(
 249         new crypto::HMAC(crypto::HMAC::SHA256));
 250     if (!new_engine->Init(key))
 251       return;
 252     engine_.swap(new_engine);
 253     key_ = key;
 254     key_change_tick_ = GetCurrentTick();
 255   }
 256
 257  private:
 258   static int get_verification_window_ticks() {
 259     return InternalAuthVerification::get_verification_window_ticks();
 260   }
 261
 262   // Returns tick bound to given passport on success or zero on failure.
 263   int64 PreVerifyPassport(
 264     const std::string& passport,
 265     const std::string& domain,
 266     int64 current_tick) {
 267     if (passport.size() != kPassportSize ||
 268         !base::IsStringASCII(passport) ||
 269         !IsDomainSane(domain) ||
 270         current_tick <= dark_tick_ ||
 271         current_tick > key_change_tick_  + kKeyRegenerationHardTicks ||
 272         key_.empty() ||
 273         engine_ == NULL) {
 274       return 0;
 275     }
 276
 277     // Passport consists of 2 parts: first hmac and then tick.
 278     std::string tick_decimal =
 279         passport.substr(BASE64_PER_RAW(kHMACSizeInBytes));
 280     DCHECK(tick_decimal.size() == kTickStringLength);
 281     int64 tick = 0;
 282     if (!base::StringToInt64(tick_decimal, &tick) ||
 283         tick <= dark_tick_ ||
 284         tick > key_change_tick_ + kKeyRegenerationHardTicks ||
 285         tick < current_tick - get_verification_window_ticks() ||
 286         std::binary_search(used_ticks_.begin(), used_ticks_.end(), tick)) {
 287       return 0;
 288     }
 289     return tick;
 290   }
 291
 292   // Current key.
 293   std::string key_;
 294
 295   // We keep previous key in order to be able to verify passports during
 296   // regeneration time.  Keys are regenerated on a regular basis.
 297   std::string old_key_;
 298
 299   // Corresponding HMAC engines.
 300   scoped_ptr<crypto::HMAC> engine_;
 301   scoped_ptr<crypto::HMAC> old_engine_;
 302
 303   // Tick at a time of recent key regeneration.
 304   int64 key_change_tick_;
 305
 306   // Keeps track of ticks of successfully verified passports to prevent their
 307   // reuse. Size of this container is kept reasonably low by purging outdated
 308   // ticks.
 309   std::deque<int64> used_ticks_;
 310
 311   // Some ticks before |dark_tick_| were purged from |used_ticks_| container.
 312   // That means that we must not trust any tick less than or equal to dark tick.
 313   int64 dark_tick_;
 314
 315   DISALLOW_COPY_AND_ASSIGN(InternalAuthVerificationService);
 316 };
 317
 318 }  // namespace chrome
 319
 320 namespace {
 321
 322 static base::LazyInstance<chrome::InternalAuthVerificationService>
 323     g_verification_service = LAZY_INSTANCE_INITIALIZER;
 324 static base::LazyInstance<base::Lock>::Leaky
 325     g_verification_service_lock = LAZY_INSTANCE_INITIALIZER;
 326
 327 }  // namespace
 328
 329 namespace chrome {
 330
 331 class InternalAuthGenerationService : public base::ThreadChecker {
 332  public:
 333   InternalAuthGenerationService() : key_regeneration_tick_(0) {
 334     GenerateNewKey();
 335   }
 336
 337   void GenerateNewKey() {
 338     DCHECK(CalledOnValidThread());
 339     scoped_ptr<crypto::HMAC> new_engine(new crypto::HMAC(crypto::HMAC::SHA256));
 340     std::string key = base::RandBytesAsString(kKeySizeInBytes);
 341     if (!new_engine->Init(key))
 342       return;
 343     engine_.swap(new_engine);
 344     key_regeneration_tick_ = GetCurrentTick();
 345     g_verification_service.Get().ChangeKey(key);
 346     std::fill(key.begin(), key.end(), 0);
 347   }
 348
 349   // Returns zero on failure.
 350   int64 GetUnusedTick(const std::string& domain) {
 351     DCHECK(CalledOnValidThread());
 352     if (engine_ == NULL) {
 353       NOTREACHED();
 354       return 0;
 355     }
 356     if (!IsDomainSane(domain))
 357       return 0;
 358
 359     int64 current_tick = GetCurrentTick();
 360     if (!used_ticks_.empty() && used_ticks_.back() > current_tick)
 361       current_tick = used_ticks_.back();
 362     for (bool first_iteration = true;; first_iteration = false) {
 363       if (current_tick < key_regeneration_tick_ + kKeyRegenerationHardTicks)
 364         break;
 365       if (!first_iteration)
 366         return 0;
 367       GenerateNewKey();
 368     }
 369
 370     // Forget outdated ticks if any.
 371     used_ticks_.erase(
 372         used_ticks_.begin(),
 373         std::lower_bound(used_ticks_.begin(), used_ticks_.end(),
 374                          current_tick - kGenerationWindowTicks + 1));
 375     DCHECK(used_ticks_.size() <= kGenerationWindowTicks + 0u);
 376     if (used_ticks_.size() >= kGenerationWindowTicks + 0u) {
 377       // Average speed of GeneratePassport calls exceeds limit.
 378       return 0;
 379     }
 380     for (int64 tick = current_tick;
 381         tick > current_tick - kGenerationWindowTicks;
 382         --tick) {
 383       int idx = static_cast<int>(used_ticks_.size()) -
 384           static_cast<int>(current_tick - tick + 1);
 385       if (idx < 0 || used_ticks_[idx] != tick) {
 386         DCHECK(used_ticks_.end() ==
 387             std::find(used_ticks_.begin(), used_ticks_.end(), tick));
 388         return tick;
 389       }
 390     }
 391     NOTREACHED();
 392     return 0;
 393   }
 394
 395   std::string GeneratePassport(
 396       const std::string& domain, const VarValueMap& map, int64 tick) {
 397     DCHECK(CalledOnValidThread());
 398     if (tick == 0) {
 399       tick = GetUnusedTick(domain);
 400       if (tick == 0)
 401         return std::string();
 402     }
 403     if (!IsVarValueMapSane(map))
 404       return std::string();
 405
 406     std::string result;
 407     CreatePassport(domain, map, tick, engine_.get(), &result);
 408     used_ticks_.insert(
 409         std::lower_bound(used_ticks_.begin(), used_ticks_.end(), tick), tick);
 410     return result;
 411   }
 412
 413  private:
 414   static int get_verification_window_ticks() {
 415     return InternalAuthVerification::get_verification_window_ticks();
 416   }
 417
 418   scoped_ptr<crypto::HMAC> engine_;
 419   int64 key_regeneration_tick_;
 420   std::deque<int64> used_ticks_;
 421
 422   DISALLOW_COPY_AND_ASSIGN(InternalAuthGenerationService);
 423 };
 424
 425 }  // namespace chrome
 426
 427 namespace {
 428
 429 static base::LazyInstance<chrome::InternalAuthGenerationService>
 430     g_generation_service = LAZY_INSTANCE_INITIALIZER;
 431
 432 }  // namespace
 433
 434 namespace chrome {
 435
 436 // static
 437 bool InternalAuthVerification::VerifyPassport(
 438     const std::string& passport,
 439     const std::string& domain,
 440     const VarValueMap& var_value_map) {
 441   base::AutoLock alk(g_verification_service_lock.Get());
 442   return g_verification_service.Get().VerifyPassport(
 443       passport, domain, var_value_map);
 444 }
 445
 446 // static
 447 void InternalAuthVerification::ChangeKey(const std::string& key) {
 448   base::AutoLock alk(g_verification_service_lock.Get());
 449   g_verification_service.Get().ChangeKey(key);
 450 };
 451
 452 // static
 453 int InternalAuthVerification::get_verification_window_ticks() {
 454   int candidate = kVerificationWindowTicks;
 455   if (verification_window_seconds_ > 0)
 456     candidate = verification_window_seconds_ *
 457         base::Time::kMicrosecondsPerSecond / kTickUs;
 458   return std::max(1, std::min(candidate, kVerificationWindowTicks));
 459 }
 460
 461 int InternalAuthVerification::verification_window_seconds_ = 0;
 462
 463 // static
 464 std::string InternalAuthGeneration::GeneratePassport(
 465     const std::string& domain, const VarValueMap& var_value_map) {
 466   return g_generation_service.Get().GeneratePassport(domain, var_value_map, 0);
 467 }
 468
 469 // static
 470 void InternalAuthGeneration::GenerateNewKey() {
 471   g_generation_service.Get().GenerateNewKey();
 472 }
 473
 474 }  // namespace chrome