倪博煜^{1, 2},
董晓阳^3,,
1.山东大学密码技术与信息安全教育部重点实验室 济南 250100
2.山东大学网络空间安全学院 青岛 266237
3.清华大学高等研究院 北京 100084
基金项目:国家重点研发计划(2017YFA0303903)，国家自然科学基金(61902207)，国家密码发展基金(MMJJ20180101, MMJJ20170121)

详细信息

作者简介:董晓阳：男，1988年生，助理研究员。研究方向为对称密码算法的安全性分析与设计

通讯作者:董晓阳　xiaoyangdong@tsinghua.edu.cn

中图分类号:TN918; TP309

计量

文章访问数:1703
HTML全文浏览量:456
PDF下载量:83
被引次数:0

出版历程

收稿日期:2019-08-26
修回日期:2019-11-26
网络出版日期:2019-11-29
刊出日期:2020-02-19

Improved Quantum Attack on Type-1 Generalized Feistel Schemes and Its Application to CAST-256

Boyu NI^{1, 2},
Xiaoyang DONG^3,,
1. Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan 250100, China
2. School of Cyber Science and Technology, Shandong University, Qingdao 266237, China
3. Institute for Advanced Study, Tsinghua University, Beijing 100084, China
Funds:The National Key Research and Development Program of China (2017YFA0303903), The National Natural Science Foundation of China (61902207), The National Cryptography Development Fund (MMJJ20180101, MMJJ20170121)


摘要
摘要:广义Feistel结构(GFS)是设计对称密码算法的重要基础结构之一，其在经典计算环境中受到了广泛的研究。但是，量子计算环境下对GFS的安全性评估还相当稀少。该文在量子选择明文攻击(qCPA)条件下和量子选择密文攻击(qCCA)条件下，分别对Type-1 GFS进行研究，给出了改进的多项式时间量子区分器。在qCPA条件下，给出了3d – 3轮的多项式时间量子区分攻击，其中$d(d \ge 3)$是Type-1 GFS的分支数，攻击轮数较之前最优结果增加$d - 2$轮。得到更好的量子密钥恢复攻击，即相同轮数下攻击的时间复杂度降低了${2^{(d - 2)n/2}}$。在qCCA条件下，对于Type-1 GFS给出了$3d - 2$轮的多项式时间量子区分攻击，比之前最优结果增加了$d - 1$轮。该文将上述区分攻击应用到CAST-256分组密码中，得到了12轮qCPA多项式时间量子区分器，以及13轮qCCA多项式时间量子区分器，该文给出19轮CAST-256的量子密钥恢复攻击。
关键词:分组密码/
广义Feistel结构/
量子攻击/
CAST-256加密算法
Abstract:Generalized Feistel Schemes (GFS) are important components of symmetric ciphers, which have been extensively researched in classical setting. However, the security evaluations of GFS in quantum setting are rather scanty. In this paper, more improved polynomial-time quantum distinguishers are presented on Type-1 GFS in quantum Chosen-Plaintext Attack (qCPA) setting and quantum Chosen-Ciphertext Attack (qCCA) setting. In qCPA setting, new quantum polynomial-time distinguishers are proposed on $3d - 3$ round Type-1 GFS with branches $d \ge 3$, which gain $d - 2$ more rounds than the previous distinguishers. Hence, key- recovery attacks can be obtained, whose time complexities gain a factor of ${2^{\frac{{\left( {d - 2} \right)n}}{2}}}$. In qCCA setting, $3d - 3$ round quantum distinguishers can be obtained on Type-1 GFS, which gain $d-1$ more rounds than the previous distinguishers. In addition, given some quantum attacks on CAST-256 block cipher. 12-round and 13-round polynomial-time quantum distinguishers are obtained in qCPA and qCCA settings, respectively. Hence, the quantum key-recovery attack on 19-round CAST-256 is derived.
Key words:Block cipher/
Generalized Feistel Scheme (GFS)/
Quantum attack/
CAST-256 cipher algorithm



PDF全文下载地址:

https://jeit.ac.cn/article/exportPdf?id=796cfb4c-7275-415e-bef9-92e7ecf44588