blob: f97baeca7c786ffe3bca476eaf0abb7eb02a8f1f [file] [log] [blame]
// Copyright (c) 2012 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include "chrome/browser/internal_auth.h"
#include <stdint.h>
#include <algorithm>
#include <deque>
#include <limits>
#include "base/base64.h"
#include "base/lazy_instance.h"
#include "base/rand_util.h"
#include "base/strings/string_number_conversions.h"
#include "base/strings/string_split.h"
#include "base/strings/string_util.h"
#include "base/synchronization/lock.h"
#include "base/threading/thread_checker.h"
#include "base/time/time.h"
#include "base/values.h"
#include "crypto/hmac.h"
namespace {
typedef std::map<std::string, std::string> VarValueMap;
// Size of a tick in microseconds. This determines upper bound for average
// number of passports generated per time unit. This bound equals to
// (kMicrosecondsPerSecond / TickUs) calls per second.
const int64_t kTickUs = 10000;
// Verification window size in ticks; that means any passport expires in
// (kVerificationWindowTicks * TickUs / kMicrosecondsPerSecond) seconds.
const int kVerificationWindowTicks = 2000;
// Generation window determines how well we are able to cope with bursts of
// GeneratePassport calls those exceed upper bound on average speed.
const int kGenerationWindowTicks = 20;
// Makes no sense to compare other way round.
static_assert(kGenerationWindowTicks <= kVerificationWindowTicks,
"generation window should not be larger than the verification window");
// We are not optimized for high value of kGenerationWindowTicks.
static_assert(kGenerationWindowTicks < 30,
"generation window should not be too large");
// Regenerate key after this number of ticks.
const int kKeyRegenerationSoftTicks = 500000;
// Reject passports if key has not been regenerated in that number of ticks.
const int kKeyRegenerationHardTicks = kKeyRegenerationSoftTicks * 2;
// Limit for number of accepted var=value pairs. Feel free to bump this limit
// higher once needed.
const size_t kVarsLimit = 16;
// Limit for length of caller-supplied strings. Feel free to bump this limit
// higher once needed.
const size_t kStringLengthLimit = 512;
// Character used as a separator for construction of message to take HMAC of.
// It is critical to validate all caller-supplied data (used to construct
// message) to be clear of this separator because it could allow attacks.
const char kItemSeparator = '\n';
// Character used for var=value separation.
const char kVarValueSeparator = '=';
const size_t kKeySizeInBytes = 128 / 8;
const size_t kHMACSizeInBytes = 256 / 8;
// Length of base64 string required to encode given number of raw octets.
#define BASE64_PER_RAW(X) (X > 0 ? ((X - 1) / 3 + 1) * 4 : 0)
// Size of decimal string representing 64-bit tick.
const size_t kTickStringLength = 20;
// A passport consists of 2 parts: HMAC and tick.
const size_t kPassportSize =
BASE64_PER_RAW(kHMACSizeInBytes) + kTickStringLength;
int64_t GetCurrentTick() {
int64_t tick = base::Time::Now().ToInternalValue() / kTickUs;
if (tick < kVerificationWindowTicks || tick < kKeyRegenerationHardTicks ||
tick > std::numeric_limits<int64_t>::max() - kKeyRegenerationHardTicks) {
return 0;
}
return tick;
}
bool IsDomainSane(const std::string& domain) {
return !domain.empty() &&
domain.size() <= kStringLengthLimit &&
base::IsStringUTF8(domain) &&
domain.find_first_of(kItemSeparator) == std::string::npos;
}
bool IsVarSane(const std::string& var) {
static const char kAllowedChars[] =
"ABCDEFGHIJKLMNOPQRSTUVWXYZ"
"abcdefghijklmnopqrstuvwxyz"
"0123456789"
"_";
static_assert(
sizeof(kAllowedChars) == 26 + 26 + 10 + 1 + 1, "some mess with chars");
// We must not allow kItemSeparator in anything used as an input to construct
// message to sign.
DCHECK(std::find(kAllowedChars, kAllowedChars + arraysize(kAllowedChars),
kItemSeparator) == kAllowedChars + arraysize(kAllowedChars));
DCHECK(std::find(kAllowedChars, kAllowedChars + arraysize(kAllowedChars),
kVarValueSeparator) == kAllowedChars + arraysize(kAllowedChars));
return !var.empty() &&
var.size() <= kStringLengthLimit &&
base::IsStringASCII(var) &&
var.find_first_not_of(kAllowedChars) == std::string::npos &&
!base::IsAsciiDigit(var[0]);
}
bool IsValueSane(const std::string& value) {
return value.size() <= kStringLengthLimit &&
base::IsStringUTF8(value) &&
value.find_first_of(kItemSeparator) == std::string::npos;
}
bool IsVarValueMapSane(const VarValueMap& map) {
if (map.size() > kVarsLimit)
return false;
for (VarValueMap::const_iterator it = map.begin(); it != map.end(); ++it) {
const std::string& var = it->first;
const std::string& value = it->second;
if (!IsVarSane(var) || !IsValueSane(value))
return false;
}
return true;
}
void ConvertVarValueMapToBlob(const VarValueMap& map, std::string* out) {
out->clear();
DCHECK(IsVarValueMapSane(map));
for (VarValueMap::const_iterator it = map.begin(); it != map.end(); ++it)
*out += it->first + kVarValueSeparator + it->second + kItemSeparator;
}
void CreatePassport(const std::string& domain,
const VarValueMap& map,
int64_t tick,
const crypto::HMAC* engine,
std::string* out) {
DCHECK(engine);
DCHECK(out);
DCHECK(IsDomainSane(domain));
DCHECK(IsVarValueMapSane(map));
out->clear();
std::string result(kPassportSize, '0');
std::string blob;
blob = domain + kItemSeparator;
std::string tmp;
ConvertVarValueMapToBlob(map, &tmp);
blob += tmp + kItemSeparator + base::Int64ToString(tick);
std::string hmac;
unsigned char* hmac_data = reinterpret_cast<unsigned char*>(
base::WriteInto(&hmac, kHMACSizeInBytes + 1));
if (!engine->Sign(blob, hmac_data, kHMACSizeInBytes)) {
NOTREACHED();
return;
}
std::string hmac_base64;
base::Base64Encode(hmac, &hmac_base64);
if (hmac_base64.size() != BASE64_PER_RAW(kHMACSizeInBytes)) {
NOTREACHED();
return;
}
DCHECK(hmac_base64.size() < result.size());
std::copy(hmac_base64.begin(), hmac_base64.end(), result.begin());
std::string tick_decimal = base::Int64ToString(tick);
DCHECK(tick_decimal.size() <= kTickStringLength);
std::copy(
tick_decimal.begin(),
tick_decimal.end(),
result.begin() + kPassportSize - tick_decimal.size());
out->swap(result);
}
} // namespace
namespace chrome {
class InternalAuthVerificationService {
public:
InternalAuthVerificationService()
: key_change_tick_(0),
dark_tick_(0) {
}
bool VerifyPassport(
const std::string& passport,
const std::string& domain,
const VarValueMap& map) {
int64_t current_tick = GetCurrentTick();
int64_t tick = PreVerifyPassport(passport, domain, current_tick);
if (tick == 0)
return false;
if (!IsVarValueMapSane(map))
return false;
std::string reference_passport;
CreatePassport(domain, map, tick, engine_.get(), &reference_passport);
if (passport != reference_passport) {
// Consider old key.
if (key_change_tick_ + get_verification_window_ticks() < tick) {
return false;
}
if (old_key_.empty() || old_engine_ == NULL)
return false;
CreatePassport(domain, map, tick, old_engine_.get(), &reference_passport);
if (passport != reference_passport)
return false;
}
// Record used tick to prevent reuse.
std::deque<int64_t>::iterator it =
std::lower_bound(used_ticks_.begin(), used_ticks_.end(), tick);
DCHECK(it == used_ticks_.end() || *it != tick);
used_ticks_.insert(it, tick);
// Consider pruning |used_ticks_|.
if (used_ticks_.size() > 50) {
dark_tick_ = std::max(dark_tick_,
current_tick - get_verification_window_ticks());
used_ticks_.erase(
used_ticks_.begin(),
std::lower_bound(used_ticks_.begin(), used_ticks_.end(),
dark_tick_ + 1));
}
return true;
}
void ChangeKey(const std::string& key) {
old_key_.swap(key_);
key_.clear();
old_engine_.swap(engine_);
engine_.reset(NULL);
if (key.size() != kKeySizeInBytes)
return;
scoped_ptr<crypto::HMAC> new_engine(
new crypto::HMAC(crypto::HMAC::SHA256));
if (!new_engine->Init(key))
return;
engine_.swap(new_engine);
key_ = key;
key_change_tick_ = GetCurrentTick();
}
private:
static int get_verification_window_ticks() {
return InternalAuthVerification::get_verification_window_ticks();
}
// Returns tick bound to given passport on success or zero on failure.
int64_t PreVerifyPassport(const std::string& passport,
const std::string& domain,
int64_t current_tick) {
if (passport.size() != kPassportSize ||
!base::IsStringASCII(passport) ||
!IsDomainSane(domain) ||
current_tick <= dark_tick_ ||
current_tick > key_change_tick_ + kKeyRegenerationHardTicks ||
key_.empty() ||
engine_ == NULL) {
return 0;
}
// Passport consists of 2 parts: first hmac and then tick.
std::string tick_decimal =
passport.substr(BASE64_PER_RAW(kHMACSizeInBytes));
DCHECK(tick_decimal.size() == kTickStringLength);
int64_t tick = 0;
if (!base::StringToInt64(tick_decimal, &tick) ||
tick <= dark_tick_ ||
tick > key_change_tick_ + kKeyRegenerationHardTicks ||
tick < current_tick - get_verification_window_ticks() ||
std::binary_search(used_ticks_.begin(), used_ticks_.end(), tick)) {
return 0;
}
return tick;
}
// Current key.
std::string key_;
// We keep previous key in order to be able to verify passports during
// regeneration time. Keys are regenerated on a regular basis.
std::string old_key_;
// Corresponding HMAC engines.
scoped_ptr<crypto::HMAC> engine_;
scoped_ptr<crypto::HMAC> old_engine_;
// Tick at a time of recent key regeneration.
int64_t key_change_tick_;
// Keeps track of ticks of successfully verified passports to prevent their
// reuse. Size of this container is kept reasonably low by purging outdated
// ticks.
std::deque<int64_t> used_ticks_;
// Some ticks before |dark_tick_| were purged from |used_ticks_| container.
// That means that we must not trust any tick less than or equal to dark tick.
int64_t dark_tick_;
DISALLOW_COPY_AND_ASSIGN(InternalAuthVerificationService);
};
} // namespace chrome
namespace {
static base::LazyInstance<chrome::InternalAuthVerificationService>
g_verification_service = LAZY_INSTANCE_INITIALIZER;
static base::LazyInstance<base::Lock>::Leaky
g_verification_service_lock = LAZY_INSTANCE_INITIALIZER;
} // namespace
namespace chrome {
class InternalAuthGenerationService : public base::ThreadChecker {
public:
InternalAuthGenerationService() : key_regeneration_tick_(0) {
GenerateNewKey();
}
void GenerateNewKey() {
DCHECK(CalledOnValidThread());
scoped_ptr<crypto::HMAC> new_engine(new crypto::HMAC(crypto::HMAC::SHA256));
std::string key = base::RandBytesAsString(kKeySizeInBytes);
if (!new_engine->Init(key))
return;
engine_.swap(new_engine);
key_regeneration_tick_ = GetCurrentTick();
g_verification_service.Get().ChangeKey(key);
std::fill(key.begin(), key.end(), 0);
}
// Returns zero on failure.
int64_t GetUnusedTick(const std::string& domain) {
DCHECK(CalledOnValidThread());
if (engine_ == NULL) {
NOTREACHED();
return 0;
}
if (!IsDomainSane(domain))
return 0;
int64_t current_tick = GetCurrentTick();
if (!used_ticks_.empty() && used_ticks_.back() > current_tick)
current_tick = used_ticks_.back();
for (bool first_iteration = true;; first_iteration = false) {
if (current_tick < key_regeneration_tick_ + kKeyRegenerationHardTicks)
break;
if (!first_iteration)
return 0;
GenerateNewKey();
}
// Forget outdated ticks if any.
used_ticks_.erase(
used_ticks_.begin(),
std::lower_bound(used_ticks_.begin(), used_ticks_.end(),
current_tick - kGenerationWindowTicks + 1));
DCHECK(used_ticks_.size() <= kGenerationWindowTicks + 0u);
if (used_ticks_.size() >= kGenerationWindowTicks + 0u) {
// Average speed of GeneratePassport calls exceeds limit.
return 0;
}
for (int64_t tick = current_tick;
tick > current_tick - kGenerationWindowTicks; --tick) {
int idx = static_cast<int>(used_ticks_.size()) -
static_cast<int>(current_tick - tick + 1);
if (idx < 0 || used_ticks_[idx] != tick) {
DCHECK(used_ticks_.end() ==
std::find(used_ticks_.begin(), used_ticks_.end(), tick));
return tick;
}
}
NOTREACHED();
return 0;
}
std::string GeneratePassport(const std::string& domain,
const VarValueMap& map,
int64_t tick) {
DCHECK(CalledOnValidThread());
if (tick == 0) {
tick = GetUnusedTick(domain);
if (tick == 0)
return std::string();
}
if (!IsVarValueMapSane(map))
return std::string();
std::string result;
CreatePassport(domain, map, tick, engine_.get(), &result);
used_ticks_.insert(
std::lower_bound(used_ticks_.begin(), used_ticks_.end(), tick), tick);
return result;
}
private:
static int get_verification_window_ticks() {
return InternalAuthVerification::get_verification_window_ticks();
}
scoped_ptr<crypto::HMAC> engine_;
int64_t key_regeneration_tick_;
std::deque<int64_t> used_ticks_;
DISALLOW_COPY_AND_ASSIGN(InternalAuthGenerationService);
};
} // namespace chrome
namespace {
static base::LazyInstance<chrome::InternalAuthGenerationService>
g_generation_service = LAZY_INSTANCE_INITIALIZER;
} // namespace
namespace chrome {
// static
bool InternalAuthVerification::VerifyPassport(
const std::string& passport,
const std::string& domain,
const VarValueMap& var_value_map) {
base::AutoLock alk(g_verification_service_lock.Get());
return g_verification_service.Get().VerifyPassport(
passport, domain, var_value_map);
}
// static
void InternalAuthVerification::ChangeKey(const std::string& key) {
base::AutoLock alk(g_verification_service_lock.Get());
g_verification_service.Get().ChangeKey(key);
}
// static
int InternalAuthVerification::get_verification_window_ticks() {
int candidate = kVerificationWindowTicks;
if (verification_window_seconds_ > 0)
candidate = verification_window_seconds_ *
base::Time::kMicrosecondsPerSecond / kTickUs;
return std::max(1, std::min(candidate, kVerificationWindowTicks));
}
int InternalAuthVerification::verification_window_seconds_ = 0;
// static
std::string InternalAuthGeneration::GeneratePassport(
const std::string& domain, const VarValueMap& var_value_map) {
return g_generation_service.Get().GeneratePassport(domain, var_value_map, 0);
}
// static
void InternalAuthGeneration::GenerateNewKey() {
g_generation_service.Get().GenerateNewKey();
}
} // namespace chrome