Private API for extensions like ssh-client that need access to TCP.

chrome/browser/internal_auth.cc

+// Copyright (c) 2011 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 <algorithm>
+#include <deque>
+
+#include "base/crypto/symmetric_key.h"
+#include "base/base64.h"
+#include "base/hmac.h"
+#include "base/lazy_instance.h"
+#include "base/synchronization/lock.h"
+#include "base/string_number_conversions.h"
+#include "base/string_split.h"
+#include "base/string_util.h"
+#include "base/time.h"
+#include "base/timer.h"
+#include "base/values.h"
+#include "content/browser/browser_thread.h"
+
+namespace {
+
+typedef std::map<std::string, std::string> VarValueMap;
+
+// Size of a tick in microseconds. This determines upper bound for average
+// number of tokens generated per time unit. This bound equals to
+// (base::Time::kMicrosecondsPerSecond / TickUs) calls per second.
+const int64 kTickUs = 10000;
+
+// Verification window size in ticks; that means any token expires in
+// (kVerificationWindowSizeTicks * TickUs / kMicrosecondsPerSecond) seconds.
+const int kVerificationWindowSizeTicks = 2000;
+
+// Generation window determines how well we are able to cope with bursts of
+// GenerateToken calls those exceed upper bound on average speed.
+const int kGenerationWindowSizeTicks = 20;
+
+// Makes no sense to compare other way round.
+COMPILE_ASSERT(kGenerationWindowSizeTicks <= kVerificationWindowSizeTicks,
+    makes_no_sense_to_have_generation_window_larger_than_verification_one);
+// We are not optimized for high value of kGenerationWindowSizeTicks.
+COMPILE_ASSERT(kGenerationWindowSizeTicks < 30, too_large_generation_window);
+
+// Regenerate key after this number of ticks.
+const int kKeyRegenerationSoftTicks = 500000;
+// Reject tokens 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 = '=';
+
+// Regular expression pattern imposed on variables.
+const char kVarPattern[] = "^[a-zA-Z_]*$";
+
+const size_t kKeySizeInBytes = 128 / 8;
+const int 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 token consists of 2 parts: HMAC and tick.
+const size_t kTokenSize = BASE64_PER_RAW(kHMACSizeInBytes) + kTickStringLength;
+
+// TODO(dilmah): move this into "base/string_split.h".
+bool SplitStringIntoKeyValue(
+    const std::string& line,
+    char key_value_delimiter,
+    std::string* key, std::string* value) {
+  key->clear();
+  value->clear();
+
+  size_t end_key_pos = line.find_first_of(key_value_delimiter);
+  if (end_key_pos == std::string::npos)
+    return false;  // no key
+  if (end_key_pos == 0)
+    return false;  // empty key
+  key->assign(line, 0, end_key_pos);
+
+  // Find the value string. Empty value is OK.
+  value->assign(line, end_key_pos + 1, std::string::npos);
+  return true;
+}
+
+int64 GetCurrentTick() {
+  int64 tick = base::Time::Now().ToInternalValue() / kTickUs;
+  if (tick < kVerificationWindowSizeTicks ||
+      tick < kKeyRegenerationHardTicks ||
+      tick > kint64max - kKeyRegenerationHardTicks) {
+    return 0;
+  }
+  return tick;
+}
+
+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 (var.size() > kStringLengthLimit ||
+        !IsStringASCII(var) ||
+        var.find_first_of(kItemSeparator) != std::string::npos ||
+        !MatchPattern(var, kVarPattern) ||
+        value.size() > kStringLengthLimit ||
+        !IsStringUTF8(value) ||
+        value.find_first_of(kItemSeparator) != std::string::npos) {
+      return false;
+    }
+  }
+  return true;
+}
+
+// Convert arguments list into var=value map. Returns true on success.
+bool ConvertArgListToVarValueMap(
+    const std::vector<std::string>& arg_list, VarValueMap* out) {
+  out->clear();
+  VarValueMap result;
+
+  if (arg_list.size() > kVarsLimit)
+    return false;
+  for (size_t i = 0; i < arg_list.size(); ++i) {
+    if (arg_list[i].size() > kStringLengthLimit)
+      return false;
+    if (!IsStringUTF8(arg_list[i]))
+      return false;
+    if (arg_list[i].find_first_of(kItemSeparator) != std::string::npos)
+      return false;
+
+    std::string var;
+    std::string value;
+    if (!SplitStringIntoKeyValue(
+        arg_list[i], kVarValueSeparator, &var, &value) ||
+            var.empty() ||
+            !MatchPattern(var, "^[a-zA-Z_]*$")) {
+      return false;
+    }
+    if (result.find(var) != result.end())
+      return false;
+    result[var] = value;
+  }
+  DCHECK(IsVarValueMapSane(result));
+  out->swap(result);
+  return true;
+}
+
+class VarValuePair {
+ public:
+  VarValuePair(const std::string& var, const std::string& value)
+      : var_(&var),
+        value_(&value) {
+    DCHECK(!var.empty());
+    DCHECK(var.size() <= kStringLengthLimit);
+    DCHECK(value.size() <= kStringLengthLimit);
+    DCHECK(IsStringASCII(var));
+    DCHECK(IsStringUTF8(value));
+    DCHECK(MatchPattern(var, "^[a-zA-Z_]*$"));
+    DCHECK(var.find_first_of(kItemSeparator) == std::string::npos);
+    DCHECK(value.find_first_of(kItemSeparator) == std::string::npos);
+  }
+
+  bool operator<(const VarValuePair& rhs) const {
+    DCHECK(this == &rhs || *var_ != *rhs.var_);
+    // Compare strings in deterministic way disregarding any locale setting.
+    return std::lexicographical_compare(
+        var_->c_str(), var_->c_str() + var_->size(),
+        rhs.var_->c_str(), rhs.var_->c_str() + rhs.var_->size());
+  }
+
+  bool operator==(const VarValuePair& rhs) const {
+    DCHECK(this == &rhs || *var_ != *rhs.var_);
+    return *var_ == *rhs.var_;
+  }
+
+  std::string var() const { return *var_; }
+  std::string value() const { return *value_; }
+
+ private:
+  const std::string* var_;
+  const std::string* value_;
+};
+
+void ConvertVarValueMapToBlob(const VarValueMap& map, std::string* out) {
+  out->clear();
+  DCHECK(IsVarValueMapSane(map));
+  std::vector<VarValuePair> var_values;
+  for (VarValueMap::const_iterator it = map.begin(); it != map.end(); ++it)
+    var_values.push_back(VarValuePair(it->first, it->second));
+  std::sort(var_values.begin(), var_values.end());
+  for (size_t i = 0; i < var_values.size(); ++i) {
+    *out += var_values[i].var() + kVarValueSeparator;
+    *out += var_values[i].value() + kItemSeparator;
+  }
+}
+
+bool IsHolderIdSane(const std::string& holder_id) {
+  return !holder_id.empty() &&
+      holder_id.size() <= kStringLengthLimit &&
+      IsStringUTF8(holder_id) &&
+      holder_id.find_first_of(kItemSeparator) == std::string::npos;
+}
+
+void CreateToken(
+    const std::string& holder_id,
+    const VarValueMap& map,
+    int64 tick,
+    const base::HMAC* engine,
+    std::string* out) {
+  DCHECK(engine);
+  DCHECK(out);
+  DCHECK(IsHolderIdSane(holder_id));
+  DCHECK(IsVarValueMapSane(map));
+
+  out->clear();
+  std::string result(kTokenSize, '0');
+
+  std::string blob;
+  blob = holder_id + kItemSeparator;
+  std::string tmp;
+  ConvertVarValueMapToBlob(map, &tmp);
+  blob += tmp + kItemSeparator + base::Uint64ToString(tick);
+
+  std::string hmac;
+  unsigned char* hmac_data = reinterpret_cast<unsigned char*>(
+      WriteInto(&hmac, kHMACSizeInBytes + 1));
+  if (!engine->Sign(blob, hmac_data, kHMACSizeInBytes)) {
+    NOTREACHED();
+    return;
+  }
+  std::string hmac_base64;
+  if (!base::Base64Encode(hmac, &hmac_base64)) {
+    NOTREACHED();
+    return;
+  }
+  if (hmac_base64.size() != BASE64_PER_RAW(kHMACSizeInBytes)) {
+    NOTREACHED();
+    return;
+  }
+  std::copy(hmac_base64.begin(), hmac_base64.end(), result.begin());
+
+  std::string tick_decimal = base::Uint64ToString(tick);
+  DCHECK(tick_decimal.size() <= kTickStringLength);
+  std::copy(
+      tick_decimal.begin(),
+      tick_decimal.end(),
+      hmac_base64.begin() + kTokenSize - tick_decimal.size());
+
+  out->swap(result);
+}
+
+class InternalAuthVerificationService {
+ public:
+  InternalAuthVerificationService()
+      : key_change_tick_(0),
+        dark_tick_(0) {
+  }
+
+  bool VerifyToken(
+      const std::string& token,
+      const std::string& holder_id,
+      const std::vector<std::string>& arg_list) {
+    int64 current_tick = GetCurrentTick();
+    int64 tick = PreVerifyToken(token, holder_id, current_tick);
+    if (tick == 0)
+      return false;
+
+    VarValueMap map;
+    if (!ConvertArgListToVarValueMap(arg_list, &map))
+      return false;
+    DCHECK(IsVarValueMapSane(map));
+    return VerifyToken(token, holder_id, map, true);
+  }
+
+  bool VerifyToken(
+      const std::string& token,
+      const std::string& holder_id,
+      const VarValueMap& map,
+      bool map_known_sane) {
+    int64 current_tick = GetCurrentTick();
+    int64 tick = PreVerifyToken(token, holder_id, current_tick);
+    if (tick == 0)
+      return false;
+    if (map_known_sane) {
+      DCHECK(IsVarValueMapSane(map));
+    } else {
+      if (!IsVarValueMapSane(map))
+        return false;
+    }
+    std::string reference_token;
+    CreateToken(holder_id, map, tick, engine_.get(), &reference_token);
+    if (token != reference_token) {
+      // Consider old key.
+      if (key_change_tick_ + kVerificationWindowSizeTicks < tick)
+        return false;
+      if (old_key_.empty() || old_engine_ == NULL)
+        return false;
+      CreateToken(holder_id, map, tick, old_engine_.get(), &reference_token);
+      if (token != reference_token)
+        return false;
+    }
+
+    // Record used tick to prevent reuse.
+    std::deque<int64>::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 - kVerificationWindowSizeTicks);
+      std::deque<int64>::iterator it = std::lower_bound(
+          used_ticks_.begin(), used_ticks_.end(), dark_tick_ + 1);
+      if (it != used_ticks_.end())
+        used_ticks_.erase(used_ticks_.begin(), ++it);
+    }
+    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;
+    engine_.reset(new base::HMAC(base::HMAC::SHA256));
+    engine_->Init(key);
+    key_ = key;
+    key_change_tick_ = GetCurrentTick();
+  }
+
+ private:
+  // Returns tick bound to given token on success or zero on failure.
+  int64 PreVerifyToken(
+    const std::string& token,
+    const std::string& holder_id,
+    int64 current_tick) {
+    if (token.size() != kTokenSize ||
+        !IsStringASCII(token) ||
+        !IsHolderIdSane(holder_id) ||
+        current_tick <= dark_tick_ ||
+        current_tick > key_change_tick_  + kKeyRegenerationHardTicks ||
+        key_.empty() ||
+        engine_ == NULL) {
+      return 0;
+    }
+
+    // Token consists of 2 parts: first hmac and then tick.
+    std::string tick_decimal = token.substr(BASE64_PER_RAW(kHMACSizeInBytes));
+    DCHECK(tick_decimal.size() == kTickStringLength);
+    int64 tick = 0;
+    if (!base::StringToInt64(tick_decimal, &tick) ||
+        tick <= dark_tick_ ||
+        tick > key_change_tick_ + kKeyRegenerationHardTicks ||
+        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 tokens during
+  // regeneration time.. Keys are regenerated on a regular basis.
+  std::string old_key_;
+
+  // Corresponding HMAC engines.
+  scoped_ptr<base::HMAC> engine_;
+  scoped_ptr<base::HMAC> old_engine_;
+
+  // Tick at a time of recent key regeneration.
+  int64 key_change_tick_;
+
+  // States that we forget information about some ticks used before this tick.
+  // Implies that we must not trust any tick less than or equal to dark tick.
+  int64 dark_tick_;
+
+  std::deque<int64> used_ticks_;
+
+  DISALLOW_COPY_AND_ASSIGN(InternalAuthVerificationService);
+};
+
+static base::LazyInstance<InternalAuthVerificationService>
+    g_verification_service(base::LINKER_INITIALIZED);
+static base::LazyInstance<base::Lock> g_verification_service_lock(
+    base::LINKER_INITIALIZED);
+
+class InternalAuthGenerationService {
+ public:
+  InternalAuthGenerationService() : key_regeneration_tick_(0) {
+    GenerateNewKey();
+  }
+
+  void GenerateNewKey() {
+    if (!timer_.IsRunning()) {
+      timer_.Start(
+          base::TimeDelta::FromMicroseconds(
+              kKeyRegenerationSoftTicks * kTickUs),
+          this,
+          &InternalAuthGenerationService::GenerateNewKey);
+    }
+
+    key_.clear();
+    engine_.reset(NULL);
+
+    unsigned char* key_data = reinterpret_cast<unsigned char*>(
+        WriteInto(&key_, kKeySizeInBytes + 1));
+    if (!base::SymmetricKey::GenerateRandomBytes(kKeySizeInBytes, key_data)) {
+      NOTREACHED();
+      key_ = std::string();
+      return;
+    }
+    engine_.reset(new base::HMAC(base::HMAC::SHA256));
+    engine_->Init(key_);
+    key_regeneration_tick_ = GetCurrentTick();
+    g_verification_service.Get().ChangeKey(key_);
+  }
+
+  // Returns zero on failure.
+  int64 GetUnusedTick(const std::string& holder_id) {
+    if (!timer_.IsRunning()) {
+      NOTREACHED();
+      return 0;
+    }
+    if (key_.empty() || engine_ == NULL) {
+      NOTREACHED();
+      return 0;
+    }
+    if (!IsHolderIdSane(holder_id))
+      return 0;
+
+    int64 current_tick = GetCurrentTick();
+    if (!used_ticks_.empty() && used_ticks_.back() > current_tick)
+      current_tick = used_ticks_.back();
+    if (current_tick > key_regeneration_tick_ + kKeyRegenerationHardTicks)
+      return 0;
+
+    std::deque<int64>::iterator it = std::lower_bound(
+        used_ticks_.begin(), used_ticks_.end(),
+        current_tick - kGenerationWindowSizeTicks + 1);
+    if (it != used_ticks_.end()) {
+      // Forget outdated ticks.
+      used_ticks_.erase(used_ticks_.begin(), ++it);
+    }
+    DCHECK(used_ticks_.size() <= kGenerationWindowSizeTicks + 0u);
+    if (used_ticks_.size() >= kGenerationWindowSizeTicks + 0u) {
+      // Average speed of GenerateToken calls exceeds limit.
+      return 0;
+    }
+    for (int64 tick = current_tick;
+        tick > current_tick - kGenerationWindowSizeTicks;
+        --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 GenerateToken(
+      const std::string holder_id,
+      const VarValueMap& map,
+      int64 tick,
+      bool map_known_sane) {
+    if (tick == 0) {
+      tick = GetUnusedTick(holder_id);
+      if (tick == 0)
+        return std::string();
+    }
+    if (map_known_sane) {
+      DCHECK(IsVarValueMapSane(map));
+    } else {
+      if (!IsVarValueMapSane(map))
+        return std::string();
+    }
+
+    std::string result;
+    CreateToken(holder_id, map, tick, engine_.get(), &result);
+    used_ticks_.insert(
+        std::lower_bound(used_ticks_.begin(), used_ticks_.end(), tick), tick);
+    return result;
+  }
+
+  std::string GenerateToken(
+      const std::string holder_id,
+      const std::vector<std::string>& arg_list) {
+    int64 tick = GetUnusedTick(holder_id);
+    if (tick == 0)
+      return std::string();
+
+    VarValueMap map;
+    if (!ConvertArgListToVarValueMap(arg_list, &map))
+      return false;
+    return GenerateToken(holder_id, map, tick, true);
+  }
+
+ private:
+  std::string key_;
+  scoped_ptr<base::HMAC> engine_;
+  base::RepeatingTimer<InternalAuthGenerationService> timer_;
+  int64 key_regeneration_tick_;
+  std::deque<int64> used_ticks_;
+
+  DISALLOW_COPY_AND_ASSIGN(InternalAuthGenerationService);
+};
+
+static base::LazyInstance<InternalAuthGenerationService> g_generation_service(
+    base::LINKER_INITIALIZED);
+
+}  // namespace
+
+namespace browser {
+
+// static
+bool InternalAuthVerification::VerifyToken(
+    const std::string& token,
+    const std::string& holder_id,
+    const std::vector<std::string>& arg_list) {
+  base::AutoLock alk(g_verification_service_lock.Get());
+  return g_verification_service.Get().VerifyToken(token, holder_id, arg_list);
+}
+
+// static
+bool InternalAuthVerification::VerifyToken(
+    const std::string& token,
+    const std::string& holder_id,
+    const VarValueMap& var_value_map) {
+  base::AutoLock alk(g_verification_service_lock.Get());
+  return g_verification_service.Get().VerifyToken(
+      token, holder_id, var_value_map, false);
+}
+
+// static
+void InternalAuthVerification::ChangeKey(const std::string& key) {
+  base::AutoLock alk(g_verification_service_lock.Get());
+  g_verification_service.Get().ChangeKey(key);
+};
+
+// static
+std::string InternalAuthGeneration::GenerateToken(
+    const std::string& holder_id,
+    const std::vector<std::string>& arg_list) {
+  DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
+  return g_generation_service.Get().GenerateToken(holder_id, arg_list);
+}
+
+// static
+std::string InternalAuthGeneration::GenerateToken(
+    const std::string& holder_id,
+    const VarValueMap& var_value_map) {
+  DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
+  return g_generation_service.Get().GenerateToken(
+      holder_id, var_value_map, 0, false);
+}
+
+}  // namespace browser
+