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.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       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       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       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   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
 192 namespace chrome {
 193
 194 class 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
 323 namespace {
 324
 325 static base::LazyInstance<chrome::InternalAuthVerificationService>
 326     g_verification_service = LAZY_INSTANCE_INITIALIZER;
 327 static base::LazyInstance<base::Lock>::Leaky
 328     g_verification_service_lock = LAZY_INSTANCE_INITIALIZER;
 329
 330 }  // namespace
 331
 332 namespace chrome {
 333
 334 class 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
 430 namespace {
 431
 432 static base::LazyInstance<chrome::InternalAuthGenerationService>
 433     g_generation_service = LAZY_INSTANCE_INITIALIZER;
 434
 435 }  // namespace
 436
 437 namespace chrome {
 438
 439 // static
 440 bool 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
 450 void 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
 456 int 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
 464 int InternalAuthVerification::verification_window_seconds_ = 0;
 465
 466 // static
 467 std::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
 473 void InternalAuthGeneration::GenerateNewKey() {
 474   g_generation_service.Get().GenerateNewKey();
 475 }
 476
 477 }  // namespace chrome