MFA の認証クライアントを作りたいので仕様を調べた

昨今、設定を求められることが多くなってきた MFA（多要素認証）です
QRコードを読み取っただけで登録できてお手軽ですよね
そんな認証ですが、どういう仕組みなのか知りたかったので調べてみました

多要素認証の仕組み

QRコードを読んで登録したら、30秒ごとに更新される 6桁の数字を入力してログインしますよね

こちらは TOTP というアルゴリズムがつかわれています
AWS も TOTP が使われていますね
仮想 Multi-Factor Authentication (MFA) デバイスの有効化 (コンソール) - AWS Identity and Access Management

Time-Based One-Time Password Algorithm の略で、
とてつもなく分かりやすい名前してますが時間ベースのワンタイムパスワードということです
どうりで直接繋がっていないデバイスとサーバ間で認証できるわけですね

そしてこの TOTP ですが中では HOTP というアルゴリズムがつかわれています
HMAC-Based One-Time Password Algorithm というやつです

これらの関係はとても簡単で、HOTP に現在時刻を渡して求めるのが TOTP です
なので、多要素認証を理解するなら HOTP を理解すれば「多要素認証完全に理解した」と言えますね
なんかアルゴリズムというと小難しそうですが、実装を理解するのは意外と簡単です🥳

HOTP

大元になる HOTP からいきましょう
HOTP ですが RFC 4226 で定義されています
めちゃめちゃ長い。初めて RFC を見た僕の心は折れかけました
でも実際はこの 5章と最後のオマケのところを読んだら OK です

めちゃめちゃざっくり説明すると、「鍵」と「カウンタ」と「桁数」という 3つの値から得られる任意の桁の数字列です
鍵は認証するサーバと共有している文字列で、いわゆる秘密鍵というやつですね
カウンタというのは任意の数値です。 1とか 2とか 50 とかそういうやつ
桁数は「何桁の数字が欲しいか」を指定します。 AWS の多要素認証では 6つの数値を求められますが、その時の「6」のことです

HTOP を生成する流れはこういう感じで、簡単 4ステップでできます

# Step1. HMAC-SHA-1 の計算
HS = HMAC-SHA-1(K, C)
# Step2. HS を DT する
Sbits = DT(HS)
# Step3. Sbits を数値に変換する
Snum = StToNum(Sbits)
# Step4. 任意の桁になるように桁を落とす
D = Snum mod 10^Digit

K が鍵、 C がカウンタ、 Digit が桁数、 D が認証キーです

Step4 までありますが、Step2 の DT 関数に全てが詰まっていますね
Ruby (2.6.5) でサンプルコードを実装しつつ、みていきましょう

Step1. HMAC-SHA-1 の計算

HMAC-SHA-1 というのは HMAC のハッシュ関数に Sha1 を使ったものです
HMAC の解説は割愛しますが、 Keyed-Hashing for Message Authentication の略で RFC 2104 で定義されているので読んでみてください

Ruby では openssl モジュールに OpenSSL::HMAC クラスがあるのでこれを使えば一発です

require 'openssl'

key = 'a'
data = 'b'
p OpenSSL::HMAC.digest('sha1', key, data) # => "fW\x85V\x86\x829\x86\xC8t6'1\x13\x97R\x01L\xB6\v"

第一引数でハッシュ関数を指定しますが、今回は HMAC-SHA-1 が欲しいので Sha1 を指定します

Step2. DT 関数

こいつがキモですね
Dynamic Truncation の略です
役割としては HMAC-SHA-1 の値からいい感じに数値を取り出す、というヤツです

まず Step1 で取得した HS ですがこれは HMAC-SHA-1 から得られる値なので 20バイトの文字列です
4ビットづつ 16進数で表して 1バイトで区切って 16進数で表すとこうなります

fW\x85V\x86\x829\x86\xC8t6'1\x13\x97R\x01L\xB6\v
が
66 57 85 56 86 82 39 86 c8 74 36 27 31 13 97 52 01 4c b6 0b
になる

※ 1byte = 8bit で 16進数 1桁で 4bit を表せます

この文字（数値）列からいい感じに一部分を取り出したいです

そこで、まず末尾の 4ビットを取り出して OffsetBits と名付けます
この例だと OffsetBits = 0xb = 11 です

> hs = OpenSSL::HMAC.digest('sha1', 'a', 'b')
=> "fW\x85V\x86\x829\x86\xC8t6'1\x13\x97R\x01L\xB6\v"
> hs.length
=> 20 # データ長なので 20バイト
> hs[19] # 末尾の 1バイト
=> "\v"
> hs[19].unpack('B*').first # ビットストリングとして 2進数値に変換
=> "00001011"
> hs[19].unpack('B*').first.to_i(2) # 2進数として解釈して 10進数値に変換
=> 11
> hs[19].unpack('B*').first.to_i(2) & 0x0f # 下位 4ビットが欲しいので 0x0f (0b00001111)でマスク
=> 11

String#unpack (Ruby 2.7.0 リファレンスマニュアル)

ここで元の文字列の OffsetBits 番目から 4バイトを取り出します
OffsetBits = 11 なので 11-14番目の値です

表にするとこんな感じです
上がインデックスで下がデータです
+ が OffsetBits で * が OffsetBits 番目から 4バイト分のデータです

-------------------------------------------------------------
| Byte Number                                               |
-------------------------------------------------------------
|00|01|02|03|04|05|06|07|08|09|10|11|12|13|14|15|16|17|18|19|
-------------------------------------------------------------
| Byte Value                                                |
-------------------------------------------------------------
|66|57|85|56|86|82|39|86|c8|74|36|27|31|13|97|52|01|4c|b6|0b|
----------------------------------**-**-**-**--------------+|

コードだとこうなりますね

> offset_bits = d[19].unpack('B*').first.to_i(2) & 0x0f
=> 11
> d[offset_bits..(offset_bits+3)].unpack('H*').first # 16進数変換
=> "27311397"

表の * の部分と一致しましたね

最後に最上位ビットを潰した値が DT関数の値になります

コードを書き換えてこうします
（もうちょっと分かりやすい書き方ないかなぁ）

((hs[offset_bits].unpack('B*').first.to_i(2) & 0x7f) << 24) | hs[(offset_bits+1)..(offset_bits+3)].unpack('B*').first.to_i(2)
=> 3216311

3216311 が K = 'a' C='b' のときの値になります

メソッドにまとめるとこんな感じ

def dt(hs)
  offset_bits = hs[19].unpack('B*').to_i(2) & 0x0f
  ((hs[offset_bits].unpack('B*').to_i(2) & 0x7f) << 24) |
    hs[(offset_bits + 1)..(offset_bits + 3)].unpack1('B*').to_i(2)
end

ここまでくればもうおしまいです。次行きましょう

Step3. Sbits を数値に変換する

DT 関数で求めた値を数値に変換します

先ほどの Ruby コードは数値なので特に何もせずです

snum = dt(hs)

Step4. 任意の桁になるように桁を落とす

D = Snum mod 10^Digit の計算です
Digit を 6としたら下6桁を取り出すという単純な計算ですね

> digit = 6
> snum = 3216311
> d = snum % 10**digit
=> 216311

はい、ということで 216311 が求められました
これで完璧ですね

RFC にテスト用のデータも用意されているので、テストに使ったり、イマイチ理解しきれてない方は見比べてみてください
RFC 4226 - HOTP: An HMAC-Based One-Time Password Algorithm

1点どハマりしたところがあるので補足を。
Count のところ、一桁の数字になっていますがこれは java での例なので実際は 8バイトの integer らしいです

byte [] counter = {0, 0, 0, 0, 0, 0, 0, 0};

なので正しく読み込んで使いましょう

> OpenSSL::HMAC.hexdigest('sha1', '12345678901234567890', [0,0,0,0,0,0,0,0].pack('C*'))
=> "cc93cf18508d94934c64b65d8ba7667fb7cde4b0"
> OpenSSL::HMAC.hexdigest('sha1', '12345678901234567890', [0,0,0,0,0,0,0,1].pack('C*'))
=> "75a48a19d4cbe100644e8ac1397eea747a2d33ab"
> OpenSSL::HMAC.hexdigest('sha1', '12345678901234567890', [0,0,0,0,0,0,0,2].pack('C*'))
=> "0bacb7fa082fef30782211938bc1c5e70416ff44"

（ Array#pack 初めて使いましたが便利ですね。バイナリが秘匿されている分、知見がなくて苦労しました）

TOTP

今回のメインターゲットですが、すでにもう理解することは 9割終わってます
HOTP のカウンタに現在時刻をエポックタイムで渡すだけです
TOTP は RFC 6238 で定義されています。 HOTP と比べるとめっちゃ薄いですね
RFC 6238 - TOTP: Time-Based One-Time Password Algorithm

TOTP を生成する流れはこんな感じです

# Step.1 現在時刻からタイムステップを求める
T = (Current Unix time - T0) / X
# Step.2 # TOTP をだす
TOTP = HOTP(K, T)

Current Unix time はそのまま現在の Unix Time 、
T0 はタイムステップを数え始める時間（ Unix Time の基準が違う時用）、
X はタイムステップの間隔（何秒ごとにキーを生成するか。30秒が多い）、
K は鍵です

Ruby で書くととても簡単

> k = 'a'
> x = 30
> t = Time.now.to_i / x
> totp = hotp(k, t)

補足で T の計算は切り捨てで、 Tは 32bit 以上をサポートすべきとなっています

はい、これだけです

うまく実装できているか試す時はこちらでできますよ
Authenticator

サンプルコード

# frozen_string_literal: true

require 'openssl'

DIGITS = 6

def hmac_sha_1(key, data)
  OpenSSL::HMAC.digest('sha1', key, data)
end

def htop(key, counter)
  hs = hmac_sha_1(key, counter)
  # Sbits は割愛
  snum = dt(hs)
  snum % 10**DIGITS
end

def dt(hs)
  offset_bits = hs[19].unpack1('B*').to_i(2) & 0x0f
  ((hs[offset_bits].unpack1('B*').to_i(2) & 0x7f) << 24) |
    hs[(offset_bits + 1)..(offset_bits + 3)].unpack1('B*').to_i(2)
end

def totp(k)
  current_time = Time.now
  p current_time

  t = current_time.to_i / 30

  htop(k, t.to_s)
end

p totp('this is a secret key')

String#unpack1 (Ruby 2.7.0 リファレンスマニュアル)

おまけ

ここまで触れてこなかった鍵の受け渡しについてです
Google とか AWS とかで MFA 登録をするときに QR コードを読んでいると思いますが、それを通じて鍵のやりとりをしています
同時にプロバイダの名前とかのラベル（ Google だったらメールアドレス）もやりとりしています

これは特に決まりはないですが Google のアプリでの仕様がデファクトになっているようです
Key Uri Format · google/google-authenticator Wiki

こういうフォーマットになっています

otpauth://TYPE/LABEL?PARAMETERS

TYPE が認証方法、 LABEL が表示ラベル、 PARAMETERS に secret というパラメータで鍵を指定します

例えばこんな感じです

otpauth://totp/basicinc?secret=SECRETKEY

このとき secret は Base32 でエンコードされているので、認証で使うときにはデコードしてから使います

QR コードが読めないときは、 次のコードを入力してください 的な所に表示されている鍵を直接入力して使えます
この鍵も Base32 でエンコードされているのでデコードしましょう

まとめ

はい、こんな感じで多要素認証が実装できます
普段の業務は rails での web サイト運用なのでこんなアルゴリズムは出てきませんが、
ビット演算とかしてると低レイヤー感がカッコよくてテンション上がりますね🤩

ということで、皆さんも自分専用の多要素認証アプリを作ってみてはいかがでしょうか？
次回は僕が作ったやつを紹介します