MD5暴力破解高效多线程实现

Question

我想实现一个多线程的MD5暴力攻击算法(在C++中)。我知道彩虹表和字典，但我不打算实现最有效的MD5破解器，只对暴力算法感兴趣

问题是如何在线程之间分配所有可用长度的所有密码变体。例如，要恢复只包含4到6个符号的小写字符的密码，我们应该检查N=26^4+26^5+26^6=321254128组合(根据重复公式的变化，Vnk = n^k)

例如，在8个线程之间以相等部分分配所有排列，我们应该知道每(N/8)*t个变化，其中t=(1..7)。请注意，这些变体具有不同的长度(4,5,6)，并且4-5个符号的变体可以通过一定数量的6-符号变体被推送到同一线程中

有人知道该算法是如何在“真实世界”暴力破解应用程序中实现的吗？也许是某种线程池？

Answer 1

我发现非常灵活的方法是生成运行以下代码的线程：

void thread_fn() {
    PASSWORD_BLOCK block;
    while (get_next_password_block(&block) {
        for (PASSWORD password in block) {
            if (verify_password(password)) set_password_found(password);
        }
    }
}

通常，如果代码优化得很好，您将产生与活动核心一样多的线程；然而，在某些情况下，启动比核心更多的线程可以提供一些性能提升(这表明代码优化不是最优的)。

get_next_password_block()是完成所有锁定和同步的地方。此函数负责跟踪密码列表/范围、递增密码等。

为什么要使用PASSWORD_BLOCK，而不是只有一个密码？嗯，MD5是一个非常快的算法，所以如果我们为每个密码调用get_next_password_block()，那么锁定/递增的开销将是极端的。此外，SIMD指令允许我们执行批量MD5计算(一次4个密码)，因此我们需要一种快速有效的方法来获得大量密码，以减少开销。

块的具体大小取决于CPU的速度和算法的复杂度；对于MD5，我预计它会有数百万个密码。

Answer 2

这样做的“正确”方法应该是有一个工作线程池(等于CPU核心的数量，要么不计算超线程核心，要么将它们全部计算为“1”)和一个无锁FIFO队列，您可以向该队列提交大约十万个任务。这在同步开销和负载平衡之间提供了可接受的平衡。

诀窍是将工作划分为相对较小的组，这样只有一个线程执行最后一个组的时间不会太长(没有并行性！)，但同时不会使组太小，因此您会受到同步/总线争用的限制。MD5相当快，所以几万到几十万个工作项就可以了。

然而，考虑到具体的问题，这实际上是言过其实。太复杂了。

5个字母的密码比4个字母的密码多26倍，6个字母的密码比5个字母的多26倍，以此类推。换句话说，到目前为止，最长的密码长度使在组合总数中所占份额最大。所有4、5、6位数字组合加起来仅占所有7位数字组合的3.9%左右。换句话说，它们是完全无关紧要的。无论你如何处理剩下的部分，总运行时的96%都在7位数组合内。如果你考虑字母和数字或大写，那就更极端了。

因此，您可以简单地启动与CPU核心数量相同的线程，并在一个线程中运行所有4位数组合，在另一个线程中运行所有5位数组合，依此类推。这不是很好，但它已经足够好了，因为无论如何没有人会注意到区别。

然后简单地将可能的7位数组合划分为num_thread大小相等的范围，并让每个完成初始范围的线程继续该范围。

工作不会总是完美平衡，但它将在运行时的96%的时间内完全平衡。而且，它在任务管理(none)和同步(只需要设置一个全局标志以在找到匹配时退出)的绝对最小值下工作。

由于您不能期望完美的负载平衡，即使您进行了完美、正确的任务调度(因为线程调度掌握在操作系统手中，而不是您的手中)，所以这应该非常接近于“完美”方法。

或者，您可以考虑启动一个额外的线程，它完成所有但最长的组合范围(“微不足道的3%")，并平均划分其余的部分。这将在启动期间导致一些额外的上下文切换，但另一方面会使程序逻辑变得更加简单。

Answer 3

从消耗的工作量和产生的负载平衡这两个角度来看，将任务手动分区到工作线程的效率并不高。现代处理器和OSes甚至增加了最初看起来非常平衡的工作负载的不平衡，原因是：

缓存未命中:一个线程可能命中缓存，另一个线程可能会在每次内存加载操作中花费高达数千个周期的缓存未命中，其中相同的负载可以在几个cycles.

• Turbo-boost，电源管理和核心放置功能中执行。处理器本身和操作系统都可以管理有助于imbalance.

• Thread抢占的计算单元的频率和可用性:在现代多任务操作系统中运行的其他进程可以暂时中断线程的执行流。

现代的工作窃取调度算法在将不平衡的工作映射和负载平衡到工作线程方面非常有效:您只需描述潜在的并行性，任务调度器就会将其分配给可用的资源。工作窃取是一种分布式方法，它不涉及一个共享状态(例如迭代器)，因此没有瓶颈。

有关此类调度算法的实现的更多信息，请查看cilk、tbb或ppl。此外，它们对嵌套和递归并行构造也很友好，比如：

void check_from(std::string pass) {
    check_password(pass);
    if(pass.size() < MAX_SIZE)
        cilk_for(int i = 0; i < syms; i++)
            check_from(pass+sym[i]);
}