エントロピー枯渇と脆弱な鍵のバグ

エントロピー枯渇とは、システムに CSPRNG のシード処理に十分な予測不能な入力がない状態です。起動直後の組み込みデバイス、仮想化サーバー、ユーザー入力がないシステムで発生します。その結果、RNG の出力が予測可能になります。

2006 年、Debian の開発者が Valgrind によって問題を指摘された行、MD_Update(&m, buf, j) を削除しました。この行がエントロピー源でした。その結果、Debian 上の OpenSSL は PID のみをシードにするようになりました（最大 32,768 通り）。2006～2008 年に生成されたすべての鍵は、32,768 通りの候補に含まれます。

2006～2008 年に Debian または Ubuntu システム上で生成された RSA、DSA、ECDSA の鍵、SSH ホスト鍵、TLS 証明書、SSL VPN 鍵が侵害されました。影響を受けたシステムは Debian Etch、Debian Lenny、Ubuntu 7.04～8.04 です。ブラックリストが公開され、証明書は失効されました。

VM は同一のディスク状態で複製できます。両方の VM が同じ CSPRNG 状態から鍵を生成すると、同じ鍵が生成されます。現在のハイパーバイザーは、VirtIO RNG や ACPI テーブルを通じてエントロピーを注入しますが、設定が不適切な VM では、起動時に依然としてこのリスクがあります。

IoT デバイス（ルーターやカメラ）は、エントロピーが蓄積される前の初回起動時に SSH/TLS 鍵を生成することがよくあります。調査では、数百万台のデバイスが数千組の RSA 鍵ペアを共有していることが判明しました。すべて同じ、エントロピーの少ない起動時状態からシードしていたためです。

Lenstra らは 2012 年に 1,170 万件の TLS 証明書を収集し、鍵のペアごとに最大公約数（GCD）を計算しました。その結果、12,720 個の RSA 鍵が素因数を 1 つ共有していることが判明しました。つまり、両方の鍵を完全に素因数分解できたということです。公開鍵全体の 0.2% が破られました。原因は、起動時のエントロピー不足です。

ECDSA では、署名ごとに一意なランダムノンス k が必要です。k が再利用される（または弱い）と、秘密鍵を即座に復元できます。d = (s1-s2)^{-1} * (z1-z2) * k / (r1-r2) mod n です。Sony の PS3 は k=constant を使用していたため、復元された鍵ですべてのゲームに署名できました。

Android 4.x の Java SecureRandom は、特定の条件下でシステム時刻をシードにしていました。複数の Bitcoin ウォレットアプリが同じ k ノンスで署名を生成し、秘密鍵が漏えいしました。数百万ドル相当の資金が盗まれました。Google は SecureRandom の実装にパッチを適用しました。

ツール: ssh-vulnkey（Debian の弱い鍵のブラックリストと照合）、badkeys（TLS 証明書を既知の弱い素数と照合）、大量の RSA 鍵を監査する GCD バッチアルゴリズム。Certificate Transparency のログにより、大規模な鍵の分析が可能になります。

初回の鍵生成時には getrandom(GRND_RANDOM) を使用してください。初期シード処理が完了するまで待ってから（/proc/sys/kernel/random/entropy_avail > 128 を確認してから）/dev/urandom を読み取ってください。補助的なエントロピー源としてハードウェア RNG（RDRAND）を使用します。待機せず、初回起動時に鍵を生成することは絶対に避けてください。

再起動後も CSPRNG の状態を保持します。シャットダウン時に /dev/urandom から 32 バイトをシードファイルに保存し、起動時に読み込んで CSPRNG に再投入します。これにより、コールドブートをまたいでエントロピーの連続性を確保できます。Linux では自動的に行われますが、組み込みシステムでは行われないことがよくあります。

Debian OpenSSL のエントロピーバグの根本原因は何でしたか。

エントロピー枯渇は、予測可能な鍵の原因になります。実際に鍵が破られた例として、Debian OpenSSL（PID のみをシード）、IoT への GCD 攻撃、PS3 での ECDSA ノンス再利用、Android の Bitcoin ウォレットがあります。必ず OS のエントロピーを使ってシードし、組み込みシステムでの鍵生成を慎重に監査してください。次は、鍵、ノンス、IV を安全に生成する方法です。