NIST楕円曲線シード懸賞金が請求されました

2026年10月16日 NIST楕円曲線シード懸賞金が請求されました NIST楕円曲線のシードがどのように生成されたかが判明しました。それは、忘れられた文章のハッシュではなく、1997年から1998年にかけてのタイムスタンプをシードとしたdrand48の出力でした。John Wood、Henry de Valence、Ava Howell、Zack Voase、Lucy Sweet、Amir Omidi、Paul Crowley、Iain McGinniss、Nicholas Carlini、そしてAnthropicのスティーブ・ワイスがこの謎を解き明かし、3年前に発表した懸賞金の全額を2026年10月15日 01:07:51 UTCに請求しました。彼らは賞金をLet's Encryptを運営する非営利団体ISRGに寄付することを選択し、その価値を36,864ドル（36Ki$）に倍増させました。懸賞金に貢献してくれたAmir Omidi、Chris Palmer、Colm MacCárthaigh、David Adrian、David Anderson、Jeff Hodges、Matt Green、Matthew McPherrin、Paul Kehrer、Ryan Sleevi、そしてSoatokに感謝します。これは、暗号史の一ページを埋めるのに役立ち、これらの重要な暗号プリミティブに対する信頼を強化します。 NIST楕円曲線（P-192, P-224, P-256, P-384, P-521）は、2000年にNISTによってFIPS 186-2で公開されました。これらは、ANSI X9.62に従って、任意のシードを選択し、それをSHA-1でハッシュし、その出力をパラメータの導出に使用することでランダムに生成されました。この週まで、これらの任意のシードがどのように選ばれたのか全く不明でした。伝承では、2023年初頭に亡くなったジェリー・ソリナス博士が、後に忘れてしまった英語の文章をハッシュして1997年に生成したとされていました。スティーブ・ワイスの記事や元の懸賞金発表で詳細を読むことができます。 記憶は誰にでもいたずらをすることがありますが、実際にはPOSIX標準のdrand48乱数生成器で生成されていたことが判明しました。アルゴリズムは非常にシンプルで、当時のUNIXタイムスタンプをsrand48()に渡し、drand48で1バイトずつ生成するというものです。20バイトの各シーケンスはANSI X9.62に従ってシードとして試行され、結果の曲線が有効でない場合は拒否されます。一部のタイムスタンプは、最初の1つを受け入れた後もシードの試行を続けることで、複数の曲線生成に使用されました。私は主張を検証するためにGoでアルゴリズムを再実装しました。詳細はAnthropicの解説記事をご覧ください。 ANSI X9.62の基準以外に、2つの追加の文書化されていない基準があります。1つはかなり明確ですが、もう1つはまだ不明です。結果の曲線の位数nのビット長が、曲線の基底体のビット長pよりも大きい場合、シードは拒否されます。（条件はより厳密なn < pではありません。なぜならprime239v2はp < n < 2²³⁹だからです。）これにより、公開された有効なシードの約2倍の候補が残ります。この最後のビットについては様々な説明を検討しましたが、適切なものは見つかりませんでした。同じRNGがシードの検証に使用され、RNG出力を消費して一部の候補をスキップした可能性がありますが、「ギャップ」は規則的ではありません。あるいは、アルゴリズムのいずれかにバグがあり、計算が半分間違った結果を返しただけかもしれません。これらの計算は、現在では市販のソフトウェアで数分で行えますが、1997年当時はまだ最先端でした。 srand48(863711343) [1997-05-15 15:49:03 +0000 UTC]: 36番目のシード 25e5[...] を受け入れ: 公開されず 受け入れた1562番目のシード d09b[...] : 公開されず 受け入れた2185番目のシード e43b[...] : prime239v1 受け入れた2320番目のシード e8b4[...] : prime239v2 受け入れた2491番目のシード 1256[...] : 公開されず 受け入れた2682番目のシード d2c1[...] : 公開されず 受け入れた2863番目のシード 3a70[...] : 公開されず 受け入れた3048番目のシード 7d73[...] : prime239v3 srand48(863966734) [1997-05-18 14:45:34 +0000 UTC]: 139番目のシード 3045[...] を受け入れ: P-192 a.k.a. prime192v1 受け入れた2198番目のシード 692d[...] : 公開されず 受け入れた5228番目のシード c469[...] : prime192v3 受け入れた5405番目のシード 3ad1[...] : 公開されず 受け入れた6013番目のシード 31a9[...] : prime192v2 srand48(871002724) [1997-08-08 01:12:04 +0000 UTC]: 1136番目のシード d09e[...] を受け入れ: P-521 srand48(871696354) [1997-08-16 01:52:34 +0000 UTC]: 876番目のシード 50c7[...] を受け入れ: 公開されず 受け入れた1842番目のシード c49d[...] : P-256 a.k.a. prime256v1 srand48(872952608) [1997-08-30 14:50:08 +0000 UTC]: 2688番目のシード a335[...] を受け入れ: P-384 srand48(891607927) [1998-04-03 12:52:07 +0000 UTC]: 777番目のシード d007[...] を受け入れ: 公開されず 受け入れた1485番目のシード 18cf[...] : 公開されず 受け入れた5736番目のシード 3c17[...] : 公開されず 受け入れた7026番目のシード bd71[...] : P-224 これは、NIST曲線に基づく楕円曲線暗号のセキュリティに何を意味するのでしょうか？さて、この発見以前から、実務家の間には深刻な懸念はありませんでした。2015年の論文「A riddle wrapped in an enigma」のセクション3.1で、KoblitzとMenezesは、NSAが15年以上（現在は25年）の暗号解読を逃れた脆弱性を悪用するシードを選択できたとは考えにくいという説得力のある議論をしています。しかし、その論文の後続バージョンで報告されているように、Daniel BernsteinとTanja Langeは2017年にKoblitzとMenezesに、シード選択における70ビットの自由度を悪用して、仮説上の61ビットの弱素数位数曲線のクラスを標的とする可能性のある技術について説明しました。（Bernsteinは競合する楕円曲線設計であるCurve25519の作者です。）これは、一般大衆（多くはその後他の隣接する陰謀論に移ったが）に大きなアピールがあった、永続的な陰謀論に寄与しました。これらの憶測は、堅牢な暗号システムへの信頼を損ない、私の懸賞金発表の動機の一部でした。 今週の発見は、BernsteinとLangeが説明した技術を完全に排除します。たとえNSAが1997年から1998年の任意のタイムスタンプと、最初の16個の素数位数候補のいずれか（説明されていない拒否を寛大に考慮した場合）を選択する自由があったとしても、彼らはわずか30ビット強の自由度しか持たなかったでしょう。仮説上の少数の弱曲線クラスを意図的に標的とするには十分ではなく、いかなる種類のNOBUSバックドアを埋め込むにも十分ではありません。決定論的かつヘッジされたECDSA署名アルゴリズム、形式的に検証されたフィールド実装、そしてRenes、Costello、Batinaによる2015年の完全加算公式と合わせて、これはNIST楕円曲線暗号の「復権の弧」をうまく完成させ、私は個人的にはCurve25519/Ed25519/X25519よりも推奨するでしょう。ポスト量子署名に置き換えられる直前です。 P.S. Anthropicチームは、NIST B曲線（バイナリフィールド上のもの）のシードがどのように生成されたかも解明しましたが、誰もそれらを使用しないので、誰が気にするでしょうか。 写真 台湾のファミリーマートで、この素敵なサイコロセットを見つけました。1回のロールはlog₂(6²⁰) ≈ 51.7ビットのエントロピーを持ちます。2回振れば、かなり堅牢な暗号キーを作成できます！Geomys FIPS 140-3エントロピーソース（もちろんそうではありませんが、それも持っています）とラベルを付けて、配布用のノベルティにするのは面白いと思いました。しかし、オンラインで注文する方法が見つからなかったので、12以上のファミリーマートを訪れて50パック持ち帰りました。 ノベルティと言えば、srand48()シードを使ったステッカーと、Anthropicチームおよび懸賞金貢献者向けのTシャツを100%作成します。他のシードベースのノベルティの提案も受け付けます。もし興味があれば、Blueskyの@filippo.abyssdomain.expertまたはMastodonの@filippo@abyssdomain.expertで私をフォローしてください。