基于差分表的Blow-CAST-Fish算法的密钥恢复攻击

doi:10.11772/j.issn.1001-9081.2021071340

《计算机应用》唯一官方网站 ›› 2022, Vol. 42 ›› Issue (9): 2742-2749.DOI: 10.11772/j.issn.1001-9081.2021071340

所属专题：网络空间安全

基于差分表的Blow-CAST-Fish算法的密钥恢复攻击

孙晓玲(), 李姗姗, 杨光, 杨秋格

防灾科技学院信息工程学院，河北三河 065201

收稿日期:2021-07-27 修回日期:2021-09-27 接受日期:2021-10-13 发布日期:2021-11-01 出版日期:2022-09-10
通讯作者: 孙晓玲
作者简介:李姗姗（1981—），女，河南洛阳人，副教授，博士，主要研究方向：大规模地球科学计算；
杨光（1985—），女，吉林洮南人，副教授，博士，主要研究方向：数据分析、图像处理；
杨秋格（1981—），女，山东聊城人，讲师，硕士，主要研究方向：数据分析。
基金资助:
国家自然科学基金资助项目(42007422);中央高校基本科研业务费专项(ZY20215152);廊坊市科技局科学研究与发展计划项目(2020011024)

Blow-CAST-Fish key recovery attack based on differential tables

Xiaoling SUN(), Shanshan LI, Guang YANG, Qiuge YANG

School of Information Engineering，Institute of Disaster Prevention，Sanhe Hebei 065201，China

Received:2021-07-27 Revised:2021-09-27 Accepted:2021-10-13 Online:2021-11-01 Published:2022-09-10
Contact: Xiaoling SUN
About author:LI Shanshan， born in 1981， Ph. D.， associate professor. Her research interests include large-scale geoscience computing.
YANG Guang， born in 1985， Ph. D.， associate professor. Her research interests include data analysis， image processing.
YANG Qiuge， born in 1981， M. S.， lecturer. Her research interests include data analysis.
Supported by:
National Natural Science Foundation of China(42007422);Fundamental Research Funds for Central Universities(ZY20215152);Scientific Research and Development Program of Langfang Science and Technology Bureau(2020011024)

摘要/Abstract

摘要：

针对Blow-CAST-Fish算法攻击轮数有限和复杂度高等问题，提出一种基于差分表的Blow-CAST-Fish算法的密钥恢复攻击。首先，对S盒的碰撞性进行分析，分别基于两个S盒和单个S盒的碰撞，构造6轮和12轮差分特征；然后，计算轮函数f₃的差分表，并在特定差分特征的基础上扩充3轮，从而确定密文差分与f₃的输入、输出差分的关系；最后，选取符合条件的明文进行加密，根据密文差分计算f₃的输入、输出差分值，并查寻差分表找到对应的输入、输出对，从而获取子密钥。在两个S盒碰撞的情况下，所提攻击实现了9轮Blow-CAST-Fish算法的差分攻击，比对比攻击多1轮，时间复杂度由2^107.9降低到2⁷⁴；而在单个S盒碰撞的情况下，所提攻击实现了15轮Blow-CAST-Fish算法的差分攻击，与对比攻击相比，虽然攻击轮数减少了1轮，但弱密钥比例由 $2 - 52.4$ 提高到 $2 - 42$ ，数据复杂度由2⁵⁴降低到2⁴⁷。测试结果表明，在相同差分特征基础上，基于差分表的攻击的攻击效率更高。

关键词: Blow-CAST-Fish算法, 差分特征, 差分表, 轮函数, 密钥恢复

Abstract:

Aiming at the problems of limited attack rounds and high attack complexity of Blow-CAST-Fish （Blow-C.Adams S.Tavares-Fish） algorithm， a key recovery attack of Blow-CAST-Fish algorithm based on differential table was proposed. Firstly， after analyzing the collision of S-box， based on the collision of two S-boxes and a single S-box respectively， the 6-round and 12-round differential characteristics were constructed. Secondly， the differential tables of f₃ were calculated， and three rounds were expanded based on the specific differential characteristic， thereby determining the relationship between ciphertext difference and the input and output differences of f₃. Finally， the plaintexts meeting the conditions were selected to encrypt， the input and output differences of f₃were calculated according to the ciphertext difference， and the corresponding input and output pairs were found by querying the differential table， as a result， the subkeys were obtained. At the situation of two S-boxes collision， the proposed attack completed a differential attack of 9-round Blow-CAST-Fish algorithm， compared with the comparison attack， the number of attack rounds was increased by one， and the time complexity was reduced from 2^107.9 to 2⁷⁴. At the situation of single S-box collision， the proposed attack completed a differential attack of 15-round Blow-CAST-Fish algorithm， compared with the comparison attack， although the number of attack rounds was reduced by one， the proportion of weak keys was increased from $2 - 52.4$ to $2 - 42$ and the data complexity was reduced from 2⁵⁴ to 2⁴⁷. The test results show that the attack based on differential table can increase the efficiency of attack based on the same differential characteristics.

Key words: Blow-CAST-Fish (Blow-C.Adams S.Tavares-Fish) algorithm, differential characteristic, differential table, round function, key recovery

中图分类号:

TP309.7

孙晓玲, 李姗姗, 杨光, 杨秋格. 基于差分表的Blow-CAST-Fish算法的密钥恢复攻击[J]. 计算机应用, 2022, 42(9): 2742-2749.

Xiaoling SUN, Shanshan LI, Guang YANG, Qiuge YANG. Blow-CAST-Fish key recovery attack based on differential tables[J]. Journal of Computer Applications, 2022, 42(9): 2742-2749.

图/表 8

表1 CAST类算法攻击方案对比

Tab. 1 Comparison of attack schemes for CAST algorithms

算法	方案	攻击轮数	差分特征概率	弱密钥比例	时间复杂度	数据复杂度
Blow-CAST-Fish	文献［6］方案	8	$2 - 61$	$2 - 12$	2^107.9	2⁶⁴选择明文
	文献［7］方案	16	$2 - 49$	$2 - 52.4$	2⁶⁰	2⁵⁴选择明文
	本文方案	9	$2 - 61$	$2 - 12$	2⁷⁴	2⁶⁴选择明文
	本文方案	15	$2 - 42$	$2 - 42$	2^66.1	2⁴⁷选择明文
CAST-128	文献［5］方案	9	$2 - 53$	$2 - 23.8$	2^101.8	2⁵⁸选择明文
CAST-128	文献［8］方案	9	$2 - 53$	$2 - 23.8$	2⁷³	2⁵⁸选择明文
CAST-256	文献［9］方案	36	$2 - 120$	$2 - 35$	2⁹⁵	2¹²³选择明文
CAST-256	文献［8］方案	40	$2 - 120$	$2 - 35$	2²¹⁷	2¹²³选择明文

表1 CAST类算法攻击方案对比

Tab. 1 Comparison of attack schemes for CAST algorithms

算法	方案	攻击轮数	差分特征概率	弱密钥比例	时间复杂度	数据复杂度
Blow-CAST-Fish	文献［6］方案	8	$2 - 61$	$2 - 12$	2^107.9	2⁶⁴选择明文
	文献［7］方案	16	$2 - 49$	$2 - 52.4$	2⁶⁰	2⁵⁴选择明文
	本文方案	9	$2 - 61$	$2 - 12$	2⁷⁴	2⁶⁴选择明文
	本文方案	15	$2 - 42$	$2 - 42$	2^66.1	2⁴⁷选择明文
CAST-128	文献［5］方案	9	$2 - 53$	$2 - 23.8$	2^101.8	2⁵⁸选择明文
CAST-128	文献［8］方案	9	$2 - 53$	$2 - 23.8$	2⁷³	2⁵⁸选择明文
CAST-256	文献［9］方案	36	$2 - 120$	$2 - 35$	2⁹⁵	2¹²³选择明文
CAST-256	文献［8］方案	40	$2 - 120$	$2 - 35$	2²¹⁷	2¹²³选择明文

图1 Blow-CAST-Fish算法的加密流程

Fig.1 Encryption flow of Blow-CAST-Fish algorithm

图2 6轮差分特征

Fig.2 Six-round differential characteristics

表2 S1-S2碰撞情况示例

Tab. 2 Examples of S1-S2 collision

初始密钥	I_a	I_b	$I a'$	$I b'$	$S 1 [I a] - S 2 [I b]$
95656948035942784	af _x	92 _x	b0 _x	9e _x	cce905b3 _x
602941517916109562	4f _x	4b _x	b1 _x	98 _x	34de6716 _x
1997665281530169090	3e _x	ee _x	47 _x	f2 _x	b62ea113 _x
2743494785645034369	03 _x	53 _x	9f _x	ce _x	eb5046bc _x
23088328012032389153	56 _x	0f _x	c4 _x	a3 _x	dbde33db _x

表2 S1-S2碰撞情况示例

Tab. 2 Examples of S1-S2 collision

初始密钥	I_a	I_b	$I a'$	$I b'$	$S 1 [I a] - S 2 [I b]$
95656948035942784	af _x	92 _x	b0 _x	9e _x	cce905b3 _x
602941517916109562	4f _x	4b _x	b1 _x	98 _x	34de6716 _x
1997665281530169090	3e _x	ee _x	47 _x	f2 _x	b62ea113 _x
2743494785645034369	03 _x	53 _x	9f _x	ce _x	eb5046bc _x
23088328012032389153	56 _x	0f _x	c4 _x	a3 _x	dbde33db _x

图3 9轮Blow-CAST-Fish算法的差分攻击过程

Fig.3 Flow of differential attack of 9-round Blow-CAST-Fish algorithm

图4 十二轮差分特征

Fig.4 Twelve-round differential characteristics

表3 S1碰撞情况示例

Tab. 3 Examples of S1 collision

初始密钥	I_a	I_a '	S₁［I_a ］=S₁［I_a '］
10153051852039760926	a5 _x	ae _x	9c86ab4 _x
36617852633644692586	31 _x	a0 _x	8aabb39d _x
15257399593555034979	2d _x	88 _x	5fc73b3a _x
400417395294535793	38 _x	b0 _x	11975b50 _x

图5 15轮Blow-CAST-Fish算法的差分攻击过程

Fig.5 Flow of differential attack of 15-round Blow-CAST-Fish algorithm

参考文献 19

1	KRISHNAMURTHY G N， RAMASWAMY V， LEELA G H， et al. Blow-CAST-Fish： a new 64-bit block cipher［J］. International Journal of Computer Science and Network Security， 2008， 8（4）：282-290.
2	SCHNEIER B. Description of a new variable-length key， 64-bit block cipher （Blowfish）［C］// Proceedings of the 1993 International Conference on Fast Software Encryption， LNCS 809. Berlin： Springer， 1994：191-204.
3	ADAMS C. RFC 2144： the CAST-128 encryption algorithm［EB/OL］. ［2021-03-21］..
4	VAUDENAY S. On the weak keys of Blowfish［C］// Proceedings of the 1996 International Conference on Fast Software Encryption， LNCS 1039. Berlin： Springer， 1996： 27-32.
5	WANG M Q， WANG X Y， CHOW K P， et al. New differential cryptanalysis results for reduced round CAST-128［J］. IEICE Transactions on Fundamentals of Electronics， Communications and Computer Sciences， 2010， E93-A（12）：2744-2754. 10.1587/transfun.e93.a.2744
6	孙晓玲，王美琴，李忠，等. 低轮Blow-CAST-Fish算法的差分攻击［J］. 计算机工程， 2012， 38（12）：99-101. 10.3969/j.issn.1000-3428.2012.12.029
	SUN X L， WANG M Q， LI Z， et al. Differential attack on reduced-round Blow-CAST-Fish algorithm［J］. Computer Engineering， 2012， 38（12）：99-101. 10.3969/j.issn.1000-3428.2012.12.029
7	孙晓玲，王美琴，孙旭光，等. 16轮Blow-CAST-Fish的弱密钥攻击［J］. 计算机工程与应用， 2011，47（35）：110-112. 10.3778/j.issn.1002-8331.2011.35.031
	SUN X L， WANG M Q， SUN X G， et al. Weak-key attack on 16-round Blow-CAST-Fish［J］. Computer Engineering and Applications， 2011， 47（35）： 110-112. 10.3778/j.issn.1002-8331.2011.35.031
8	WANG S M， CUI T T， WANG M Q. Improved differential cryptanalysis of CAST-128 and CAST-256［C］// Proceedings of the 2016 International Conference on Information Security and Cryptology， LNCS 10143. Cham： Springer， 2017：18-32.
9	SEKI H， KANEKO T. Differential cryptanalysis of CAST-256 reduced to nine quad-rounds［J］. IEICE Transactions on Fundamentals of Electronics， Communications and Computer Sciences， 2001， E84-A（4）：913-918. 10.1007/3-540-44983-3_23
10	CUI T T， CHEN H F， WEN L， et al. Statistical integral attack on CAST-256 and IDEA［J］. Cryptography and Communication， 2018， 10（1）： 195-209. 10.1007/s12095-017-0245-6
11	郑向前，张文英，肖祯，等. 缩减轮数的CAST-256积分分析［J］. 计算机应用研究， 2017， 34（1）： 221-223. 10.3969/j.issn.1001-3695.2017.01.050
	ZHENG X Q， ZHANG W Y， XIAO Z， et al. Integral cryptanalytic on reduced-round of CAST-256［J］. Application Research of Computers， 2017， 34（1）： 221-223. 10.3969/j.issn.1001-3695.2017.01.050
12	倪博煜，董晓阳. 改进的Type-1型广义Feistel结构的量子攻击及其在分组密码CAST-256上的应用［J］. 电子与信息学报， 2020， 42（2）： 295-306. 10.11999/JEIT190633
	NI B Y， DONG X Y. Improved quantum attack on Type-1 generalized Feistel scheme and its application to CAST-256［J］. Journal of Electronics and Information Technology， 2020， 42（2）： 295-306. 10.11999/JEIT190633
13	WANG M Q， CUI T T， CHEN H F， et al. Integrals go statistical： cryptanalysis of full skipjack variants［C］// Proceedings of the 2016 International Conference on Fast Software Encryption， LNCS 9783. Berlin： Springer， 2016： 399-415.
14	ZONG R， DONG X Y， WANG X Y. Related-tweakey impossible differential attack on reduced-round Deoxys-BC-256［J］. SCIENCE CHINA Information Sciences， 2019， 62（3）： No.32102. 10.1007/s11432-017-9382-2
15	GUO H， SUN S W， SHI D P， et al. Differential attacks on CRAFT exploiting the involutory S-boxes and tweak additions［J］. IACR Transactions on Symmetric Cryptology， 2020， 2020（3）：119-151. 10.46586/tosc.v2020.i3.119-151
16	ITO G， HOSOYAMADA A， MATSUMOTO R， et al. Quantum chosen-ciphertext attacks against Feistel ciphers［C］// Proceedings of the 2019 Cryptographers’ Track at the RSA Conference， LNCS 11405. Cham： Springer， 2019： 391-411.
17	HOSOYAMADA A， SASAKI Y. Quantum Demiric-Selçuk meet-in-the-middle attacks： applications to 6-round generic Feistel constructions［C］// Proceedings of the 2018 International Conference on Security and Cryptography for Networks， LNCS 11035. Cham： Springer， 2018：386-403.
18	DONG X Y， WANG X Y. Quantum key recovery attack on Feistel structures［J］. Science China Information Sciences， 2018， 61（10）： No.102501. 10.1007/s11432-017-9468-y
19	DONG X Y， LI Z， WANG X Y. Quantum cryptanalysis on some generalized Feistel schemes［J］. SCIENCE CHINA Information Sciences， 2019， 62（2）： No.22501. 10.1007/s11432-017-9436-7

[1]	李艳俊, 景小宇, 谢惠琴, 项勇. 量子计算模型下PFP算法的安全性分析[J]. 《计算机应用》唯一官方网站, 2024, 44(4): 1166-1171.
[2]	项勇, 李艳俊, 黄丁韫, 陈愚, 谢惠琴. 全轮Shadow算法的差分和线性特征分析[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3839-3843.
[3]	巫光福, 戴子恒. 应对反应攻击的级联中密度准循环奇偶校验码公钥方案[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3274-3280.
[4]	付荣. 基于智能卡实现的分组加密算法的功耗分析[J]. 计算机应用, 2015, 35(9): 2546-2552.
[5]	周拥军尹忠海高大化. 一种抗缩放攻击的盲检测数字水印方案[J]. 计算机应用, 2010, 30(05): 1233-1235.

基于差分表的Blow-CAST-Fish算法的密钥恢复攻击

Blow-CAST-Fish key recovery attack based on differential tables

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 19

相关文章 5

编辑推荐

Metrics