Có thể sử dụng GPU để tăng tốc băm trong Python không?

Question

Gần đây tôi đã đọc bài đăng trên blog của Jeff có tên là Speed Hashing, trong số những thứ khác anh đề cập rằng bạn có thể băm mọi thứ nhanh chóng bằng cách khai thác sức mạnh của GPU của bạn.

Tôi đã tự hỏi liệu có thể khai thác sức mạnh của GPU để băm những thứ bằng Python (md5, sha-1 vv) không?

Tôi quan tâm đến việc này để tìm hiểu xem tôi có thể nhanh chóng đẩy mạnh mọi thứ (không phải công cụ thực tế, từ các bãi dữ liệu bị rò rỉ cũ).

Tại thời điểm này, tôi đang làm việc này (ví dụ đơn giản):

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 

Nhưng tôi đã tự hỏi liệu có một cách để tăng tốc độ đó lên bằng cách sử dụng GPU? Tôi đoán tôi sẽ cần một mô-đun mà có thể tạo ra các chuỗi băm như thế này - có ai biết không?

Answer 1

Có hai trở ngại:

1. Viết một chương trình để thực thi trên GPU. AFAIK, hiện không có cơ chế nào để chuyển đổi chương trình Python sang mã được thực thi bởi GPU. Vì vậy, trừ khi bạn có thể tìm thấy những gì bạn cần (có thể là có thể, vì nó trông giống như một trường hợp sử dụng hợp lý), thì bạn sẽ phải làm điều đó bằng một trong các ngôn ngữ lập trình GPU (CUDA, OpenCL, Haskell, .. .)

2. Gọi chương trình đang chạy trên GPU từ Python và trao đổi dữ liệu. Có một số dự án Python + CUDA mà làm phần đó:

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

   Với phù hợp tìm kiếm, bạn có thể tìm hiểu thêm.

   Cũng Python GPU programming trông có liên quan

   Sau đó, chương trình Python sẽ được tải và gọi GPU 'hạt nhân' (chương trình tạo sử dụng công nghệ từ phần 1 của câu trả lời này) bằng một trong những công nghệ từ phần 2, hoặc tương đương.

EDIT Bạn có thể tạo ra toàn bộ các giá trị 'brute force', và băm md5 trên GPU. Sau đó, chỉ cần truy xuất kết quả bằng Python. Điều này có thể dễ dàng hơn việc tạo ra các giá trị trong Python, chuyển chúng vào GPU, sau đó lấy lại md5.

Nếu tôi đã hiểu, chương trình sẽ tạo tất cả 1 chuỗi ký tự 1, 2, 3, 4, 5 và 6 chữ thường, và tạo ra băm md5, vâng?

---

Edit2 - phân tích trước của tôi là hoàn toàn sai - Tôi xin lỗi

---

Edit3: Lướt Wikipedia MD5 nó trông giống như tính toán MD5 cho một chuỗi dài liên tục (ví dụ 6 ký tự ASCII) có thể được tối ưu hóa.

Theo mã giả của Wikipedia, nó chỉ là 64 vòng lặp, với các nhóm lặp 16 vòng lặp sử dụng cùng một số học. Vì vậy, nếu chính là dưới 55 byte, cốt lõi của việc tính toán có thể được 'trải' từ:

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 

tới:

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

Đó unrolling nguyên nhân một số việc lập chỉ mục mảng là không đổi, điều này sẽ cho phép trình biên dịch GPU tốt thực hiện việc truyền bá liên tục nhiều hơn. Điều này có thể giúp cải thiện đáng kể. Mỗi bước là khoảng 9 hoạt động và trình biên dịch sẽ cần phải trộn 5 mẩu dữ liệu, vì vậy khoảng 14 thao tác/bước * 64 bước, khoảng 1000 hoạt động.

Chỉnh sửa4:
Glerk! Tôi đã đọc thêm về thuật toán MD5 của Wikipedia - MD5 dễ tấn công hơn tôi nhận ra. Chỉ có hai vòng đầu tiên của mỗi nhóm 16 trực tiếp sử dụng chuỗi khóa biến là 6 byte, phần còn lại của chuỗi là hằng số. Phần còn lại của thuật toán là hoạt động xáo trộn và bit-khôn ngoan, có khả năng tuân theo tối ưu hóa rất đáng kể. Chỉ có 2 trong số 16 vòng liên quan đến khóa, sau đó có thể lên đến 8x nhanh hơn và có thể nhiều hơn 4x.

Vì vậy, thay vì hơn 1024 lõi GPU, chạy ở 1GHz, cho 1024 băm/micro, thay vì nói 4096/micro giây hoặc 8.096/chúng tôi = 4-8 băm/nanosecond

Có khoảng 27^6 phím = 387.420.489 phím và do đó băm md5.

387.420.489 phím/4-8/nano giây xấp xỉ = 0,05-0,1 giây

Truyền thông giữa máy chủ và GPU, sẽ là khá chậm, nhưng nhiều khó hơn 100%.

Vì vậy, khoảng từ 0,1 giây đến 0,2 giây.

Băm md5 là 16 byte, do đó sẽ tiêu thụ 6,2 GByte nếu nó được lưu trữ. Trên hai GPU hiện đại, sẽ chỉ yêu cầu 2 lần chuyển, nhưng sẽ là một chi phí rất quan trọng. Nếu các giá trị băm được lưu vào đĩa (thậm chí sử dụng SSD), hoặc di chuyển qua Ethernet 10Gbit, thế hệ băm sẽ bị thay đổi bởi thời gian I/O.

Chỉ có 94 ký tự ASCII in được, như vậy cho mỗi ASCII key 6 nhân vật:

94^6 = 689.869.781.056 phím/4-8/nano giây = 86-172 giây

Ôi - (!

phím Long, và một cái gì đó tốt hơn so với MD5!

lẽ cố gắng để viết một chương trình Python để tạo ra các thuật toán GPU tối ưu?

Tạo văn bản của hạt nhân GPU bằng cách 'Bỏ vòng' các vòng trong chương trình Python, và in văn bản của phép tính đường thẳng, với tất cả các hằng số được điền.

Sau đó cố gắng tìm hiểu xem chuỗi hướng dẫn tối ưu là tính MD5 cho mỗi độ dài khóa.Sử dụng chương trình chưa được kiểm tra, cố gắng theo dõi các hoạt động trên từng bit và các phụ thuộc, sau đó cố gắng tập hợp lại các bit & hoạt động của chúng thành các từ 32 bit tiếp giáp và tính toán đường thẳng mới. (Để công bằng, có lẽ trình biên dịch GPU có thể thực hiện một số thao tác này? Có thể thú vị khi tìm hiểu)