我试图找到两个消息之间的冲突,这将导致相同的CRC哈希.考虑到我使用CRC32,有什么方法可以缩短我在进行暴力攻击时必须尝试的消息列表？
任何带有相关提示的网站链接都会有所帮助.我已经有了一个强力算法,它会做到这一点,但它只是增加整数,看它是否会匹配其他哈希值.
小智 23
这完全取决于你所说的"消息".如果你可以在其中一条消息中添加四个字节的乱码.(IE四个字节在消息的上下文中没有任何意义.)然后,在最真实的意义上,它变得微不足道.
考虑通过CRC32状态机的位.
CRC32基于galois反馈移位寄存器,其状态中的每个位将被有效载荷数据中32位的感应替换.在每个位的归纳处,多项式指示的位置将与从移位寄存器的末尾观察到的序列相对应.在填充移位寄存器之前,该序列不受输入数据的影响.
举个例子,假设我们有一个移位寄存器,它填充初始状态10101110,多项式10000011,并填充未知位X.
Polynomial * ** |feedback (End of SR.)
State 10101110 0
State X1010111 1
State XX101000 0
State XXX10100 0
State XXXX1010 0
State XXXXX101 1
State XXXXXX01 1
State XXXXXXX1 1
State XXXXXXXX 0
在SR被填满之前,反馈不是X的反馈!因此,为了生成具有预定校验和的消息,您可以获取新消息,生成CRC,并计算出接下来的32位反馈.这可以在CRC功能的32个步骤中完成.然后,您需要计算此反馈对移位寄存器内容的影响.
执行此操作的快捷方式是使用四个零字节填充消息,然后查看校验和.(校验和是最后SR的状态,如果填充四个零字节则是反馈和空字节的影响.)
使用您想要的校验和值影响的异或,用该计算值替换四字节尾部并重新生成校验和.您可以使用生成CRC32的任何程序,十六进制编辑器和可以处理十六进制的计算器来执行此操作.
如果你想生成两条既完全正确又不包含尾随垃圾的消息,那么事情会变得更难.确定一些部分,您可以编写似乎合理的替代方案,长度完全相同.
以英文散文为例."我认为这可行"和"我相信这种方法"具有大致相似的含义,并且具有完全相同的长度.
在消息中识别足够的示例是非常棘手的一点(除非你想用空格作弊!)CRC 32是线性的,前提是数据在消息中具有正确的偏移量.所以CRC([messagea] [padding])^ CRC([padding] [messageb])= CRC([messagea] [messageb])作为一般提示,你需要处理一些带有单词对齐的警告,您希望将段落扩展到消息的"固定"部分.作为一般规则,您希望有n*1.5段的替代方案,其中n是CRC的大小.
您现在可以计算骨架消息所具有的CRC,每个替代段落对其的印象,然后绘制一个表格,比较每个段落的每个替代方案将产生的影响.然后,您需要选择将修改骨架CRC以匹配您想要的CRC的替代方案.解决这个问题实际上非常有趣,首先找到任何可以唯一修改位的替代方案,如果该位需要为您的CRC更改,请选择该替代方案并将其影响折叠到CRC中,然后再循环.这应该会减少您需要搜索的解决方案空间.
编码起来非常困难,但它会在很短的时间内产生碰撞.
mjv*_*mjv 14
在我的微积分缺陷的情况下,在N次试验后没有发现一次碰撞的概率在下表中近似:
N Probability ------- ----------- 50,000 74.7% 77,000 50.1% 78,000 49.2% 102,000 29.8% 110,000 24.5% 128,000 14.8% 150,000 7.3% 200,000 0.95%
换句话说,在找到重复之前必须计算超过200,000个CRC32值的概率小于1%,或者,在 102,000次尝试之前找到重复的概率是70.2%
BTW这是显着的,因为发现一次碰撞的概率很大比方说,第 200,000次尝试仍然是1%((4M - 200,0000)/ 4M)的1/1000,但可能在第200,000次尝试之前发现一次碰撞是准确的(无论如何,99%以上). 这表明到目前为止计算CRC数据库的兴趣.
我们当然可以花一些时间来研究CRC32算法及其基础数学,试图找到更有可能产生CRC32冲突的消息,但是相对少量的真正随机尝试需要找到至少一次具有准确定性的碰撞,这使得这种密码分析方法几乎不值得努力.例如,假设我们可以发现一种方法来选择相互碰撞的可能性高10倍的消息,我们仍然需要尝试大约63,000次,然后才能达到至少一次碰撞的99%几率(优于200,000但仍然需要大致相同类型的应用程序.)
在这方面,我们唯一想要考虑的是避免短于4个字节的消息(我在某处读到CRC32在此消息空间中是双射的因为在CRC32的最初目的是检测(并且可能自动纠正)消息中的这种小差异之后,以及避免过于相似的消息(即仅相差一个或两个字符).
因此,看起来分配的难度并不是找到以极快的速度计算CRC32的方法(尽管我们也不应该太慢),而是管理一个快速搜索的数据库,直到200,000条消息(或消息"密钥",下面有更多内容)及其相关的CRC32值.
实现这一切的一些想法