为什么 GPU 如此擅长破解密码?

信息安全 密码学 密码 哈希 蛮力 密码破解
2021-08-28 22:36:36

是什么让 GPU 如此快速地破解密码?

似乎采用良好的密码密钥派生函数(bcrpyt、PBKDF2、scrypt)而不是昨天的加密哈希(MD*、SHA*)背后的驱动力是,后者容易受到在 GPU 上运行并猜测大量数字的程序的攻击密码的速度非常快。为什么 GPU 在评估这些哈希函数方面会比 CPU 好得多?

2个回答

完成@Terry 的回答:GPU 有很多内核(数百个)。每个内核基本上能够在每个时钟周期计算一个 32 位算术运算——作为一个流水线事实上,GPU 在极高的并行性下工作得很好:当有许多相同的工作单元要执行时,实际上比实际的内核要多得多(“相同”的意思是“相同的指令”,但不是“相同的数据”)。

一些细节,对于有点旧的 NVidia 卡(GTX 9800+,从 2009 年初开始):有 128 个内核,分为 16 个“多核单元”。每个多核每个周期可以启动 8 次操作(因此有 128 个内核的概念:即 16 乘以 8)。多核以 32 个为一组处理工作单元(“线程”),因此当多核有一条指令要运行时,它实际上会在 4 个时钟周期内将该指令发送给它的 8 个核。这是操作启动:每个单独的操作最多需要 22 个时钟周期才能运行。您可以将进入电路的指令及其操作数想象为前进的前线,就像水池中的波浪:给定的波浪需要一些时间才能到达水池的另一端,但您可以顺序发送多个波浪。

所以只要你有至少 22 倍的“线程”来运行(即最少 22·128 = 2816),你就可以保持“每个周期 128 个 32 位操作”的节奏,这样线程就可以由同时执行相同指令的 32 个“相同”线程包组成,就像嘻哈舞者一样。在实践中,有一些内部阈值和约束需要更多线程才能实现最佳带宽,最高可达 4096 左右。

通过 SHA-1 实现,我可以实现接近 99% 的最佳带宽。SHA-1 使用了超过 1100 个 32 位操作(在 CPU 上大约是 900,但 GTX 9800+ 没有旋转操作码,因此旋转必须分为两个移位和一个逻辑或),而 GPU以 1450 MHz 运行,每秒总共进行约1.6 亿次 SHA-1 计算。这只有在您有数百万个 SHA-1 实例要并行计算时才能实现,就像密码破解的情况一样(在任何时候,您都需要 4096 个并行 SHA-1 来为 GPU 内核提供数据,但您也有处理输入潜在密码的 I/O 成本,如果您没有大量 SHA-1 实例要处理,这些成本将占主导地位)。

主机 PC 在其 CPU(四核 2.4 GHz Intel Core2)上可以达到每秒约4800 万次 SHA-1,是通过彻底优化的 SSE2 代码实现的。单个 SHA-1 在这样的 CPU 上将使用大约 500 个时钟周期(CPU 可以在一个周期内计算多个指令,前提是它们不竞争资源并且不相互依赖),但是,对于密码破解,值得使用具有 128 位寄存器的SSE2,并且能够并行计算 4 条指令。使用 SSE2 约束,运行四个并行 SHA-1 大约需要 800 个时钟周期,因此每个 SHA-1 实例需要 200 个时钟周期。该 CPU 中有四个内核,整个处理器以 2400 MHz 运行,因此每秒 4800 万次。

更新的硬件会更快,但 GPU 更快。GTX 680 拥有高达 1536 个内核,而GTX 690 中两个这样的 GPU。我们在这里谈论的是每秒数十亿个 SHA-1 实例。

(为了比较,我还在Cell 处理器上实现了 SHA-1 ,即 PS3 控制台中的 CPU,它有 8 个“SPU”协处理器。一个 SPU 不可用。加上其他 7 个,我达到了大约 1 亿每秒SHA-1,即比当代大PC CPU好,但不如同时代好的GPU。)


摘要: GPU 通过使用具有数百个(如果不是数千个)核心的重度并行性来实现出色的性能。这可以通过流水线(每个单独的操作需要许多周期来运行,但可以像高速公路上的卡车一样启动)和共享指令解码(因为许多内核将同时运行相同的指令)来实现。

GPU 擅长处理数学计算。图形渲染只是一系列复杂的数学计算。哈希算法也是如此。

GPU 有数百个内核,可用于并行计算数学函数。CPU通常有4-8个内核。尽管 CPU 内核比 GPU 内核快得多,但密码哈希是可以很容易并行完成的功能之一。这就是 GPU 在破解密码方面具有巨大优势的原因。

您应该注意到,在您提到的三种算法中,PBKDF2 在 GPU 上仍然可以相对容易地破解。PBKDF2 算法在非常基本的术语中使用 MD5 或 SHA1 等散列函数对密码进行数千次散列。虽然比简单的 MD5 或 SHA1 哈希要强大得多,但它仍然可以使用 GPU 相对快速地破解。

bcrypt 和 scrypt 旨在避免 GPU 为攻击者提供的大量破解时间加速。有关更多信息,请参阅 Thomas Pornin 这个令人难以置信的答案:https ://security.stackexchange.com/a/31846/10211