魏普文 山东大学密码技术与信息安全 教育部重点实验室

Presentation on theme: "魏普文 山东大学密码技术与信息安全 教育部重点实验室"— Presentation transcript:

1 魏普文 山东大学密码技术与信息安全 教育部重点实验室
第五章 分组密码 2.攻击方法 魏普文 山东大学密码技术与信息安全 教育部重点实验室

2 DES攻击方法 时间-存储权衡攻击 差分分析 线性分析

3 时间-存储权衡攻击(Time-memory trade-off)
选择明文攻击 不依赖于DES的结构，只与输入/输出/密钥长度有关 穷搜法与查表法的混合 S=O(n2/3), T=O(n2/3), 其中n为密钥量 关于符号O

4 时间-存储权衡攻击 穷搜法（已知明文攻击） 查表法（选择明文攻击）
给定一个明密文对(m*,c*),穷举所有可能2^56密钥k, 直到c=E(k*,m*) 时间复杂度T=O(256), 空间复杂度S=O(1) 查表法（选择明文攻击） 给定一个明文m*，对于所有可能的密钥k, 预计算 有序对表{(c,k)|c=E(k,m)},参照加密者提供的相应密 文c*, 选出正确的密钥 空间复杂度S=O(256)，构建预计算表至少与穷搜同 样耗时

5 时间-存储权衡攻击 定义约化函数 目标

6 时间-存储权衡攻击: 随机选择s个长度为56-bit的串 K(1, 0), K(2,0),…,K(s,0) 根据所选择的明文m*, 利用
计算K(i , j)： K(i , j)=g(K(i,j-1))=R(E(K(i,j-1，m*)))

7 时间-存储权衡攻击: 计算K(i,j)： K(i,j)=g(K(i,j-1))

8 时间-存储权衡攻击: 进一步节省空间 只需存储K(i,j)表的第一列与最后一列 n为密钥量大小

9 参考文献 [Hel80] M. Hellman. A cryptanalytic time memory trade-off, IEEE Transactions on Information Theory 26 (4): 401–406.

10 DES差分分析 80年代末，Eli Biham与Adi Shamir提出的一种选 择明文攻击方法 基本观点
Eli Biham, Adi Shamir, Differential Cryptanalysis of the Data Encryption Standard, Springer Verlag, 1993. ISBN , ISBN 基本观点 比较两个明文的异或（差分值）与相应的两个密文 的异或。分析特定明文差分对相应密文差分的影响 来获得可能性最大的密钥

11 DES差分分析 差分分析理论依据

12 DES差分分析 差分分析理论依据 Bj Bj*有序对

13 S1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 DES差分分析 差分分析理论依据 0000 0001 0010 0011 0100 0101 0110 0111 8 16 6 2 12 1000 1001 1010 1011 1100 1101 1110 1111 6 8

14 input xor 110100 output xor possible inputs 0000 0001
000011,001111,011110,011111,101010,101011,110111,111011 0010 000100,000101,001110,010001,010010,010100,011010,011011, 100000,100101,010110,101110,101111,110000,110001,111010 0011 000001,000010,010101,100001,110101,110110 0100 010011,100111 0101 0110 0111 000000,001000,001101,010111,011000,011101,100011,101001, 101100,110100,111001,111100 1000 001001,001100,011001,101101,111000,111101 1001 1010 1011 1100 1101 111001,010000,010110,011100,100010,100100,101000,110010 1110 1111 000111,001010,001011,110011,111110,111111 为了与3轮DES分析一致，可给出101111的表

15 DES差分分析 对8个S-盒中的每一个，都有64个可能的输入异或， 所以共需计算512个输入输出异或分布 Bj (6-bit)
S-box(j-th) Bj (6-bit) Cj(4-bit)

16 DES差分分析 将以上规律由S-box向外扩展

17 DES差分分析 确定密钥

18 DES差分分析 明文 密文 差分分析应用举例—3轮DES 忽略IP置换，IP逆置换， 注：最后一轮交换

19 DES差分分析 缩减到3圈的DES的差分分析

20 DES差分分析 缩减到3圈的DES的差分分析

21 DES差分分析 缩减到3圈的DES的差分分析 *：差分值任意，0:差分值为0

22 DES差分分析 缩减到3圈的DES的差分分析

23 DES差分分析 缩减到3圈的DES的差分分析

24 DES差分分析 缩减到3圈的DES的差分分析 注意J5，只有7个位置有计数：可能的密钥集合有很多重合

25 DES差分分析 缩减到3圈的DES的差分分析

26 DES差分分析 我们现在可通过查找第3轮的密钥方案能构造出密 钥的48比特。密钥K具有下列形式： 0001101 0110001
01?01? ?00100 ??0 111?11? ?100011 这里已略去了校验比特，“？”表示一个未知的 密钥比特。完全的密钥是（用16进制表示，并包 括校验比特）1A624C89520DEC46

27 DES差分分析 回顾差分分析（Biham，Shamir）

28 DES差分分析 影响差分特征概率的几个因素（多轮DES） 复杂性分析——选择明文个数，加密次数 活性S-盒：输入差分非零的S-盒
P置换、E扩展对活性S-盒的影响 1.注意J5，只有7个位置有计数：可能的密钥集合有很多重合 2.对于多轮DES，S-box输出差分能以确定（子密钥未知）… 3. 只有S-box,差分位置固定… More in Note

29 参考文献 Eli Biham, Adi Shamir, Differential Cryptanalysis of the Data Encryption Standard, Springer Verlag, 1993. ISBN , ISBN Biham, E. and A. Shamir. (1990). Differential Cryptanalysis of DES-like Cryptosystems. Advances in Cryptology — CRYPTO '90. Springer-Verlag. 2–21. Eli Biham, Adi Shamir,"Differential Cryptanalysis of the Full 16-Round DES," CS 708, Proceedings of CRYPTO '92, Volume 740 of Lecture Notes in Computer Science, December  

30 DES线性分析（linear cryptanalysis）
M. Matsui提出线性分析攻击方法（1993） Matsui, M., Linear Cryptanalysis Method for DES Cipher, Advances in Cryptology-EUROCRYPT ’93 Lecture Notes in Computer Science, Volume 765, 1994, pp 线性分析是一种已知明文攻击 221个已知明文 8轮DES 247个已知明文 16轮DES

31 DES线性分析 基本思想 1.寻找有效的线性逼近式降低密钥的熵，从而破译 密码系统 2.极大似然法确定K [k1,k2…,kc]

32 DES线性分析 符号表示

33 DES线性分析 线性分析基本原理 N ¼|p-1/2|-2 1/2|p-1/2|-2 |p-1/2|-2 2|p-1/2|-2
Success Rate 84.1% 92.1% 97.7% 99.8%

34 DES线性分析 对n轮的DES进行线性分析时，在（n-1）轮DES的 最佳线性逼近式后面添加一轮 ，则逼近式变为
对每一个明-密文对，猜测最后一轮的密钥Kn，并 计算包含在线性关系式中的相关状态比特的异或 值。如果在该等式中带入一个不正确的候选者Kn， 那么这个等式的有效性显著降低 使用最大似然方法来推导 和 注意猜测Kn

35 DES线性分析 n轮的DES进行线性分析 N 2|p-1/2|-2 4|p-1/2|-2 8|p-1/2|-2 16|p-1/2|-2
Success Rate 48.6% 78.5% 96.7% 99.9%

36 DES线性分析 线性表达式及其成立概率

37 DES线性分析 线性分析基本原理

38 DES线性分析 线性分析基本原理 低位0st bit 注意：bit位置的表示 （8，14，25，3）[24,18,7,29]
高位 47th bit 低位0st bit 线性分析基本原理 [22](26) S5的输入X[4]： 从右向左（从0开始）是22 从左向右(从1开始) 实际是26，查E表，反推得到输入E前的17位，换算回来为（从右向左的）15位（32-17） S5的输出S(X)[0,1,2,3]: 从右向左（从0开始）[12,13,14,15] 从左向右(从1开始) (17,18,19,10) 考虑P置换后从左向右（从1开始）（8，14，25，3） 从右向左（从0开始）[24,18,7,29] （8，14，25，3）[24,18,7,29]

39 DES线性分析 以三轮DES为例

40 DES线性分析 以三轮DES为例

41 DES线性分析 堆积引理 归纳法证明

42 其他分组密码的分析方法 差分-线性分析，Susan K. Langford and Martin E. Hellman, Crypto 1994 截断差分和高阶差分， Lars R. Knudsen，FSE 1995 不可能差分分析，Biham， Biryuko，Shamir， Eurocrypt 1999 回飞棒攻击，David Wagner, FSE 1999

43 其他分组密码的分析方法 滑动攻击， Alex Biryukov and David Wagner, FSE 1999
矩形攻击， Eli Biham, Orr Dunkelman and Nathan Keller, Eurocrypt 2001 Square攻击， Daemen J., Knuden L. R., Rijmen V, FSE 1997

44 参考书目 Matsui, M., Linear Cryptanalysis Method for DES Cipher, Eurocrypt’93 应用密码学--协议、算法与C源程序, Bruce Schneier 冯登国，裴定一，密码学导引，科学出版社， 2001 A. Menezes, P. van Oorschot and S. Vanstone, Handbook of Applied Cryptography, CRC Press, 1996

45 参考书目 A. Menezes, P. van Oorschot and S. Vanstone, 胡磊， 王鹏译，应用密码学手册，电子工业出版社， 2005 冯登国，密码分析学，清华大学出版社，2000