chrome/browser/internal_auth.cc

   1 // Copyright 2012 The Chromium Authors
   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 <stddef.h>
   8 #include <stdint.h>
   9
  10 #include <algorithm>
  11 #include <limits>
  12 #include <memory>
  13
  14 #include "base/base64.h"
  15 #include "base/check.h"
  16 #include "base/containers/circular_deque.h"
  17 #include "base/containers/contains.h"
  18 #include "base/lazy_instance.h"
  19 #include "base/notreached.h"
  20 #include "base/rand_util.h"
  21 #include "base/ranges/algorithm.h"
  22 #include "base/strings/string_number_conversions.h"
  23 #include "base/strings/string_split.h"
  24 #include "base/strings/string_util.h"
  25 #include "base/synchronization/lock.h"
  26 #include "base/threading/thread_checker.h"
  27 #include "base/time/time.h"
  28 #include "base/values.h"
  29 #include "crypto/hmac.h"
  30
  31 namespace {
  32
  33 typedef std::map<std::string, std::string> VarValueMap;
  34
  35 // Size of a tick in microseconds. This determines upper bound for average
  36 // number of passports generated per time unit. This bound equals to
  37 // (kMicrosecondsPerSecond / TickUs) calls per second.
  38 const int64_t kTickUs = 10000;
  39
  40 // Verification window size in ticks; that means any passport expires in
  41 // (kVerificationWindowTicks * TickUs / kMicrosecondsPerSecond) seconds.
  42 const int kVerificationWindowTicks = 2000;
  43
  44 // Generation window determines how well we are able to cope with bursts of
  45 // GeneratePassport calls those exceed upper bound on average speed.
  46 const int kGenerationWindowTicks = 20;
  47
  48 // Makes no sense to compare other way round.
  49 static_assert(kGenerationWindowTicks <= kVerificationWindowTicks,
  50     "generation window should not be larger than the verification window");
  51 // We are not optimized for high value of kGenerationWindowTicks.
  52 static_assert(kGenerationWindowTicks < 30,
  53     "generation window should not be too large");
  54
  55 // Regenerate key after this number of ticks.
  56 const int kKeyRegenerationSoftTicks = 500000;
  57 // Reject passports if key has not been regenerated in that number of ticks.
  58 const int kKeyRegenerationHardTicks = kKeyRegenerationSoftTicks * 2;
  59
  60 // Limit for number of accepted var=value pairs. Feel free to bump this limit
  61 // higher once needed.
  62 const size_t kVarsLimit = 16;
  63
  64 // Limit for length of caller-supplied strings. Feel free to bump this limit
  65 // higher once needed.
  66 const size_t kStringLengthLimit = 512;
  67
  68 // Character used as a separator for construction of message to take HMAC of.
  69 // It is critical to validate all caller-supplied data (used to construct
  70 // message) to be clear of this separator because it could allow attacks.
  71 const char kItemSeparator = '\n';
  72
  73 // Character used for var=value separation.
  74 const char kVarValueSeparator = '=';
  75
  76 const size_t kKeySizeInBytes = 128 / 8;
  77 const size_t kHMACSizeInBytes = 256 / 8;
  78
  79 // Length of base64 string required to encode given number of raw octets.
  80 #define BASE64_PER_RAW(X) (X > 0 ? ((X - 1) / 3 + 1) * 4 : 0)
  81
  82 // Size of decimal string representing 64-bit tick.
  83 const size_t kTickStringLength = 20;
  84
  85 // A passport consists of 2 parts: HMAC and tick.
  86 const size_t kPassportSize =
  87     BASE64_PER_RAW(kHMACSizeInBytes) + kTickStringLength;
  88
  89 int64_t GetCurrentTick() {
  90   int64_t tick = base::Time::Now().ToInternalValue() / kTickUs;
  91   if (tick < kVerificationWindowTicks || tick < kKeyRegenerationHardTicks ||
  92       tick > std::numeric_limits<int64_t>::max() - kKeyRegenerationHardTicks) {
  93     return 0;
  94   }
  95   return tick;
  96 }
  97
  98 bool IsDomainSane(const std::string& domain) {
  99   return !domain.empty() &&
 100       domain.size() <= kStringLengthLimit &&
 101       base::IsStringUTF8(domain) &&
 102       domain.find_first_of(kItemSeparator) == std::string::npos;
 103 }
 104
 105 bool IsVarSane(const std::string& var) {
 106   static const char kAllowedChars[] =
 107       "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
 108       "abcdefghijklmnopqrstuvwxyz"
 109       "0123456789"
 110       "_";
 111   static_assert(
 112       sizeof(kAllowedChars) == 26 + 26 + 10 + 1 + 1, "some mess with chars");
 113   // We must not allow kItemSeparator in anything used as an input to construct
 114   // message to sign.
 115   DCHECK(!base::Contains(kAllowedChars, kItemSeparator));
 116   DCHECK(!base::Contains(kAllowedChars, kVarValueSeparator));
 117   return !var.empty() &&
 118       var.size() <= kStringLengthLimit &&
 119       base::IsStringASCII(var) &&
 120       var.find_first_not_of(kAllowedChars) == std::string::npos &&
 121       !base::IsAsciiDigit(var[0]);
 122 }
 123
 124 bool IsValueSane(const std::string& value) {
 125   return value.size() <= kStringLengthLimit &&
 126       base::IsStringUTF8(value) &&
 127       value.find_first_of(kItemSeparator) == std::string::npos;
 128 }
 129
 130 bool IsVarValueMapSane(const VarValueMap& map) {
 131   if (map.size() > kVarsLimit)
 132     return false;
 133   for (auto it = map.begin(); it != map.end(); ++it) {
 134     const std::string& var = it->first;
 135     const std::string& value = it->second;
 136     if (!IsVarSane(var) || !IsValueSane(value))
 137       return false;
 138   }
 139   return true;
 140 }
 141
 142 void ConvertVarValueMapToBlob(const VarValueMap& map, std::string* out) {
 143   out->clear();
 144   DCHECK(IsVarValueMapSane(map));
 145   for (auto it = map.begin(); it != map.end(); ++it)
 146     *out += it->first + kVarValueSeparator + it->second + kItemSeparator;
 147 }
 148
 149 void CreatePassport(const std::string& domain,
 150                     const VarValueMap& map,
 151                     int64_t tick,
 152                     const crypto::HMAC* engine,
 153                     std::string* out) {
 154   DCHECK(engine);
 155   DCHECK(out);
 156   DCHECK(IsDomainSane(domain));
 157   DCHECK(IsVarValueMapSane(map));
 158
 159   out->clear();
 160   std::string result(kPassportSize, '0');
 161
 162   std::string blob;
 163   blob = domain + kItemSeparator;
 164   std::string tmp;
 165   ConvertVarValueMapToBlob(map, &tmp);
 166   blob += tmp + kItemSeparator + base::NumberToString(tick);
 167
 168   std::string hmac;
 169   unsigned char* hmac_data = reinterpret_cast<unsigned char*>(
 170       base::WriteInto(&hmac, kHMACSizeInBytes + 1));
 171   if (!engine->Sign(blob, hmac_data, kHMACSizeInBytes)) {
 172     NOTREACHED();
 173     return;
 174   }
 175   std::string hmac_base64;
 176   base::Base64Encode(hmac, &hmac_base64);
 177   if (hmac_base64.size() != BASE64_PER_RAW(kHMACSizeInBytes)) {
 178     NOTREACHED();
 179     return;
 180   }
 181   DCHECK(hmac_base64.size() < result.size());
 182   base::ranges::copy(hmac_base64, result.begin());
 183
 184   std::string tick_decimal = base::NumberToString(tick);
 185   DCHECK(tick_decimal.size() <= kTickStringLength);
 186   base::ranges::copy(tick_decimal,
 187                      result.begin() + kPassportSize - tick_decimal.size());
 188
 189   out->swap(result);
 190 }
 191
 192 }  // namespace
 193
 194 class InternalAuthVerificationService {
 195  public:
 196   InternalAuthVerificationService()
 197       : key_change_tick_(0),
 198         dark_tick_(0) {
 199   }
 200
 201   InternalAuthVerificationService(const InternalAuthVerificationService&) =
 202       delete;
 203   InternalAuthVerificationService& operator=(
 204       const InternalAuthVerificationService&) = delete;
 205
 206   bool VerifyPassport(
 207       const std::string& passport,
 208       const std::string& domain,
 209       const VarValueMap& map) {
 210     int64_t current_tick = GetCurrentTick();
 211     int64_t tick = PreVerifyPassport(passport, domain, current_tick);
 212     if (tick == 0)
 213       return false;
 214     if (!IsVarValueMapSane(map))
 215       return false;
 216     std::string reference_passport;
 217     CreatePassport(domain, map, tick, engine_.get(), &reference_passport);
 218     if (passport != reference_passport) {
 219       // Consider old key.
 220       if (key_change_tick_ + get_verification_window_ticks() < tick) {
 221         return false;
 222       }
 223       if (old_key_.empty() || old_engine_ == nullptr)
 224         return false;
 225       CreatePassport(domain, map, tick, old_engine_.get(), &reference_passport);
 226       if (passport != reference_passport)
 227         return false;
 228     }
 229
 230     // Record used tick to prevent reuse.
 231     base::circular_deque<int64_t>::iterator it =
 232         std::lower_bound(used_ticks_.begin(), used_ticks_.end(), tick);
 233     DCHECK(it == used_ticks_.end() || *it != tick);
 234     used_ticks_.insert(it, tick);
 235
 236     // Consider pruning |used_ticks_|.
 237     if (used_ticks_.size() > 50) {
 238       dark_tick_ = std::max(dark_tick_,
 239           current_tick - get_verification_window_ticks());
 240       used_ticks_.erase(
 241           used_ticks_.begin(),
 242           std::lower_bound(used_ticks_.begin(), used_ticks_.end(),
 243                            dark_tick_ + 1));
 244     }
 245     return true;
 246   }
 247
 248   void ChangeKey(const std::string& key) {
 249     old_key_.swap(key_);
 250     key_.clear();
 251     old_engine_.swap(engine_);
 252     engine_.reset();
 253
 254     if (key.size() != kKeySizeInBytes)
 255       return;
 256     std::unique_ptr<crypto::HMAC> new_engine(
 257         new crypto::HMAC(crypto::HMAC::SHA256));
 258     if (!new_engine->Init(key))
 259       return;
 260     engine_.swap(new_engine);
 261     key_ = key;
 262     key_change_tick_ = GetCurrentTick();
 263   }
 264
 265  private:
 266   static int get_verification_window_ticks() {
 267     return InternalAuthVerification::get_verification_window_ticks();
 268   }
 269
 270   // Returns tick bound to given passport on success or zero on failure.
 271   int64_t PreVerifyPassport(const std::string& passport,
 272                             const std::string& domain,
 273                             int64_t current_tick) {
 274     if (passport.size() != kPassportSize || !base::IsStringASCII(passport) ||
 275         !IsDomainSane(domain) || current_tick <= dark_tick_ ||
 276         current_tick > key_change_tick_ + kKeyRegenerationHardTicks ||
 277         key_.empty() || engine_ == nullptr) {
 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_t 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   std::unique_ptr<crypto::HMAC> engine_;
 305   std::unique_ptr<crypto::HMAC> old_engine_;
 306
 307   // Tick at a time of recent key regeneration.
 308   int64_t 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   base::circular_deque<int64_t> 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_t dark_tick_;
 318 };
 319
 320 namespace {
 321
 322 static base::LazyInstance<InternalAuthVerificationService>::DestructorAtExit
 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 class InternalAuthGenerationService : public base::ThreadChecker {
 330  public:
 331   InternalAuthGenerationService() : key_regeneration_tick_(0) {
 332     GenerateNewKey();
 333   }
 334
 335   InternalAuthGenerationService(const InternalAuthGenerationService&) = delete;
 336   InternalAuthGenerationService& operator=(
 337       const InternalAuthGenerationService&) = delete;
 338
 339   void GenerateNewKey() {
 340     DCHECK(CalledOnValidThread());
 341     std::unique_ptr<crypto::HMAC> new_engine(
 342         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_t GetUnusedTick(const std::string& domain) {
 354     DCHECK(CalledOnValidThread());
 355     if (engine_ == nullptr) {
 356       NOTREACHED();
 357       return 0;
 358     }
 359     if (!IsDomainSane(domain))
 360       return 0;
 361
 362     int64_t 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_t tick = current_tick;
 384          tick > current_tick - kGenerationWindowTicks; --tick) {
 385       int idx = static_cast<int>(used_ticks_.size()) -
 386           static_cast<int>(current_tick - tick + 1);
 387       if (idx < 0 || used_ticks_[idx] != tick) {
 388         DCHECK(!base::Contains(used_ticks_, tick));
 389         return tick;
 390       }
 391     }
 392     NOTREACHED();
 393     return 0;
 394   }
 395
 396   std::string GeneratePassport(const std::string& domain,
 397                                const VarValueMap& map,
 398                                int64_t tick) {
 399     DCHECK(CalledOnValidThread());
 400     if (tick == 0) {
 401       tick = GetUnusedTick(domain);
 402       if (tick == 0)
 403         return std::string();
 404     }
 405     if (!IsVarValueMapSane(map))
 406       return std::string();
 407
 408     std::string result;
 409     CreatePassport(domain, map, tick, engine_.get(), &result);
 410     used_ticks_.insert(
 411         std::lower_bound(used_ticks_.begin(), used_ticks_.end(), tick), tick);
 412     return result;
 413   }
 414
 415  private:
 416   static int get_verification_window_ticks() {
 417     return InternalAuthVerification::get_verification_window_ticks();
 418   }
 419
 420   std::unique_ptr<crypto::HMAC> engine_;
 421   int64_t key_regeneration_tick_;
 422   base::circular_deque<int64_t> used_ticks_;
 423 };
 424
 425 namespace {
 426
 427 static base::LazyInstance<InternalAuthGenerationService>::DestructorAtExit
 428     g_generation_service = LAZY_INSTANCE_INITIALIZER;
 429
 430 }  // namespace
 431
 432 // static
 433 bool InternalAuthVerification::VerifyPassport(
 434     const std::string& passport,
 435     const std::string& domain,
 436     const VarValueMap& var_value_map) {
 437   base::AutoLock alk(g_verification_service_lock.Get());
 438   return g_verification_service.Get().VerifyPassport(
 439       passport, domain, var_value_map);
 440 }
 441
 442 // static
 443 void InternalAuthVerification::ChangeKey(const std::string& key) {
 444   base::AutoLock alk(g_verification_service_lock.Get());
 445   g_verification_service.Get().ChangeKey(key);
 446 }
 447
 448 // static
 449 int InternalAuthVerification::get_verification_window_ticks() {
 450   int candidate = kVerificationWindowTicks;
 451   if (verification_window_seconds_ > 0)
 452     candidate = verification_window_seconds_ *
 453         base::Time::kMicrosecondsPerSecond / kTickUs;
 454   return std::clamp(candidate, 1, kVerificationWindowTicks);
 455 }
 456
 457 int InternalAuthVerification::verification_window_seconds_ = 0;
 458
 459 // static
 460 std::string InternalAuthGeneration::GeneratePassport(
 461     const std::string& domain, const VarValueMap& var_value_map) {
 462   return g_generation_service.Get().GeneratePassport(domain, var_value_map, 0);
 463 }
 464
 465 // static
 466 void InternalAuthGeneration::GenerateNewKey() {
 467   g_generation_service.Get().GenerateNewKey();
 468 }