原创 有趣的CRC位域9碰撞及CRC非对称密码体系碰撞准则

2009-11-22 01:20 2291 7 7 分类: MCU/ 嵌入式

有趣的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 构思于雁塔菜地

PARTNER CONTENT

文章评论0条评论)

登录后参与讨论
EE直播间
更多
我要评论
0
7
关闭 站长推荐上一条 /3 下一条