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
22namespace {
23
24typedef 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.
29const int64 kTickUs = 10000;
30
31// Verification window size in ticks; that means any passport expires in
32// (kVerificationWindowTicks * TickUs / kMicrosecondsPerSecond) seconds.
33const 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.
37const int kGenerationWindowTicks = 20;
38
39// Makes no sense to compare other way round.
40COMPILE_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.
43COMPILE_ASSERT(kGenerationWindowTicks < 30, too_large_generation_window);
44
45// Regenerate key after this number of ticks.
46const int kKeyRegenerationSoftTicks = 500000;
47// Reject passports if key has not been regenerated in that number of ticks.
48const int kKeyRegenerationHardTicks = kKeyRegenerationSoftTicks * 2;
49
50// Limit for number of accepted var=value pairs. Feel free to bump this limit
51// higher once needed.
52const size_t kVarsLimit = 16;
53
54// Limit for length of caller-supplied strings. Feel free to bump this limit
55// higher once needed.
56const 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.
61const char kItemSeparator = '\n';
62
63// Character used for var=value separation.
64const char kVarValueSeparator = '=';
65
66const size_t kKeySizeInBytes = 128 / 8;
67const 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.
73const size_t kTickStringLength = 20;
74
75// A passport consists of 2 parts: HMAC and tick.
76const size_t kPassportSize =
77    BASE64_PER_RAW(kHMACSizeInBytes) + kTickStringLength;
78
79int64 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
89bool 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
96bool 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
117bool IsValueSane(const std::string& value) {
118  return value.size() <= kStringLengthLimit &&
119      IsStringUTF8(value) &&
120      value.find_first_of(kItemSeparator) == std::string::npos;
121}
122
123bool 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
135void 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
142void 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
192namespace chrome {
193
194class 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
323namespace {
324
325static base::LazyInstance<chrome::InternalAuthVerificationService>
326    g_verification_service = LAZY_INSTANCE_INITIALIZER;
327static base::LazyInstance<base::Lock>::Leaky
328    g_verification_service_lock = LAZY_INSTANCE_INITIALIZER;
329
330}  // namespace
331
332namespace chrome {
333
334class 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
430namespace {
431
432static base::LazyInstance<chrome::InternalAuthGenerationService>
433    g_generation_service = LAZY_INSTANCE_INITIALIZER;
434
435}  // namespace
436
437namespace chrome {
438
439// static
440bool 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
450void 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
456int 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
464int InternalAuthVerification::verification_window_seconds_ = 0;
465
466// static
467std::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
473void InternalAuthGeneration::GenerateNewKey() {
474  g_generation_service.Get().GenerateNewKey();
475}
476
477}  // namespace chrome
478