12

私は最近、「 Speed Hashing」というタイトルの Jeff のブログ記事を読みました。その中で彼は、GPU のパワーを活用することで非常に高速に物事をハッシュできると述べています。

GPU のパワーを利用して Python (md5、sha-1 など) でハッシュ化できるかどうか疑問に思っていました。

私はこれに興味があります。これは、物事をブルートフォースできる速度を確認しようとしているからです (古いリークされたデータダンプからの現実世界のものではありません)。

現時点では、私はこのようなことをしています (簡略化された例):

from itertools import product
from hashlib import md5

hashes = ["some","hashes"]

chars = []
for i in range(97,123): # a-z only
    chars.append(chr(i))

for i in range(1,6): # all combos of a-z, 1-5 chars
    for c in product(chars,repeat=i):
       s = ''.join(c)
       if md5(s).hexdigest() in hashes:
           print "Found",s

しかし、GPUを使用してそれを高速化する方法があるかどうか疑問に思っていましたか? このようなハッシュを連続的に生成するモジュールが必要になると思います-誰か知っていますか?

4

1 に答える 1

26

次の 2 つの障害があります。

  1. GPU で実行するプログラムを作成します。知る限り、Python プログラムを GPU によって実行されるコードに変換するために現在利用できるメカニズムはありません。したがって、必要なものが見つからない限り (かなり一般的なユースケースのように見えるため、可能かもしれません)、GPU プログラミング言語 (CUDA、OpenCL、Haskell、.. .)

  2. Python から GPU 上で動作するプログラムを呼び出し、データを交換します。その部分を行う Python+CUDA プロジェクトがいくつかあります。

    適切な検索を行うと、さらに多くの情報を見つけることができます。

    Python GPUプログラミングも 関連しているようです

    次に、Python プログラムは GPU の「カーネル」(この回答のパート 1 のテクノロジを使用して作成されたプログラム) をロードし、パート 2 のテクノロジのいずれか、または同等のものを使用して呼び出します。

編集「ブルートフォース」値のセット全体と、GPU 上の md5 ハッシュを生成する場合があります。次に、Python を使用して結果を取得します。これは、Python で値を生成して GPU に渡し、md5 を取得するよりも簡単かもしれません。

私が理解していれば、プログラムは 1 文字、2、3、4、5、および 6 個の小文字の文字列をすべて生成し、md5 ハッシュを生成します。

Edit2 - 私の以前の分析は完全に間違っていました - 申し訳ありません

Edit3: Wikipedia MD5のスキミング一定長の文字列 (たとえば 6 つの ASCII 文字) の MD5 の計算を最適化できるようです。

ウィキペディアの疑似コードによると、同じ演算を使用する 16 ループ反復のグループを含む、64 ループのみです。そのため、キーが 55 バイト未満の場合、計算のコアは以下から「展開」できます。

for i from 0 to 63
    if 0 ≤ i ≤ 15 then
        f := (b and c) or ((not b) and d)
        g := i
    else if 16 ≤ i ≤ 31
        f := (d and b) or ((not d) and c)
        g := (5×i + 1) mod 16
    else if 32 ≤ i ≤ 47
        f := b xor c xor d
        g := (3×i + 5) mod 16
    else if 48 ≤ i ≤ 63
        f := c xor (b or (not d))
        g := (7×i) mod 16
    temp := d
    d := c
    c := b
    b := b + leftrotate((a + f + k[i] + w[g]) , r[i])
    a := temp
end for

に：

// i == 0
f := (b and c) or ((not b) and d)   // +4 ops
// g := i
temp := d
d := c
c := b
b := b + leftrotate((a + f + k[0] + w[0]) , r[0])  // 9 ops
a := temp
// i == 1
f := (b and c) or ((not b) and d)
// g := i
temp := d
d := c
c := b
b := b + leftrotate((a + f + k[1] + w[1]) , r[1])
a := temp

その展開により、配列のインデックス付けの一部が一定になり、優れた GPU コンパイラがさらに一定の伝播を実行できるようになります。これにより、大幅な改善が得られる可能性があります。各ステップは約 9 操作であり、コンパイラは 5 つのデータをシャッフルする必要があるため、約 14 操作/ステップ * 64 ステップ、約 1000 操作になります。

Edit4:
グラーク! ウィキペディアの MD5 アルゴリズムの詳細を読みました - MD5 は私が思っていたよりも簡単に攻撃できます。16 の各グループの最初の 2 つのループだけが 6 バイトの可変キー文字列を直接使用し、残りの文字列は定数です。アルゴリズムの残りの部分は、シャッフルとビット単位の操作であり、非常に重要なさらなる最適化に適している可能性があります。16 ループごとに 2 つだけがキーに関係するため、最大で 8 倍、場合によっては 4 倍以上高速になる可能性があります。

したがって、1GHz で動作する 1024 コア GPU ではなく、1024 ハッシュ/マイクロ秒を提供し、代わりに 4096/マイクロ秒または 8096/us = 4-8 ハッシュ/ナノ秒と言います。

約 27^6 キー = 387,420,489 キー、したがって md5 ハッシュがあります。

387,420,489 キー / 4-8/ナノ秒 = 約 0.05 - 0.1 秒

ホストと GPU 間の通信は非常に遅くなりますが、100% を超えることはありません。

つまり、およそ 0.1 秒から 0.2 秒の間です。

md5 ハッシュは 16 バイトなので、格納すると 6.2 GB を消費します。2 つの最新の GPU では、それぞれ 2 回の転送しか必要ありませんが、非常に大きなオーバーヘッドになります。ハッシュ値が (SSD を使用していても) ディスクに保存されるか、10Gbit イーサネットを介して移動される場合、ハッシュ生成は I/O 時間によって圧倒されます。

印刷可能な ASCII 文字は 94 文字しかないため、ASCII 6 文字キーごとに次のようになります。

94^6 = 689,869,781,056 キー / 4-8/ナノ秒 = 86-172 秒

ああ！-（

長いキー、そして MD5 より優れたもの!

最適な GPU アルゴリズムを生成する Python プログラムを作成してみませんか?

Python プログラム内でループを「展開」して GPU の「カーネル」のテキストを生成し、すべての定数を入力して直線計算のテキストを出力します。

次に、キーの長さごとに MD5 を計算するための最適な命令シーケンスを見つけてください。展開されたプログラムを使用して、各ビットの操作と依存関係を追跡し、ビットとその操作を連続した 32 ビット ワードと新しい直線計算に再構築します。（公平を期すために、GPUコンパイラはとにかくこれのいくつかを行うことができますか?見つけるのは興味深いかもしれません)

于 2012-04-06T19:52:39.527 に答える