专栏中心

EEPW首页 > 专栏 > CRC密钥碰撞及S盒的遐想

CRC密钥碰撞及S盒的遐想

发布人：0750long 时间：2009-07-27 来源：工程师

加入技术交流群
- 扫码加入
  和技术大咖面对面交流
  海量资料库查询

引用:

再如DES的8个S盒。(6入4出)
每个S盒有4行16列，8个S盒共32行16列。
根据数学的“全排列”定义，DES的S盒排列数应该有16!=20927789888000
故此密码的编码只是其全排列的很小一部分。

CRC4和DES的S盒都属于这个全排列，CRC4有16行(初值、权)16列(明文)。
可惜在CRC4的一行(表)中找不到DES的S盒的一行~~~
但我们可以在CRC4表中到处找到S盒的“身影”。

CRC碰撞一般指CRC明文的碰撞，即CRC密钥确定时不同明文流所产生同一CRC结果的现象。

而CRC密钥碰撞是指一对CRC明文和CRC密文确定时,有多少个CRC密钥与之配对的问题。

站在CRC密钥碰撞的立场上，“CRC明文碰撞”是“一对一”的关系，而“CRC密钥碰撞”是“多对一”的关系。

前者是CRC密码的问题，后者是CRC运算的问题。故菜农自贺的是后者。

本文不再讨论CRC明文碰撞问题。

在CRC密码体系中，成员包括CRC密钥(初值、权及方向)和明文及密文三个主要部分。算法为基本的CRC运算
即简单的移位和异或运算。

CRC一次运算的结果实际是在密钥下对应的一组结果即明文和密文对。
我们可以把这样的操作视为一个广义的“表”，如同S盒或特殊数组及矩阵一样。

在密钥即表的行列确定时，必得到一组唯一无重码的成员即明文和密文对。即“一对一”的关系。

但是CRC或S盒都只选取了这张全排列的广义表的其中一小部分，故不同的密钥就比对应同一结果。
即“多对一”得关系。

如S盒的“6入4出”。2^6中选2^4,必有2^2个冗余，即有4次密钥碰撞概率。
其中"6入4出"即4行(2位)和16列(4位)对应于4位输出(0~15)
由于DES的S盒“非线性”排列，即每个S盒的某行某列对应的值无重码，故其密钥(行,列)碰撞次数为0。
但是8个S盒之间是有密钥碰撞即行列碰撞，只是DES用轮次错开碰撞而已。

再以CRC4加以说明：
已知明文0x01，密文0x02。那么有对少个密钥即初值和权与之配对???
这实际是个类同S盒的“6入4出”的"12入4出"问题。故必有2^8个CRC密钥碰撞概率。
其中"12入4出"即4位初值、3位权、1位方向和4位明文对应于4位密文。
由于CRC4表可逆及排列有序，故CRC4必有2^4个CRC密钥碰撞次数。
当密钥确定(如同S盒的某轮)，CRC4的某一密钥即“S盒”内每个明文也只对应一个密文，
故和S盒一样，此时其密钥(行,列)碰撞次数也为0。

16组碰撞数据列举如下：
          方向：    左移CRC4           右移CRC4
明文0x01  初值：3 E 9 6 2 9 C 5    3 7 B F A C 6 0
密文0x02  权值：1 3 5 7 9 B D F    8 9 A B C D E F

从表中可以看到：

初值=0x03 权=0x01 左移CRC4 明文0x01 得到密文0x02 即CRC校验结果0x02
初值=0x06 权=0x07 左移CRC4 明文0x01 得到密文0x02 即CRC校验结果0x02

初值=0x03 权=0x08 右移CRC4 明文0x01 得到密文0x02 即CRC校验结果0x02
初值=0x06 权=0x0E 右移CRC4 明文0x01 得到密文0x02 即CRC校验结果0x02

故得此结论：
在CRC密钥不确定即“一次一密”时，与明文及密文有关的所有攻击手段是“徒劳”的。
因为它是“多对一”即不可逆的。(这就是CRC密码或S盒应用的目的所在)

CRC密钥碰撞的“碰撞次数”恒为2^N。

即DES的S盒有0次密钥碰撞，而CRC4恒为16次CRC密钥碰撞，CRC8恒为256次CRC密钥碰撞...

可见DES的S盒的0次“碰撞”比CRC密钥碰撞要少许多，只不过是选择的“广义表”不同而已。
CRC的“广义表”依据CRC运算规则排列，S盒的排列规则只能去问美国大鼻子老头了~~~

实际“密钥碰撞”的次数愈大，逆向的难度就更大。因为逆向最怕的就是“碰撞”即“多对一”。
从以上CRC4的“S盒”分析，当CRC密钥中的权确定后,即DES的“S盒”确定后，
CRC密钥中的初值(类同S盒的行)对应的CRC明文(类同S盒的列)内所有数据都是从0到F散列开的。
所以，分析CRC4密码和S盒是“完全一样”的。

“CRC密钥碰撞”是菜农选择CRC做HotWC3密码系统中的“S盒”最重要的原因之一。
也是菜农回应某些人嘲笑“CRC太简单”的“论据吧”~~~
分组加密体系的DES的S盒是“6入4出”，一轮8个S盒就是“48入32出”，而在HotWC3中，
由于是流加密体系，故其“S盒”即CRC8为“24入8出”.

若以流加密来衡量，DES的8个S盒实际为“12入8出”，比CRC8的“密钥碰撞”概率还小，
故分组密码都需要N轮，而流加密往往只需或只能（传输要求）一轮即可。

S盒“号称非线性”菜农绝不认同！！！它的排列规则肯定类同CRC4.(因为它跑不过数学的排列与组合)
S盒与CRC4同属于一个“广义表”，难道它就无算法可循吗？？？

专栏文章内容及配图由作者撰写发布，仅供工程师学习之用，如有侵权或者其他违规问题，请联系本站处理。联系我们

关键词：