はじめに
7月の初め、新卒研修も終わり OJT プロジェクトに配属されて初めての作業が AWS 環境の MFA 登録でした。環境は全部で 6 個あり、3 個目の登録あたりから怠くなり始めてダルメシアンになってしまいそうになる中、ふと「どんな仕組みで動作しているんだろ」という疑問が湧き、純粋な好奇心から調べ再実装しました。
DEMO
内訳
TOTPは、主に、以下の技術で成り立っていました。
1. HOTP: An HMAC-Based One-Time Password Algorithm
2. HMAC: Keyed-Hashing for Message Authentication
3. SHA1: US Secure Hash Algorithm 1
HOTP
HMAC という署名技術をベースにして、使い捨てパスワードを生成するアルゴリズム
HMAC の結果（20バイト）を 6 桁(もしくは 8 桁)の数字に変換する機能を持っている
アルゴリズムの中核には Dynamic Truncation という手法を利用しています
関数の操作は以下です
- 下位 4 ビットの数値をオフセットとして取得 ( 0~15 )
- 開始位置から 4 バイト分を切り出す
- 最上位ビットを 0 に変換し符号無しを強制
private static DT(HS: Buffer): number {
let offset = HS[19]! & 0x0f
let P = (HS[offset]! & 0x7f) << 24 | HS[offset + 1]! << 16 | HS[offset + 2]! << 8 | HS[offset+3]!
return P >>> 0
}
最終的に取得した32ビットに対して 10^6(もしくは8)をわりあまりを求める
HMAC
Message Authentication Code の一種
秘密鍵を持っていることを、二者間で 「共通のメッセージ」 を通して署名・検証する方法
RFC2104では以下のように定義されています
H: 暗号学的ハッシュ関数
K: 秘密鍵
B: ハッシュ関数が、データを分割して内部で処理する単位のバイト長
text: 任意バイト数のデータ
ipad: 0x36 を B 回繰り返した固定文字列
opad: 0x5c を B 回繰り返した固定文字列
$$\text{HMAC}(K, M) = H \left( (K \oplus \text{opad}) \parallel H \left( (K \oplus \text{ipad}) \parallel text \right) \right)$$
返却値は使用するハッシュ関数に依存します
SHA-1
Cryptographic hash function の一種
最大 2^64-1 桁のビット列をメッセージ入力として受け取り、160ビットのダイジェストとして出力する関数
構造：Merkle–Damgård construction
SHA-1 の根幹は、I. Damgård が 1989 年の論文 A Design Principle for Hash Functions で示した設計指針に基づいています。
- Definition 2.1: 固定長を扱う「安全な部品（圧縮関数）」の定義
- Definition 2.2: どんな長さでも安全に処理できる「ハッシュ関数」の定義
$$f : \lbrace{0,1\rbrace}^m \to \lbrace{0,1\rbrace}^{t(m)} \quad＆＆\quad t(m) < m$$
上記の論文の定義を SHA-1 に当てはめると、各変数は以下の役割を担っています。
- m: メッセージから切り出した 512 bit のブロック + 直前のステップから引き継いだ 160 bit の内部状態 = 672
- t(m): 次のステップへ引き継がれる新しい内部状態 = 160
NIST (米国国立標準技術研究所) が定義しているセキュリティ要件として以下の3項目が定義されています
1. 衝突耐性(Collision resistance): 異なる入力から同じハッシュ値を見つけることが計算上困難であること
2. 原像計算困難性(Preimage resistance): ハッシュ値から元の入力（秘密鍵など）を逆算することが計算上困難であること
3. 第二原像計算困難性(Second preimage resistance): 特定の入力と同じハッシュ値を持つ別の入力を探すことが計算上困難であること
※ Google Security Blogによると衝突耐性の点で暗号学的に非推奨とされている
TOTP
RFC 6238 で定義されている TOTP は、実質的に 「HOTP のカウンタを現在時刻に置き換えたもの」 です
秘密鍵 $K$ と、現在時刻から算出される時間ステップ $T$ を HOTP に渡すことで、30秒間だけ有効なコードを生成します
$$ TOTP = HOTP（K, T）$$
カウンタの算出式TOTP では、以下の式で求められる $T$ を HOTP のカウンタとして利用します。
$$T = \lfloor (\text{Current Unix Time} - T_0) / X \rfloor$$
$T_0$: 時間の起点（通常は 0 = 1970年1月1日）
$X$: ステップ時間（デフォルトは 30秒）
TOTPの要件は以下のように定められています
R1: 双方が現在の Unix Time（1970年からの経過秒数）を知っていること
R2: 両者が同じ「秘密の鍵（Shared Secret）」を共有しているか、あるいはそれを生成するための共通の知識を持っていること
R3: アルゴリズムの基盤として、HOTP ([RFC4226]) を採用していること
R4: 両者は、同じステップ時間（通常は30秒）を使用しなければならない
R5: 証明者（ユーザー）ごとに、一意（ユニーク）な秘密鍵が必要
R6: 鍵はランダムに生成されるか、強力な鍵生成アルゴリズムによって導出されたものでなければならない
R7: は、不正なアクセスや使用から保護されるデバイス（ハードウェアトークンやスマートフォンのセキュアな領域など）に保存されるべき
秘密鍵の共有
QRコードで読み取っている正体は、otpauth:// 形式の URI です
Google Authenticator のプロジェクトが Wiki で提唱した独自仕様でしたが、現在は IANA (Internet Assigned Numbers Authority） の Provisional（暫定）スキーム として正式に登録されています
終わりに
最初は「AWS の MFA 登録がダルい」というだけの動機でした。 しかし、その裏側を覗いてみると、1989年の論文から続く暗号学者たちの知恵と、Googleの提唱した実用的な仕様が複雑に絡み合って、私たちのセキュリティが守られていることが分かりました。