前回のレッスンで学んだ数学は決して失敗しません。しかし、残念ながら頻繁に失敗するのは、3行目の抽選です。そしてそれが失敗すると、秘密鍵は高校生でも追える4行の代数で明らかになります。
同じ鍵と同じノンスkを使用して異なるメッセージに署名した2つの署名を考えてみましょう。rはkにGを掛けた点のx座標であり、kが同じであるため、2つのrは同一です。そしてそれは、ブロックチェーン上で誰でも無料で見ることができます。
2つの署名を書き出します。s1はkの逆数にz1とrにdを掛けたものを足したものを掛けたものです。s2はkの逆数にz2とrにdを掛けたものを足したものを掛けたものです。片方からもう片方を引きます。rにdを掛けた項は同一なのでキャンセルされ、s1からs2を引いたものはkの逆数にz1からz2を引いたものを掛けたものになります。これを整理すると、kはz1からz2を引いたものをs1からs2を引いたもので割ったものになります。kを手に入れたら、最初の方程式に戻り、dを整理します。dはs1にkを掛けてz1を引いたものをrで割ったものです。
これで終わりです。2回の引き算、2回の割り算で秘密鍵が画面に表示されます。ブルートフォースも、テーブルも、特別なハードウェアも必要ありません。そして、事後に防御する方法はありません。なぜなら、2つの署名はすでに公開されており、誰もそれを消すことはできないからです。
最初の有名なケースはBitcoinではありませんでした。2010年12月27日、ベルリンで開催されたChaos Computer Clubの会議で、グループfail0verflowは、SonyがPlayStation 3のソフトウェアに常に同じkを使用して署名していることを示しました。それはコードに書かれた定数値でした。任意の2つの署名で十分でした。コンソールのすべてのソフトウェアを認証する鍵がステージ上で公開されました。
Bitcoinでの同等の災害は2013年8月に発生しました。Androidの乱数生成器の欠陥により、アプリケーションは同じランダムシードを受け取り、複数のトランザクションに署名するウォレットは問題を示すことなくノンスを繰り返しました。8月11日、bitcoin.orgは警告を発表しました。ブロックチェーンをスキャンして繰り返されたrの値を探していた人々は、すでに影響を受けたアドレスを空にしていました。
問題は過去のものではありません。ブロックチェーン全体を調べて繰り返されたrを探す研究者たちは、ほとんどが手作りのウォレットや即席のプログラムからのものですが、依然として発見しています。
防御策はエレガントで、2013年以来の標準です。それは抽選をやめることです。RFC 6979規格は、秘密鍵とメッセージのハッシュを使用してkを決定的に導出する方法を説明しています。kは依然として外部の人には予測不可能ですが、それはマシンの乱数生成器の質に依存しなくなります。同じ鍵が同じメッセージに署名すると、常に同じ署名が生成されます。これは安全であるだけでなく、テストにも便利です。
同じ問題のより微妙なバージョンも存在し、それは美しいので最後の段落に値します。ノンス全体を繰り返す必要はありません。少し漏れるだけで十分です。例えば、最初のビットが予測可能である場合、生成器が偏っているためです。各署名は情報の断片を提供します。それらを数百集めると、格子削減技術を使用して、これらの断片から完全な秘密鍵を回復できます。ノンスが一度も繰り返されていなくてもです。
これらの破綻に共通する点に注目してください。どれも曲線を攻撃していません。secp256k1は無傷であり、離散対数は未解決のままです。常に落ちたのは、誤ったコードの一部や欠陥のある生成器でした。
しかし、数学に直接アプローチする攻撃のファミリー全体が存在します。それは数学が脆弱であると信じているからではなく、空間の平方根が恐ろしくなくなる範囲を選ぶからです。それがブロックチェーンの課題を可能にするものであり、次のモジュールのテーマです。