algorithm - EngineYard SHA1 竞赛方法

Question

EngineYard正在举行比赛here ，其中给定一个短语和一个单词字典，提出一个 12 个单词的短语，其 SHA1 哈希与给定短语的 SHA1 哈希的汉明距离最小。

一些站点正在使用云/众包来尝试对其进行暴力破解，而其他站点则使用 CUDA 和 GPU。一些报告显示 GPU 的汉明距离在 30 左右，而众包 javascript 的汉明距离在 40 左右。

您对本次比赛的态度是什么？每个答案一种方法。

比赛已经结束

Answer 1

选项几乎是 (1) 蛮力，(2) 利用 SHA-1 中的弱点。如果你能在不到蛮力时间内用遗传算法解决这个问题，那么我认为这将构成 SHA-1 的定义弱点。当然，如果遗传算法能够在比蛮力时间更短的时间内产生精确匹配，那就可以了。

请注意，我不知道找到近似匹配的难度是否实际上是加密散列的必需属性。如果很容易找到近似匹配但仍然很难找到完全匹配，那么哈希对于所有标准加密应用程序是否安全？如果是这样，那么可能会有一个中间立场，您可以在其中使用 SHA-1 的某些属性，这不是弱点。

但是，我怀疑获胜短语必须恰好由给定词典中的 12 个单词组成的原因是因为我非常确信不会有不那么粗暴的方法。即使已知一种技术可以在 SHA-1 中找到近似原像，但要对其进行调整以产生合法的结果也很可能非常困难。