是否可以使用GPU加速Python中的散列？

Question

我最近阅读了Jeff的博客文章" Speed Hashing",除此之外,他还提到你可以通过利用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的速度？我猜我需要一个能够连续生成这样的哈希的模块 - 有人知道吗？

Answer 1

有两个障碍:

1. 编写程序以在GPU上执行.AFAIK,目前没有可用于将Python程序转换为GPU执行的代码的机制.因此,除非你能找到你需要的东西(这可能是可能的,因为它看起来像一个相当常见的用例),那么你将不得不使用其中一种GPU编程语言(CUDA,OpenCL,Haskell,... .)

2. 从Python调用GPU上运行的程序,并交换数据.有几个Python + CUDA项目可以完成这一部分:

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

   通过适当的搜索,您可能会发现更多

   Python GPU编程看起来也 很相似

   然后,Python程序将使用第2部分中的一种技术或等效技术加载并调用GPU"内核"(使用本答案第1部分中的技术创建的程序).

编辑您可能会生成整套"强力"值,以及GPU上的md5哈希值.然后使用Python检索结果.这可能比在Python中生成值,将它们传递给GPU,然后返回md5更容易.

如果我已经理解,程序会生成所有1个字符,2,3,4,5和6个小写字母字符串,并生成md5哈希,是吗？

Edit2 - 我以前的分析是完全错误的 - 我道歉

编辑3:略读维基百科MD5看起来像计算MD5的恒定长度字符串(例如6个ASCII字符)可以进行优化.

根据维基百科的伪代码,它只有64个循环,其中16个循环迭代组使用相同的算法.因此,如果密钥小于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个操作.

编辑4:
Glerk!我已经阅读了更多维基百科的MD5算法 - MD5比我意识到的更容易攻击.只有每组16个的前两个循环直接使用6个字节的变量键字符串,其余的字符串是常量.算法的其余部分是混洗和逐位操作,这些操作可能适用于非常显着的进一步优化.每16个循环中只有2个涉及密钥,然后可能快8倍,可能超过4倍.

因此,不是1024核心GPU,运行在1GHz,给出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.在两个现代GPU上,每个只需要2次传输,但这将是一个非常重要的开销.如果哈希值保存到磁盘(即使使用SSD),或者通过10Gbit以太网移动,则哈希生成会被I/O时间所淹没.

只有94个可打印的ASCII字符,因此对于每个ASCII 6字符键:

94 ^ 6 = 689,869,781,056键/ 4-8 /纳秒= 86-172秒

天啊!-(

长按键,比MD5更好!

也许尝试编写一个Python程序来生成最优的GPU算法？

通过'展开'Python程序中的循环生成GPU'内核'的文本,并打印直线计算的文本,填写所有常量.

然后尝试找出最佳的指令序列,以计算每个密钥长度的MD5.使用展开的程序,尝试跟踪每个位的操作和依赖关系,然后尝试将位及其操作重新组合为连续的32位字和新的直线计算.(公平地说,也许GPU编译器可以做到这一点吗？可能有趣的是找出来)