原创最新版的HotWC3很黄很暴力

 2009-11-4 00:42  3505 5 5 分类: MCU/ 嵌入式

引用:
最初由 HotPower发布

伪造实际很容易：图中的CRC64不知是何种？？？具体些，像CRC64-ECMA就很明确

入值=0000000000000000
出值=EE2939579550E938（伪造一个）
初值=0000000000000000
权值=42F0E1EBA9EA3693 CRC64= EA7438964D2F9734

明文1=3C4DE0E9B2B1E075671281DEF4E6BC3D
密文1=0123456789ABCDEF045D01C1D87F7E0C
CRC64= EA7438964D2F9734

至于CRC64_ecma我需要知道它的权值

实在找不到里面的CRC64,CRC64_ecma那里都有
http://zh.wikipedia.org/wiki/%E5%BE%...A0%A1%E9%A9%97

1)
既然 HotPower 在【原创】用CRC编解码矩阵的概念任意制造CRC碰撞 54 樓引述了 wikipedia 的內容，請問對於該內容兩個 viewoints如何說明!?

一:理論上來講，CRC64 的碰撞機率大約是每 18×10^18 個 CRC 碼出現一次。
二:CRC 並不能可靠地驗證數據完整性（即數據沒有發生任何變化），這是因為 CRC 多項式是線性結構，可以非常容易地故意改變數據而維持 CRC 不變，參見CRC and how to Reverse it -- A CRC Tutorial & The c00l way to Reverse CRC 中的證明。

2)
從第一點得知，有人給出了 CRC64 的碰撞率。
從第二點得知， CRC 是線性結構，因此對於這種 characteristic，是有方法進行 prediction 的，因為它是 linear structure。該文提到可以用 Message authentication code 驗證數據完整性；因超出本帖範圍，故不討論。

3)
我想知道 HotPower 的 CRC 方法，有否概估碰撞機率?
我想知道 HotPower 的 CRC 方法，是線性結構還是非線性結構?
我想知道 HotPower 的 CRC 方法，如何可靠地進行數據完整性的驗證?

我研究的是前人未曾研究过的东西，俺没什么理论依据。

可以仔细看贴：http://bbs.pediy.com/showthread.php?t=93968&page=4

我研究的是任意碰撞，而不是穷举得来的结果，因为那些全部都是可预测的。

我把帖中网友给的CRC32碰撞的数据给出分析结果，工具是最新版的HotWC3_V4.09
它支持任意碰撞、对任意CRC逆向出多项式，支持位域4表即可操作半字节。支持16个通用的CRC多项式。
并支持任意多项式的CRC4~CRC64.

http://bbs.pediy.com/showthread.php?t=93968
14楼
可设长度
像 '1234' 的 CRC32 为 9BE3E0A3
我试过长度=4 的明文只有 '1234'
菜农回答：此话是对的

但长度=5的明文有256个, 例如下列几个明文 (十六进制), 其CRC32都是 9BE3E0A3:
20 74 FD 5F DD
21 E2 CD 58 AA
22 58 9C 51 33
23 CE AC 56 44
24 6D 39 32 DA
25 FB 09 35 AD
26 41 58 3C 34
27 D7 68 3B 43
28 46 75 84 D3
29 D0 45 83 A4
2A 6A 14 8A 3D
2B FC 24 8D 4A
长度=16 的明文只有下列一组附合 CRC32=9BE3E0A3
00 00 00 00 00 00 00 01 CE DD 16 26
菜农注解：此话天大的错误！！！
00 00 00 00 00 00 00 01 CE DD 16 26实际长度为12，因为它大于4个字节，故有2^(16-4)次碰撞！！！

输入：0000000000000001CEDD1626
输出：DEBB20E3EDDA1000641C1F5C  结果：9BE3E0A3
攻击位XXXXXXXXXXXXXXXX641C1F5C
菜农开始攻击！

输入：FFFFFFFF00000000CECDCCCB
输出：0000000000000000641C1F5C  结果：9BE3E0A3

输入：E075C51A0E9B2BF4DFDCDDDA
输出：1111111111111111641C1F5C  结果：9BE3E0A3

输入：9D0AD96D9D0AD96D31323334
输出：FFFFFFFFFFFFFFFF641C1F5C  结果：9BE3E0A3

现在再选择16位攻击：
输入：FFFFFFFF0000000000000000CECDCCCB
输出：000000000000000000000000641C1F5C  结果：9BE3E0A3

输入：9D0AD96D9D0AD96D9D0AD96D31323334
输出：FFFFFFFFFFFFFFFFFFFFFFFF641C1F5C  结果：9BE3E0A3

哈哈～～～现在看出来了吧,碰撞次数一定是个“天文数字”～～～

可设长度
像 '1234' 的 CRC32 为 9BE3E0A3
我试过长度=4 的明文只有 '1234'
但长度=5的明文有256个, 例如下列几个明文 (十六进制), 其CRC32都是 9BE3E0A3:
输入明文输出密文输入碰撞等效明文校验结果
2074FD5FDD 77B79CC4641C1F5C 2074FD5F0A517BBC 9BE3E0A3
YYYYYYYYNNNNNNNN Y:可攻击位置 N:不准攻击位置
21E2CD58AA 77B79CB3641C1F5C 21E2CD587D517BBC 9BE3E0A3
22589C5133 77B79C2A641C1F5C 22589C51E4517BBC 9BE3E0A3
23CEAC5644 77B79C5D641C1F5C 23CEAC5693517BBC 9BE3E0A3
246D3932DA 77B79CC3641C1F5C 246D39320D517BBC 9BE3E0A3
25FB0935AD 77B79CB4641C1F5C 25FB09357A517BBC 9BE3E0A3
2641583C34 77B79C2D641C1F5C 2641583CE3517BBC 9BE3E0A3
27D7683B43 77B79C5A641C1F5C 27D7683B94517BBC 9BE3E0A3
28467584D3 77B79CCA641C1F5C 2846758404517BBC 9BE3E0A3
29D04583A4 77B79CBD641C1F5C 29D0458373517BBC 9BE3E0A3
2A6A148A3D 77B79C24641C1F5C 2A6A148AEA517BBC 9BE3E0A3
2BFC248D4A 77B79C53641C1F5C 2BFC248D9D517BBC 9BE3E0A3
XX 攻击位置 00~FF 共256次

实际有密文位数-32个攻击点，如
输入明文输出密文输入碰撞等效明文校验结果
XXXXXXXXXX 77B79C53641C1F5C 2BFC248D67577886 9BE3E0A3
XX 攻击位置 00~FF 共256次
XXXXXXXXXX 00B79C53641C1F5C 4AC8733B675778F1 9BE3E0A3
YY 新攻击位置 00~FF 共256次

长度=16 的明文只有下列一组附合 CRC32=9BE3E0A3
输入明文输出密文校验结果
0000000000000001CEDD1626 DEBB20E3EDDA1000641C1F5C 9BE3E0A3
YYYYYYYYYYYYYYYYNNNNNNNN Y:可攻击位置 N:不准攻击位置
00000000410671DACFDD1626 DEBB20E3EDDA1001641C1F5C 9BE3E0A3
00000000C30A936CCCDD1626 DEBB20E3EDDA1002641C1F5C 9BE3E0A3
X 攻击位置 0~F 共16次
实际有密文位数-64个攻击点，如
输入明文输出密文校验结果
00000000C30A936CCCDD1626 DEBB20E3EDDA1002641C1F5C 9BE3E0A3
X 攻击位置 0~F 共16次
C46692D5C30A286CCCDD1626 DE0020E3EDDA1002641C1F5C 9BE3E0A3
YY 新攻击位置 00~FF 共256次

由crchead, crcfinal可快速得出1个32bit的值,这个32 bit是可逆的。
附件是我写的一个工具。
比如：
crchead = 0xFFFFFFFF;
crcfianl = 0xDEADBEEF;
5 byte，每个byte范围 0 - FF,
则符合值为：
004E3726D4
01D80721A3
026256283A
...
FE55E8238E
FFC3D824F9
它们的crc都是
0xDEADBEEF
输入明文输出密文输入碰撞等效明文校验结果
004E3726D4 E6B5A5E021524110 004E3726DC826E1F DEADBEEF
YYYYYYYYNNNNNNNN Y:可攻击位置 N:不准攻击位置
01D80721A3 E6B5A59721524110 01D80721AB826E1F DEADBEEF
026256283A E6B5A50E21524110 0262562832826E1F DEADBEEF
FE55E8238E E6B5A5BA21524110 FE55E82386826E1F DEADBEEF
FFC3D824F9 E6B5A5CD21524110 FFC3D824F1826E1F DEADBEEF
XX 攻击位置 00~FF 共256次
实际有密文位数-32个攻击点，如
输入明文输出密文输入碰撞等效明文校验结果
XXXXXXXXXX E6B5A5CD21524110 FFC3D824F1826E1F DEADBEEF
XX 攻击位置 00~FF 共256次
XXXXXXXXXX 00B79C53641C1F5C 4AC8733B6FBB6CF9 DEADBEEF
YY 新攻击位置 00~FF 共256次
引用:
1)
既然 HotPower 在【原创】用CRC编解码矩阵的概念任意制造CRC碰撞 54 樓引述了 wikipedia 的內容，請問對於該內容兩個 viewoints如何說明!?

一:理論上來講，CRC64 的碰撞機率大約是每 18×10^18 個 CRC 碼出現一次。
二:CRC 並不能可靠地驗證數據完整性（即數據沒有發生任何變化），這是因為 CRC 多項式是線性結構，可以非常容易地故意改變數據而維持 CRC 不變，參見CRC and how to Reverse it -- A CRC Tutorial & The c00l way to Reverse CRC 中的證明。

2)
從第一點得知，有人給出了 CRC64 的碰撞率。
從第二點得知， CRC 是線性結構，因此對於這種 characteristic，是有方法進行 prediction 的，因為它是 linear structure。該文提到可以用 Message authentication code 驗證數據完整性；因超出本帖範圍，故不討論。

3)
我想知道 HotPower 的 CRC 方法，有否概估碰撞機率?
我想知道 HotPower 的 CRC 方法，是線性結構還是非線性結構?
我想知道 HotPower 的 CRC 方法，如何可靠地進行數據完整性的驗證?

我只回答：

引用:
一:理論上來講，CRC64 的碰撞機率大約是每 18×10^18 個 CRC 碼出現一次。

CRC8为2^8=256故CRC8 的碰撞機率大約是每 256個 CRC 碼出現一次。
CRC64:2^64=18446744073709551616
         故：CRC64 的碰撞機率大約是每 18×10^18 個 CRC 碼出現一次。

所以，要想让CRC8碰撞多于1次，就必须要大于8位即至少要2个字节才能制造“任意碰撞”

引用:
我想知道 HotPower 的 CRC 方法，有否概估碰撞機率?

举例CRCL8_07_00_00
即左移CRC8，权值0x07，初值0出值0,多项式：左移CRC8=X8+X2+X+1

输入(明文)：1234 输出(密文)：7EF1 结果(CRC校验和)F1

我们即可用HotWC3制造任意碰撞：

1.必须记住碰撞概率CRC8为2^8即密文的最后8位即1个字节F1不需改变，因为它就是我们需要
预测的碰撞值。
2.将密文的第1个字节从0x00碰撞到最后1个字节0xFF
3.点击“还原”即做CRC的逆运算

故得到碰撞列表：
输入(明文)：004A 输出(密文)：00F1 结果(CRC校验和)F1
输入(明文)：D94B 输出(密文)：01F1 结果(CRC校验和)F1
输入(明文)：B548 输出(密文)：02F1 结果(CRC校验和)F1
..........................................................................................
输入(明文)：91B4 输出(密文)：FEF1 结果(CRC校验和)F1
输入(明文)：48B5 输出(密文)：FFF1 结果(CRC校验和)F1

正因为菜农逆向了“CRC逆运算”，才导致了"CRC任意碰撞"，"逆向CRC表达式"
"CRC编解码矩阵"，"CRC编解码表"，"CRC位域4"及"CRC任意位域"等怪问题的轻松解决。

这些都是菜农18年对CRC研究的结果，看到这里的论坛有密界高人想探讨一番。

不料这里还要穷举碰撞，实在是郁闷。

同时也谢谢这些网友，否则我真不愿意再升级HotWC3网上运算器。

不敢自吹，没任何CRC计算器的功能比它强大的，至少没有“还原功能”！！！

我给王育民教授表演CRC任意碰撞时，估计他是看呆了，因为他从未看见这样的碰撞～～～