基于Nonce重用的ACORN v3状态恢复攻击

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

Abstract

Abstract:

Based on differential-algebraic method and guess-and-determine technique,the state recovery attack of ACORN v3 was presented when one pair of key and Nonce was used to encrypt two messages.The time complexity of the attack was 2^122.5c,where c was the time complexity of solving linear equations.The data complexity and the storage complexity were negligible.Furthermore,according to the analysis on the sense of multiple nonce reuse,it is found that relatively complicated filter function of ACORN v3 makes it infeasible to extract the linear equations about the internal state directly from key streams.Thus,the risk of significantly reducing the attack complexity by increasing the times of nonce reuse can be effectively avoided.

Key words: authenticated cipher, cryptanalysis, ACORN, state recovery attack

CLC Number:

TN918.1

Guoshuang ZHANG,Xiao CHEN,Dongdai LIN,Fengmei LIU. State recovery attack on ACORN v3 in nonce-reuse setting[J]. Journal on Communications, 2020, 41(8): 11-21.

Figures/Tables 7

符号	解释
S^t	t时刻内部状态
$s_{i}^{t}$	t时刻内部状态 $S^{t}$ 的第i个比特
k_t	t时刻生成的密钥比特
f_t	t时刻生成的更新比特
m_t	t时刻输入比特
$K$	128 bit算法密钥
$N$	128 bit Nonce
AD	关联数据
P	明文
p_t	明文P的第t个比特
$Δ S^{t}$	t时刻的内部状态差分
$Δ s_{i}^{t}$	t时刻内部状态第i个比特的差分
Δk_t	第t个密钥流比特的差分

References 19

[1]	WU H J . ACORN:a lightweight authenticated cipher (v1)[R]. CAESAR First Round Submission, 2014.
[2]	WU H J . ACORN:a lightweight authenticated cipher (v2)[R]. CAESAR Second Round Submission, 2015.
[3]	WU H J . ACORN:a lightweight authenticated cipher (v3)[R]. Candidate for the CAESAR Competition, 2016.
[4]	LIU M C , LIN D D . Cryptanalysis of lightweight authenticated cipher acorn[R]. Crypto-Competition Mailing List, 2014.
[5]	CHAIGNEAU C , FUHR T , GIBERT H . Full key-recovery on acorn in nonce-reuse and decryption-misuse settings[R]. Crypto-Competition Mailing List, 2015.
[6]	WANG S P , HU B , LIU Y ,et al. Nonce-reuse attack on authenticated cipher ACORN[C]// 2016 International Conference on Artificial Intelligence and Computer Science. Lancaster:DEStech Publication, 2016: 379-385.
[7]	ZHANG X J , LIN D D . Cryptanalysis of ACORN in nonce-reuse setting[C]// 13th International Conference on Information Security and Cryptology. Berlin:Springer, 2017: 342-361.
[8]	SALAM M , BARTLETT H , DAWSON E ,et al. Investigating cube attacks on the authenticated encryption stream cipher acorn[C]// 2016 International Conference on Applications and Techniques in Information Security. Berlin:Springer, 2016: 15-26.
[9]	SALAM M , WONG K , BARTLETT H ,et al. Finding state collisions in the authenticated encryption stream cipher ACORN[C]// 2016 Proceedings of the Australasian Computer Science Week Multiconference. New York:ACM Press, 2016,36: 1-10.
[10]	LAFITTE F , LERMAN L , MARKOWITCH O ,et al. SAT-based cryptanalysis of ACORN[R]. IACR Cryptology ePrint Archive,Report 2016/521, 2016.
[11]	DWIVEDI A D , KLOU?EK M , MORAWIECKI P . SAT-based cryptanalysis of authenticated ciphers from the CAESAR competetion[C]// 2017 The 14th International Conference on Security and Cryptography. Berlin:Springer, 2017: 275-284.
[12]	DIBYENDU R , SOURAV M . Some results on ACORN[R]. IACR Cryptology ePrint Archive,Report 2016/1132, 2016.
[13]	TODO Y , ISOBE T , HAO Y L ,et al. Cube attacks on non-blackbox polynomials based on division property[C]// 2017 37th Annual International Cryptology Conference. Berlin:Springer, 2017: 250-279.
[14]	SIDDHANTI A A , MAITRA S , SINHA N . Certain observations on acorn v3 and the implications to TMDTO attacks[C]// 2017 7th International Conference on Security,Privacy,and Applied Cryptography Engineering. Berlin:Springer, 2017: 264-280.
[15]	GHAFARI V A , HU H G . A new chosen IV statistical distinguishing framework to attack symmetric ciphers,and its application to ACORN-v3 and Grain-128a[J]. Journal of Ambient Intelligence and Humanized Computing, 2019,10: 2393-2400.
[16]	WANG Q J , HAO Y L , TODO Y ,et al. Improved division property based cube attacks exploiting algebraic properties of superpoly[C]// 2018 38th Annual International Cryptology Conference. Berlin:Springer, 2018: 275-305.
[17]	ZHANG F , LIANG Z Y , YANG B L ,et al. Survey of design and security evaluation of authenticated encryption algorithms in the CAESAR competition[J]. Frontiers of Information Technology ＆Electronic Engineering, 2018,19(12): 1475-1499.
[18]	YANG J C , LIU M C , LIN D D . Cube cryptanalysis of round-reduced ACORN[C]// 2019 22nd International Conference on Information Security. Berlin:Springer, 2019: 44-64.
[19]	KESARWANI A , ROY D , SARKAR S ,et al. New cube distinguishers on NFSR-based stream ciphers[J]. Design,Codes and Cryptography, 2020,88: 173-199.

Metrics

Recommended 0

No Suggested Reading articles found!

算法版本	Nonce重用次数	数据复杂度/bit	计算复杂度	文献
ACORN v1	2	164	2^114.6c	文献[4]
ACORN v2	2	2×100	2¹⁹³c	文献[5]
ACORN v2	3	3×142	2¹⁵¹c	文献[5]
ACORN v2	4	4×184	2¹⁰⁹c	文献[5]
ACORN v2	2	2×192	2^126.5c	文献[6]
ACORN v2	3	3×192	2^98.2c	文献[6]
ACORN v2	4	4×192	2^75.8c	文献[6]
ACORN v2	3	3×234	2⁷⁸c	文献[7]
ACORN v3	3	3×234	2^120.6c	文献[7]
ACORN v3	2	2×148+293	2^122.5c	本文
ACORN v3	3	3×98+293	2^118.3c	本文

参数初始化	关联数据处理			加密			认证码生成
m_tK NK ′ K K K K K K K K KKK	AD	10"0	00"0	P	10"0	00"0	00"0
a_t1	1	0	1	0	1
b_t1	1			0			1

Nonce重用次数	数据复杂度/bit	计算复杂度
3	3×98+l	2^118.3c
4	4×147+l	2^113.6c
5	5×196+l	2^109.4c
6	6×245+l	2^105.2c
7	7×294+l	2^101.5c
8	8×343+l	2^101.5c

State recovery attack on ACORN v3 in nonce-reuse setting

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 7

References 19

Related Articles 15

Metrics

Recommended 0

[1]	Xiaoni DU, Xiangyu WANG, Lifang LIANG, Kaibin LI. Quantum cryptanalysis of lightweight block cipher Piccolo [J]. Journal on Communications, 2023, 44(6): 175-182.
[2]	Wei LI, Chun LIU, Dawu GU, Wenqian SUN, Jianning GAO, Mengyang QIN. Statistical ineffective fault analysis of the lightweight authenticated cipher algorithm Saturnin-Short [J]. Journal on Communications, 2023, 44(4): 167-175.
[3]	Zhengbin LIU, Yongqiang LI, Chaoxi ZHU. Fast algorithm to search for the minimum number of active S-boxes of block cipher [J]. Journal on Communications, 2023, 44(1): 118-128.
[4]	Nianping WANG, Qing YIN. Differential security evaluation of Piccolo-like structure [J]. Journal on Communications, 2022, 43(2): 55-64.
[5]	Zhaocun ZHOU, Dengguo FENG. Survey on approaches of stream cipher cryptanalysis [J]. Journal on Communications, 2022, 43(11): 183-198.
[6]	Nianping WANG, Zhicheng GUO. Security evaluation against differential cryptanalysis for dynamic cryptographic structure [J]. Journal on Communications, 2021, 42(8): 70-79.
[7]	Jie CUI,Hai-feng ZUO,Hong ZHONG. Biclique cryptanalysis on lightweight block ciphers I-PRESENT-80 and I-PRESENT-128 [J]. Journal on Communications, 2017, 38(11): 13-23.
[8]	Zhi-yan XU,Li-bing WU,Li LI,De-biao HE. New certificateless aggregate signature scheme with universal designated verifier [J]. Journal on Communications, 2017, 38(11): 76-83.
[9]	Jing HUANG,Xin-jie ZHAO,Fan ZHANG,Shi-ze GUO,Ping ZHOU,Hao CHEN,Jian YANG. Improvement and evaluation for algebraic fault attacks on PRESENT [J]. Journal on Communications, 2016, 37(8): 144-156.
[10]	IRong-jia L,INChen-hui J. Meet-in-the-middle attacks on FOX block cipher [J]. Journal on Communications, 2016, 37(8): 185-190.
[11]	Jian-sheng GUO,Jing-yi CUI,Zhi-shu PAN,Yi-peng LIU. Integral attack on HIGHT block cipher [J]. Journal on Communications, 2016, 37(7): 71-78.
[12]	Meng MA,Ya-qun ZHAO. Research on linear approximations of simplified Trivium [J]. Journal on Communications, 2016, 37(6): 185-191.
[13]	Qing-cong LIU,Ya-qun ZHAO,Meng MA,Feng-mei LIU. Zero correlation-integral attack of MIBS block cipher [J]. Journal on Communications, 2016, 37(11): 189-195.
[14]	Zhi-shu PAN,Jian-sheng GUO,Jin-ke CAO,Wei LUO. Integral attack on MIBS block cipher [J]. Journal on Communications, 2014, 35(7): 157-163.
[15]	. Integral attack on MIBS block cipher [J]. Journal on Communications, 2014, 35(7): 19-163.