約7年前、Armadilloと呼ばれるトレッド用のキージェネレーターを備えたアーカイブがクラッカーの手に渡りました。 製品の感謝の気持ちのあるユーザーの一部は、耐久性をテストしたいと考えていました。 そして、クラッカーフォーラムでなくても、このような興味深いコードの無料監査をどこで受けられますか。
このジェネレーターは、クライアントがArmadilloで保護されたプログラムを購入したときに、マーチャントがそのライセンスキーを自動的に生成できるようにするために必要でした。 Armadillo自体でも使用されており、秘密を見つける機会があれば、彼女自身のためにkeygenを作成することも可能です。 コード監査を二重に面白くした理由。
だから、 ここにあるのは 、タイタニックの努力によって得られたオリジナルのアーカイブです。 （Cのソース）
脆弱性が隠されているものを正確に理解する手掛かりなしで試してください。 たくさんのコードがありますが、よく読まれています。 うまくいかなかった？ そして、528行を見ると？
さて、最初にいくつかのタイプのキーがあります。 古いもの、新しいものなど。私たちは、クールなものに興味があります。いわゆるショートレベルV10 ECC署名キーには、多数の数学と楕円の数学を持つクラスの半分が予約されています。 だから、我々はECDSAを破ります！
曲線は112ビットであり、秘密鍵（ x ）も112ビットです。 これはブルートフォースには少し多すぎます。
しかし！
秘密の値はPRNGから取得されます。PRNGは初期化されます...多田！ 32ビット数 ！
マタン
keygenを作成するには、プログラムの有効なキーのペアが必要です。 原則として、1つで十分ですが、ブルートフォースマシンの最初のバージョンでは、理論の正確性を検証するために2つのキーが必要でした。 以下にその理由を示します。
ああ、それを手に入れるのは簡単ではありませんでした！ 結局のところ、Armadilloを購入すると、一時キーが生成されます。 そして、開発者と個人的に話し合って初めて、本当の開発者になります。 しかし、私は再びトピックから戻って、続行します。
キーには、パラメーターECDSAパラメーターh、r、sがあります。 h-メッセージハッシュ、 r、s-署名パラメーター。
そこからそれらを取得する方法は、並べ替えて見ることができます。唯一のことは、 rとsがcとdで呼び出されることです。
したがって、2つのトリプル（r、s）hと（r '、s'）h 'があります。
（EC）DSA
DSAを例として使用して、式を示します。 脆弱性の本質は同じであり、フォーミュラの本質は同じです。それらははるかに読みやすいものです。
（EC）DSAの秘密鍵は乱数xです。 また（すでにDSAでのみ）、2つの大きな素数が選択されています。
q 、サイズはハッシュ関数のサイズ（ビット単位）と一致します。
（p-1）がqで割り切れるようなp。
また、 pを法とする乗法次数がqと なるような数gを選択します（wiki記事を参照）。 しかし、私たちは興味がありません、この数だけが式で見つかります。
デジタル署名を生成するには、次のアクションを実行します。
- ランダムkを生成
- 計算r = g k mod p mod q
- s = k -1 （H（ m ）+ x * r）mod qを計算する
H（ m ）は、署名するメッセージのハッシュです。
脆弱性
2つの同一のrを持つ2つの署名に出会ったと仮定します。 ■次のように考慮されます。
s = k -1 （H（m）+ x * r）mod q
s '= k -1 （H（m'）+ x * r）mod q
一方から他方を引きます（すべての操作はモジュロで実行されます）
s-s '= k -1 （h + x * r）-k -1 （h' + x * r）
これで、 kは同じであるため、括弧で囲むことができます
s– s '= k -1 （h + x * r-h'– x * r）
x * r縮小
s– s '= k -1 （h– h'）
kを左に移動
k =（h–h '）/（s-s'）
そして、思い出すと、 r = g k mod p mod qです。
ここでの問題はすべてkにあります。 既知の場合は、式によって秘密鍵xを計算できます
x =（（s * k）-h）* r -1 mod q
2010年にfail0verflowによって行われました。 ソニーのzhoporukyeエンコーダーはkを 1 回だけ生成すると考えました
Armadilloでは、物事はそれほど単純ではありませんでした。 rは常に異なっていましたが、ジェネレーターが32ビットの数値で初期化されたため、オプションの総数は2 32であり、数時間の列挙を行いました。
検索アルゴリズム（すべての演算法）：
- h '= -h
- r '= r -1
- s '= s * r'
- h '= h' * r '
- サイクルを0から2 32 -1で開始し、その中で：
- RNGカウンターを初期化します
- 数kを生成する
- 計算x =（（s * k）-h）* r -1 mod q
- これを保存x
そして、両方のキーについて。 2.6ギガバイトのデータがどこかにあることが判明しました。 次に、それらの中で同じxを見つける必要があります。それが秘密鍵になります。
同様に、Debianの任意のキーペアを計算できましたが、2008年にOpenSSLのバグにより、PRNGが0〜2 15の範囲の数値で初期化されたことが判明しました。 これはアルマジラよりもさらに簡単です。 そして、2006年から2008年までにDebianによって生成されたすべてのDSAキーが侵害されました 。
さて、armadillaに関しては、開発者を特にトロールし（keygenはいくつかのバージョンで動作しました）、脆弱性は修正されました（更新されたkeygenの種類も利用できます 、比較できます）。 ところで、このキャンペーンは排他的です。私はこのアーカイブを公開しませんでした。 ちなみに、それは前述のPSPハックよりも早く、Debianに穴が開いたものでした。
面白かったと思います。 PRNGの世話をします。
PS
これは同じアルマジラと私の名前の2つの有効なキーを持つアーカイブです。 ホームタスクとして自分用のキーを生成してみることができます。
80レベルの場合：1つのキーを実行します。 そして、何、オリンピアードの問題