グリッド攻撃について私たちは何を知っていますか?
まず、 楕円曲線デジタル署名アルゴリズム (ECDSA) は、多くのコード レビューで見られる一般的なデジタル署名スキームです。これにはいくつかの望ましい特性がありますが、秘密の nonce の 1 ビット未満しか明らかにしないサイドチャネル攻撃で秘密鍵を回復するのは非常に脆弱な場合もあります。
ECDSAデジタル署名アルゴリズムの特別な形式です(DSA)。DSAはかなり一般的なデジタル署名スキームであり、鍵の生成、署名、および検証の 3 つのアルゴリズムによって定義されます。 鍵生成アルゴリズムは、秘密鍵と公開鍵を生成します。 秘密鍵は署名の作成を担当します。 公開鍵は署名の検証を担当します。 署名アルゴリズムは、メッセージと秘密鍵を入力として受け取り、署名を生成します。検証アルゴリズムは、メッセージ、署名、および公開鍵を入力として取り、 署名が有効かどうかを示すtrueまたは の値を返します。false
DSA は任意の数学的グループに対して定義されており、このスキームは離散対数問題がそのグループにとって困難である限り安全です。一般的に使用されるグループは、素数 p を法とする整数です。
このグループに加えて、グループ ジェネレータ g といくつかの暗号的に安全な ハッシュ 関数 がありますH。私たちはそれを仮定することができ、 常識になるでしょうp , g . H
鍵生成は、最初 x にモジュロ整数から 値をランダムに選択することによって機能しますp 。次に、値が計算されます y = g^x mod p
署名の秘密鍵は
x、公開鍵はyです。署名キーは、署名を作成できるようにするものであるため、秘密にしておく必要があります。
署名アルゴリズムは、メッセージ m と秘密鍵 x から署名を作成します。まず、乱数群の要素が生成され k ます。これはナンスとして知られており、攻撃に関しては重要です。
次に、値が計算され r = g^k mod p 、 s = ( k^-1 ( H ( m ) + xr )) mod p
ここで k^- 1 、 は逆群で、 H ( m ) はハッシュ m を計算し、その結果を p を法とする整数として解釈した結果です。
署名は のペアとして定義され ( r , s )ます。(注: または のr いずれか の値sが と等しい場合 0、アルゴリズムは の新しい値で再開されます k )。
検証アルゴリズムは、署名 ( r , s )、メッセージ m 、および公開鍵 y を入力として受け取ります。とすると、アルゴリズムはtrue ŝ = s^-1 を返すのは、 の場合のみです r , s ≠ 0 и r = ( g H ( m ) y r ) ŝ 。
この検証チェックが機能する理由 g^H( m ) y^r = g^H(m)+ xr = g^ksは、したがって (g^H(m)y^r)^ŝ = g^k = r
デジタル署名方式は、偽造できない場合、安全であると見なされます。
不変性には正式な暗号化の意味がありますが、大まかに言えば、秘密鍵を知らなければ署名を作成できないことを意味します (秘密鍵から作成された既存の署名をコピーした場合を除く)。離散ログDSAの仮定の下で偽造することは不可能であること が証明されて います 。
DSA 数学的グループに対して定義されます。DSA この数学的グループとして楕円曲線のグループで使用される場合、それを と呼び ます ECDSA。 楕円曲線グループ( x , y )は、ある の方程式を満たす の y^2 = x^3 + ax + b ペア である楕円曲線ポイントで構成され a , b ます。このブログ投稿で知っておく必要があるのは、楕円曲線を使用して有限群を定義できることです。つまり、群生成器 g (楕円曲線の点)と、 これとまったく同じように加算演算 と ドット乗算演算を取得できます。整数を使用できます。それらは有限群、ジェネレータ、g 、有限次数、 になり pます。このブログ投稿では、これらの楕円曲線演算がどのように機能するかを説明したり、知っている必要はありません 。
ECDSA と同じよう DSAに機能しますが、グループが異なります。 秘密鍵 x は、整数を法とするランダムな値のまま p です。 g が楕円曲線上の点であることを除いて、公開鍵 y は引き続き として計算され ます。y = g^xこれは、y も楕円曲線上の点になることを意味します (以前は、y は p を法とする整数でした)。もう 1 つの違いは、 r の値を計算する方法です。以前と同様に、p を法とする整数としてランダムなナンス k を生成します。を計算 g^k しますが、g は楕円曲線の点であり、したがって、 g^k も同様です。したがって、 を計算 ( x^k , y^k ) = g^k して設定 できますr = x^k 。もう意味は s は以前と同じように計算でき、以前と同じように を 法と( r , s )する整数のままである signature を取得しますp 。r 確認するには、計算方法が少し異なっていたという事実を修正する必要があります 。
したがって、前と同様に の値 を計算
( g^H(m)y^r)^ŝしますが 、その値は楕円曲線上の点であるためx、その点の座標を取得し、それを の値と比較しますr。
再利用されたナンスから の秘密鍵の回復 NONCES
それが何であり、どのように機能するかを理解したので 、その脆弱性ECDSA を示しましょう . 繰り返しますが、これはデジタル署名スキームであるため、 秘密鍵 はメッセージに署名した人以外には絶対に明かされないようにする必要があります。
ただし、署名者が署名を発行し、使用されたノンスも発行した場合、 攻撃者はすぐに秘密鍵 を復元でき ます。
( r , s ) メッセージ の署名を解放しm 、誤って nonce を使用していることを発見したとし ましょう k 。
s = ( k^-1 ( H ( m ) + xr )), 秘密鍵は簡単に計算できるので :
s = (k^-1(H(m) + xr))
ks = H(m) + xr
ks – H(m) = xr
x = r^-1(ks – H(m))
したがって、署名者は自分の 秘密鍵を秘密にしておく必要があるだけでなく、これまでに生成したすべての nonce を秘密にする必要があります。
署名者が各 ナンス
NONCESを秘密にしていても、誤って 1 つの ナンスNONCESを繰り返した場合 (異なるメッセージであっても)、 秘密鍵 もすぐに 復元できます。
メッセージと (それぞれ) 同じノンスから 作成された 2 つの署名を ( r , s 1 ) と します。これらは同じナンスを持つため、 r 値は同じになり、攻撃者がこれを検出するのは非常に簡単です。( r , s 2 )m 1m 2k
s1 = k^-1(H(m1) + xr) and s2 = k^-1(H(m2) + xr)
s1 – s2 = k^-1(H(m1) – H(m2))
k(s1 – s2) = H(m1) – H(m2)
k = (s1 – s2)^-1(H(m1) – H(m2))
上記の式を使用してノンスを回復したら k 、前述の攻撃を実行して秘密鍵を回復できます。
ちょっと消化してみましょう。
署名ナンス
NONCESが公開された場合、 秘密 鍵はすぐに 回復でき、署名スキーム全体が 壊れます。
また、メッセージが何であれ、2 つの nonce が繰り返された場合 、攻撃者 はこれを簡単に検出し、すぐ に秘密鍵を復元して、スキーム全体を破ることができます。
かなり脆くて 軽い攻撃ばかり！
しかし 、非常に詳細に説明されている 新しい ラティス アタックがあります(Joachim Breitner と Nadia Heninger) 。Йоахим Брайтнер и Надя Хенингер
ドキュメント [PDF] : Biased Nonce Sense: 暗号通貨の弱い ECDSA 署名に対する格子攻撃
ビットコイン ブロックチェーンで、特定のトランザクションが見つかりました。
トランザクション: 08d917f0fee48b0d765006fa52d62dd3d704563200f2817046973e3bf6d11f1f
ビットコインアドレスの場合: 15N1KY5ohztgCXtEe13BbGRk85x2FPgW8E
そして、偽の署名を増やしてグリッドを適用することができました
GOOGLE COLAB にパッケージをインストールし てPython スクリプト algorithmLLL.pyを使用する 場合
インストール >> SAGE + ECDSA + BITCOIN + アルゴリズム LLL
で 1 つの脆弱なトランザクションから
Private Keyなんとか 取得でき ました。Bitcoin WalletECDSA
秘密鍵が見つかりました！
https://www.blockchain.com/btc/address/15N1KY5ohztgCXtEe13BbGRk85x2FPgW8E
ADDR: 15N1KY5ohztgCXtEe13BbGRk85x2FPgW8E
WIF: 5JCAmNLXeSwi2SCgNH7wRL5qSQhPa7sZvj8eDwxisY5hJm8Uh92
HEX: 31AFD65CAD430D276E3360B1C762808D1D051154724B6FC15ED978FA9D06B1C1 このビデオは、 CRYPTO DEEP TECHポータル向けに作成され 、ビットコイン暗号通貨の脆弱な ECDSA 署名に対するデータと secp256k1 楕円曲線暗号の財務セキュリティを確保します。
ビデオ: https://youtu.be/YP4Xj6gUcf4
電報: https://t.me/cryptodeeeptech
ソース: https://cryptoeep.ru/lattice-attack
No comments:
Post a Comment