Time-based One-Time Passwordの仕組みを提供するGem「rotp」をサクッと試して内部実装を把握する

こんにちは!kossyです!



今回はTime-based One-Time Passwordの仕組みを提供するGem「rotp」をサクッと試して内部実装を把握してみたので、ブログに残してみたいと思います。




環境
Ruby 2.6.6
Rails 6.0.3
MacOS catalina



まずはコンソールでサクッと試す

github.com

何はともあれGemfileの編集とbundle install。

#  Gemfile

gem 'rotp'
your_app $ bundle

インストールが終了したらReadMeを見ながらコンソールで試してみます。

$ totp = ROTP::TOTP.new("kossywebengineer", issuer: "Test Service")

$ totp.now
=> 388204

$ totp.verify('388204')
=> 1622295690

# 30秒後に再度実行

$ totp.verify('388204')
=> nil

# 前回実行時から6桁の認証コードが変わっている

$ totp.now
=> 197355

30秒で認証コードが更新されていることがわかります。
verifyメソッドを実行してnilが返った場合は、ワンタイムパスワードが間違っていて認証に失敗したことを表していると思われます。

ちなみにQRコードを生成したい場合は、provisioning_uriメソッドを使います。

$ uri = totp.provisioning_uri('kossywebengineer@example.com')
=> "otpauth://totp/Test%20Service:kossywebengineer%40example.com?secret=kossy-web-engineer&issuer=Test%20Service

このURIQRコード生成サイトでQRコード化します。

qr.quel.jp

生成したQRコードスマホの GoogleAuthenticator 等のアプリで読み取ります。

play.google.com

GoogleAuthenticatorに6桁の認証コードが表示されますので、そのコードをvefiryメソッドに渡してみます。

$ totp.verify('651353')
=> 1622295720

認証に成功しました。

サクッと実行して挙動を確認してみましたが、rotpでは認証の部分のみの実装のため、もしWebアプリ内で2段階認証を組み込むとなると、

QRコードの生成」
「2段階認証を有効にしているかどうか」
「secret_keyの管理(newの引数に渡す認証keyです)」
「そのsecret_keyは有効になっているものかどうか」

等を管理する必要があります。上記(QRコードの生成は別ですが)をよしなに行ってくれているのが、devise_two_factorというGemになります。

github.com


rotpの内部実装を追ってみる

ここからはrotpの内部実装をソースコードを実行しながら追ってみたいと思います。

ROTP::TOTP.new

initializeメソッドから見ていきます。

module ROTP
  DEFAULT_INTERVAL = 30
  class TOTP < OTP
    attr_reader :interval, :issuer

    # @option options [Integer] interval (30) the time interval in seconds for OTP
    #     This defaults to 30 which is standard.
    def initialize(s, options = {})
      @interval = options[:interval] || DEFAULT_INTERVAL
      @issuer = options[:issuer]
      super
    end

  # 省略
end

引数で渡されたintervalとissuerをインスタンス変数として定義し、superクラス(OTPクラス)のinitializeを呼び出す実装になっていました。

コンソールで試してみます。

$ totp = ROTP::TOTP.new("kossywebengineer", interval: 15, issuer: "Test Service")
=> #<ROTP::TOTP:0x000056128fa78698
 @digest="sha1",
 @digits=6,
 @interval=15,
 @issuer="Test Service",
 @secret="kossy-web-engineer">

$ totp.now
=> 086478

# 15秒後に再度実行。認証コードが変わっている

$ totp.now
=> 800896

インターバルを15秒に設定したので、15秒で認証コードが更新されています。

OTPクラスのinitializeメソッドも見てみましょう。

module ROTP
  class OTP
    attr_reader :secret, :digits, :digest
    DEFAULT_DIGITS = 6

    # @param [String] secret in the form of base32
    # @option options digits [Integer] (6)
    #     Number of integers in the OTP.
    #     Google Authenticate only supports 6 currently
    # @option options digest [String] (sha1)
    #     Digest used in the HMAC.
    #     Google Authenticate only supports 'sha1' currently
    # @returns [OTP] OTP instantiation
    def initialize(s, options = {})
      @digits = options[:digits] || DEFAULT_DIGITS
      @digest = options[:digest] || 'sha1'
      @secret = s
    end
end

デフォルトのdigits(認証コードの桁数)は「6」で、ハッシュ関数は「sha1」となっています。

こちらもコンソールで試してみましょう。

$ totp = ROTP::TOTP.new("kossywebengineer", digits: 8, issuer: "Test Service")
=>  #<ROTP::TOTP:0x000056128a41b228
 @digest="sha1",
 @digits=8,
 @interval=30,
 @issuer="Test Service",
 @secret="kossywebengineer">

$ totp.now
=> "95928414"

$ totp = ROTP::TOTP.new("kossywebengineer", digest: 'md5', issuer: "Test Service")
=> #<ROTP::TOTP:0x000056128d676b78
 @digest="md5",
 @digits=6,
 @interval=30,
 @issuer="Test Service",
 @secret="kossywebengineer">

# サポートされていないdigestを指定するとnow実行時に例外が上がる
$ ROTP::TOTP.new("kossywebengineer", digest: 'sha0', issuer: "Test Service").now
=> RuntimeError: Unsupported digest algorithm (sha0).: first num too large

$ ROTP::TOTP.new("kossywebengineer", digest: 'sha128', issuer: "Test Service").now
=> RuntimeError: Unsupported digest algorithm (sha0).: first num too large

認証アプリにGoogleAuthenticatorを用いた場合、サポートしている桁数が6桁なので、8桁のdigitsには対応していないので注意が必要とのこと。(2021年5月時点)

同様にdigestも「sha1」のみのサポートとのこと。

残りの処理はsecret_keyのインスタンス変数化処理でした。

initializeメソッドも一通り把握できたので、次はnowメソッドを見てみます。

ROTP::TOTP#now

# Generate the current time OTP
# @return [Integer] the OTP as an integer
def now
  generate_otp(timecode(Time.now))
end

# generate_otpメソッドはROTP::OTPクラスに定義されています。

# @param [Integer] input the number used seed the HMAC
# @option padded [Boolean] (false) Output the otp as a 0 padded string
# Usually either the counter, or the computed integer
# based on the Unix timestamp
def generate_otp(input)
  hmac = OpenSSL::HMAC.digest(
    OpenSSL::Digest.new(digest),
    byte_secret,
    int_to_bytestring(input)
  )

  offset = hmac[-1].ord & 0xf
  code = (hmac[offset].ord & 0x7f) << 24 |
          (hmac[offset + 1].ord & 0xff) << 16 |
          (hmac[offset + 2].ord & 0xff) << 8 |
          (hmac[offset + 3].ord & 0xff)
  (code % 10**digits).to_s.rjust(digits, '0')
end

generate_otpに渡しているtimecodeメソッドを見てみます。

def timecode(time)
  timeint(time) / interval # intervalはinitialize時にセットされた値です。デフォルトはintで「30」
end

# Ensure UTC int
def timeint(time)
  return time.to_i unless time.class == Time

  time.utc.to_i
end

引数がTimeクラスの値でなければ引数をto_iしたものを返却して、そうでない場合は.utc.to_iした値を返却していました。

返却された値を、initialize時に設定したintervalの値で割った値を返却するメソッドでした。

generate_otpの処理は、引数の数値とdigits、secret_keyをBase32でdecodeした値を元に、ワンタイムパスワードを生成しています。このワンタイムパスワードがnowメソッドの返り値となります。

次にverifyメソッドを見てみます。

ROTP::TOTP#verify

# Verifies the OTP passed in against the current time OTP
# and adjacent intervals up to +drift+.  Excludes OTPs
# from `after` and earlier.  Returns time value of
# matching OTP code for use in subsequent call.
# @param otp [String] the one time password to verify
# @param drift_behind [Integer] how many seconds to look back
# @param drift_ahead [Integer] how many seconds to look ahead
# @param after [Integer] prevent token reuse, last login timestamp
# @param at [Time] time at which to generate and verify a particular
#   otp. default Time.now
# @return [Integer, nil] the last successful timestamp
#   interval
def verify(otp, drift_ahead: 0, drift_behind: 0, after: nil, at: Time.now)
  timecodes = get_timecodes(at, drift_behind, drift_ahead)

  timecodes = timecodes.select { |t| t > timecode(after) } if after

  result = nil
  timecodes.each do |t|
    result = t * interval if super(otp, generate_otp(t))
  end
  result
end

コメントアウト部分を訳してみます。

渡された OTP を、現在時刻の OTP および +drift+ までの隣接する間隔に対して検証します。 「後」以前の OTP を除外します。
後続の呼び出しで使用するために、一致する OTP コードの時間値を返します。

@param otp [String] 検証するワンタイムパスワード
@param drift_behind [Integer] 遡って何秒か
@param drift_ahead [Integer] 先読みする秒数
@param after [Integer] は、トークンの再利用、最終ログインのタイムスタンプを防止します
@param at [Time] 特定の

driftは認証コードが有効な期間を設定できるものです。例えばSMSで認証コードを伝える場合、デフォルトの30秒のままだと受け取ってからすぐに認証期限が切れてしまいますが、
driftの設定を長めに設定することで、この問題を回避することができます。

Google翻訳なので一部日本語がおかしいところもありますが、概ね内容は理解できました。

まずはget_timecodesメソッドから読んでみます。

# Get back an array of timecodes for a period
def get_timecodes(at, drift_behind, drift_ahead)
  now = timeint(at)
  timecode_start = timecode(now - drift_behind)
  timecode_end = timecode(now + drift_ahead)
  (timecode_start..timecode_end).step(1).to_a
end

先ほど読んだtimeintメソッドとtimecodeメソッドを使いながら、引数のdrift値を使ってRangeオブジェクトから配列を生成して返却するメソッドになっています。

返り値は以下のような値になります。

=> [54078254, 54078255, 54078256, 54078257, 54078258, ...]

このtimecodesを引数のafterが渡されていれば、afterで指定された秒数で計算したtimecodeよりも数値が大きいものをselectして、新たなtimecodesを生成しています。

読み進めるとsuperメソッドでOTPクラスのverifyが呼ばれているので、こちらも読んでみます。

def verify(input, generated)
  raise ArgumentError, '`otp` should be a String' unless
      input.is_a?(String)

  time_constant_compare(input, generated)
end

# constant-time compare the strings
def time_constant_compare(a, b)
  return false if a.empty? || b.empty? || a.bytesize != b.bytesize

  l = a.unpack "C#{a.bytesize}"
  res = 0
  b.each_byte { |byte| res |= byte ^ l.shift }
  res == 0
end

こちらもコンソールで試してみます。

$ totp = ROTP::TOTP.new("kossywebengineer", issuer: "Test Service")

$ a, b = [totp.now] * 2 # 今回のコードは435752です

$ a.empty? || b.empty? || a.bytesize != b.bytesize
=> false

$ l = a.unpack "C#{a.bytesize}" # a.bytesizeの返り値は6です
=> [52, 51, 53, 55, 53, 50]

$ b.each_byte { |byte| res |= byte ^ l.shift }
=> "435752"

$ res
=> 0

# ここからeach_bytesの挙動の確認
$ l = a.unpack "C#{a.bytesize}"

$ res |= b.bytes[0] ^ l.shift
=> 0
$ res |= b.bytes[1] ^ l.shift
=> 0
$  res |= b.bytes[2] ^ l.shift
=> 0
$  res |= b.bytes[3] ^ l.shift
=> 0
$  res |= b.bytes[4] ^ l.shift
=> 0
$  res |= b.bytes[5] ^ l.shift
=> 0

$ l
=> []

引数で渡されたワンタイムパスワードと、現在のワンタイムパスワードをバイナリにしてビット演算し、両者が一致(0だったら)していれば TRUE が返る処理になっていました。

なぜこのような処理になっているかはrotp内では言及されていませんでしたが、deviseに似たような処理があり、以下のブログで、
「これは、認証用の文字列 (ハッシュされたパスワードか API トークンかに関係なく) を比較するときに本当に実行したいことです。
これにより、アプリケーションでタイミング攻撃を使用することがはるかに難しくなります。」

と言及されていました。なので、Timing Attackを軽減させるための実装なのかもしれません。

spazidigitali.com

寄り道が長くなってしまいました。

OTPクラスのverifyが TRUE だった場合、timecodeとintervalを乗算した値が返り値となります。

一度もvefiryが TRUE にならなかった場合は、nilが返り値となります。


まとめ

Tokenの生成やビット演算など、普段Webアプリの実装をしているとあまり見かけないコードにお目にかかることができました。

2段階認証の機能をごくごく簡単に実装できる素晴らしいGemだと思うので、機会があれば使ってみようかと思います。