改进的减轮Kiasu-BC算法的中间相遇攻击

doi:10.11959/j.issn.1000-436x.2022112

通信学报 ›› 2022, Vol. 43 ›› Issue (7): 41-48.doi: 10.11959/j.issn.1000-436x.2022112

改进的减轮Kiasu-BC算法的中间相遇攻击

李曼曼¹^,²^,³, 陈少真¹^,²^,³

¹ 信息工程大学网络空间安全学院，河南郑州 450001
² 密码科学技术国家重点实验室，北京 100878
³ 河南省网络密码技术重点实验室，河南郑州 450001

修回日期:2022-05-09 出版日期:2022-07-25 发布日期:2022-06-01
作者简介:李曼曼（1986- ），女，河南开封人，博士，信息工程大学讲师，主要研究方向为网络空间安全、信息安全、对称密码的设计与分析等
陈少真（1967- ），女，江苏无锡人，博士，信息工程大学教授，主要研究方向为密码学与信息安全
基金资助:
河南省网络密码技术重点实验室开放课题基金资助项目(LNCT2019-S03)

Improved meet-in-the-middle attack on reduced-round Kiasu-BC algorithm

Manman LI¹^,²^,³, Shaozhen CHEN¹^,²^,³

¹ College of Cyberspace Security, Information Engineering University, Zhengzhou 450001, China
² State Key Laboratory of Cryptology, Beijing 100878, China
³ Henan Key Laboratory of Network Cryptography Technology, Zhengzhou 450001, China

Revised:2022-05-09 Online:2022-07-25 Published:2022-06-01
Supported by:
Henan Key Laboratory of Network Cryptography Technology Open Funds(LNCT2019-S03)

摘要/Abstract

摘要：

Kiasu-BC算法是加密认证竞赛CAESAR第一轮入选方案Kiasu的内置可调分组密码。Kiasu-BC算法是基于AES-128轮函数构造的可调分组密码算法，通过对Kiasu-BC算法的结构特征进行研究，利用调柄自由度以及内部密钥间的制约关系，降低预计算的复杂度。结合差分枚举技术，构造新的5轮中间相遇区分器，改进Kiasu-BC算法的8轮中间相遇攻击。改进后攻击的时间复杂度为2¹¹⁴，存储复杂度为2⁶³，数据复杂度为2¹⁰⁸。

关键词: 可调分组密码, Kiasu-BC算法, 中间相遇攻击, 差分枚举

Abstract:

Kiasu-BC algorithm is an internal tweakable block cipher of authenticated encryption algorithm Kiasu as one of first-round candidates in the CAESAR competition.The precomputation complexity is reduced by utilizing the freedom of the tweak and the internal key restriction through the research on structural characteristics of Kiasu-BC algorithm based on AES-128 round function.Combined with the differential enumeration technique, a new 5-round meet-in-the-middle distinguisher was constructed to improve the meet-in-the-middle attack on 8-round Kiasu-BC algorithm.The improved attack requires the time complexity of 2¹¹⁴, the memory complexity of 2⁶³ and the data complexity of 2¹⁰⁸.

Key words: tweakable block cipher, Kiasu-BC algorithm, meet-in-the-middle attack, differential enumeration

中图分类号:

TN918.1

李曼曼, 陈少真. 改进的减轮Kiasu-BC算法的中间相遇攻击[J]. 通信学报, 2022, 43(7): 41-48.

Manman LI, Shaozhen CHEN. Improved meet-in-the-middle attack on reduced-round Kiasu-BC algorithm[J]. Journal on Communications, 2022, 43(7): 41-48.

图/表 7

表1

符号说明"

符号	说明
m，n	状态矩阵的行数，列数
P，C	明文，密文
Δ P，ΔC	明文差分，密文差分
x _i，y_i，z_i，w_i	第i轮中字节代替、行移位、列混合、轮调柄密钥加变换前的状态
$x [i]$	状态矩阵 $x$ 的第i单元
$x [i, \dots, j]$	状态矩阵 $x$ 的第i至第 j单元
$x ∥ y$	x和y 级联
$x^{≪ k}$	状态x循环左移k bit

表1

图1

图2

图3

图4

图5

表2

参考文献 25

[1]	LISKOV M , RIVEST R , WAGNER D . Tweakable block ciphers[C]// Advances in Cryptology – CRYPTO 2002. Berlin:Springer, 2002: 31-46.
[2]	JEAN J , NIKOLIC I , PEYRIN T . Tweaks and keys for block ciphers:the Tweakey framework[C]// Advances in Cryptology – ASIACRYPT 2014. Berlin:Springer, 2014: 274-288.
[3]	JEAN J , NIKOLI? I , PEYRIN T . KIASU-submission to the CAESAR competition[EB].[2018-11-28](2022-02-09).
[4]	JEAN J , NIKOLI? I ,, PEYRIN T . Joltik-submission to the CAESAR competition[EB].[2018-11-28](2022-02-09).
[5]	JEAN J , NIKOLI? I ,, PEYRIN T . Submission to CAESAR[EB].[2016-10](2022-02-09).
[6]	DOBRAUNIG C , EICHLSEDER M , MENDEL F . Square attack on 7-round Kiasu-BC[C]// International Conference on Applied Cryptography and Network Security. Berlin:Springer, 2016: 500-517.
[7]	ABDELKHALEK A , TOLBA M , YOUSSEF A M . Cryptanalysis of some block cipher constructions[D]. Montreal:The Concordia Institute, 2017.
[8]	TOLBA M , ABDELKHALEK A , YOUSSEF A M . A meet in the middle attack on reduced round Kiasu-BC[J]. IEICE Transactions on Fundamentals of Electronics,Communications and Computer Sciences, 2016,99(10): 1888-1890.
[9]	DOBRAUNIG C , LIST E . Impossible-differential and boomerang cryptanalysis of round-reduced Kiasu-BC[C]// Topics in Cryptology –CT-RSA 2017. Berlin:Springer, 2017: 207-222.
[10]	JIANG Z L , JIN C H . Multiple impossible differentials cryptanalysis on 7-round ARIA-192[J]. Security and Communication Networks,2018, 2018:7453572.
[11]	LIU Y , SHI Y F , GU D W ,et al. Improved meet-in-the-middle attacks on reduced-round Kiasu-BC and Joltik-BC[J]. The Computer Journal, 2019,62(12): 1761-1776.
[12]	DIFFIE W , HELLMAN M E . Special feature exhaustive cryptanalysis of the NBS data encryption standard[J]. Computer, 1977,10(6): 74-84.
[13]	DEMIRCI H , SEL?UK A A ,, . A meet-in-the-middle attack on 8-round AES[C]// International Workshop on Fast Software Encryption. Berlin:Springer, 2008: 116-126
[14]	GILBERT H , MINIER M . A collisions attack on the 7-rounds Rijndael[C]// AES Candidate Conference. Berlin:Springer, 2000: 1-11.
[15]	DUNKELMAN O , KELLER N , SHAMIR A . Improved single-key attacks on 8-round AES-192 and AES-256[C]// Advances in Cryptology - ASIACRYPT 2010. Berlin:Springer, 2010: 158-176.
[16]	DERBEZ P , FOUQUE P A , JEAN J . Improved key recovery attacks on reduced-round AES in the single-key setting[C]// Advances in Cryptology – EUROCRYPT 2013. Berlin:Springer, 2013: 371-387.
[17]	LI L B , JIA K T , WANG X Y . Improved single-key attacks on 9-round AES-192/256[C]// International Workshop on Fast Software Encryption. Berlin:Springer, 2015: 127-146.
[18]	DONG X Y , LI L B , JIA K T ,et al. Improved attacks on reduced-round camellia-128/192/256[C]// Lecture Notes in Computer Science. Berlin:Springer, 2015: 59-83.
[19]	LIN L , WU W L , ZHENG Y F . Improved meet-in-the-middle distinguisher on Feistel schemes[C]// International Conference on Selected Areas in Cryptography. Berlin:Springer, 2015: 122-142.
[20]	BIRYUKOV A , DERBEZ P , PERRIN L . Differential analysis and meet-in-the-middle attack against round-reduced TWINE[C]// International Workshop on Fast Software Encryption. Berlin:Springer, 2016: 3-27.
[21]	DERBEZ P , PERRIN L . Meet-in-the-middle attacks and structural analysis of round-reduced PRINCE[C]// International Workshop on Fast Software Encryption. Berlin:Springer, 2015: 190-216.
[22]	DERBEZ P , FOUQUE P A . Automatic search of meet-in-the-middle and impossible differential attacks[C]// Advances in Cryptology –CRYPTO 2016. Berlin:Springer, 2016: 157-184.
[23]	BIHAM E , SHAMIR A . Differential cryptanalysis of DES-like cryptosystems[J]. Journal of Cryptology, 1991,4(1): 3-72.
[24]	KANDA M , . Practical security evaluation against differential and linear cryptanalyses for Feistel ciphers with SPN round function[C]// Selected Areas in Cryptography. Berlin:Springer, 2001: 168-179.
[25]	LI R J , JIN C H . Meet-in-the-middle attacks on 10-round AES-256[J]. Designs,Codes and Cryptography, 2016,80(3): 459-471.

文献	攻击方法	轮数	时间复杂度	存储复杂度	数据复杂度
文献[8]	中间相遇攻击	8	2¹¹⁶	2⁸⁶	2¹¹⁶
文献[11]	中间相遇攻击	8	2^112.8	2^92.91	2¹⁰⁹
本文	中间相遇攻击	8	2¹¹⁴	2⁶³	2¹⁰⁸

改进的减轮Kiasu-BC算法的中间相遇攻击

Improved meet-in-the-middle attack on reduced-round Kiasu-BC algorithm

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献 25

相关文章 12

Metrics

推荐阅读 0

[1]	邹剑,董乐. 对缩减轮数SM3散列函数改进的原像与伪碰撞攻击[J]. 通信学报, 2018, 39(1): 46-55.
[2]	李荣佳,金晨辉. FOX算法的中间相遇攻击[J]. 通信学报, 2016, 37(8): 185-190.
[3]	任炯炯,陈少真. 11轮3D密码算法的中间相遇攻击[J]. 通信学报, 2015, 36(8): 182-191.
[4]	李曼曼,陈少真. 对ARIA算法中间相遇攻击的改进[J]. 通信学报, 2015, 36(3): 89-94.
[5]	郑雅菲,卫宏儒. 分组密码TWIS的三子集中间相遇攻击[J]. 通信学报, 2014, 35(6): 180-184.
[6]	郑雅菲，卫宏儒. 分组密码TWIS的三子集中间相遇攻击[J]. 通信学报, 2014, 35(6): 23-184.
[7]	王高丽1,2，申延召1. 带消息填充的29步SM3算法原根和伪碰撞攻击[J]. 通信学报, 2014, 35(2): 6-45.
[8]	王高丽,申延召. 带消息填充的29步SM3算法原根和伪碰撞攻击[J]. 通信学报, 2014, 35(2): 40-45.
[9]	邹剑1,2，吴文玲1，吴双1，董乐1,2. 对缩减轮数DHA-256的原像与伪碰撞攻击[J]. 通信学报, 2013, 34(6): 2-15.
[10]	邹剑,吴文玲,吴双,董乐. 对缩减轮数DHA-256的原像与伪碰撞攻击[J]. 通信学报, 2013, 34(6): 8-15.
[11]	董晓丽,胡予濮,陈杰,李顺波,杨旸. 改进的7轮AES-192和8轮AES-256的中间相遇攻击[J]. 通信学报, 2010, 31(9A): 197-201.
[12]	温凤桐. 基于MISTY结构的可调分组密码的设计与分析[J]. 通信学报, 2010, 31(7): 76-80.