新闻  |   论坛  |   博客  |   在线研讨会
利用CRC权攻击特性对fsum frontend-1.5.5.1软件的CRC攻击结果:
0750long | 2009-07-28 11:29:24    阅读:2092   发布文章


这里主要是论述如何攻击特定CRC算法的权值。(假设什么都不公开,只告诉是一种CRC算法)

“权的攻击法则”:
左移时攻击明文为1得到的密文即为权值。
右移时攻击明文为2^(N-1)得到的密文即为权值。
 
CRC8:(成功)
初值=00 权值=XX 入值=XX 出值=XX 方向=X
输入=01 输出=07 预测攻击结果:左移CRC8,入值=00 出值=00 权值=07(X8=X,X0=1可逆) 最终确认
输入=80 输出=89 预测攻击结果:右移CRC8,入值=00 出值=00 权值=89(X8=1可逆,X0=X) 攻击失败
CRC8成功确认:
初值=00 权值=07 入值=00 出值=00 方向=左移
 
CRC16:(失败)
初值=0000 权值=XXXX 入值=XXXX 出值=XXXX 方向=X
输入=0001 输出=C0C1 预测攻击结果:左移CRC16,入值=0000 出值=0000 权值=C0C1(X16=X,X0=1可逆) 攻击失败
输入=8000 输出=C061 预测攻击结果:右移CRC16,入值=0000 出值=0000 权值=C061(X16=1可逆,X0=X) 攻击失败
输入=FFFE 输出=70C0 预测攻击结果:左移CRC16,入值=FFFF 出值=FFFF 权值=8F3F(X16=X,X0=1可逆) 攻击失败 
输入=7FFF 输出=7060 预测攻击结果:右移CRC16,入值=FFFF 出值=FFFF 权值=8F9F(X16=1可逆,X0=X) 攻击失败
CRC16失败确认:
初值=0000 权值=XXXX 入值=XXXX 出值=XXXX 方向=X
 
CRC16_ccitt:(成功)
初值=0000 权值=XXXX 入值=XXXX 出值=XXXX 方向=X
输入=0001 输出=0D2E 预测攻击结果:左移CRC16,入值=0000 出值=0000 权值=0D2E(X16=X,X0=1可逆) 攻击失败
输入=8000 输出=0697 预测攻击结果:右移CRC16,入值=0000 出值=0000 权值=0697(X16=0单向,X0=X) 放弃攻击
输入=FFFE 输出=1021 预测攻击结果:左移CRC16,入值=FFFF 出值=0000 权值=1021(X16=X,X0=1可逆) 最终确认 
输入=7FFF 输出=1B98 预测攻击结果:右移CRC16,入值=FFFF 出值=0000 权值=1B98(X16=0单向,X0=X) 放弃攻击
CRC16_ccitt成功确认:
初值=0000 权值=1021 入值=FFFF 出值=0000 方向=左移
 
CRC16_zmodem:(成功)
初值=0000 权值=XXXX 入值=XXXX 出值=XXXX 方向=X
输入=0001 输出=1021 预测攻击结果:左移CRC16,入值=0000 出值=0000 权值=1021(X16=X,X0=1可逆) 最终确认
输入=8000 输出=1B98 预测攻击结果:右移CRC16,入值=0000 出值=0000 权值=1B98(X16=0单向,X0=X) 放弃攻击
CRC16_zmodem成功确认:
初值=0000 权值=1021 入值=0000 出值=0000 方向=左移
 
CRC16_xmodem:(失败)
初值=0000 权值=XXXX 入值=XXXX 出值=XXXX 方向=X
输入=0001 输出=17CE 预测攻击结果:左移CRC16,入值=0000 出值=0000 权值=17CE(X16=X,X0=0单向) 放弃攻击
输入=8000 输出=0BE7 预测攻击结果:右移CRC16,入值=0000 出值=0000 权值=0BE7(X16=0单向,X0=X) 放弃攻击
输入=0001 输出=17CE 预测攻击结果:左移CRC16,入值=0000 出值=FFFF 权值=E831(X16=X,X0=1可逆) 攻击失败
输入=8000 输出=0BE7 预测攻击结果:右移CRC16,入值=0000 出值=FFFF 权值=F418(X16=1单向,X0=X) 攻击失败
输入=FFFE 输出=0AC7 预测攻击结果:左移CRC16,入值=FFFF 出值=0000 权值=0AC7(X16=X,X0=1可逆) 攻击失败 
输入=7FFF 输出=16EE 预测攻击结果:右移CRC16,入值=FFFF 出值=0000 权值=16EE(X16=0单向,X0=X) 放弃攻击
输入=FFFE 输出=0AC7 预测攻击结果:左移CRC16,入值=FFFF 出值=FFFF 权值=F538(X16=X,X0=0单向) 放弃攻击 
输入=7FFF 输出=16EE 预测攻击结果:右移CRC16,入值=FFFF 出值=FFFF 权值=E911(X16=1可逆,X0=X) 攻击失败
CRC16_xmodem失败确认:
初值=0000 权值=XXXX 入值=XXXX 出值=XXXX 方向=X
 
CRC16_ibm:(成功)
初值=0000 权值=XXXX 入值=XXXX 出值=XXXX 方向=X
输入=0001 输出=8005 预测攻击结果:左移CRC16,入值=0000 出值=0000 权值=8005(X16=X,X0=1可逆) 最终确认 
输入=8000 输出=8009 预测攻击结果:右移CRC16,入值=0000 出值=0000 权值=8009(X16=1可逆,X0=X) 攻击失败
CRC16_ibm成功确认:
初值=0000 权值=8005 入值=0000 出值=0000 方向=左移
 
CRC16_x25:(失败)
初值=0000 权值=XXXX 入值=XXXX 出值=XXXX 方向=X
输入=0001 输出=1ECE 预测攻击结果:左移CRC16,入值=0000 出值=0000 权值=1ECE(X16=X,X0=0单向) 放弃攻击 
输入=8000 输出=838B 预测攻击结果:右移CRC16,入值=0000 出值=0000 权值=838B(X16=1可逆,X0=X) 攻击失败
输入=FFFE 输出=EE76 预测攻击结果:左移CRC16,入值=FFFF 出值=0000 权值=1189(X16=X,X0=1可逆) 攻击失败 
输入=7FFF 输出=7333 预测攻击结果:右移CRC16,入值=FFFF 出值=0000 权值=8CCC(X16=1可逆,X0=X) 攻击失败
CRC16_x25失败确认:
初值=0000 权值=XXXX 入值=XXXX 出值=XXXX 方向=X
 
CRC24:(失败)
初值=000000 权值=XXXXXX 入值=XXXXXX 出值=XXXXXX 方向=X
输入=000001 输出=A3A3D9 预测攻击结果:左移CRC24,入值=000000 出值=000000 权值=A3A3D9(X24=X,X0=1 可逆) 攻击失败
输入=800000 输出=3EEB8B 预测攻击结果:右移CRC24,入值=000000 出值=000000 权值=3EEB8B(X24=0,X0=X 单向) 放弃攻击 
输入=FFFFFE 输出=4E5B17 预测攻击结果:左移CRC24,入值=FFFFFF 出值=FFFFFF 权值=A3A3D9(X24=X,X0=1 可逆) 攻击失败
输入=7FFFFF 输出=D31345 预测攻击结果:右移CRC24,入值=FFFFFF 出值=FFFFFF 权值=3EEB8B(X24=0,X0=X 单向) 放弃攻击
CRC24失败确认:
初值=0000 权值=8005 入值=0000 出值=0000 方向=左移
 
 
CRC64_ecma:(成功)
初值=0000000000000000 权值=XXXXXXXXXXXXXXXX 入值=XXXXXXXXXXXXXXXX 出值=XXXXXXXXXXXXXXXX 方向=X
输入=0000000000000001 输出=41A3A0A90F2460FE 预测攻击结果:左移CRC64,入值=0000000000000000 出值=0000000000000000 权值=01B0000000000000(X64=X,X0=0 单向) 放弃攻击
输入=8000000000000000 输出=01A9A0A153672B36 预测攻击结果:右移CRC64,入值=0000000000000000 出值=0000000000000000 权值=00000000000000D8(X64=0单向,X0=X) 放弃攻击
输入=FFFFFFFFFFFFFFFE 输出=BD0F1E145615C96C 预测攻击结果:左移CRC64,入值=FFFFFFFFFFFFFFFF 出值=FFFFFFFFFFFFFFFF 权值=42F0E1EBA9EA3693(X64=X,X0=1 可逆) 最终确认
输入=7FFFFFFFFFFFFFFF 输出=FD051E1C0A5682A4 预测攻击结果:右移CRC64,入值=FFFFFFFFFFFFFFFF 出值=FFFFFFFFFFFFFFFF 权值=02FAE1E3F5A97D5B(X64=0单向,X0=X) 放弃攻击
CRC64_ecma成功确认:
初值=0000000000000000 权值=42F0E1EBA9EA3693 入值=FFFFFFFFFFFFFFFF 出值=FFFFFFFFFFFFFFFF 方向=左移
 
CRC64:(失败)
初值=0000000000000000 权值=XXXXXXXXXXXXXXXX 入值=XXXXXXXXXXXXXXXX 出值=XXXXXXXXXXXXXXXX 方向=X
输入=0000000000000001 输出=01B0000000000000 预测攻击结果:左移CRC64,入值=0000000000000000 出值=0000000000000000 权值=01B0000000000000 (X64=X,X0=0 单向) 放弃攻击(不可逆攻击出下表)
输入=8000000000000000 输出=00000000000000D8 预测攻击结果:右移CRC64,入值=0000000000000000 出值=0000000000000000 权值=00000000000000D8 (X64=0单向,X0=X) 放弃攻击
输入=FFFFFFFFFFFFFFFE 输出=52B0000000000000 预测攻击结果:左移CRC64,入值=FFFFFFFFFFFFFFFF 出值=FFFFFFFFFFFFFFFF 权值=AD4FFFFFFFFFFFFF (X64=X,X0=1 可逆) 攻击失败
输入=7FFFFFFFFFFFFFFF 输出=53000000000000D8 预测攻击结果:右移CRC64,入值=FFFFFFFFFFFFFFFF 出值=FFFFFFFFFFFFFFFF 权值=ACFFFFFFFFFFFF27 (X64=1可逆, X0=X) 攻击失败 
CRC64失败确认:
初值=0000000000000000 权值=XXXXXXXXXXXXXXXX 入值=XXXXXXXXXXXXXXXX 出值=XXXXXXXXXXXXXXXX 方向=X

下面是对CRC64攻击出来的CRC表,它显然是不可逆的(与57楼的CRC表格完全相同):

引用:
module fsumfe.digest.algo.crc64;

import fsumfe.digest.digest;

public final class CRC64: Digest {
    private final long crctab[256] = [
  0x0000000000000000L, 0x01b0000000000000L, 0x0360000000000000L, 0x02d0000000000000L, 0x06c0000000000000L, 0x0770000000000000L,
  0x05a0000000000000L, 0x0410000000000000L, 0x0d80000000000000L, 0x0c30000000000000L, 0x0ee0000000000000L, 0x0f50000000000000L,
  0x0b40000000000000L, 0x0af0000000000000L, 0x0820000000000000L, 0x0990000000000000L, 0x1b00000000000000L, 0x1ab0000000000000L,
  0x1860000000000000L, 0x19d0000000000000L, 0x1dc0000000000000L, 0x1c70000000000000L, 0x1ea0000000000000L, 0x1f10000000000000L,
  0x1680000000000000L, 0x1730000000000000L, 0x15e0000000000000L, 0x1450000000000000L, 0x1040000000000000L, 0x11f0000000000000L,
  0x1320000000000000L, 0x1290000000000000L, 0x3600000000000000L, 0x37b0000000000000L, 0x3560000000000000L, 0x34d0000000000000L,
  0x30c0000000000000L, 0x3170000000000000L, 0x33a0000000000000L, 0x3210000000000000L, 0x3b80000000000000L, 0x3a30000000000000L,
  0x38e0000000000000L, 0x3950000000000000L, 0x3d40000000000000L, 0x3cf0000000000000L, 0x3e20000000000000L, 0x3f90000000000000L,
  0x2d00000000000000L, 0x2cb0000000000000L, 0x2e60000000000000L, 0x2fd0000000000000L, 0x2bc0000000000000L, 0x2a70000000000000L,
  0x28a0000000000000L, 0x2910000000000000L, 0x2080000000000000L, 0x2130000000000000L, 0x23e0000000000000L, 0x2250000000000000L,
  0x2640000000000000L, 0x27f0000000000000L, 0x2520000000000000L, 0x2490000000000000L, 0x6c00000000000000L, 0x6db0000000000000L,
  0x6f60000000000000L, 0x6ed0000000000000L, 0x6ac0000000000000L, 0x6b70000000000000L, 0x69a0000000000000L, 0x6810000000000000L,
  0x6180000000000000L, 0x6030000000000000L, 0x62e0000000000000L, 0x6350000000000000L, 0x6740000000000000L, 0x66f0000000000000L,
估计攻击失败的应该都是右移CRC
 
例如右移CRC8:
多项式=X8+X5+X4+1 (符合1-Wire总线协议)
这是1-Wire总线协议的缔造者Dallas/Maxim给出多项式
且权=0x18. 网上可以找到权=0x31,0x8c,0x98这三种。http://blog.ednchina.com/hotpower/220371/message.aspx
0x18的算法是先记忆最低位,直接XOR 0x18,再右移。
0x8c的算法是先记忆最低位,再右移,然后XOR 0x8c。
但是表达式自动计算就很难受,因为0x8c被解释为:X8+X4+X3+1,和X8+X5+X4+1有1位的差距。
 
结果一样,可能叫法有出入,在03年的CRC演算器就采用了0x18
 
后来发现CRC编解码矩阵后决定采用0x8c.
因为在0x18时,明文0x80对应的密文=0x8c.而它应该是新规则中被攻击为合法的权值。
 
为统一权的攻击法则:
左移时攻击明文0x01得到的密文即为权值。
右移时攻击明文0x80得到的密文即为权值。
 
显然0x18已不符合时代的要求,而且左右移CRC程序框架上也不太相似。
 
故新的CRC右移算法采用:先记忆最低位,再右移,然后XOR 0x8c。
而且规定若要满足可逆条件,右移CRC权的最高位恒为1.这样左右移CRC运算程序架构师一样的。
原来正运算中,XOR的是初值,由于初值和明文可以交换,现算法可以改为XOR明文,
这样正运算和逆运算的XOR的分别是明文和密文,非常对称。
 
对CRC64权的攻击结果中发现它的CRC表是权为0x01b0000000000000生成的表。
必须去掉可逆选项,此时明文从0~0xff全部正确,但超过0x100后全部出错。
显然0x01b0000000000000不满足CRC可逆的规定,强行可逆和CRC表不同。
更奇怪的是CRC表是左移生成的不可逆表,查表程序却是右移的算法,很是晕!!!
故攻击此CRC64必定失败。
若要兼容此算法,不采用查表,则在0~0xFF采用不可逆左移,其他采用可逆的右移。晕。
 
菜农做的CRC演算器主要是为CRC密码及CRC碰撞设计的,所有的权必须要满足可逆的要求。
故有些不可逆即单向散列的CRC菜农不会去支持。

因为HotWC3密码的核将随意地选用这些具有可能关系的CRC,这样才能实现加密和解密。
不可逆就无法做成密码体系。

*博客内容为网友个人发布,仅代表博主个人观点,如有侵权请联系工作人员删除。

参与讨论
登录后参与讨论
推荐文章
最近访客