NIST楕円曲線シードのバウンティ
(words.filippo.io)- 現代暗号で広く使われている 5つのNIST楕円曲線のシードは、1990年代にNSAが提供した値に由来しており、その元の入力を見つけるために $12,288のバウンティが設定されている
- 対象はFIPS 186-2の P-192、P-224、P-256、P-384、P-521 で、成功者が米国の501(c)(3)慈善団体への寄付を選んだ場合、支払額は $36,864 と3倍になる
- シードはJerry Solinasが1997年に作成したものとされ、英語の文をSHA-1でハッシュした可能性があるが、実際の文言は機器の交換やアップグレード後に失われた状態である
- 文言の形式は、ピリオド、改行、カウンターの位置と形式、曲線名の有無まで不確実で、まず約 12k件のハッシュ一覧を攻撃対象としている
- 少なくとも1つのpre-seedを最初に提出すると $6,144、5つすべてを最初に提出すると残りの $6,144 を受け取れ、提出順はメールサーバーのReceivedヘッダーで判定される
バウンティ対象と支払規模
- 公開バウンティの目的は、5つのNIST楕円曲線のシードを作った ハッシュ入力値（pre-seed） を見つけること
- 総バウンティは $12,288、つまり12 Ki$に設定されている
- 成功者が現金ではなく米国の 501(c)(3)慈善団体への寄付を選ぶと、総額は $36,864 に増える
- クラック対象のハッシュは次の5つ
3045AE6FC8422F64ED579528D38120EAE12196D5BD71344799D5C7FCDC45B59FA3B9AB8F6A948BC5C49D360886E704936A6678E1139D26B7819F7E90A335926AA319A27A1D00896A6773A4827ACDAC73D09E8800291CB85396CC6717393284AAA0DA64BA
NIST曲線のシードが疑念を持たれた理由
- NIST曲線 P-192、P-224、P-256、P-384、P-521 は2000年のFIPS 186-2で公開され、ANSI X9.62方式に従って、任意のシードをSHA-1でハッシュした出力から一部のパラメーターを導出している
- 多くの暗号システムがNIST曲線を使用しており、とくに P-256 と P-384 が広く使われている
- 2つの曲線はCommercial National Security Algorithm Suiteに含まれる
- Webの多くを保護するECDSA X.509証明書にも使われている
- Steve Weisの NIST curve seed origins は、FIPS 186仕様に入った任意シードについて知られていることを整理している
- シードはNSAが提供したものと見られる
- Jerry Solinasが1997年に生成したものとされる
- 英語の文をSHA-1でハッシュして作った可能性がある
- Jerry Solinasは例として
SHA1("Jerry deserves a raise.")のようなシードを使ったと話したことがあるが、実際の文言は失われており、似た文言もハッシュと一致しなかった
pre-seedの発見が減らし得る不信感
- NIST曲線は最近の評価では、より肯定的に見える面がある
- complete addition formulas が主要なfootgunを緩和している
- より安全なインターフェース設計の方法が知られるようになった
- cofactor攻撃に免疫のある素数位数曲線の価値も、より明確になった
- 一部の非実務者の間では、NSAが意図的に弱い曲線を選ぶためにシードを選択した可能性があるという懸念が残っている
- KoblitzとMenezesの A riddle wrapped in an enigma は、NSAがシードを完全に制御していたとしても、そのような攻撃は説得力が低いと見ている
- 25年間にわたって学界や業界が発見できないほど大きな弱い曲線クラスが必要になるためである
- こうした懸念に十分な根拠があるようには見えないが、pre-seedの発見はNIST曲線をめぐる FUD を減らす助けになり得る
- 英語のpreimageを見つけても rigidity が完全に保証されるわけではないが、暗号史で欠けていた1ピースを埋める作業にはなり得る
ハッシュ入力値について知られている手がかり
- 入力値はJerry Solinasに言及する 英語の文言である可能性が高く、他の人名やカウンターが入っていた可能性もある
- カウンターが必要だった可能性が高い理由は、曲線のビットサイズに応じて、192〜521個のハッシュのうちおよそ1個だけが曲線生成に適しているためである
- 最大の曲線を基準にすると、カウンターが 2400未満である確率は99%
- P-256を基準にすると、カウンターが 1175未満である確率がある
- P-192とP-256のシードは以前のANSI X9.62標準に例として登場しており、残りはFIPS 186-2で新たに登場したため、文の構造が異なる可能性がある
- バウンティ対象は5つの素数位数NIST曲線だけだが、テストコストが低いなら、ANSI X9.62の他の例やFIPS 186-2のbinary curveシードもあわせて試せる
- ANSI prime192v2、prime192v3、prime239v1、prime239v2、prime239v3はバウンティ対象ではない
- NIST B-163、B-233、B-283、B-409、B-571もバウンティ対象ではない
あり得る文字列形式と攻撃リスト
- 文字列形式自体が 謎として残っている
- 文がピリオドで終わるかもしれず、終わらないかもしれない
- 改行があるかもしれず、ないかもしれない
- カウンターは10進数かもしれず、leading zeroがあるかもしれず、16ビットまたは32ビットのバイナリかもしれない
- カウンターがピリオドの後に来るか、別の区切り方で付いていた可能性がある
- 同じ文に異なるカウンターを付けてすべてのシードを作った可能性も、各シードごとに異なる文を使った可能性もある
- 曲線名やサイズが文言に含まれていた可能性もある
- 人の記憶には誤りが多いため、間接証言の細部の一部が間違っていた可能性も残されている
- カウンターの代わりに
SHA-1(s)、SHA-1(SHA-1(s))のような反復ハッシュを使った可能性もある - 別の候補は、
SHA-1(s)から始めてANSI X9.62 Section A.3.3.1のようにハッシュ値をインクリメントする方式である - 攻撃対象リストとして、約 12k件のハッシュを含む nist-and-ansi-prime-order-seeds-increments-99-percent.txt が提供されている
- このリストは、FIPS 186-2とANSI X9.62のprime order curve seedそれぞれについて、99%の確率空間をカバーする
- 多数のハッシュを確認するコストが低いなら、このリストを攻撃対象にすることが推奨される
- 可能なら、ハッシュの先頭 16バイト だけを比較しても同じ結果を得られる
- SHA-1はブルートフォースが非常に高速なため、passphraseクラッキングやbrainwalletブルートフォースの経験がある人に適した問題である
提出方法と支払条件
- 5つの素数位数NIST曲線のpre-seedを
seeds@filippo.ioに最初にメールで提出した人がバウンティを受け取る - 支払構造は2段階
- 少なくとも 1つのpre-seed を最初に提出すると、半額の $6,144 が支払われる
- 5つのpre-seedすべて を最初に提出すると、残りの $6,144 が支払われる
- 1人が両方の支払いを受け取れるため、5つすべてを見つけるまで待つ必要はない
- 現金受け取りと米国の 501(c)(3)慈善団体への寄付のどちらかを選べる
- 慈善団体への寄付を選ぶと金額は3倍になる
- 価値観と著しく合わない慈善団体の選択は拒否される可能性がある
- 米国人またはイタリア国籍者が法的に送金できない相手であれば、慈善団体オプションを選ぶ必要がある
- 現金バウンティに対する税金は受取人の責任である
- 提出メールの件名には、allowlistingルールを通過するよう
ANTISPAMを入れる必要がある - 提出順はメールホストの Receivedヘッダー が最終基準となる
- バウンティはシードが公に知られた時点で失効し、そうでなければこのページで別途告知があるまで有効である
- バウンティを取り消す、または減額する場合は 6か月前 に告知される
- シードを見つける方法に制限はない
- ブルートフォース、巧妙な推測、調査、過去のNISTバックアップの復元など、どの方法でもよい
- 望まなければ方法は尋ねないという条件が付いている
1件のコメント
Hacker News の意見
この背景がかなり面白いのですが、1990年代に NSA の Jerry Solinas が作った NIST P-curve の「ランダム」シードは、実は
"Give Jerry a raise"の変形文字列を SHA1 ハッシュした値だった、という話が最近出回っています。当時は、文字列を SHA1 に通せばシードの構造が消えるため、NSA が意図的に弱いシードを選ぶことはできない、という信頼の仕組みだと見なされていました。
しかし2000年代に NIST/NSA が自ら評判を損ねたことで、この説明だけでは陰謀論を鎮めるには不十分になり、後に NIST がシードが benign だったことを示そうとして Jerry Solinas に再構成させようとしたところ、当の本人が使った文字列を忘れてしまっていたそうです。
本物の陰謀論者なら、このシードを生成する文字列は誰にも見つけられないと見るでしょうが、もし誰かが見つければ、NIST P-curve が悪意を持って生成されたという説にはかなり大きな打撃になり得るので、面白いバウンティです。
"Give Jerry a raise of $100000 dollars now!!!"のような文字列のハッシュがシードと一致するものを見つけたとしても、それが悪意がなかった証拠にはならないと思います。弱い曲線が持つべき特殊な性質を知っていたなら、似た文字列の変形を大量にハッシュして、望む性質の定数が出るまで選べたはずだからです。
SSLv2 と SSLv3 がよい例で、出力サイズは SHA1 と合いますが、
echo "$string" | md5sum | sha1sumのようなパイプラインだったとしても、それほど驚きではありません。https://eprint.iacr.org/2015/1018
https://eprint.iacr.org/2015/1018.pdf
同じような バックドア疑惑は (EC)DSA にもあり、RSA 支持者たちは、NSA が DSA にバックドアを仕込んだから推しているのだと主張しましたが、証拠はなく、20年間 DSA や ECDSA にバックドアを入れる方法も見つかっていないそうです。
また、ある標準化会議で NSA の代表が電話をして戻ってきたあと、ECC は Federal Reserve を含む米国政府の全機関の安全な通信に十分だと NSA は信じている、と述べて皆が驚いたという逸話もあります。
DES の調整は後に 差分解読への防御だったことが明らかになり、元の SHA である SHA-0 の弱点が最終版の SHA-1 にはなかったのと同じように、NSA のほかの行動も疑わしく受け止められていました。
どちらの曲線でも G の選択は、怪しいほどサイズが合う x 座標を持つ点の2倍で、その特徴が両方の曲線で同じです。
これらの曲線で G の選択は唯一エントロピーの大きい入力ですが、実際にはほぼ無関係であることが証明可能で、それを選んだ人が特定の任意の 離散対数を1つ知る程度です。
こじつけのプロトコルではバックドアになり得るかもしれませんが、かなり作為的なものになるでしょう。それでも唯一わからないパラメータなので、探してみる価値はあると思いました。
P-curve のシードが見つかれば、ほかの曲線の生成点に使われたシードと似ている可能性もあり、その小さな謎も解けるかもしれません。
文言は、理論上は望むハッシュが出るように選べてしまいます。
英国のGCHQは、国内のどの研究所や大学よりも多くの数学者を雇用している。米国の対応機関も似たようなものだと思う。
Diffie-Hellman鍵交換も、DiffieとHellmanが再発見する前にGCHQとNSAは知っていた。
情報機関の基礎能力について断定するのは難しく、彼らが実際にこのような弱い曲線の族を知っていると言っているわけではないが、不可能とも見なしにくい。この分野は彼らの本業なのだから。
たいていは、学界が非常に優秀なので、NSAが何かをやったならすでに発見されているはずだ、という話になり、同意しなければ事情を知らないFUD扱いされる。この記事もその路線を繰り返しているが、組織的なバウンティによって問題がより真剣に扱われるのは良いことだ。
私は過去に暗号の仕事をしており、数年間、業務上暗号論文を定期的にレビューしていた。学会への参加や研究者との対話、複数の「風変わりな」楕円曲線暗号実装も経験した。完全な内部者ではないが完全な外部者でもない立場から見ると、この通説は危険に思える。
核心となる論拠は2つある。NIST曲線の標準化にクレプトグラフィ攻撃が可能だったなら学界や産業界がすでに見つけていたはずだ、という主張と、Dual_EC_DRBGがすぐに疑われたのだから公開暗号コミュニティはバックドアをうまく見つけられる、という主張だ。
1つ目は説得力が弱い。学界にはファイルドロワー問題と「publish or perish」のインセンティブがあり、若い研究者にとって、新しいゼロ知識証明アルゴリズムを作って引用される論文を出すことと、誰もが強いと信じているアルゴリズムを攻撃して何も得られないことのどちらが有利かは明らかだ。
「多くの賢い人たちが深く研究したが何も見つけられなかった」という専門家の合意が根拠になっているが、学界ではネガティブな結果を出版するのが難しいため、実際にどれだけの努力が投じられたのかを知る方法がない。
クレプトグラフィ、つまり標準にバックドアを入れる方法そのものも、NSAでなければほとんど役に立たず、良いキャリアパスではない。産業界への転身や引用の面でも不利だ。
一方でNSAは学界より高い給与を出せるし、学界全体より多くの研究者を雇って、失敗の可能性が高い研究や標準のバックドアにしか役立たない研究に専念させることができる。また、ハードウェア予算のために学界の暗号研究ではできない学際的研究も、数十年にわたって行えた。
ECCの理解度がNSAと学界のどちらで高いかに賭けるなら、火力は政府側にあり、比較にならない。政府が雇用している数学博士の数はおおよそ推測できるが、学界がこの問題空間に実際に投入した火力は分からない。
2つ目の論拠も理想的ではない。Dual_EC_DRBGだけでなく、NIST曲線についても人々はすぐに懸念を示していた。違いは、前者では必要な攻撃を実行する既知のアルゴリズムがあったが、後者ではなかったというだけだ。
そもそも、このような論争を不要にする方法は数十年前から知られており、NIST曲線がSHA1の出力から作られた理由もそのためだ。NIST曲線を段階的に廃止する最良の時期は数十年前で、次善の時期は今だ。
このバウンティに貢献する理由は、それが本当にパスワードクラッキング可能なフレーズなら、それを突き止めることに歴史的に大きな意味があるからだ。
NISTの楕円曲線がNSAの提供したシードをハッシュして作られたというのは、かなり不安だ。
「心配するな、取るに足らない文をハッシュして作っただけだ。今では忘れてしまったが、Jerryが昇給について冗談を言っただけだ」というように聞こえる。
なぜもっと早く厳格な検証を経なかったのか、そして利害の異なる複数の当事者のランダムシードやハードウェア乱数生成器などを混ぜるような、より合理的なシード選択をしなかったのか、信じがたい。
そういう方法が良かっただろうが、当時はその必要性を見ていた人は多くなかったはずだ。
https://en.wikipedia.org/wiki/Utah_Data_Center
Dan Boneh教授が背景を説明した動画がある: https://youtu.be/8WDOpzxpnTE?t=892
正しく理解できているなら、コミュニティは出所の分からない怪しい文字列を受け入れ、ハッシュに既知の別の入力を入れて出所が明確な文字列に置き換えるのは非常に簡単だった、ということなのか？
残念ながら、NSAと暗号標準に関して無能が取り沙汰される例は、私の知る限りこれだけで、普通は逆方向の話だ。
さらに問題なのは、NISTにはすでに楕円曲線関連の標準にバックドアを入れた前歴があり、このメカニズムでは信頼を生み出せないことも即座に指摘されていたのに、NISTもNSAも何の措置も取らなかったことだ。Dual_EC_DRBGの時と同じだ。
なおさら問題なのは、NSAが2015年に、NIST曲線より後の別の曲線へアップグレードしないよう明示的に述べたことだ。量子コンピュータが間もなくECC全体を破れるほど良くなるので、全員がポスト量子暗号へ移行すべきだ、という理由だった。
ECCがうまく機能していて、量子コンピュータがまだ遠く、人々をできるだけ長くNIST曲線に縛りつけておきたいなら、まさにそう言っただろう。
暗号コミュニティは、この状況で名誉ある立場にあるとは言い難い。ほぼ25年が経ち、この問題のないより新しい曲線があるのに、なぜNIST曲線はいまだに使われているのか？ SHA1のように段階的に退役させようとする取り組みはどこにあるのか？ この記事はむしろ、その曲線を宣伝しているように見える。
運がいいと思うなら、ここで SHA1 ハッシュの推測を試せます: https://wending.dev/hash_guessing/
NSA のシード生成者が暗号学とコンピュータについて少しでも知っていたなら、良い曲線が出るまで異なるフレーズを 500 個も手で入力していたはずがありません
仮にそうしていたとしても、末尾にピリオドを付ける、大文字小文字を変える、タイトルケースにするなど、考えられる変形は無限にあります
試すべきもっともらしい変形の一覧が完全になることはまずありませんが、このページのように SHA1 ハッシュだけを生成するのでは、句読点や大文字小文字まで正しく文字列を推測できたとしても、実際のハッシュを見つけるのは事実上不可能です
少なくとも結果のハッシュがインクリメントされた値かどうか確認するために、先頭または末尾の 10 バイト程度が一致するかは確認できるべきです。それでも大半は時間の無駄になるだけで、作者もそこから何もつながらないことは分かっているはずです
ページには、これはデモ用のおもちゃにすぎず、正しく推測しても実際のシードを見つけられるわけではない、と書くべきです
暗号学者たちの激しい論争を長く見てきて学んだのは、「Bernstein に賭けるな、NIST を信じるな」でした
今では「Bernstein や Filippo に賭けるな、NIST を信じるな。この 2 つのルールが衝突したら、それでも NIST を信じるな」に改めるべきだと思います
SHA-1 が破られたのは確かですが、主に長さ拡張攻撃による衝突や既知平文攻撃のような問題だと思っていました
ハッシュだけが与えられたときに実質的に 合言葉を見つけるのは、依然として扱いが難しいと考えていました
しかしシード構造の仮説が正しければ、ここでは原像耐性はそれほど重要ではありません。SHA-1 は非常に高速で並列化もしやすいため、
"Jerry needs a raise"の変形空間を粘り強く探索する人が元の入力を発見する可能性はかなりありますSHA1 自体とはあまり関係ありません