パスワード生成ツールを自作したら、Math.randomが使えない理由から学び直しになった
パスワード自動生成ツールを自作した話。Math.randomが暗号用途に使えない理由、crypto.getRandomValuesの剰余バイアスをリジェクトサンプリングで消す実装、エントロピーは何bitあれば安全かを実装者目線で整理した。
サイトのツール群にパスワード生成ツールを足そうと思い立って、最初は「文字の配列からランダムに選んで連結するだけ。30分で終わる」と見積もっていた。実際、動くものは30分でできた。Math.random()で。
そこでふと「パスワード生成にMath.randomって使っていいんだっけ」と調べ始めたのが運の尽きで、気づいたら擬似乱数の内部状態の話から剰余バイアス、エントロピーの計算までを一通り学び直すことになった。この記事はその過程の記録だ。
Math.randomは「予測できる乱数」
MDNのMath.random()のページには、はっきりと「暗号論的に安全な乱数を提供しない。セキュリティに関わる用途には使わないこと」と書いてある。知識としては知っていたが、「なぜダメなのか」を人に説明できるレベルでは理解していなかった。
Math.random()の実体は擬似乱数生成器（PRNG）で、V8（Chrome/Node.js）ではxorshift128+というアルゴリズムが使われている。これは128bitの内部状態から決定的に次の値を計算する仕組みで、統計的な品質は良い。ゲームの敵の出現位置やパーティクルの散らし方には何の問題もない。実際、うちのブラウザゲームでは普通にMath.randomを使っている。
問題は、出力から内部状態を逆算できることだ。xorshift128+は連続した数個の出力を観測すれば、制約ソルバーで内部状態を復元し、以降の出力をすべて予測できることが実証されている。つまり「攻撃者が同じ生成器の出力をいくつか知っている」状況では、次に生成されるパスワードは乱数ではなく既知の値になる。パスワード生成器が満たすべき性質は「散らばって見える」ではなく「過去の出力をいくら見ても次が予測できない」で、これはPRNGの統計品質とは別の性質だ。
というわけで正解はブラウザ標準の暗号論的乱数、crypto.getRandomValues()になる。OSの乱数源から種を取るCSPRNGで、モダンブラウザなら追加ライブラリなしで使える。
const buf = new Uint8Array(1);
crypto.getRandomValues(buf); // buf[0] に 0-255 の暗号論的乱数ここまでは調べればすぐ出てくる話で、書き換えも5分で終わった。本題はここからだった。
byte % 文字数 に潜む剰余バイアス
乱数バイトから文字を選ぶとき、素直に書くとこうなる。
// ダメな例
const idx = buf[0] % pool.length;
out += pool[idx];一見問題なさそうだが、これには**剰余バイアス（modulo bias）**がある。buf[0]は0〜255の256通り。仮に文字プールが85文字（英大小＋数字＋記号23種。自作ツールのデフォルト構成がちょうどこれ）だとすると、256 ÷ 85 = 3 余り 1。つまり0〜254のバイトは各インデックスに3回ずつ均等に割り当たるが、余った255が255 % 85 = 0でインデックス0に落ちる。
結果、プールの先頭の文字（この構成だとA）だけ出現確率が4/256、他の84文字は3/256になる。先頭の1文字だけ33%も出やすいわけだ。
正直に言うと、この偏りが実際の攻撃で致命傷になる場面は限られると思う。1文字あたりの偏りは小さいし、パスワード全体のエントロピーが大きく削れるわけでもない。ただ、攻撃者が生成器の実装を知っていれば総当たりの候補順を最適化する材料にはなるし、何より「暗号論的に一様な乱数で生成しています」と謳うツールで一様じゃない選び方をするのは嘘になる。直し方が簡単なので、直さない理由がない。
直し方がリジェクトサンプリングで、「256を文字数で割り切れる範囲」だけを採用し、余りの領域に落ちたバイトは捨てて引き直す。
function randInt(max) {
const limit = 256 - (256 % max); // max=85なら255。255以上のバイトは捨てる
const buf = new Uint8Array(1);
do {
crypto.getRandomValues(buf);
} while (buf[0] >= limit);
return buf[0] % max;
}捨てる確率は最悪でも半分未満なので、引き直しのループは平均2回未満で終わる。パスワード1本の生成で体感できる遅さには絶対にならない。「偏りを消すために乱数を捨てる」という発想は、知ってしまえば当たり前なのだが、自分で書くまで思いつかなかった。
ついでに言うと、「英大文字・数字・記号を最低1文字ずつ含める」というよくあるオプションも同じ発想で実装した。素朴にやると「まず各文字種から1文字ずつ選んで、残りを埋めてからシャッフル」になりがちだが、これは一様分布からの生成とは微妙に違う分布になる。条件を満たさないパスワードが出たら丸ごと捨てて作り直す方が、実装も分布の説明もシンプルだった。
エントロピーは何bitあれば足りるのか
強度表示を付けようとして、次は「強い・弱いの根拠」を数字にする必要が出てきた。ここは意外と話が単純で、パスワードの強度は組み合わせの総数、つまりエントロピー = 長さ × log2(文字種数) で決まる。85文字プールで16文字なら 16 × log2(85) ≈ 16 × 6.41 ≈ 102.6 bit。
じゃあ何bitあれば十分なのか。これは攻撃のシナリオで分かれる。
- オンライン攻撃（ログイン画面への総当たり）: サーバー側のレート制限やロックアウトで試行回数が絞られるので、要求水準は実はそれほど高くない
- オフライン攻撃（漏えいしたパスワードハッシュを攻撃者の手元のGPUで総当たり）: 試行速度に上限がなく、こちらを想定するなら80bit以上が目安になる
サービス側がbcryptやArgon2のような遅いハッシュを使っていればオフライン攻撃のコストは大きく上がるが、それは利用者からは確認できない。確認できない前提には頼らない、というのがパスワード側でできる自衛で、だからツールのデフォルトは16文字（約102bit）にした。
面白いのは、文字種を増やすより長さを伸ばす方が効くという点だ。数字だけの16文字は 16 × log2(10) ≈ 53 bitだが、これに記号を足して85種にしても102bit。一方、85種のまま長さを24文字にすると154bitになる。log2の中身を増やすより掛け算の係数を増やす方が伸びが速い。「記号を必ず含めよ」と強制するくせに長さ上限が12文字だったりするサービスの要件が、いかにズレているかがよくわかる。NIST（SP 800-63B）が文字種の強制よりも長さを重視する方針を打ち出しているのも同じ理屈だ。
自作ツールでは、この計算式を隠さずに「16文字 × log2(85種) ≈ 102.6 bit」とそのまま表示するようにした。強度メーターが5段階の星で光るより、根拠の数字が見える方が自分は信用できる。
パスフレーズという別解と、その正直な弱点
ランダム文字列の弱点は覚えられないことだ。パスワードマネージャに保存してコピーして使うなら問題ないが、PCのログインパスワードやマネージャ自体のマスターパスワードのように「覚えて手で打つ」ものはそうはいかない。
そこで単語をランダムに選んでつなぐパスフレーズ（Diceware方式）が出てくる。maple-canyon-sparrow-ember-tideのような形式で、xkcdの「correct horse battery staple」で有名になったやつだ。エントロピーの計算は同じで、語数 × log2(語彙数)。本家Dicewareの単語リストは7776語なので1語あたり約12.9bit、5語で約64.6bitになる。1文字ずつ覚えるのではなく単語のイメージで覚えられるので、同じエントロピーならランダム文字列より記憶の負荷が圧倒的に軽い。
自作ツールにもパスフレーズタブを付けたのだが、ここでひとつ設計上の妥協をした。外部ファイルの読み込みをゼロにしたかったので、単語リストをページに直接埋め込んだ200語に絞ったのだ。200語だと1語あたりlog2(200) ≈ 7.6bitしかなく、5語で約38.2bit。本家Dicewareの5語（64.6bit）にはっきり劣る。この差はツールの画面にもそのまま書いた。「覚えて使う用途向け。重要な用途では語数を増やすかランダム型を」と。エントロピーの計算式を表示するツールが、自分のパスフレーズの弱さだけ隠すわけにはいかない。
一番危ないのは弱いパスワードではなく、使い回し
ここまで乱数とエントロピーの話をしてきて言うのも何だが、調べるほどに「個々のパスワードの強度は、実は2番目の問題」だと思うようになった。1番の問題は使い回しだ。
どれだけ102bitの強いパスワードでも、複数のサービスで使い回していたら、セキュリティが一番弱い1社から漏れた時点で全部が破られる。漏えいしたIDとパスワードの組で他サービスへのログインを試すリスト型攻撃は、総当たりと違ってレート制限もエントロピーも関係ない。正しい組み合わせを1回入力するだけだからだ。
だから現実的な結論は昔から変わらない。サービスごとに別のランダムパスワードを生成し、記憶はパスワードマネージャに任せる。ブラウザ内蔵のもので構わない。生成ツールはその「サービスごとに別の」を面倒なく続けるための道具であって、覚えられる最強の1本を作る道具ではない。
作ってみて気づいた、生成ツールに一番必要なもの
最後に、作り終えてから気づいたことを書く。強い乱数、バイアスのない選択、正確なエントロピー計算。どれも真面目に実装したが、パスワード生成ツールにとって一番重要な性質はたぶんそのどれでもない。生成したパスワードがどこにも送信されないことの保証だ。
考えてみれば当たり前で、これから使うパスワードを入力（生成）するページというのは、フィッシングサイトと紙一重の存在だ。生成結果を裏でサーバーに送るパスワード生成サイトがあったら、それは乱数がどれだけ高品質でも一撃でアウトになる。外部のツールに「送信していません」と書いてあっても、それを自分で検証した上で使っている人はほぼいないと思う。
これは以前本番のJWTを外部のデコードサイトに貼りかけて手が止まった話で書いたのと同じ構図で、結局のところ自分で書いたコードなら「送信しない」を信頼ではなく実装で保証できる。自作のパスワード生成ツールでは、fetchもXMLHttpRequestも一切書かず、生成結果はlocalStorageにも保存せず、ページを閉じれば消えるようにした。静的ページなのでソースは開発者ツールでそのまま読めるし、Networkタブを開いたまま何度生成してもリクエストが1本も飛ばないことを誰でも確認できる。同じ理由で作ったJWTデコーダと合わせて、「認証に関わる文字列を外部に渡さない」ための道具が2つになった。
30分で終わるはずだったツールにここまで時間を使うことになったが、剰余バイアスのような「知らなければ一生気づかない偏り」を自分の手で消す経験は、正直かなり面白かった。パスワードを作る用事があったらツールを触ってみてほしい。エントロピーの計算式が生成のたびに表示されるので、この記事の内容がそのまま画面で確認できる。