不可能差分攻击AES中的新密钥筛选算法

董晓丽，胡予濮，陈 杰,2

(1. 西安电子科技大学计算机网络与信息安全教育部重点实验室 西安 710071；2. 中国科学院软件研究所 北京 海淀区 100049)

高级加密标准(AES)[1]成为全球最受关注的分组密码之一，并涌现出了各种攻击方法包括不可能差分攻击[2]、矩形攻击[3]、中间相遇攻击[4-5]、相关密钥攻击[6-7]等。

不可能差分攻击由文献[8]针对Skipjack提出。它通过寻找不可能差分路径，排除满足这种关系的密钥，最终恢复出秘密密钥的攻击方法。文献[2]使用4轮不可能差分区分器攻击5轮AES-128，需要229.5选择明文，231的5轮加密。文献[9]将不可能差分应用于6轮AES，需要291.5选择明文，2122的6轮加密。文献[10]利用192 bit和256 bit密钥扩展弱点将不可能差分攻击应用于7轮AES-192和AES-256，分别需要292和292.5选择明文及2186和2250.5的7轮加密。文献[11]提出7轮AES-128攻击方案，需要2121的7轮加密。文献[12]首次把不可能差分攻击应用于8轮AES-256，需要2116.5选择明文，2247.5的8轮加密。文献[13]在INDOCRYPT2008上改进了文献[10-12]的攻击，是目前最新的不可能差分攻击。

不可能差分主要包括两步[8,14]，第一步是寻找不可能差分路径；第二步是密钥恢复。密钥恢复使用密钥筛选方法，利用猜测密钥部分加解密后，排除符合不可能差分路径的错误候选密钥。密钥筛选常用表查询技术[2]与分别攻击技术[15]，本文在对AES不可能差分攻击中将两种技术结合提出新密钥筛选算法。结果表明，新算法在时间复杂度函数选择恰当自变量时，时间复杂度低于已有密钥筛选方法。表查询技术和分别攻击技术是新算法的特殊情况。将已有方法中最优的表查询技术和新算法详细比较，指出新算法优势何时更明显。将新算法应用于INDOCRYPT2008上对AES的不可能差分攻击，给出时间复杂度曲线，得出最佳点降低了时间复杂度。

1 基础知识

1.1 AES

AES[1]分组长度是128 bit，密钥长度有128、192和256 bit等3种，分别用AES-128、AES-192和AES-256表示，且分别需要迭代10轮、12轮和14轮。AES 128-bit分组表示以字节Xi为元素的4×4矩阵阵列：

1.2 不可能差分攻击[8,14-15]

1.3 不可能差分攻击AES中的密钥筛选

图1 不可能差分分析AES中的算法 aE

2 新的AES-密钥筛选算法

2.1 AES子密钥性质

2.2 新的AES-密钥筛选算法

2.3 新算法时间复杂度

3 与已有AES-密钥筛选方法比较

可看出降低率D(m)仅与m有关，与kb没有关系。给出如图2所示的曲线图，m越大，降低率越大。

图2 时间复杂度降低率D(m)曲线图

已有方法中表查询技术最优，对表查询技术和新算法比较，指出新算法优势何时更明显。在INDOCRYPT2008上针对AES提出最优不可能差分攻击，本文把新算法应用到这一攻击中，给出时间复杂度曲线，选择最佳点，相应时间复杂度降低，且保持数据复杂度不变，如表1所示。其中CP表示选择明文。

表1 与I NDOCRYPT2008攻击结果比较

4 新算法改进文献[13]的攻击

4.1 7轮AES-128

4.2 7轮AES-192和7轮AES-256

图3 新算法与已有的密钥筛选方法比较

4.3 8轮AES-256

5 结 论

本文在不可能差分攻击AES的密钥筛选中把表查询技术和分别攻击技术相结合提出新算法。研究结果表明，该算法在时间复杂度函数选择恰当的自变量时，时间复杂度低于已有的密钥筛选方法。

本文算法思想可以使用在其他分组密码算法分析中，研究中可以进一步关注。

[1] DAEMEN J, RIJMEN V. The design of Rijndael: AES-the advanced encryption standard[M]. Berlin: Springer, 2002:31-148.

[2] BIHAM E, KELLER N. Cryptanalysis of reduced variants of rijndael[C]//Proceedings of the Third Advanced Encryption Standard Candidate Conference. [S.l.]: [s.n.],2000.

[3] KIM J, HONG S, PRENEEL B. Related-key rectangle attacks on reduced AES-192 and AES-256[C]//Fast Software Encryption. Berlin: Springer-Verlag, 2007, 4593: 225-241.

[4] DEM IRCI H, SELCUK A. A meet-in-the-m iddle attack on 8-round AES[C]//Fast Software Encryption. Berlin:Springer-Verlag, 2008, 5086: 116-126.

[5] DEM IRCI H, TASKM I, COBAN M, et al. Improved meet-in-the-middle attacks on AES[C]//Progress in Cryptology-INDOCRYPT 2009. Berlin: Springer-Verlag,2009, 5922: 144-156.

[6] BIRYUKOV A, KHOVRATOVICH D, NIKOLIC I.Distinguisher and related-key attack on the full AES-256[C]//Advances in Cryptology-CRYPTO 2009.Berlin: Springer-Verlag, 2009, 5677: 231-249.

[7] BIRYUKOV A, KHOVRATOVICH D. Related-key cryptanalysis of the full AES-192 and AES-256[C]//Advances in Cryptology-ASIACRYPT 2009. Berlin:Springer-Verlag, 2009, 5912: 1-18.

[8] BIHAM E, BIRYUKOV A, SHAM IR A. Cryptanalysis of skipjack reduced to 31 rounds using impossible differentials[C]//Advances in Cryptology-EUROCRYPT’99.Berlin: Springer-Verlag, 1999, 1592: 12-23.

[9] CHEON J, KIM M, KiIM K, et al. Improved impossible differential cryptanalysis of rijndael and crypton[C]//Information Security and Cryptology-ICISC 2001. Berlin:Springer-Verlag, 2002, 2288: 39-49.

[10] PHAN R C-W. Impossible differential cryptanalysis of 7-round advanced encryption standard (AES)[J].Information Processing Letters, 2004, 91(1): 33-38.

[11] BAHRAK B. AREF M R. A novel impossible differential cryptanalysis of AES[C]//Proceedings of WEWoRc'07-Western European Workshop on Research in Cryptology.Bochum, Germany: [s.n.], 2007.

[12] ZHANG Wen-tao, WU Wen-ling, FENG Deng-guo. New results on impossible differential cryptanalysis of reduced AES[C]//Information Security and Cryptology-ICISC 2007.Berlin: Springer-Verlag, 2007, 4817: 239-250.

[13] LU J, DUNKELMAN O, KELLER N, et al. New impossible differential attacks on AES[C]//Progress in Cryptology-INDOCRYPT 2008. Berlin: Springer-Verlag,2008, 5365: 279-293.

[14] 吴文玲, 张蕾. 不可能差分密码分析研究进展[J]. 系统科学与数学, 2008, 28(8): 971-983.

WU Wen-ling, ZHANG. Lei. The state-of-the-art of research of impossible differential cryptanalysis[J]. Journal of Systems Science and Mathematical Sciences, 2008,28(8): 971-983.

[15] LU J. Cryptanalysis of block ciphers[D]. London: Royal Holloway University of London, 2008.

编 辑 漆 蓉