原创 对CRC安全密码的攻击及改进和穷举时间

在http://www.hotc51.com/HotPower_HotWC3_V508d.html中，CRC安全密码是这样定义的：

将CRC的初值和出值分别作用于明文流和CRC结果流中，CRC本次的结果作为下次的一个初值之一。

假若：

CRC多项式：左移CRC8=X8+X2+X+1

CRC简  写：CRCL8_07_12_34

则：

      CRC运算     CRC安全密码
明文：121212      121212           
密文：007E03      343434

结果：37

可以看出，当选择几组相同的明文组进行攻击时，CRC安全密码会被攻击暴露出CRC的初值和出值。

这种攻击主要依据：

CRC编码矩阵[初值，明文]=0，其中初值=明文。

故修改之：http://www.hotc51.com/HotPower_HotWC3.html

CRC安全密码的正运算全部和CRC校验算法相同，差异在于：

CRC校验结果是由最后一次CRC运算的结果与CRC出值相异或后得到CRC的最终校验和。

CRC安全密码规定：

每次CRC的运算结果与CRC出值相异或后得到每次的密文，最后一次为CRC的最终校验和。

这样修改后，MCU具备内置CRC校验功能增加CRC安全密码功能所需的成本最低。

对CRC安全密码的攻击

多项式：左移CRC8=X8+X2+X+1
简  写：CRCL8_07_12_34

      CRC运算     CRC安全密码
明文：121212      121212           
密文：007E03      344A37
结果：37

看以看出CRC安全密码修改的必要。

多项式：左移CRC8=X8+X2+X+1
简  写：CRCL8_07_12_34

      CRC运算     CRC安全密码
明文：141414      141414           
密文：121212      262626
结果：26(12 ^ 34)

多项式：左移CRC8=X8+X2+X+1
简  写：CRCL8_07_34_12

      CRC运算     CRC安全密码
明文：8B8B8B      8B8B8B           
密文：343434      262626
结果：26(34 ^ 12)

多项式：左移CRC8=X8+X2+X+1
简  写：CRCL8_07_55_AA

      CRC运算     CRC安全密码
明文：909090      909090           
密文：555555      FFFFFF
结果：FF(55 ^ AA)

多项式：左移CRC8=X8+X2+X+1
简  写：CRCL8_07_AA_55

      CRC运算     CRC安全密码
明文：272727      272727           
密文：AAAAAA      FFFFFF
结果：FF(AA ^ 55)

从以上对改进后的CRC安全密码的攻击可以看出：

当用两组以上相同的明文攻击时，当密文组也对应相同时，

此时CRC安全密码的密文=初值^出值。故此结果也必须穷举验证，结论还是安全的。

以上和以下讨论都是假定CRC权值和方向都是已知时，故CRC安全密码是很安全的。

CRC安全密码的穷举时间：

假若可以论证CRC安全密码必须穷举，CRC密钥(权值、方向和初值及出值) 长度列举：

例CRC32,那么假若在知道CRC密钥(权值、方向）而CRC密钥(初值及出值）未知时，则:

密钥长度为2^64=18446744073709551616=1844674.4073709551616*10^13

1分钟=60秒=60*10^6uS
1小时=60分钟=60*60秒=3600*10^6uS
1天=24小时=24*60分钟=24*60*60秒=24*3600*10^6uS
1年=365天=365*24小时=365*24*60分钟=365*24*60*60秒=365*24*3600*10^6uS=31536000*10^6uS
   = 3.1536*10^13uS

假定MCU穷举1个密钥需要1uS,即1秒钟可以穷举一百万个CRC32密钥。

则2^64/(3.1536*10^13)=1844674.4073709551616*10^13/(3.1536*10^13)=600000年=60万年，

按50%概率则至少需要30万年破解CRC32密钥。