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

doi:10.11772/j.issn.1001-9081.2021071340

Journal of Computer Applications ›› 2022, Vol. 42 ›› Issue (9): 2742-2749.DOI: 10.11772/j.issn.1001-9081.2021071340

Special Issue: 网络空间安全

• Cyber security • Previous Articles Next Articles

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)

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

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

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

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

Abstract

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

摘要：

针对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算法, 差分特征, 差分表, 轮函数, 密钥恢复

CLC Number:

TP309.7

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.

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

Figures/Tables 8

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¹²³选择明文

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¹²³选择明文

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

Fig.2 Six-round differential characteristics

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

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

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

Fig.4 Twelve-round differential characteristics

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

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

References 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]	Yanjun LI, Xiaoyu JING, Huiqin XIE, Yong XIANG. Security analysis of PFP algorithm under quantum computing model [J]. Journal of Computer Applications, 2024, 44(4): 1166-1171.
[2]	Yong XIANG, Yanjun LI, Dingyun HUANG, Yu CHEN, Huiqin XIE. Differential and linear characteristic analysis of full-round Shadow algorithm [J]. Journal of Computer Applications, 2024, 44(12): 3839-3843.
[3]	Guangfu WU, Ziheng DAI. Cascaded quasi-cyclic moderate-density parity-check code based public key scheme for resisting reaction attack [J]. Journal of Computer Applications, 2021, 41(11): 3274-3280.

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

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 8

References 19

Related Articles 3

Recommended Articles

Metrics