首页
社区
课程
招聘
问答 CTF 排行榜 知识库 工具下载 看雪峰会 看雪商城 证书查询
  1. 看雪社区
  2. 密码应用
    3. 发新帖
[原创]用CRC编解码矩阵的概念任意制造CRC碰撞
2009-7-21 02:11 51016

[原创]用CRC编解码矩阵的概念任意制造CRC碰撞

HotPower 活跃值
2009-7-21 02:11
51016
CRC编解码矩阵见：http://bbs.pediy.com/showthread.php?t=93844
可以看到用CRC编解码矩阵的概念更容易实现“CRC碰撞”

网上的一个求助帖：求生成的CRC64编码完全相同的两个串

我们可以做2个CRC64(左移):
设CRC64权(左移)=0x42F0E1EBA9EA3693 CRC64校验和=0x012345678ABCDEF
要求:
CRC64明文1=0x1122334455667788
CRC64明文2=0x8877665544332211

那么CRC64的2个初值为多少？？？
因为CRC64的初值我们无法立即得到，但我们可以间接得到：

在CRC正运算即CRC编码(对称)矩阵中，初值和明文可以相互交换。
在CRC逆运算即CRC解码(非对称)矩阵中,密文和初值锁定明文，密文和明文锁定初值。

故CRC64的初值1：
CRC64权=0x42F0E1EBA9EA3693
CRC64初值1=0x1122334455667788(先用明文1替代)
CRC64校验和=0x012345678ABCDEF(就是密文1或密文2)
求CRC64的逆运算即查CRC64的解码表，得到
CRC64明文1=0x2D6FD3ADE7D797FD(此时是逆运算时的明文)

故CRC64初值1=0x2D6FD3ADE7D797FD和CRC64明文1=0x1122334455667788
在CRC64权=0x42F0E1EBA9EA3693时的校验和=0x012345678ABCDEF

同理：
CRC64初值2=0xB43A86BCF682C264和CRC64明文2=0x8877665544332211
在CRC64权=0x42F0E1EBA9EA3693时的校验和=0x012345678ABCDEF

从以上2个例子可以看出：
CRC密码的密钥虽然由初值、权及方向组成，一旦权和方向确定后，初值、明文即密文
三者的关系只要知道两者即可求解出第三者。

故CRC密码的安全之关键在于对CRC权及方向的保护，即对CRC编解码矩阵的保护。

以上问题都归为一般的“CRC碰撞”，即权确定时的CRC碰撞。

若用其它CRC元素求解CRC权，则属于“CRC密钥碰撞”。

以CRC8密钥为例，它有2^16，其中初值2^8,(权+方向)为2^8.

(权+方向)对应1个矩阵，故有2^8次“CRC密钥碰撞”。

但是CRC密钥不确定时，最多只能发生一次“CRC密钥碰撞”。

即其它CRC元素所对应的权即编解码矩阵就不存在。

下图是HotWC3对CRC权及方向的保护：


[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课

收藏
点赞・7
打赏
分享
最新回复 (81)
helpmsg
雪    币： 236
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
helpmsg 2009-7-21 13:26
2 楼
0
LZ也弄个强大的算法吧。
skykrnl
雪    币： 70
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
skykrnl 2009-7-23 00:35
3 楼
0
太TMD专业了~
sessiondiy
雪    币： 2071
活跃值： (77)
能力值： ( LV9，RANK：180 )
在线值：
发帖
回帖
粉丝
私信
sessiondiy 4 2009-7-23 01:23
4 楼
0
落落的问一下
请问得到的CRC64值一样 的2个明文各是什么?
ccfer
雪    币： 8191
活跃值： (4268)
能力值： ( LV15，RANK：2459 )
在线值：
发帖
回帖
粉丝
私信
ccfer 16 2009-7-23 09:19
5 楼
0
我用DAMN Hash Calculator计算"1234"的CRC32=9BE3E0A3

Calculating hash of 4 bytes string `1234`...
CRC-32      : 9BE3E0A3
Calculation took 0.000 seconds

用楼主的计算器如何才能得到相同的结果呢？
HotPower
雪    币： 129
活跃值： (1095)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
HotPower 2009-7-23 18:28
6 楼
0
CRC32的表达式和运算过程很乱，我的演算器是为ARM芯片STM32做的。
它的输出没反向。

一般CRC32都是初值为0xffffffff,输出反向，即xor 0xffffffff

CRC主要看采用的多项式和移动方向

用楼主的计算器如何才能得到相同的结果呢？


必须有相同的表达式和初值，至于输出反向那不是什么问题。
HotPower
雪    币： 129
活跃值： (1095)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
HotPower 2009-7-23 18:50
7 楼
0
请问得到的CRC64值一样 的2个明文各是什么?


我举得就是这种例子呀~~~“CRC碰撞”就是不同的明文得到相同的密文即CRC的结果值。
“CRC碰撞”实际有“明文”和“密钥”碰撞2种。
前者是初值和权(多项式)确定时不同的明文产生相同的CRC结果值。
后者是初值和权(多项式)不确定时相同的明文产生相同的CRC结果值。

CRC实际有5个元素：初值、权和方向及明文和密文(结果)。

一个权即锁定一个CRC编码矩阵或CRC解码矩阵。
此“CRC编解码矩阵”的行为初值，列为明文或密文，矩阵元素为密文或明文。

锁定了矩阵，就是初值、明文和密文三者之间的“查表”关系了。

CRC编码矩阵是个对称矩阵，它满足初值和明文的“交换率”。
CRC解码矩阵是个对对称矩阵，它们之间是“可逆”的关系。(可惜不符合逆矩阵)

大家可以看一下“CRC4编解码矩阵”的图表(其它太大不好分析)：



上传的附件：
ccfer
雪    币： 8191
活跃值： (4268)
能力值： ( LV15，RANK：2459 )
在线值：
发帖
回帖
粉丝
私信
ccfer 16 2009-7-23 20:04
8 楼
0
sessiondiy的问题很直接，你回复那么多大家也看不懂答案是什么，你只需要回答：
明文1=？
明文2=？
HotPower
雪    币： 129
活跃值： (1095)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
HotPower 2009-7-23 21:00
9 楼
0
故CRC64初值1=0x2D6FD3ADE7D797FD和CRC64明文1=0x1122334455667788
在CRC64权=0x42F0E1EBA9EA3693时的校验和=0x012345678ABCDEF

同理：
CRC64初值2=0xB43A86BCF682C264和CRC64明文2=0x8877665544332211
在CRC64权=0x42F0E1EBA9EA3693时的校验和=0x012345678ABCDEF


不知是我没理解还是sessiondiy没看清楚，楼主位的例子已经说明白了。

可能有人说初值和权已确定，如何“碰撞”？？？
答案明文1=明文2，因为初值和权已确定，每个明文对应唯一一个密文即校验和。

若非要碰撞，就只能明文大于64位即至少要2个64位数才能产生“CRC碰撞”。

参见：http://bbs.pediy.com/showthread.php?t=93139

里面2楼里有---如何“人造”CRC碰撞？？？
ccfer
雪    币： 8191
活跃值： (4268)
能力值： ( LV15，RANK：2459 )
在线值：
发帖
回帖
粉丝
私信
ccfer 16 2009-7-23 21:48
10 楼
0
你标题名字就是说的是"任意制造CRC碰撞"
按照我们一般的理解就是要碰撞两组明文
HotPower
雪    币： 129
活跃值： (1095)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
HotPower 2009-7-23 22:02
11 楼
0
“CRC碰撞”的碰撞是指“相同的CRC校验和”
sessiondiy
雪    币： 2071
活跃值： (77)
能力值： ( LV9，RANK：180 )
在线值：
发帖
回帖
粉丝
私信
sessiondiy 4 2009-7-23 22:14
12 楼
0
这个直接一点. 里头的工具就很会碰(相同的CRC校验和)

http://bbs.pediy.com/showthread.php?t=66767&tcatid=37&viewgoodnees=1

另外, 能实作出来的东西才有用吧.
HotPower
雪    币： 129
活跃值： (1095)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
HotPower 2009-7-23 22:34
13 楼
0
我不知道它“碰撞”原理，但我分析的是“任意碰撞”。

当初值和权确定时，明文为2组即可产生2^N碰撞。

当明文为2组时:
CRC8有256个碰撞值，CRC16有65536个碰撞值，CRCN有2^N个碰撞值。

当明文为3组时:
CRC8有256*256个碰撞值，CRC16有65536*65536个碰撞值，CRCN有2^N*2^N个碰撞值。

......

不知道它能否有这麽多的“碰撞”？？？
sessiondiy
雪    币： 2071
活跃值： (77)
能力值： ( LV9，RANK：180 )
在线值：
发帖
回帖
粉丝
私信
sessiondiy 4 2009-7-23 22:48
14 楼
0
可设长度
像 '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
HotPower
雪    币： 129
活跃值： (1095)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
HotPower 2009-7-23 22:50
15 楼
0
点击直接运行: 112位HotWC3/CRC通用网上演算器V2.20

对于“CRC碰撞”，上面的工具就是“还原键”

“碰撞模板”：

初值：0   输入：待“碰撞”的明文                            【计算键】
权值：9   输出：第1个数据为“碰撞种子”，第2个数据为校验和  【还原键】

假设碰撞值即校验和=8. 则：
初值：0   输入：0B   (对应输出08单击还原键后的明文)
权值：9   输出：08  【还原键】

初值：0   输入：3A   (对应输出18单击还原键后的明文)
权值：9   输出：18  【还原键】

...........

初值：0   输入：24   (对应输出F8单击还原键后的明文)
权值：9   输出：F8  【还原键】
HotPower
雪    币： 129
活跃值： (1095)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
HotPower 2009-7-23 22:58
16 楼
0
可设长度
像 '1234' 的 CRC32 为 9BE3E0A3
我试过 长度=4 的明文 只有 '1234'
但长度=5的明文有256个, 例如下列几个明文 (十六进制), 其CRC32都是 9BE3E0A3:


对于CRC32即每组为4个字节，所以长度应该设置为4的倍数才行，设置5，实际内部设置为8, 数据位补零。
长度=5的明文有256个，即多的1个字节变化有256次，故“明文有256个”。

实际就是:
初值：XXXXXXXX   XXXXXXXX XXXXXXXX
权值：XXXXXXXX   000000YY XXXXXXXX    这个“YY” 有256个对应的明文。

我试过 长度=4 的明文 只有 '1234'


在CRC中，在初值和权确定后，一组明文对应与唯一一组密文即校验和。

所以这个工具在长度为4时，只能有一个校验和，即无碰撞。

在2组即长度选择8时，将会发生2^32次碰撞。

注意15楼的-------第1个数据为“碰撞种子”，可想CRC32的一个“种子”可从0~2^32-1即2^32次任意碰撞。

这个软件我没用过，不知道用的什么原理，不会真的去搜索“碰撞”吧~~~

实际“碰撞”是可以“人造”的~~~

等我又时间把http://www.hotc51.com/HotPower_HotWC3.html升级为支持普遍的CRC32.可惜现在只支持STM32的CRC32.
ccfer
雪    币： 8191
活跃值： (4268)
能力值： ( LV15，RANK：2459 )
在线值：
发帖
回帖
粉丝
私信
ccfer 16 2009-7-24 09:26
17 楼
0
普通的CRC32不用4个字节分组的，长度5就是5，不需要补位到8字节长度
HotPower
雪    币： 129
活跃值： (1095)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
HotPower 2009-7-24 09:59
18 楼
0
这是由计算机内部的寄存器位数或程序语言的数据类型决定的。

所以“长度5就是5”是你外部操作软件的结果。
搞编程的人都明白这些。

因为世界上没有“5位”即20位计算能力或20位处理的计算机。

普通的CRC32不用4个字节分组的，长度5就是5，不需要补位到8字节长度


实际上:

CRC4为分组半字节(4位)
CRC8为分组1字节(8位)
CRC12为分组1.5字节(12位)
CRC16为分组2字节(16位)
CRC24为分组3字节(24位)
CRC32为分组4字节(32位)
CRC48为分组6字节(48位)
CRC64为分组8字节(64位)
CRC128为分组16字节(128位)
CRC256为分组32字节(256位)
sessiondiy
雪    币： 2071
活跃值： (77)
能力值： ( LV9，RANK：180 )
在线值：
发帖
回帖
粉丝
私信
sessiondiy 4 2009-7-24 10:20
19 楼
0
我要回火星了, 地球太可怕了.
ccfer
雪    币： 8191
活跃值： (4268)
能力值： ( LV15，RANK：2459 )
在线值：
发帖
回帖
粉丝
私信
ccfer 16 2009-7-24 10:36
20 楼
0
楼上的带我一起走吧，请求避难
ccfer
雪    币： 8191
活跃值： (4268)
能力值： ( LV15，RANK：2459 )
在线值：
发帖
回帖
粉丝
私信
ccfer 16 2009-7-24 10:44
21 楼
0
s带我回火星之前，还是忍不住回一下：
长度5是指5字节，一个字节是8位，5*8＝40位
在x86中一般都是32位寄存器和8位寄存器组合操作居多

难道楼主的112位密码系统是用的112位计算能力或112位处理的计算机实现的？
HotPower
雪    币： 129
活跃值： (1095)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
HotPower 2009-7-24 12:25
22 楼
0
s带我回火星之前，还是忍不住回一下：
长度5是指5字节，一个字节是8位，5*8＝40位
在x86中一般都是32位寄存器和8位寄存器组合操作居多

难道楼主的112位密码系统是用的112位计算能力或112位处理的计算机实现的？


不知ccfer是否编过程序，是否知道“大端”“小端”和数据类型占用的字节。

可能你要问我会什么：http://blog.ednchina.com/hotpower/

这个博客可以告诉你菜农学过多少种计算机语言。

至于“112位计算能力”，可以告诉你它是多个8位密钥流的级联。

DES密钥长度是56位，难道112位很奇怪吗？？？


HotPower的文潭



博客公告

在21ic只保留Hotpower的水潭
其他将依次改为:
Hotpower的文潭
Hotpower的自留地
Hotpower的菜地等~~~

我的分类

ARM （25）
Keil C51 （39）
GCCAVR之C++ （20）
PICC （12）
DSP （11）
Delphi语言设计 （6）
尿童学堂 （28）
非典应用怪潭 （11）
HotPower水潭导航 （3）
菜地公告 （34）
非典型LPCARM之攻防体系 （4）
CUPL语言设计 （11）
ABEL语言设计 （3）
非典应用怪潭 （7）
尿童答疑 （5）
尿童图解 （3）
串行数据通讯 （9）
自言自语 （35）
看门狗专栏 （12）
非典型LPCARM专栏 （2）
实用电子书籍 （1）
LPCARM之ISP （12）
菜农键盘专栏 （14）
51反汇编 （26）
51演示程序 （4）
串口通讯专栏 （10）
函数指针 （1）
LPCARM爬鸟 （4）
程序安全 （4）
菜农文件 （5）
ARM入门 （1）
开源文件包 （3）
SPI接口 （3）
I2C接口 （12）
程序优化 （3）
上位机 （7）
菜农搞笑 （34）
CRC专栏 （18）
菜农文集 （3）
数据库 （9）
LabWindows/CVI （19）
CRC/PEC （20）
菜农的HotComm串口控件 （26）
无线通讯 （6）
IAR C++ （4）
USB （9）
电源技术 （1）
PIC C30 （4）
STM32菜鸟实习 （18）
三十年追梦 （9）
LM菜鸟实习 （9）
单总线通讯 （6）
电信交换 （14）
CPLD （2）
DSP/BIOS （36）
DSP GEL语言 （5）
MSP430 （7）
DSP2812 （13）
DSP5402 （26）
DSP206 （3）
DSP/RTDX （9）
COM编程技术 （14）
C++裸奔大法系列 （9）
HotBIOS （12）
C5402CFG头文件 （7）
红色黑客 （15）
菜农公式 （9）
VC++程序设计 （25）
C#编程设计 （47）
菜农玩C# （9）
VB.Net程序设计 （6）
菜农玩VB.NET （6）
Java程序设计 （17）
菜农玩Java （3）
HotTask51操作系统 （26）
HotC51共产儿童团 （59）
HotTIDSP帝国 （3）
TI博客大赛 （0）
HotCRC逆向世界 （1）
HotWC3密码 （17）

友情链接

·电子工程师的收藏夹
·菜农的农家博客
·嵌入式公社



博客信息

日志总数：992 篇
评论数量：435
访问次数：842147
ccfer
雪    币： 8191
活跃值： (4268)
能力值： ( LV15，RANK：2459 )
在线值：
发帖
回帖
粉丝
私信
ccfer 16 2009-7-24 12:57
23 楼
0
我没编过程序，不懂得什么大道理
我只知道x86是可以单字节寻址的，也有8位的寄存器
因此5字节的数据不需要做什么补位就能够计算其CRC32值
jackozoo
雪    币： 1450
活跃值： (35)
能力值： (RANK：680 )
在线值：
发帖
回帖
粉丝
私信
jackozoo 14 2009-7-24 13:09
24 楼
0
几天没来密码学板块了, 还蛮热闹的~

还吸引来了session, ccfer 两位大侠.  多谢捧场~~
疯子鱼
雪    币： 358
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
疯子鱼 2009-7-24 13:10
25 楼
0
要说ccfer没编过程序,全论坛的程序员都笑了
游客
登录 | 注册 方可回帖
　回帖　 表情 雪币赚取及消费
高级回复
返回