先週1/24(土)に江戸前セキュリティ勉強会で「偶然にも500万個のSSH公開鍵を手に入れた俺たちは」というタイトルでLT発表してきました。以下が発表資料です。
このプレゼン資料はLT用に圧縮して作ったので、わかりにくい部分があったかもしれません。そこで、Q&A形式で補足を書いてみました。
「多数の公開鍵から共通の素因数を探す攻撃はSSHユーザー鍵についても現実的脅威なのか？」
結論から言うと、SSHユーザー鍵に限れば脅威でないというのが個人的な考えです。
今回、論文「Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices」(PDF)を参考に多数のRSA公開鍵から最大公約数を求めるような攻撃をSSHユーザー鍵について試してみました。元論文では、この攻撃はSSHホスト鍵とSSL証明書に対して行われました。これについては次の日本語解説がわかりやすいと思います。
この日本語の資料にも書いてあるのですが、素数定理から十分な個数の素数が存在することが示せるので、たとえば2048bitのRSA鍵であれば素数p,qが他人と衝突する確率はほぼゼロです（誕生日のパラドックスでも太刀打ちできないくらい素数は大量にあるのです）。もし他人と衝突するようであれば、乱数生成器のエントロピー不足しか考えられません。
しかし、SSHホスト鍵およびSSL証明書については、このようなエントロピー不足の鍵が見つかってしまいました。元論文ではこうした鍵が作られる原因の一つとして、初回起動時にSSHホスト鍵やTLS鍵を自動生成するシステムの存在を指摘しています。公開鍵の鍵ペア生成ではエントロピーソースとして/dev/urandomが使われますが、OS起動直後は十分なエントロピーが蓄積されておらず、urandomはノンブロッキングで値を返してしまうために弱い鍵が作られうるというのです。
元論文によればOS起動から60秒程度で十分なエントロピーが得られるそうですので、手動で鍵生成する状況であればほぼ安全でしょう。今回SSHユーザー鍵について狙ったような最大公約数が得られなかったのも、SSHユーザー鍵が作られる状況では十分なエントロピーが得られている証拠と言えるかもしれません（サンプル数が少なすぎただけという可能性もありますが）。
つまり、多くのSSH公開鍵が全世界にむけて公開されているからといって、即座に脅威ではないと言えそうです。とはいえ無用なリスクを取りたくないという判断もあると思いますので、その場合はgithub.comに登録する鍵を普段の鍵と別にするのが正解でしょう。
「小さい素因数を含む鍵ができた原因は何か？」
今回、多数の公開鍵のうちで小さい素因数を含むものが見つかったことを紹介しました。公開鍵に含まれる合成数は巨大な素数p,qの積として作られるはずですから、小さい素因数が見つかるというのは異常事態です。この原因はコピペミスだろうと推測しましたが、これに疑問を持った方も多かったようです。
コピペミスといっても、何文字か欠けたり増えたりするようなミスをすると公開鍵として認識されません。全体の文字数が同じままで1文字が書き換わったり前後入れ替わったりするような難易度の高いミスをする必要がありますが、500万件中155件くらいなら起こりうる気がします。
鍵ペア生成のときに使っている確率的素数判定法が合成数を素数だと判定してしまったのではないか？と考えられた方がいらっしゃったようですが、これはありえないと思います。通常使われる素数判定法の誤判定の確率は非常に低い上に、誤判定した場合でもかなり大きな素因数を持つことが知られています（参照：「RSA鍵の生成時に確率的素数判定法を使って問題ないのか」）。一方で、今回見つかった素因数はいずれも小さく、155件も見つかったわけですから、今回の状況には合致しません。
ちなみに、見つかった素因数の中には2もありました。どんなSSH実装でも偶数を素数と判断するわけがありませんから、確証はないもののコピペミスくらいしか考えつかなかったというわけです。
「この資料、公開して良かったの？」
僕自身、割とギリギリな内容だと考えていたため、公開するかどうか悩みました。ただ、鍵長が短すぎる鍵や古いDebianで作られた鍵があるというのは調べなくても想像がつく内容なので、問題ないだろうと考えて公開することにしました。
とはいえ、あるだろうと想像していることと実際に見つけたこととは別ですから、こんな公開鍵を見つけたよとgithub.comに通報しておきました。
感想など
上に書いた通り今回はギリギリの内容だと考えていたため、当初はこんな風に発表するつもりはありませんでした。とはいえ、思ったより多くの人に面白いと思ってもらえたようで、結果的には発表して良かったです。また、普段と違うコミュニティの勉強会に行くと新しい気づきがあって楽しいですね。次回以降も参加したいと思いますので、皆様よろしくお願いいたします。
