如何“人造”CRC碰撞？？？

还以明文“1234”和“12345678”为例，菜农来讲解如何“人造碰撞”。

可惜本坛的网页在vista下不能上传图片，十分之郁闷~~~

就模拟HotWC3密码网上在线演算器吧

初值：00  输入：1234   CRC：F1
加权：07  输出：7EF1

点击“CRC表”，可以从第2行看到：70 77 7E 79...

它表示输入为10时，对应输出为70，11对应77，12对应7E，13对应79

故有：

初值：00  输入：103A   CRC：F1
加权：07  输出：70F1

初值：00  输入：113D  CRC：F1
加权：07  输出：77F1

初值：00  输入：103A   CRC：F1
加权：07  输出：70F1

初值：00  输入：1234   CRC：F1
加权：07  输出：7EF1

初值：00  输入：1333   CRC：F1
加权：07  输出：79F1

这个例子估计有人明白了~~~“人造碰撞”实际很简单，不过下面的有点难度。

初值：00  输入：12345678   CRC：1C
加权：07  输出：7EF17C1C

如果我们想“碰撞”最小，即保留明文流不变的位数最小，“水平最高”也只有“12345XXX”了。

由于CRC“上次的密文是本次的权”，故保留：

初值：00  输入：12345XXX   CRC：1C
加权：07  输出：7EF1XX1C

又CRC是“流加密”，故(注意初值的变化，此时和上例就一样了)：

初值：F1  输入：5XXX   CRC：1C
加权：07  输出：XX1C

点击“CRC表”，可以从第6行看到：6E,69,60,67,72,75,7C,7B...

它表示输入为50时，对应输出为6E，51对应69，52对应60，...56对应7C,57对应7B

故有：
初值：F1  输入：506A   CRC：1C
加权：07  输出：6E1C

初值：F1  输入：516D   CRC：1C
加权：07  输出：691C

初值：F1  输入：5264  CRC：1C
加权：07  输出：601C

初值：F1  输入：5678  CRC：1C  (就是例子)
加权：07  输出：7C1C

初值：F1  输入：577F  CRC：1C
加权：07  输出：7B1C

也就是:

初值：00  输入：1234506A   CRC：1C
加权：07  输出：7EF16E1C

初值：00  输入：1234516D   CRC：1C
加权：07  输出：7EF1691C

初值：00  输入：12345264  CRC：1C
加权：07  输出：7EF1601C

初值：00  输入：12345678  CRC：1C  (就是例子)
加权：07  输出：7EF17C1C

初值：00  输入：1234577F  CRC：1C
加权：07  输出：7EF17B1C

CRC碰撞带来的灾难及预防

在数据通信中，特别是无线或单总线通讯中，由于外部各种干扰，可能会使CRC校验失误。

还以上例为例子：

初值：00  输入：12345678   CRC：1C
加权：07  输出：7EF17C1C

假若干扰的原因，数据被“插入”了8个比特位，即“12345X678”

由于一般协议以“块”为单位，就造成：

初值：00  输入：12345X67   CRC：1C
加权：07  输出：7EF1XX1C

如何消除这种灾难呢？？？

答案：可以在每个通讯包后加发CRC结果一个字节。

因为CRC有个“性质”，密文流的最后一个字节即为CRC结果，若在明文流尾再加入此字节(上一密文)。
则CRC结果恒为0.

即正常时：
初值：00  输入：123456781C   CRC：00
加权：07  输出：7EF17C1C00

当“插入干扰”来临时，即“12345X6781C”
有：

初值：00  输入：12345X6781   CRC：XX 肯定不为0
加权：07  输出：7EF17XXXXX

当然这种方法不能阻止“人造干扰”即逆向活动，但在通讯中是很有效果的~~~

CRC碰撞概率及数据通讯安全问题

CRC碰撞概率太深奥，俺不清楚~~~也总是不明白如何统计。
总觉得有点“吓人”~~~

实际应用中几乎不可能发生或概率几乎为零，因为(以数据通信为例)：

在数据传送期间，主设备处于连续发送状态，从设备处于接收状态。
干扰即使破坏几位，甚至数个字节，但这一般并不影响主设备的继续发送(它也不知道输出的数据是否受损害)
从设备收完包校验不通过会及时处理，而且数据包内一般也会有子校验，如状态，包序，命令，参数等，都可做些容错处理来对付“碰撞”。

如果遇上前面“人造CRC碰撞”确实很不幸~~~
这样可采用“双算法校验”，例如CRC+累加和双校验。

这样校验的真实性会大大提高，因为“概率”绝不会同时落到两种不同算法的头上。

总之，在数据通讯特别是无线或单总线通讯方面的应用一定要加校验。这样才能提过数据的可信度。

呵呵  沙发啊

求生成的CRC64编码完全相同的两个串

晕~~~“都进入了CRC人造碰撞时代了”，还要穷举？？？

发表于：2008-09-23 15:52:2514楼 得分:0
基本上只能穷举了。

实在太难找了,测试了一组100万的数据和一组800万的数据,没找出来...

随便搞4组（当然长度是128位的数据>64位）：（制造碰撞必须>=N+1位）

上传的附件：

• crc64_1.gif （6.39kb，98次下载）
• crc64_2.gif （6.56kb，95次下载）
• crc64_3.gif （6.43kb，95次下载）
• crc64_4.gif （6.39kb，96次下载）

100万组？
HotWC3新版本可以手动和自动CRC碰撞。
HotWC3碰撞很简单，只需点击还原或碰撞即可。
注意要在HotWC3_V1.10版本以上！

手动CRC碰撞操作步骤:1.功能选择CRC基本运算，选择标准的CRC或HotCRC。2.在明文处输入字符串，CRCn。3.点击运算，得到密文字符串，保留最后一组CRCn不得改写，例如CRC8最后2个HEX不得改写。任意改写其它数据。4.点击还原，明文变化，即发生了CRC碰撞。5.再点击运算，结果将不会改变，即验证了CRC碰撞。

CRC随机碰撞。具体操作步骤:1.功能选择CRC基本运算，选择标准的CRC或HotCRC。2.在明文处输入一组字符串。3.点击运算，得到密文字符串。4.点击碰撞，明文和密文都将会变为新的字符串，即发生了CRCRC碰撞。5.点击运算，结果不变，即验证了CRC碰撞。第三方CRC碰撞软件基本都是穷举得到，菜农是任意制造！