3

我现在正在做我的 10 年级科学展览项目，但我有点碰壁了。我的项目正在测试并行性对暴力破解 md5 密码哈希的效率的影响。我将使用 1、4、16、32、64、128、512 和 1024 个线程计算它测试的密码组合数/秒，以查看它的效率。我不确定我会做字典蛮力还是纯蛮力。我认为字典更容易并行化；只需将列表拆分为每个线程的相等部分。我还没有写太多代码；我只是想在开始编码之前计划一下。

我的问题是：

  • 计算测试的密码组合/秒是根据线程数确定性能的最佳方法吗？

  • 字典还是纯蛮力？如果纯粹是蛮力，您将如何将任务拆分为可变数量的线程？

  • 还有其他建议吗？

4

4 回答 4

6

我并不是要抑制你的热情，但这已经是一个很好理解的问题。我将尝试解释下面会发生什么。但也许在另一个领域做你的项目会更好。“最大化 MD5 散列吞吐量”怎么样，那么您就不会仅限于查看线程。

我认为，当您编写项目时，您需要提供某种分析，以确定何时适合并行处理，何时不适合。

每次您的 CPU 更改为另一个线程时，它都必须保留当前线程上下文并加载新的线程上下文。这种开销不会发生在单线程进程中（垃圾收集等托管服务除外）。因此，在其他条件相同的情况下，添加线程不会提高性能，因为它必须完成原始工作负载以及所有上下文切换。

但是，如果您有多个 CPU（内核）可供使用，则为每个 CPU 创建一个线程意味着您可以并行计算而不会产生上下文切换成本。如果你有比 CPU 更多的线程，那么上下文切换将成为一个问题。

有 2 类计算：IO-bound 和 compute-bound。IO 密集型计算可能会花费大量 CPU 周期来等待来自某些硬件（如网卡或硬盘）的响应。由于这种开销，您可以将线程数增加到 CPU 再次达到极限的程度，这可以抵消上下文切换的成本。然而，线程数量是有限制的，超过这个限制，上下文切换将花费比线程阻塞 IO 更多的时间。

计算密集型计算只需要 CPU 时间来处理数字。这是密码破解者使用的计算类型。计算绑定操作不会被阻塞，因此添加比 CPU 更多的线程会降低整体吞吐量。

C# ThreadPool已经为您处理了所有这些 - 您只需添加任务，并将它们排队，直到线程可用。新线程仅在线程被阻塞时创建。这样，上下文切换被最小化。

我有一台四核机器 - 将问题分解为 4 个线程，每个线程在自己的核心上执行，或多或少与我的机器可以暴力破解密码一样快。

要认真并行化这个问题，您将需要大量 CPU。我读过关于使用显卡的 GPU来解决这个问题的文章。

如果对您有用的话，我在这里写了一个攻击向量分析。彩虹表和处理器/内存权衡将是另一个有趣的项目领域。

于 2011-10-09T02:15:03.730 回答
2

回答您的问题： 1) 没有什么比测试线程性能更好的方法了。根据目标问题中每个操作的独立程度，不同问题的线程规模不同。所以你可以试试字典的东西。但是，当您分析结果时，您得到的结果可能并不适用于所有问题。然而，一个非常流行的例子是人们尝试共享计数器，其中计数器由每个线程增加固定次数。

2）蛮力将覆盖大量的情况。事实上，通过蛮力，可以有无数种可能性。因此，您可能必须通过密码的最大长度等一些限制来限制您的密码。一种分配蛮力的方法是为每个线程分配不同的密码起始字符。然后该线程测试该起始字符的所有可能密码。一旦线程完成其工作，它会获得另一个起始字符，直到您使用所有可能的起始符号。

3) 我想给你的一个建议是在少量线程上进行测试。您将达到 1024 个线程。这不是一个好主意。一台机器上的内核数一般为 4 到 10 个。因此，线程数尽量不要超过内核数。因为，一个处理器不能同时运行多个线程。在任何给定时间，每个处理器都有一个线程。相反，尝试测量将问题分配给不同线程的不同方案的性能。

让我知道这是否有帮助！

于 2011-10-09T00:02:09.007 回答
1

一种适用于字典和所有可能密码的暴力破解的解决方案是使用一种基于将作业划分为工作单元的方法。有一个共享对象负责将问题空间划分为工作单元 - 理想情况下，每个工作需要 100 毫秒到 5 秒的时间 - 并为您启动的每个线程提供对该对象的引用。然后每个线程在这样的循环中运行：

for work_block in work_block_generator.get():
  for item in work_block:
    # Do work

与预先将整个工作区划分为每个线程一个块相比，这样做的优势在于，如果一个线程比其他线程工作得更快，它不会耗尽工作而只是闲置 - 它会拾取更多块。

理想情况下，您的工作项生成器将具有一个接口，该接口在调用时会返回一个迭代器，该迭代器本身会返回单个密码以进行测试。然后，基于字典的算法从字典中选择一个范围，而蛮力算法则选择一个前缀来测试每个批次。当然，您需要使用同步原语来阻止试图抢占工作单元的不同线程之间的竞争。

于 2011-10-09T04:10:50.853 回答
0

在字典和蛮力方法中，问题都是令人尴尬的并行。要使用 n 个线程将蛮力问题划分为 n 个线程，只需将前两个（或三个）字母（“前缀”）分成 n 个部分。然后，每个线程都有一组分配的前缀，例如“aa - fz”，它只负责测试其前缀后面的所有内容。

在实践中，字典通常在破解更多密码方面在统计上稍好一些，但是暴力破解，因为它涵盖了所有内容，不会错过目标长度内的密码。

于 2011-10-08T23:55:35.590 回答