有趣的CRC位域9碰撞及CRC非对称密码体系碰撞准则(雁塔菜农)

本文推导工具： 最新版的HotWC3网上在线CRC运算器V4.18



附CRC四点攻击操作方法：
1. 先选择一个方向的权值，初值及出值(一般取0)
2. 选择“基本运算”中的“CRC算法逆向”
3. 点击“运算”自动得到四点的明文和密文。
4. 再根据3的结果选择另一个方向的权值，初值及出值。
5. 重复3,4
若不相信CRC位域8表内元素不差分毫，可：
6. 选择一个方向的权值，初值及出值(表格此时与它们无关，只是文件名字有关)
7. 选择“基本运算”中的“CRC位域表及算法”
8. 选择文件类型为“.TXT”，这样只生成表格不生成算法，好比较。
特别注意“结果”编辑框内应该为空！！！(keil C51可为code, pic或avr可能为其他)
9. 点击“运算”自动得到该权值及方向的CRC位域8表格(数组为256个元素)。
10.点击“保存”即可得到该权值及方向的CRC位域8表格文件。
11.重复6到9得到另一权值的CRC位域8表格文件。
此时您可以借助于带文件比较的软件自行比较，如UE等优秀的软件。
菜农以后会考虑自动比较。

例一：
选择右移CRC可逆，保留最右端7位为0x80, 找到相对的可逆的左移CRC，发生CRC位域9碰撞
CRC多项式：右移CRC16=X16+X8+X7+X6+X5+X4+X3+X2+X+1(可逆)
CRC简 写：CRCR16_FF80_0000_0000
第1采样点 第2采样点 第3采样点 第4采样点
四点采样逆向明文: 0000 0001 0080 FFFF
四点采样逆向密文: 0000 01FF FF80 CCCC

CRC多项式：左移CRC16=X16+X8+X7+X6+X5+X4+X3+X2+X+1(可逆)
CRC简 写：CRCL16_01FF_0000_0000
第1采样点 第2采样点 第3采样点 第4采样点
四点采样逆向明文: 0000 0001 0080 FFFF
四点采样逆向密文: 0000 01FF FF80 3333

三点采样逆向碰撞： 0000 01FF FF80

例二：
选择右移CRC可逆，保留最右端7位为0x80, 找到相对的可逆的左移CRC，发生CRC位域9碰撞
CRC多项式：右移CRC16=X16+X8+X7+X6+1(可逆)
CRC简 写：CRCR16_8380_0000_0000
第1采样点 第2采样点 第3采样点 第4采样点
四点采样逆向明文: 0000 0001 0080 FFFF
四点采样逆向密文: 0000 0107 8380 02F3

CRC多项式：左移CRC16=X16+X8+X2+X+1(可逆)
CRC简 写：CRCL16_0107_0000_0000
第1采样点 第2采样点 第3采样点 第4采样点
四点采样逆向明文: 0000 0001 0080 FFFF
四点采样逆向密文: 0000 0107 8380 FF0E

三点采样逆向碰撞： 0000 0107 8380

例三：
选择左移CRC可逆，保留最左端7位为0x01, 找到相对的可逆的右移CRC，发生CRC位域9碰撞
CRC多项式：左移CRC16=X16+X8+X4+1(可逆)
CRC简 写：CRCL16_0111_0000_0000
第1采样点 第2采样点 第3采样点 第4采样点
四点采样逆向明文: 0000 0001 0080 FFFF
四点采样逆向密文: 0000 0111 8880 00FF

CRC多项式：右移CRC16=X16+X8+X4+1(可逆)
CRC简 写：CRCR16_8880_0000_0000
第1采样点 第2采样点 第3采样点 第4采样点
四点采样逆向明文: 0000 0001 0080 FFFF
四点采样逆向密文: 0000 0111 8880 FF00

三点采样逆向碰撞： 0000 0111 8880

例四：
选择左移CRC可逆，保留最左端7位为0x01, 找到相对的可逆的右移CRC，发生CRC位域9碰撞
CRC多项式：左移CRC16=X16+X8+X7+X4+X3+1(可逆)
CRC简 写：CRCL16_0199_0000_0000
第1采样点 第2采样点 第3采样点 第4采样点
四点采样逆向明文: 0000 0001 0080 FFFF
四点采样逆向密文: 0000 0199 CC80 3F3F

CRC多项式：右移CRC16=X16+X8+X5+X4+X+1(可逆)
CRC简 写：CRCR16_CC80_0000_0000
第1采样点 第2采样点 第3采样点 第4采样点
四点采样逆向明文: 0000 0001 0080 FFFF
四点采样逆向密文: 0000 0199 CC80 C0C0

三点采样逆向碰撞： 0000 0199 CC80

下面将发生所希望的事情：

例1：
选择右移CRC不可逆，保留最右端7位为0x80, 找到相对的可逆的左移CRC，发生CRC位域9碰撞
CRC多项式：右移CRC16=X16+X8+X4+X3(不可逆)
CRC简 写：CRCR16_1880_0000_0000
第1采样点 第2采样点 第3采样点 第4采样点
四点采样逆向明文: 0000 0001 0080 FFFF
四点采样逆向密文: 0000 0031 1880 0300

CRC多项式：左移CRC16=X16+X5+X4+1(可逆)
CRC简 写：CRCL16_0031_0000_0000
第1采样点 第2采样点 第3采样点 第4采样点
四点采样逆向明文: 0000 0001 0080 FFFF
四点采样逆向密文: 0000 0031 1880 FCFF

三点采样逆向碰撞： 0000 0031 1880

例2：
选择左移CRC不可逆，保留最左端7位为0x01, 找到相对的可逆的右移CRC，发生CRC位域9碰撞
CRC多项式：左移CRC16=X16+X8+X7+X4+X3(不可逆)
CRC简 写：CRCL16_0198_0000_0000
第1采样点 第2采样点 第3采样点 第4采样点
四点采样逆向明文: 0000 0001 0080 FFFF
四点采样逆向密文: 0000 0198 CC00 C048

CRC多项式：右移CRC16=X16+X5+X4+X+1(可逆)
CRC简 写：CRCR16_CC00_0000_0000
第1采样点 第2采样点 第3采样点 第4采样点
四点采样逆向明文: 0000 0001 0080 FFFF
四点采样逆向密文: 0000 0198 CC00 48C0

三点采样逆向碰撞： 0000 0198 CC00

例3：
选择右移CRC不可逆，保留最右端8位为0x00, 找到相对的不可逆的左移CRC，也发生CRC位域8碰撞
CRC多项式：右移CRC16=X16+X4+X3(不可逆)
CRC简 写：CRCR16_1800_0000_0000
第1采样点 第2采样点 第3采样点 第4采样点
四点采样逆向明文: 0000 0001 0080 FFFF
四点采样逆向密文: 0000 0030 1800 1300

CRC多项式：左移CRC16=X16+X5+X4(不可逆)
CRC简 写：CRCL16_0030_0000_0000
第1采样点 第2采样点 第3采样点 第4采样点
四点采样逆向明文: 0000 0001 0080 FFFF
四点采样逆向密文: 0000 0030 1800 0310

三点采样逆向碰撞： 0000 0030 1800

例4：
选择左移CRC不可逆，保留最左端8位为0x00, 找到相对的不可逆的右移CRC，也发生CRC位域8碰撞
CRC多项式：左移CRC16=X16+X7+X4+X3(不可逆)
CRC简 写：CRCL16_0098_0000_0000
第1采样点 第2采样点 第3采样点 第4采样点
四点采样逆向明文: 0000 0001 0080 FFFF
四点采样逆向密文: 0000 0098 4C00 C0C0

CRC多项式：右移CRC16=X16+X5+X4+X(不可逆)
CRC简 写：CRCR16_4C00_0000_0000
第1采样点 第2采样点 第3采样点 第4采样点
四点采样逆向明文: 0000 0001 0080 FFFF
四点采样逆向密文: 0000 0098 4C00 3F3F

三点采样逆向碰撞： 0000 0098 4C00

例5：
选择右移CRC可逆，保留最右端8位为0x00, 找到相对的不可逆的左移CRC，发生CRC位域8碰撞
CRC多项式：右移CRC16=X16+X4+X3+1(可逆)
CRC简 写：CRCR16_9800_0000_0000
第1采样点 第2采样点 第3采样点 第4采样点
四点采样逆向明文: 0000 0001 0080 FFFF
四点采样逆向密文: 0000 0130 9800 FCFF

CRC多项式：左移CRC16=X16+X8+X5+X4(不可逆)
CRC简 写：CRCL16_0130_0000_0000
第1采样点 第2采样点 第3采样点 第4采样点
四点采样逆向明文: 0000 0001 0080 FFFF
四点采样逆向密文: 0000 0130 9800 0300

三点采样逆向碰撞： 0000 0130 9800

例6：
选择左移CRC可逆，保留最左端8位为0x00, 找到相对的不可逆的右移CRC，发生CRC位域8碰撞
CRC多项式：左移CRC16=X16+X7+X4+X3+1(可逆)
CRC简 写：CRCL16_0099_0000_0000
第1采样点 第2采样点 第3采样点 第4采样点
四点采样逆向明文: 0000 0001 0080 FFFF
四点采样逆向密文: 0000 0099 4C80 3F48

CRC多项式：右移CRC16=X16+X8+X5+X4+X(不可逆)
CRC简 写：CRCR16_4C80_0000_0000
第1采样点 第2采样点 第3采样点 第4采样点
四点采样逆向明文: 0000 0001 0080 FFFF
四点采样逆向密文: 0000 0099 4C80 483F

三点采样逆向碰撞： 0000 0099 4C80

根据以上推论，可得出“CRC非对称密码体系碰撞准则”

当某一CRC位域8权值满足某一CRC方向上的可逆条件时，不选择CRC位域9会得到
另一CRC方向不可逆的权值。并将发生CRC位域碰撞。
当某一CRC位域8权值不满足某一CRC方向上的可逆条件时，选择CRC位域9将会得到
另一CRC方向可逆的权值。并将发生CRC位域碰撞。

此推论符合CRC非对称密码体系的要求，即一方可逆另一方不可逆。
当然最好是加密方不可逆，解密方可逆。
这样就有希望公开加密密钥，使CRC非对称密码体系升级为CRC公开密钥密码体系。
菜农估计需要初值、出值碰撞的帮助，初步感觉应该如此，需等继续研究方可定论。

反之，可得：
当某一CRC位域8权值满足某一CRC方向上的可逆条件时，选择CRC位域9将会得到
另一CRC方向也可逆的权值。并将发生CRC位域碰撞。
当某一CRC位域8权值不满足某一CRC方向上的可逆条件时，不选择CRC位域9将会得到
另一CRC方向也不可逆的权值。并将发生CRC位域碰撞。

此推论不符合CRC非对称密码体系的要求，即双方都可逆或都不可逆。

注：CRC位域碰撞需要三点CRC攻击。

菜农HotPower@126.com 2009.11.19 构思于雁塔菜地

[CTF入门培训]顶尖高校博士及硕士团队亲授《30小时教你玩转CTF》，视频+靶场+题目！助力进入CTF世界