Czy można używać GPU do przyspieszania mieszania w Pythonie?

Question

Niedawno przeczytałem post na blogu Jeffa zatytułowany Speed Hashing, w którym między innymi wspomniał, że możesz szybko mieszać rzeczy, wykorzystując moc swojego GPU.

Zastanawiam się, czy możliwe było wykorzystanie mocy procesora graficznego do mieszania rzeczy w Pythonie (md5, sha-1 itd.)?

Interesuje mnie to, ponieważ próbuję sprawdzić, jak szybko mogę wymuszać brutalne działania (a nie rzeczy z prawdziwego świata, ze starych wyciekanych zrzutów danych).

Obecnie robię tego typu rzeczy (uproszczony przykład):

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 

Ale zastanawiałem się, czy istnieje sposób, aby przyspieszyć że przy użyciu GPU? Zgaduję, że potrzebuję modułu, który generowałby takie hashe - czy ktoś o tym wie?

Answer 1

Istnieją dwie przeszkody:

1. napisanie programu do wykonania na GPU. AFAIK, nie ma obecnie mechanizmu do konwersji programu Python na kod wykonywany przez GPU. Więc jeśli nie znajdziesz tego, czego potrzebujesz (co może być możliwe, ponieważ wygląda na dość powszechny przypadek użycia), będziesz musiał to zrobić używając jednego z języków programowania GPU (CUDA, OpenCL, Haskell, .. .)

2. Wywołanie programu działającego na GPU z poziomu Pythona i wymiana danych. Istnieje kilka projektów Python + CUDA, które to zrobić część:

   • http://mathema.tician.de/software/pycuda
   • http://code.google.com/p/pystream/
   • https://launchpad.net/python-cuda

   z odpowiednimi poszukujący można znaleźć więcej.

   także Python GPU programming wygląda istotne

   Następnie program Python załaduje i powołać „jądro” GPU (program stworzony przy użyciu technologii z części 1 tej odpowiedzi) za pomocą jednej z technologii z części 2 lub równoważny.

EDIT może wygenerować cały zestaw wartości „brute force” oraz hashe MD5 na GPU. Następnie pobierz wyniki za pomocą Pythona. Może to być łatwiejsze niż generowanie wartości w Pythonie, przekazywanie ich do procesora graficznego, a następnie otrzymywanie md5.

Jeśli zrozumiałem, program generuje wszystkie 1, 2, 3, 4, 5 i 6 małych liter, i generuje hasz md5, tak?

---

Edit2 - mój poprzedni analiza była całkowicie błędne - Przepraszam

---

Edit3: Przeglądając Wikipedia MD5 wygląda obliczania MD5 dla długości stałej łańcucha (na przykład 6 znaków ASCII) mogą być optymalizowane.

Zgodnie z pseudokodem Wikipedii jest to tylko 64 pętle, z grupami po 16 powtórzeń pętli z wykorzystaniem tej samej arytmetyki. Tak więc, jeśli klucz jest pod 55 bajtów, rdzeń obliczeń może być „rozwinął” z:

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 

do:

// 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 

To rozwijając przyczyny niektóre z indeksowaniem tablicy być stała, co powinno pozwolić dobremu kompilatorowi GPU na jeszcze bardziej stałą propagację. Może to spowodować znaczną poprawę. Każdy krok to około 9 operacji, a kompilator będzie musiał przetasować 5 kawałków danych, czyli około 14 operacji/kroków * 64 kroków, około 1000 operacji.

Edytuj4:
Glerk! Czytałem więcej o algorytmie MD5 w Wikipedii - MD5 jest łatwiejszy do ataku, niż zdałem sobie z tego sprawy. Tylko pierwsze dwie pętle z każdej grupy 16 używają ciągów kluczy o zmiennej długości 6 bajtów, reszta łańcucha jest stała. Reszta algorytmu to tasowanie i operacje bitowe, które prawdopodobnie będą podlegały dalszej istotnej dalszej optymalizacji. Tylko 2 z każdych 16 pętli zawiera klucz, to może być do 8 razy szybciej i może więcej niż 4x.

Więc zamiast 1024 rdzeń GPU, działa na 1GHz, dając 1024 mieszań/mikrosekundy, zamiast powiedzieć 4096/mikrosekund lub 8096/us = 4-8 mieszań/nanosekundy

Istnieje około 27^6 klawiszy = 387420489 klucze, a zatem skróty md5.

387420489 klucze/4-8/nanosekundy przybliżeniu = 0,05 - 0,1 sekundy

komunikację pomiędzy gospodarza i graficznego, będzie bardzo powolne, lecz prawdopodobnie nie więcej niż 100%.

W przybliżeniu od 0,1 sekundy do 0,2 sekundy.

Wartość mieszania md5 wynosi 16 bajtów, więc zużyje 6,2 GB, jeśli ma być przechowywana. Na dwóch nowoczesnych procesorach graficznych wymagałoby to tylko 2 transfery, ale byłby bardzo istotny narzut. Jeśli wartości mieszania są zapisywane na dysku (nawet przy użyciu SSD) lub przenoszone przez sieć Ethernet 10 Gb/s, to generowanie skrótu jest przepełniane przez czas We/Wy.

Istnieją tylko 94 drukowane znaki ASCII, więc dla każdego klucza 6 znaków ASCII:

94^6 = 689,869,781,056 klucze/4-8/nanosekundy = 86-172 sekund

Oh My - (!

długie klucze i coś lepszego niż MD5!

Może spróbuj napisać program do generowania Python GPU algorytm optymalny?

Wygeneruj tekst jądra GPU przez "Rozwiń" pętle w programie Python i wydrukuj tekst obliczeń liniowych z wypełnionymi wszystkimi stałymi.

Następnie spróbuj dowiedzieć się, co optymalna sekwencja instrukcji polega na obliczeniu MD5 dla każdej długości klucza.Za pomocą rozwiniętego programu spróbuj śledzić operacje na każdym bicie i zależnościach, a następnie spróbuj ponownie scalić bity & w ciągłe słowa 32-bitowe i nowe obliczenia w linii prostej. (Aby być uczciwym, być może kompilator GPU może to zrobić w jakiś sposób? Może być interesujące dowiedzieć się)