🎲

「6桁のワンタイムパスワードは同じ数字が並ぶことが多い」という直感は正しいか？

に公開
math
OTP
TOTP
hotp
tech

2要素認証などでよくみる6桁のワンタイムパスワードですが、個人的に何となく気になっていることがありました。
それは 同じ数字が並ぶことが多いな と感じるということです。

この記事では

  • 「同じ数字が並ぶ」という直感が正しいのか？
  • 何かの目的 (例: 入力を楽にする) があってこうなっているのか？
  • ワンタイムパスワードの生成アルゴリズム的にこういう偏りが生まれやすくなるのか？

という素朴な疑問を解決すべく調査・検証してみました。

ワンタイムパスワードの仕様

6桁のワンタイムパスワード（以下、OTP）は、実は国際的に標準化された仕様に基づいて生成されています。

HOTPをベースに時間要素を追加した拡張版がTOTPで、30秒（または60秒）ごとに自動的に新しい値を生成されるようになっています。
Google Authenticatorなどを触ったことがある方は、まさにあのイメージです。
実際、多くの製品がこのRFC 6238で定義されたTOTPに準拠した形で提供されています。[1]

この仕様によると、生成のアルゴリズムはざっくり以下のようになります。

  1. 秘密鍵とカウンター（またはタイムスタンプ）を用意
  2. HMAC-SHA-1でハッシュ値を計算（160ビット）
  3. Dynamic Truncationで4バイトを抽出
  4. 31ビット整数に変換
  5. 10^6で剰余を取って6桁の数値を得る

詳細な説明は興味がある人向けに後ほど記述しますが、
重要なのはここで生成される6桁の数字はほぼ一様分布 、つまり000000~999999が出る確率はどれも ほぼ 1/1000000 になります。サイコロで1~6が同じように出るのと同じですね。

つまりアルゴリズムによって特定の数字がでやすくなっているわけではない ということです。
ではなぜ同じ数字が並ぶことが多いと感じるのでしょうか？

「同じ数字が並ぶことが多いと感じる」への結論

技術的な詳細はさておき「数字がどれも同じ確率で生成される」ということがわかると、中学・高校で習うような組み合わせの計算でこの直感を検証できます。
つまり「同じ数字が並びやすい」というのはただの6桁のランダムな数字の一般的な統計的性質だ ということです。

同じ数字が2回以上現れる確率は次のように計算できます。

P(\text{重複あり}) = 1 - P(\text{すべて異なる})
P(\text{すべて異なる}) = \frac{10}{10} \times \frac{9}{10} \times \frac{8}{10} \times \frac{7}{10} \times \frac{6}{10} \times \frac{5}{10}
= \frac{10 \times 9 \times 8 \times 7 \times 6 \times 5}{10^6}
= 0.1512
\therefore P(\text{重複あり}) = 1 - 0.1512 = 0.8488 \approx 84.88\%

つまり約85% の確率で同じ数字が含まれます。

また同じ数字の連続が見られる確率も同様に計算してみると

P(\text{連続なし}) = 1 × (9/10)^5 = 0.59049
P(\text{連続あり}) = 1 - 0.59049 = 0.40951 ≈ 40.95%

と約41% の確率で同じ数字が連続で並びます。

これが自分が「同じ数字が並びやすい」感じる正体でした。なんともあっけない結論ですね

6桁の数字が「ほぼ一様分布になる」という部分へのDeep Dive

すでに結論は出たのでここから先はマジで興味がある方だけ読んでいただければ良いのですが、HTOP / TOTPで生成される6桁の数字が ほぼ一様分布になる の部分について掘り下げていこうと思います。

先に全体の流れを書くとこんな感じです。

6桁の数字が"ほぼ" 一様分布であると言える
    ⇧ 結論
Dynamic Truncation後も擬似ランダム性が維持され、mod 10^6 後も「ほぼ一様分布」
（0.024%の偏りはあり）
    ⇧ RFC 4226のAppendix A.4.1. From Bits to Digits で説明あり
HMAC-SHA-1の出力が擬似ランダム（一様分布と計算量的に識別不可能）
    ⇧ PRFの定義より
HMAC-SHA-1がPRF
    ⇧ Bellare 2006で証明
SHA-1圧縮関数がPRF（仮定）

HMAC-SHA-1が擬似ランダム　⇒ 生成される6桁は"ほぼ" 一様分布

再掲にはなりますが、HOTP / TOTPは次のように計算されるのでした。

  1. 秘密鍵とカウンター（またはタイムスタンプ）を用意
  2. HMAC-SHA-1でハッシュ値を計算（160ビット）
  3. Dynamic Truncationで4バイトを抽出
  4. 31ビット整数に変換
  5. 10^6で剰余を取って6桁の数値を得る

RFC 4226の Appendix A.4.1. From Bits to Digits ではHMAC-SHA-1の出力が擬似ランダムであることを前提に、3~5の操作でほぼ偏りなく6桁の数字を得ることができることを示しています。

ここで"ほぼ" といっているのは 4~5の操作で31ビットの整数を10^6で剰余をとると綺麗に割り切れないので、

  • 10進数表示で 0〜483,647： それぞれ2148回出現
  • 10進数表示で 483,648〜999,999： それぞれ2147回出現

という偏りが生まれるからです。ただしこの偏りは0.024%程度であり、実用上は特に問題ないと言えそうです。

3の操作においては「HMAC-SHA-1の出力が擬似ランダムである場合、任意の31ビット部分列も擬似ランダムである。」ということから擬似ランダム性が保持されています。

HMAC-SHA-1がPRF (PseudoRandom Function: 擬似ランダム関数) であることについて

RFC 4226で示されているのはあくまでもHMAC-SHA-1が擬似ランダムである場合に 出力もほぼ一様になるということで、HMAC-SHA-1が擬似ランダムかどうかについては直接は触れられていません。

HMAC-SHA-1が擬似ランダムであることは Bellare 2006 [2] で 「SHA-1圧縮関数がPRF[3] ⇒ HMAC-SHA-1がPRF」という形で証明されています。

ここで最終的にSHA-1の圧縮関数がPRFであるか？という話になるのですが、これは有効な攻撃 (=SHA-1圧縮関数を真のランダム関数と識別する実用的方法)が未発見という意味で、assumption (仮定) という扱いのようです。

まとめると「SHA-1の圧縮関数がPRFであるという仮定の元、0.024%程度の偏りはあるもののほぼ一様分布と言って良い」という結論になりそうでした。

まとめ

直感はある意味正しかったですが、「同じ数字が並びやすい」というのはただの6桁のランダムな数字の一般的な統計的な性質でした。
ただ、道中いろんな余計な学びがあってよかったです。

脚注

  1. Google Authenticatorのwikipedia ではRFC6238に準拠しているとの記述がありますが、公式なソースは見当たらなかった ↩︎

  2. New Proofs for NMAC and HMAC: Security Without Collision-Resistance ↩︎

  3. Pseudorandom function family - Wikipedia ↩︎

Discussion