著者: シルヴァン・ペリシエ編集: Cointime.com 237

パブリック ブロックチェーンには、ECDSA 署名に対する攻撃の長い歴史があります。すべてのトランザクションは公開されるため、暗号化攻撃の完璧な実験場となります。 「A Curious Case of Half-Bitcoin ECDSA Random Numbers」と呼ばれるラティス攻撃が最近公開され、ビットコインで実験されました。半分ずつのフォンデュを愛するスイスのチームとして、私たちはこの攻撃を調査する必要がありました。以前の攻撃である「多項式乱数」も、この方法で ECDSA 乱数を生成できることがわかりました。この論文では、その方法を説明し、論文で得られた結果とどのように比較するかを示します。

前の攻撃

メッセージに署名するために、ECDSA は nonce と呼ばれる値を使用します。 nonce はランダムに生成される必要があり、署名されるメッセージごとに一意である必要があります。ビットコインとイーサリアムの secp256k1 曲線の場合、典型的なノンス値は次のとおりです。

ECDSA のよく知られ、よく研究されている落とし穴は、ノンスの再利用です。名前が示すように、ノンスが別の署名で再利用される場合、それらの署名から秘密鍵を復元できます。明らかに、ブロックチェーンに適用される最初の攻撃はノンス再利用攻撃です。 2 つの異なるメッセージが同じ nonce で署名されるとすぐに、秘密鍵が危険にさらされます。この問題は通常、RFC 6979 に従って決定論的な乱数を生成することで解決されます。

ただし、ECDSA ノンスは非常に重要であるため、生成に偏りがあると秘密キーの回復につながる可能性があります。したがって、より巧妙な格子ベースの攻撃が後にパブリック ブロックチェーンに適用されました。これらの攻撃では、64、110、128、および 160 ビットの長さの予想よりも短いノンスが回復される可能性があります。たとえば、次のように生成された乱数は、格子ベースの攻撃に対して脆弱です。

ノンスが小さいほど、攻撃に使用される格子の次元が小さくなり、攻撃の成功に必要な署名の数が少なくなります。 Biased Random Numbers の論文によると、2 つの 128 ビット乱数と 3 次元格子により、成功 (秘密キーの回復) の確率は 75% になります。 3 つの 170 ビット乱数と 4 次元格子を使用すると、95% の成功確率が得られます。この攻撃の変種は、共有のプレフィックスとサフィックスを持つノンスを検出するためにも適用できます。たとえば、次のように生成された乱数は、前述の攻撃や一般的なサフィックス構造に対して同様に脆弱です。

ポリノンス

ECDSA を攻撃するもう 1 つの方法は、乱数間の代数的関係を仮定することです。私たちのチームは、未知の係数 a_i 間に次の形式の多項式関係があると仮定する Polynonce 攻撃を提案しました。

k_{n+1} = a_1 k_n + a_0

また

k_{n+1} = a_2 k_n^2 + a_1 k_n + a_0

Polynonce 攻撃は、成功の確率 100% で代数的に秘密キーを回復できますが、線形の場合は 4 つの署名、二次の場合は 5 つの署名など​​が必要になります。この攻撃は主に多項式を解くことに依存しているため、格子ベースの攻撃と比較して非常に高速です。詳細については、この攻撃については今後開催される DEFCON カンファレンスで発表される予定です。

単一の署名

これまでのすべての攻撃では、同じ秘密キーからの少なくとも 2 つの異なる署名が必要でした。ただし、Ledger のようなウォレットは、単一の秘密キーを使用してトランザクションに署名し、その後秘密キーを変更します。これは、多くのビットコインのパブリック アドレスが現在 1 回しか使用されない理由を説明します。以下は、P2PKH トランザクションに限定された対数スケールでプロットされたビットコイン送金データ (2022 年 9 月 5 日時点、ブロック 752759) のグラフです。

これは、P2PKH トランザクションに使用される公開キーの 92% が 1 回のみ使用されていることを示しています。この機能は主にプライバシーを目的としていますが、間接的に以前の攻撃からも保護します。イーサリアムの場合は状況が少し異なります。 151429561 個の一意のキーから 1759432087 個の署名を分析し、線形スケール プロットを作成しました。

これは、P2PKH トランザクションに使用される公開キーの 92% が 1 回のみ使用されていることを示しています。この機能は主にプライバシーを目的としていますが、間接的に以前の攻撃からも保護します。イーサリアムの場合は状況が少し異なります。 151429561 個の一意のキーから 1759432087 個の署名を分析し、線形スケール プロットを作成しました。

これはまったく異なる状況です。公開鍵の 42% は 1 つの署名のみに使用され、22% は 2 つの署名に、13% は 3 つの署名に使用されます。したがって、イーサリアムではプライバシー保護手法はあまり適用されないか、まったく適用されないようです。

半分半分の乱数

最近、メッセージ ハッシュの上半分を使用して、ノンスが秘密キーの上半分と連結されるときに、いくつかの問題を引き起こす新しい攻撃方法が出現しました。つまり、乱数 k は次のように表すことができます。

k = h_{msb} || d_{msb}

この攻撃の新規性は、単一の署名から秘密鍵 d を回復できることです。以前の格子ベースの攻撃と同様に、乱数 k の式が ECDSA 式に挿入され、再配置されて隠れ数問題のインスタンスが形成されます。次に、BKZ アルゴリズムを使用してインスタンスが解決されます。この手法は、一度だけ使用される秘密キーを使用して発行されたトランザクションを攻撃するために必要な署名が 1 つだけであるため、非常に強力です。最適化されたバージョンの攻撃では、99.99% の成功率で 0.48 秒で秘密キーを回復できました。これは非常に強力ですが、作者がビットコイン ブロックチェーンへの攻撃を実行するのに 49 CPU 年かかりました。

Polynonce をハーフハーフ乱数に適用する

ハーフハーフ攻撃について読んでいると、Polynonce はハーフハーフ乱数を使用して秘密キーを回復するためにも使用できることがわかりました。 ECDSA 署名 (r, s)、メッセージ ハッシュ h、および秘密鍵 d については、ノンスに関連して次の関係があります。

k = s^{-1}(h + rd) mod q

前述の半々式を使用して生成された 2 つの乱数 k_0 と k_1 がある場合、それらの差は次のようになります。

k_0 - k_1 = s_0^{-1}h_0 - s_1^{-1}h_1 + (s_0^{-1}h_0 - s_1^{-1}h_1)d = h_{0,msb} - h_{1, msb}

他のすべての値が既知である d の線形方程式を見つけました。これにより、方程式を解いて秘密鍵 d を回復するための非常に高速な方法が提供されます。ただし、Polynonce を使用するには、同じ秘密キーからの 2 つの nonce と 2 つの署名が必要です。私たちはこれまでの攻撃に比べて大きなアドバンテージを失ってしまいました。それにもかかわらず、この攻撃の亜種は非常に高速であるため、最初に複数の署名を持つ公開鍵に対してこの攻撃を使用し、次に残りの署名に対してラティスベースの攻撃を使用することが可能です。

方程式の乱数の差は h_{0,msb} - h_{1,msb} のみに依存するため、これにより、式 k_i = h_{i,msb} || c の使用に戻ることができます (c は(シークレット) 定数) 生成されたすべての乱数。これはより一般的ですが、ビットコインの場合は少し複雑です。 ECDSA 署名 (r、s) から始まり、同じメッセージの別の署名 (r、-s) も有効です。ビットコインは署名の偽造を避けるために s の最大値を持つ署名を拒否するため、-k と k の両方を計算する必要があることを意味します。したがって、攻撃では、各ノンスの符号を推測する必要があります。

この構造は、共有サフィックスに対するラティス攻撃に関する以前の研究でも発見されているはずですが、成功率はわずか 75% でした。

結果

前回の分析で使用したビットコイン ブロックチェーン ダンプ ファイル (2022 年 9 月 5 日時点のブロック 752,759) に対して分析を実行しました。私たちは少なくとも 2 つの署名を持つ 3,400 万個の公開鍵を分析しました。 2.7 GHz クロックの 16 コア AMD プロセッサでは、10 分 23 秒かかりました。

私たちは 110 個の一意の秘密キーを見つけて回復することに成功しました。たとえば、住所

18zg6FG5pu8Bpq73L54AYvB8phTw3qCCR7

取引

私たちは 110 個の一意の秘密キーを見つけて回復することに成功しました。たとえば、住所

18zg6FG5pu8Bpq73L54AYvB8phTw3qCCR7

取引

f3151fc1b29c117f1e4b67045b2d2901e7c289f596c242d7de123243fb623981

と

f7bf1edf9d9cefa8421322c53bb00ecf118f99489171da72a9c11cf8d02b65f8

ハーフアンドハーフ方式を使用して乱数を生成します。私たちのスクリプトは、このアドレスの秘密キーを回復できます。

このようなトランザクションの nonce を再計算すると、次のようになります。

nonce の最下位半分が秘密キーの最上位半分に等しいことが明確にわかります。ただし、上で述べたように、他の興味深いケースを復元することができました。同じアドレスに対して 2 つのノンスが見つかりました。

この場合、実際には別の未知の定数が見つかったため、秘密キーは関係しません。また、このような乱数を使用する一部のキーは小さいキーであるという以前の調査結果も確認できました: d = {1, 2, 4, 7, 11, 24, 75, 77, 87, 128, 144, 549, 897 }。したがって、これらのキーは、Web サイト https://privatekeys.pw で行われる作業と同様に、ブルート フォース手法によって簡単に回復できます。残高がゼロ以外のアカウントは見つかりませんでした。ボットによって監視されており、残高が変化すると空になると考えられます。

この攻撃は非常に高速であるため、半乱数生成の他の亜種に対しても同じ攻撃を実行しました: k = h_{lsb} || d_{msb}, k = d_{msb} || h_{msb} および k = d_{msb} || h_{lsb} ですが、追加の結果は見つかりませんでした。

また、前回の攻撃中に収集されたイーサリアム データセットに対しても同じ攻撃を実行しました。同じマシンでの攻撃には 49 分 11 秒かかりました。この攻撃では秘密鍵は回復されませんでした。

これまでのさまざまな創造的な乱数生成構造は非常に興味深いもので、他にもエキゾチックな構造があるのではないかと考えました。これらの新たな攻撃では新しい秘密鍵は回復されませんが、他の弱い乱数生成アルゴリズムが以前のトランザクションで使用されなかったことを意味するものではなく、同様の方法で回復が達成できることを意味するものでもありません。このような問題が発見された場合、資金を保護する最善の方法は、これまで取引に使用されていない新しいアドレスに資金を移動し、脆弱なアドレスを空のままにすることです。私たちの攻撃スクリプトと得られた結果は、Polynonce 攻撃の Github リポジトリで入手できます。