代码之家 › 专栏 › 技术社区 › russau

创建自己的MD5冲突

hash language-agnostic algorithm

russau · 技术社区 · 15 年前

我正在做一个关于MD5碰撞的演示,我想告诉大家碰撞的可能性有多大。

最好有两个文本块散列到相同的内容,并解释在碰撞之前需要[a-z a-z]的多少个组合。

显而易见的答案是散列所有可能的组合,直到命中两个相同的散列。那么,你将如何对其进行编码呢?作为一个快速的实验,我尝试对5列[a-z]的每一个组合进行哈希处理,将其存储在.NET哈希表中,并捕获冲突异常。有两个问题-哈希表最终会超时,我很确定我需要更多的字符。

显然,这个数据结构太大,在内存中无法处理,所以现在我将不得不涉及到一个数据库。听起来也是一个很好的测试Azure的项目-有点像 these guys .

有人能指出我的方向吗? 有效率的 这样做的方式?

5 回复 | 直到 9 年前

Community Egal 7 年前

以下两个不同的128字节序列哈希相同:

MD5哈希 :79054025255FB1A26E4BC422AEF54EB4

以下差异突出显示(粗体)。对不起,有点难看。

d131dd02c5e6eec4693d9a0698aff95c 2fcab58712467eab4004583eb8fb7f89 
55ad340609f4b30283e488832571415a 085125e8f7cdc99fd91dbdf280373c5b 
d8823e3156348f5bae6dacd436c919c6 dd53e2b487da03fd02396306d248cda0 
e99f33420f577ee8ce54b67080a80d1e c69821bcb6a8839396f9652b6ff72a70

和

d131dd02c5e6eec4693d9a0698aff95c 2fcab50712467eab4004583eb8fb7f89 
55ad340609f4b30283e4888325f1415a 085125e8f7cdc99fd91dbd7280373c5b 
d8823e3156348f5bae6dacd436c919c6 dd53e23487da03fd02396306d248cda0 
e99f33420f577ee8ce54b67080280d1e c69821bcb6a8839396f965ab6ff72a70

碰撞/阻塞1的可视化(来源: Links.Org )

alt text

碰撞/块2的可视化(来源: 链接,org )

alt text

Nick Johnson David Cournapeau 15 年前

如果你说的是直接碰撞的可能性有多大——一个没有蓄意造成碰撞的尝试——那么你会失望的:你需要平均生成2^64个明文,然后才能看到碰撞,这比你在合理的(或真正的,电动汽车)中所能做的要大得多。在合理的时间内。

如果你想证明故意制造碰撞的难度,其他答案已经证明了这一点。但是,要求字符串完全是文本的额外约束使得这些方法在很大程度上都不可行。

ShreevatsaR 12 年前

很难只使用文本文件,阿法克。你可以得到一些碰撞,但是让它们也来自[a-z a-z]并不容易。

另一方面,如果您只需要两个具有相同哈希值的“有意义”文件,您可以使用PostScript这样的方法来完成:使用不同的二进制blob导致冲突,并使用条件表达式相应地显示不同的输出。

参见 this problem (H2部分)和 solution . 例如, this PS file 和 this one 具有相同的MD5sum,但它们都是格式良好的PostScript文件,在打开它们时,它们中的文本完全不同。

brianegge 15 年前

我想看看 Hashcash . 使用有效的散列算法(如MD5),计算与位数的指数碰撞的时间。hashcash所做的是计算部分碰撞。也就是说,哈希的低16位匹配。为了使低16位匹配,必须尝试平均散列2^15个不同的组合。如果您知道16、24或32位冲突需要多长时间,那么您可以很容易地计算出更多位的时间。

-2

Loren Pechtel 15 年前

这种散列法的要点是,碰撞极不可能发生。你不可能偶然产生一台机器——你的机器几乎肯定会在你成功之前死于老年。如果您能够合理地生成冲突,那么使用散列的整个点就会消失!