NIST曲線にかけられた疑いの雲が晴れる
Cloud of suspicion lifted from NIST curves (johndcook.com)
要約
2000年に公開されたNISTの楕円曲線暗号に、NSAによるバックドアが仕込まれているのではないかという長年の疑いが、最近の研究によって晴らされました。Anthropicの研究者たちが、曲線生成のシード値が秘密のメッセージではなく日付に基づいて生成されており、NSA担当者の記憶違いであったことを突き止め、懸賞金を受け取りました。この結果により、NIST曲線は信頼を取り戻し、普及が妨げられていた要因が解消されました。
全文翻訳
NIST曲線にかかっていた疑念が晴れる
NISTは2000年に一連の楕円曲線暗号を公開しました。これらの曲線のシード値はNSAから提供されたもので、暗号学者はNSAが曲線にバックドアを仕込んだのではないかと疑っていました。そして、その疑念はもっともなものでした。NSAは実際にDual_EC_DRBG乱数生成器にバックドアを仕込んでいたのです。
2日前にAnthropicの研究者たちが、NIST曲線にバックドアが仕込まれていなかったことを示しました。この記事の残りの部分では、この結果を理解するために必要な背景を説明します。
楕円曲線暗号の安全性は、離散対数問題を解くことの困難さに依存しています。楕円曲線演算の文脈では、指数計算に相当する操作は容易ですが、対数計算に相当する操作は困難です。
一般的に、大きな楕円曲線上の離散対数問題を計算することは実用的ではありません。しかし、曲線に関する何らかの「一般的でない」性質を知っていれば、内部情報を持つ者にとっては離散対数問題を容易に計算できる可能性があります。
具体的には、NIST曲線は以下の形式をとります。
y² = x³ − 3x + b (mod p)
ここで、p は様々な値をとります。そして、疑念は b の選択に関するものでした。b の値がほとんどすべての場合において、我々の知る限り、楕円曲線上の暗号化は安全であるはずですが、原理的には、暗号化を弱めるために b の値を意図的に設計することが可能です。
では、その b はどこから来たのでしょうか？ 誠意をもって選ばれたのでしょうか？
シード値、つまり b の選択に関する懸念は、スノーデン事件の暴露を受けて高まりました。Daniel J. Bernstein は2014年9月6日にNSAのJerry Solinasにメールを送り、シード値の出所を尋ねました。Solinas はその後のメールで返信しました。彼は、シード値はユーモラスな英語メッセージのASCII表現をハッシュ化して生成されたと述べましたが、正確なメッセージやハッシュ手順はもはや覚えていないとのことでした。
2023年10月5日、Philippo Valsorda はNIST楕円曲線シードの起源をリバースエンジニアリングするための懸賞金を発表しました。2日前にAnthropicの研究者たちが懸賞金を請求しました。Valsorda は結果を検証し、賞金を授与しました。Solinas は誠意をもって曲線シードを見つけたものの、曲線が公開されてから長年が経過し、彼の記憶は薄れていたことが判明しました。現在、シード値の生成プロセスの一部として、フレーズではなく日付が使用されていたことがわかっています。
NIST曲線には、基底体における巧妙な演算トリックを可能にするなどの優れた特性がいくつかあります。しかし、その起源に関する疑念のために、これらの曲線の採用は遅れていました。今、曲線は潔白が証明されました。Valsorda が指摘するように
…これはNIST楕円曲線暗号の「復権の弧」をうまく締めくくるものであり、私は個人的にはCurve25519/Ed25519/X25519よりもこちらを推奨するでしょう。ポスト量子署名に置き換えられるちょうどその時に。
関連記事
[1] これは、LLMが必ずしも暗号化に対する脅威であることを意味するものではありません。NISTシードの探索には多くの総当たりが必要でした。総当たりでチェックする可能性を思いつくためにはある程度の巧妙さが必要でしたが、それもより高次の抽象化レベルでの総当たりと言えます。研究所が暗号プリミティブやプロトコルの弱点を探しているという憶測がありますが、それはシードの探索とは別の問題です。
[2] P-192、P-224、P-256、P-384、P-521曲線は、p を法とする整数の体上で構築されており、p のビット数は名前に対応しています。例えば、P-192曲線は、その基底体として2192 − 264 − 1 を法とする整数（192ビットの素数）を使用しています。