CRC权值方向初值出值测试方法

2万 · 2009-10-27 20:20

本帖最后由 hotpower 于 2012-10-26 23:04 编辑

CRC权值方向初值出值测试方法
本方法是在任何CRC计算器中，未知其表达式即权值和方向及初值和出值的情况下，
选择特定的3个输入(0x00,0x01,0x80)用CRC计算3个CRC校验值。用此3组数据即可算出
当前CRC的权值和方向及初值和出值。
本方法对**非标准的CRC算法或表格非常有效。
若选用工具(最新版V4.07): http://www.hotpage.net.cn/HotPower_HotWC3.html
全面支持fsum frontend-1.5.5.1软件。并准备进行文件操作生成完整的CRC位域8表格。

正运算(正函数)请按“运算”钮，逆运算(反函数)请按“还原”钮。
应用实例：http://blog.**/hotpower/275125/message.aspx
依据：
左移CRC权值(大端) = CRC[0x01], 右移CRC权值(小端)=CRC[2^(N-1)]
其中: N=4,8,12,16...即CRC4,CRC8,CRC12,CRC16,...
注意：
N= 4时 2^(N-1)=2^3 =0x8(半字节无大小端之分)
N= 8时 2^(N-1)=2^7 =0x80(字节无大小端之分)
N=12时 2^(N-1)=2^11=0x800(大端)，故小端为0x080
N=16时 2^(N-1)=2^15=0x8000(大端)，故小端为0x0080
N=32时 2^(N-1)=2^31=0x80000000(大端)，故小端为0x00000080
N=40时 2^(N-1)=2^39=0x8000000000(大端)，故小端为0x0000000080
N=64时 2^(N-1)=2^39=0x8000000000000000(大端)，故小端为0x0000000000000080
注意在用CRC计算器(按字节计算CRC)采样时一定要输入够位数!!!
CRCx[明文] = CRCx[初值 ^ 输入] = 输出 ^ 出值 = 密文
故: CRCx[明文] = CRCx[初值 ^ 输入] = CRC[初值 ^ 输入]
= CRC[初值] ^ CRC[输入]
= CRCx[初值] ^ CRC[输入] ^ CRCx[0]
= CRC[初值] ^ CRCx[输入] ^ CRCx[0]
= 输出 ^ 出值 = 密文
即：CRCx[初值 ^ 输入] = CRC[初值] ^ CRC[输入] ^ CRCx[0]
其中:CRCx[]为初值或出值非零的CRC[],简称加壳的CRC[]或有壳的CRC[]。
CRC[]为初值和出值全零的CRC[], 简称脱壳的CRC[]或无壳的CRC[]。

CRC权值由三组确定(以CRC8为例)：
CRC4选0x0,0x1,0x8. CRC8选0x00,0x01,0x80. CRC16选0x0000,0x0001,0x0080,CRCn选0,1,0x0080
1.CRCx[0x00] 用以计算偏差和求权值和快速求初值,它是CRCx[]与CRC[]的差值即异或值
差值 = CRCx[0x00] ^ CRC[0x00] = CRCx[0x00] ^ 0x00 = CRCx[0x00]
即CRCx[0x00]就是CRCx[x]与CRC[x]的差值.
2.CRCx[0x01] 左权确定左权值=CRCx[0x00] ^ CRCx[0x01]=CRC[0x01] 且 CRC[0x80] == 右权
3.CRCx[0x80] 右权确定右权值=CRCx[0x00] ^ CRCx[0x80]=CRC[0x80] 且 CRC[0x01] == 左权
计算:
CRCx[0xFF]=CRC[0xFF] ^ CRCx[0x00] 用以快速求出值
4.disCRC[CRCx[0x00]]=初值。即需要用到CRC逆运算，这在其他运算器只能用穷举了。
CRC逆运算使HotWC3可以正向和逆向任何CRC问题，只要再掌握"CRC编解码矩阵或CRC编解码表"等
菜农的“CRC群魔乱舞”理论即可。
此4个步骤很关键，初值出值的最终确定需要以下5个条件之一。

CRC初值和出值由五组确定(以CRC8为例)：
1.初值=0x00,出值=0x00 CRCx[0x00] = 0x00
2.初值=0x00,出值=0xFF CRCx[0x00] = 0xFF
3.初值=0xFF,出值=0x00 CRCx[0xFF] = 0x00
4.初值=0xFF,出值=0xFF CRCx[0xFF] = 0xFF
5.初值=0xXX,出值=0x00 CRCx[0x00],CRCx[0xFF] != 0x00,0xFF,初值 = disCRC[CRCx[0x00]]
其它组合无法确定，必须采集连续的2点
其中:CRCx[]为初值或出值非零的CRC[],简称加壳的CRC[]或有壳的CRC[]。
CRC[]为初值和出值全零的CRC[], 简称脱壳的CRC[]或无壳的CRC[]。
disCRC[]为CRC[]的反函数。

直接用差分计算初值出值的方法(CRC8的7个例子，适合任何CRCn)
CRCL8_07_12_34表示：CRCL8左移CRC8 权值=0x07 初值=0x12 出值=0x34
CRCR8_8C_AB_CD表示：CRCR8右移CRC8 权值=0x8C 初值=0xAB 出值=0xCD
1.CRCL8_07_00_00
CRCL8_07_00_00[0x00]=0x00(初值=0x00,出值=0x00)CRCx[0x00]=0x00或0xFF 初值恒为0x00
CRCL8_07_00_00[0x01]=0x07 0x00 ^ 0x07 = 0x07 CRCL8_07_00_00[0x80] = 0x89 左权对
CRCL8_07_00_00[0x80]=0x89 0x00 ^ 0x89 = 0x89 CRCR8_89_00_00[0x07] = 0xA4 右权错
初值和出值已确定，下面只是演算其正确性：
CRCL8_07_00_00[0xFF]=CRCL8_07_00_00[0xFF] ^ CRCL8_07_00_00[0x00]
=0xF3 ^ 0x00 = 0xF3(不为0x00或0xFF)
disCRCL8_07_00_00[0x00] = 0x00 真初值
CRCL8_07_00_00[0x00] = 0x00 初值=0x00 出值=0x00
2.CRCL8_07_00_FF
CRCL8_07_00_FF[0x00]=0xFF(初值=0x00,出值=0xFF)CRCx[0x00]=0x00或0xFF 初值恒为0x00
CRCL8_07_00_FF[0x01]=0xF8 0xFF ^ 0xF8 = 0x07 CRCL8_07_00_00[0x80] = 0x89 左权对
CRCL8_07_00_FF[0x80]=0x76 0xFF ^ 0x76 = 0x89 CRCR8_89_00_00[0x07] = 0xA4 右权错
初值和出值已确定，下面只是演算其正确性：
CRCL8_07_00_FF[0xFF]=CRCL8_07_00_00[0xFF] ^ CRCL8_07_00_FF[0x00]
=0xF3 ^ 0xFF = 0x0C(不为0x00或0xFF,初值不为0xFF)
disCRCL8_07_00_00[0xFF] = 0x48 假初值
CRCL8_07_48_00[0x00] = 0xFF 初值=0x00 出值=0xFF 正确
CRCL8_07_48_00[0xFF] = 0x0C 初值=0xFF 出值=0x0C 错误
CRCL8_07_48_00[0x48] = 0x00 初值=0x48 出值=0x00 不正确
3.CRCL8_07_FF_00
CRCL8_07_FF_00[0x00]=0xF3
CRCL8_07_FF_00[0x01]=0xF4 0xF3 ^ 0xF4 = 0x07 CRCL8_07_00_00[0x80] = 0x89 左权对
CRCL8_07_FF_00[0x80]=0x7A 0xF3 ^ 0x7A = 0x89 CRCR8_89_00_00[0x07] = 0xA4 右权错
CRCL8_07_FF_00[0xFF]=CRCL8_07_00_00[0xFF] ^ CRCL8_07_FF_FF[0x00]
=0xF3 ^ 0xF3 = 0x00(初值=0xFF,出值=0x00)CRCx[0xFF]=0x00或0xFF 初值恒为0xFF
初值和出值已确定，下面只是演算其正确性：
disCRCL8_07_00_00[0xF3] = 0xFF 真初值
CRCL8_07_FF_00[0x00] = 0xF3 初值=0x00 出值=0xF3
CRCL8_07_FF_00[0xFF] = 0x00 初值=0xFF 出值=0x00 正确
4.CRCL8_07_FF_FF
CRCL8_07_FF_FF[0x00]=0x0C
CRCL8_07_FF_FF[0x01]=0x0B 0x0C ^ 0x0B = 0x07 CRCL8_07_00_00[0x80] = 0x89 左权对
CRCL8_07_FF_FF[0x80]=0x85 0x0C ^ 0x85 = 0x89 CRCR8_89_00_00[0x07] = 0xA4 右权错
CRCL8_07_00_FF[0xFF]=CRCL8_07_00_00[0xFF] ^ CRCL8_07_FF_FF[0x00]
=0xF3 ^ 0x0C = 0xFF(初值=0xFF,出值=0xFF)CRCx[0xFF]=0x00或0xFF 初值恒为0xFF
初值和出值已确定，下面只是演算其正确性：
disCRCL8_07_00_00[0x0C] = 0xB7 假初值
CRCL8_07_B7_00[0x00] = 0x0C 初值=0x00 出值=0x0C
CRCL8_07_B7_00[0xFF] = 0xFF 初值=0xFF 出值=0xFF 正确
CRCL8_07_B7_00[0xB7] = 0x00 初值=0xB7 出值=0x00
5.CRCL8_07_12_00
CRCL8_07_12_00[0x00]=0x7E
CRCL8_07_12_00[0x01]=0x79 0x7E ^ 0x79 = 0x07 CRCL8_07_00_00[0x80] = 0x89 左权对
CRCL8_07_12_00[0x80]=0xF7 0x7E ^ 0xF7 = 0x89 CRCR8_89_00_00[0x07] = 0xA4 右权错
CRCL8_07_12_00[0xFF]=CRCL8_07_00_00[0xFF] ^ CRCL8_07_12_00[0x00]
=0xF3 ^ 0x7E = 0x8D(不为0x00或0xFF)
初值和出值无法确定，用一次反函数即可确定：
disCRCL8_07_00_00[0x7E] = 0x12 真初值
CRCL8_07_12_00[0x00] = 0x7E 初值=0x00 出值=0x7E
CRCL8_07_12_00[0xFF] = 0x8D 初值=0xFF 出值=0x8D
CRCL8_07_12_00[0x12] = 0x00 初值=0x12 出值=0x00 正确
6.CRCL8_07_12_34(无解)
CRCL8_07_12_34[0x00]=0x4A
CRCL8_07_12_34[0x01]=0x4D 0x4A ^ 0x4D = 0x07 CRCL8_07_00_00[0x80] = 0x89 左权对
CRCL8_07_12_34[0x80]=0xC3 0x4A ^ 0xC3 = 0x89 CRCR8_89_00_00[0x07] = 0xA4 右权错
CRCL8_07_12_34[0xFF]=CRCL8_07_00_00[0xFF] ^ CRCL8_07_12_34[0x00]
=0xF3 ^ 0x4A = 0xB9(不为0x00或0xFF)
初值和出值无法确定，用一次反函数也无法确定：
disCRCL8_07_00_00[0x4A] = 0xAD 假初值
CRCL8_07_AD_00[0xAD] = 0x00 初值=0xAD 出值=0x00
CRCL8_07_AD_00[0x00] = 0x4A 初值=0x00 出值=0x4A
CRCL8_07_AD_00[0xFF] = 0xB9 初值=0xFF 出值=0xB9
CRCL8_07_AD_00[0xE5] = 0xFF 初值=0xE5 出值=0xFF
CRCL8_07_AD_00[0x12] = 0x34 初值=0x12 出值=0x34 很难找到,只能穷举
可以看出：
逆运算结果做初值后，其CRC表格的输入和输出即为最终的初值和出值。
CRCx[0x00],权值0x07，初值出值为任意值时，0x00对应0x4A举例(CRC初值出值碰撞)：
CRCL8_07_AD_00[0x00]=0x4A
CRCL8_07_00_4A[0x00]=0x4A
CRCL8_07_FF_B9[0x00]=0x4A
CRCL8_07_EF_FF[0x00]=0x4A
CRCL8_07_12_34[0x00]=0x4A
CRCx[0x01],权值0x07，初值出值为任意值时，0x01对应0x4D举例(CRC初值出值碰撞)：
CRCL8_07_AD_00[0x01]=0x4D
CRCL8_07_00_4A[0x01]=0x4D
CRCL8_07_FF_B9[0x01]=0x4D
CRCL8_07_EF_FF[0x01]=0x4D
CRCL8_07_12_34[0x01]=0x4D
CRCx[0x80],权值0x07，初值出值为任意值时，0x80对应0xC3举例(CRC初值出值碰撞)：
CRCL8_07_AD_00[0x80]=0xC3
CRCL8_07_00_4A[0x80]=0xC3
CRCL8_07_FF_B9[0x80]=0xC3
CRCL8_07_EF_FF[0x80]=0xC3
CRCL8_07_12_34[0x80]=0xC3
结论：HotWC3正是依据此(初值出值的任意导致CRC的陷门单向散列)建立的以CRC为核的加密体系。
7.CRCL8_07_AB_CD(无解)
CRCL8_07_AB_CD[0x00]=0x95
CRCL8_07_AB_CD[0x01]=0x92 0x95 ^ 0x92 = 0x07 CRCL8_07_00_00[0x80] = 0x89 左权对
CRCL8_07_AB_CD[0x80]=0x1C 0x95 ^ 0x1C = 0x89 CRCR8_89_00_00[0x07] = 0xA4 右权错
CRCL8_07_AB_CD[0xFF]=CRCL8_07_00_00[0xFF] ^ CRCL8_07_AB_CD[0x00]
=0xF3 ^ 0x95 = 0x66(不为0x00或0xFF)
初值和出值无法确定，用一次反函数也无法确定：
disCRCL8_07_00_00[0x95] = 0x84 假初值
CRCL8_07_84_00[0x84] = 0x00 初值=0x84 出值=0x00
CRCL8_07_84_00[0x00] = 0x95 初值=0x00 出值=0x95
CRCL8_07_84_00[0xFF] = 0x66 初值=0xFF 出值=0x66
CRCL8_07_84_00[0xCC] = 0xFF 初值=0xCC 出值=0xFF
CRCL8_07_84_00[0xAB] = 0xCD 初值=0xAB 出值=0xCD 很难找到,只能穷举
可以看出：
逆运算结果做初值后，其CRC表格的输入和输出即为最终的初值和出值。
CRCx[0x00],权值0x07，初值出值为任意值时，0x00对应0x95举例(CRC初值出值碰撞)：
CRCL8_07_84_00[0x00]=0x95
CRCL8_07_00_95[0x00]=0x95
CRCL8_07_FF_66[0x00]=0x95
CRCL8_07_CC_FF[0x00]=0x95
CRCL8_07_AB_CD[0x00]=0x95
CRCx[0x01],权值0x07，初值出值为任意值时，0x01对应0x92举例(CRC初值出值碰撞)：
CRCL8_07_84_00[0x01]=0x92
CRCL8_07_00_95[0x01]=0x92
CRCL8_07_FF_66[0x01]=0x92
CRCL8_07_CC_FF[0x01]=0x92
CRCL8_07_AB_CD[0x01]=0x92
CRCx[0x80],权值0x07，初值出值为任意值时，0x80对应0x1C举例(CRC初值出值碰撞)：
CRCL8_07_84_00[0x80]=0x1C
CRCL8_07_00_95[0x80]=0x1C
CRCL8_07_FF_66[0x80]=0x1C
CRCL8_07_CC_FF[0x80]=0x1C
CRCL8_07_AB_CD[0x80]=0x1C
结论：HotWC3正是依据此(初值出值的任意导致CRC的陷门单向散列)建立的以CRC为核的加密体系。
菜农发布此文，就是间接地论证CRC虽然时线性的非安全散列函数，一但拥有一种可逆方法，即可
将CRC升迁为单向陷门散列函数，在拥有CRC密钥(权值、方向、初值和出值)后，皆可实现对数据
的加密和解密过程。
本文实际上是已知(选择)明文及密文对CRC解密例程，它必须有3个明文密文对：
已知：CRCx[x1]=y1,CRCx[x2]=y2,CRCx[x3]=y3
满足：
x1 ^ x2 = 0x01 攻击左移CRC权值
x1 ^ x3 = 0x80 攻击右移CRC权值
即可完成对CRC的完全**。
其中x1,x2,x3的组合中，0x00,0x01,0x80最佳，可一次得到CRCx[0x00]=y1
也可选择0xFF,0xFE,0x7F,CRCx[0x00]=CRCx[x] ^ CRC[x]
CRCx[0x00]=CRCx[0xFF] ^ CRC[0xFF]=CRCx[0xFE] ^ CRC[0xFE]=CRCx[0x7F] ^ CRC[0x7F]

此方法是攻击动态CRC的“理论依据”。

应用别人发明的密码很容易，若想创建一套完整的密码体系，首先要攻破自己。
HotWC3正是知道几乎所有的CRC**条件及方法，才敢“知难而进”~~~
HotWC3采用“一次一密”技术，即每次由滚动的密钥流更换一次密钥序列，来躲避此攻击方法，逼迫
解密者不得不采用穷举的方法来**HotWC3.
在此特别注意例程中的例6和例7.它只是CRC初值出值碰撞，HotWC3还具备CRC权值、方向及明文碰撞。
故HotWC3是个真正的CRC单向安全散列函数的应用范例。
我在看雪论坛为什么不正面回答问题的主要原因是人们固有的“CRC线性非安全散列函数”束缚太深。
至于“差分”及“密码”的问题，那就更不用回答，因为CRC是线性的，所以最怕差分攻击，CRC做校验，
自然不是密码，一但掌握了CRC逆向运算，那么CRC即可成为密码。
单向散列函数不能构成密码体系，但是，单向陷门散列函数就能构成密码体系。

本方法为菜农独创，转载请注明出处。

菜农HotPower@126.com 2009.10.27 于雁塔菜地