乱数生成器の障害と nonce 再利用の致命性

なぜ乱数の障害は「数学を破らずに」鍵を壊すのか

暗号アルゴリズムの安全性証明は、ほぼ例外なく「乱数が理想的に予測不可能である」ことを前提に組まれています。鍵生成のランダム性、署名の一時値、AEAD の nonce、IV――これらが前提どおりなら数学的困難性が守る。しかしこの前提が崩れると、攻撃者は離散対数や素因数分解を解く必要がなくなり、漏れた構造を線形代数で直接解くだけで秘密が出てきます。つまり乱数の障害は、暗号の最弱点を「困難な問題」から「初等的な計算」へすり替える攻撃です。

本稿は乱数の良し悪しそのものよりも、乱数が壊れたときに何が・なぜ起きるかに焦点を当てます。生成器の品質要件についてはCSPRNG とエントロピーを参照してください。

ECDSA / DSA の nonce 再利用：秘密鍵が一行で解ける

ECDSA の署名は、署名ごとに秘密の一時値 k（per-signature nonce）を引き、r = (kG).x mod n、s = k⁻¹(z + d·r) mod n を計算します（z はメッセージのハッシュ、d は長期秘密鍵、n は曲線の位数）。ここで k が二つの署名で再利用されると、両署名の r が一致し、攻撃者にそれが観測できてしまいます。

同じ k を使った2署名:  s1 = k⁻¹(z1 + d·r),  s2 = k⁻¹(z2 + d·r)   (r 共通)
  s1 - s2 = k⁻¹(z1 - z2)
  k = (z1 - z2) / (s1 - s2)   mod n      # まず nonce が求まる
  d = (s1·k - z1) / r          mod n      # 続いて秘密鍵が一行で復元される

割り算はすべて位数 n を法とするモジュラ逆元です。署名は公開情報なので、攻撃者は曲線の難しさに一切触れず d を得ます。さらに恐ろしいのは、k の一部ビットが漏れるだけでも危険な点です。各署名で k の上位数ビットが既知なら、複数署名を「隠れた数問題（Hidden Number Problem）」に落とし込み、格子簡約（LLL/BKZ）で d を回収できます。数ビットの偏りが数十署名で命取りになります。

三つの実例とその原理

1. PlayStation 3（2010）。 ソニーはゲーム機の実行ファイルを ECDSA で署名していましたが、本来署名ごとに変えるべき k を**定数（固定値）**にしていました。結果、異なるファイルの二署名で r が常に一致し、上式そのままで署名用の長期秘密鍵が抽出されました。任意のコードに正規署名を付けられる状態となり、署名システム全体が崩壊しました。乱数を引き忘れて定数化するという、最も単純で最も破壊的な障害です。

2. Debian OpenSSL（2008）。 Debian の OpenSSL でエントロピー混入処理が誤って削除され、乱数の seed が実質プロセス ID 程度（最大 32768 通り）しか持たなくなりました。鍵生成はアルゴリズム的には正しく動くため、見た目は正常な鍵が出ます。しかし種が数万通りしかないため、生成され得る鍵は事前に全列挙でき、世界中で同一の SSH/SSL 鍵が量産されました。攻撃者は候補表を引くだけで該当鍵を割れます。エントロピー不足が鍵空間を指数サイズから総当たり可能サイズへ縮めた典型例です。

3. ブート直後・組み込み機器の seed 枯渇。 ディスク I/O もキー入力もない組み込み機器や VM の起動直後は、エントロピー源が乏しく初期 seed が弱くなります。2012 年の大規模調査では、独立に生成されたはずの多数の RSA 公開鍵が素因数 p を共有しており、無関係な二鍵の積から最大公約数を取るだけで両者の秘密鍵が割れました。原因は、起動直後の似通った状態で鍵生成が走り、seed が重複したことです。Android の SecureRandom 実装不良（2013）で同一 k が再利用され、Bitcoin 鍵が盗まれた事件も同じ系譜です。

設計で乱数事故を構造的に断つ

最も確実な対策は、危険なステップから乱数依存そのものを取り除くことです。

決定論的 nonce（RFC 6979）。 決定論的 ECDSA は k を乱数から引かず、秘密鍵 d とメッセージ z を HMAC で展開して導出します。同じ鍵・同じメッセージなら常に同じ k、異なるメッセージなら異なる k が出るため、再利用も偏りも構造的に起こり得ません。署名検証側は通常の ECDSA と互換で、生成側の乱数源が壊れていても安全です。Ed25519 も同様に、k をハッシュから決定論的に作る設計を最初から内蔵しており、nonce 事故を仕様レベルで排除しています。詳しくは署名スキームの内部を参照してください。

RFC 6979 の核心:
  k = HMAC_DRBG(seed = d || z)   # 秘密鍵とメッセージから決定論的に導出
  → 乱数源が壊れていても k は安全に一意。再利用・偏りが原理的に不可能

再播種（reseeding）と起動時ブロック。 乱数を使わざるを得ない箇所（鍵生成や IV）では、生成器が初期 seed を十分なエントロピーで完了する前に出力させないのが鉄則です。Linux の getrandom(2) は初期播種が完了するまでだけブロックし、以降は決してブロックしません。起動直後の組み込み機器・VM では、ハードウェア乱数（RDSEED／TPM）や保存エントロピーを早期注入し、播種完了まで鍵生成を待たせます。稼働中も定期的に新しいエントロピーを混ぜる再播種で、内部状態が漏れても未来の出力を回復させます。

実務での原則

乱数障害の本質は「毎回独立に予測不可能な値が出る」という前提が、コードのバグ・パッチ・仮想化・組み込み環境で静かに破れることです。確認すべき習慣は具体的です。

• 署名は決定論的方式を既定にする：新規実装では Ed25519 か RFC 6979 の決定論的 ECDSA を選び、k を乱数源から切り離す。これだけで nonce 再利用クラスの事故が消える。
• 乱数は OS の CSPRNG を直接呼ぶ：getrandom(2)／os.urandom／SecureRandom.getInstanceStrong()／crypto/rand を使い、Math.random や java.util.Random を鍵・nonce・トークンに絶対使わない。アプリ層で seed を自作・保存しない。
• 複製と起動時を疑う：VM スナップショット・コンテナイメージ・fork 後は RNG 状態の独立性が崩れる前提で、復元時の再播種や鍵再生成を組み込む。組み込み機器は播種完了まで鍵生成を待たせる。
• 鍵そのものの素性も検証する：生成済み鍵に対し、既知の弱鍵リスト照合や、フリート全体での共有素因数チェック（GCD バッチ）を回す。鍵の保管は鍵管理ライフサイクルとHSM による鍵保護の原則に従う。

アルゴリズムの強度を語る前に、その鍵と nonce がどこで・どれだけのエントロピーから・本当に毎回独立に生まれたかを確認する。乱数は暗号の安全性が最後に依存する一点であり、最も静かに壊れる一点でもあります。