Linear Forgery Attacks on the Authenticated Encryption Cipher ACORN-like

LI Yunqiang; CUI Ting

doi:10.23919/cje.2023.00.016

Article Contents

Article Navigation > Chinese Journal of Electronics > 2025 > Uncorrected proof

Yunqiang LI and Ting CUI, “Linear Forgery Attacks on the Authenticated Encryption Cipher ACORN-like,” Chinese Journal of Electronics, vol. 34, no. 1, pp. 1–9, 2025 doi: 10.23919/cje.2023.00.016

Citation:

Yunqiang LI and Ting CUI, “Linear Forgery Attacks on the Authenticated Encryption Cipher ACORN-like,” Chinese Journal of Electronics, vol. 34, no. 1, pp. 1–9, 2025 doi: 10.23919/cje.2023.00.016

Yunqiang LI and Ting CUI, “Linear Forgery Attacks on the Authenticated Encryption Cipher ACORN-like,” Chinese Journal of Electronics, vol. 34, no. 1, pp. 1–9, 2025 doi: 10.23919/cje.2023.00.016

Citation:

PDF( 4878 KB)

Linear Forgery Attacks on the Authenticated Encryption Cipher ACORN-like

doi: 10.23919/cje.2023.00.016

LI Yunqiang^,,
CUI Ting

1.
PLA SSF Information Engineering University, Zhengzhou 450004, China

More Information

Author Bio:
Yunqiang LI was born in 1968. He received the Ph.D. degree in 2004 and is currently a Professor at the PLA SSF Information Engineering University, Zhengzhou, China. His research interests include design and analysis of cryptographic algorithm. (Email: lyq203@126.com)

Ting CUI was born in 1985. He received the Ph.D. degree in 2013 and is currently a Professor at the PLA SSF Information Engineering University, Zhengzhou, China. His research interests include block cipher design and cryptanalysis. (Email: cuiting_1209@126.com)
Corresponding author: Email: lyq203@126.com
Received Date: 2023-01-12
Accepted Date: 2024-03-22

Available Online: 2024-04-29

Abstract

Abstract

The authenticated encryption stream cipher ACORN is one of the finalists of the Competition for Authenticated Encryption: Security, Applicability, and Robustness (CAESAR) and is intended for lightweight applications. Because of structural weaknesses in the state update function of ACORN, we can introduce a linear function to analyze conditions and differential trails of the state collision and present a linear method to construct forgery messages under the condition that the key and initialization vector are known or the register state at a certain time is known. The attack method is suitable for three versions of ACORN and may be also extended to any ACORN-like, of which the linear feedback shift register (LFSR) can be replaced by other LFSRs and the feedback function can be replaced by other nonlinear functions. For continuous $ l\ (l > 293) $ bits of new input data, we can construct $2^{l-294}$ forgery messages for any given message of ACORN. Using a standard PC, a concrete forgery message can be constructed almost instantly and the required CPU time and memory are equivalent to the required resources for solving a system of 293 linear equations over the binary field. These attacks in this paper make that the sender and receiver may easily cheat each other, which is not a desirable property for an ideal cipher and casts some doubt on the necessary authentication security requirements of ACORN.
- CAESAR,
- ACORN,
- Authenticated encryption,
- Collision attack,
- Forgery attack,
- State collision differential trail

FullText(HTML)

References(25)

References

[1]	CAESAR, “Competition for authenticated encryption: Security, applicability, and robustness,” Available at: http://competitions.cr.yp.to/index.html, 2013.
[2]	F. Zhang, Z. Y. Liang, B. L. Yang, et al., “Survey of design and security evaluation of authenticated encryption algorithms in the CAESAR competition,” Frontiers of Information Technology & Electronic Engineering, vol. 19, no. 12, pp. 1475–1499, 2018. doi: 10.1631/FITEE.1800576
[3]	H. J. Wu, “ACORN: A lightweight authenticated cipher (v1),” Available at: https://competitions.cr.yp.to/round1/acornv1.pdf, 2014-03-15.
[4]	H. J. Wu, “ACORN: A lightweight authenticated cipher (v2),” Available at: https://competitions.cr.yp.to/round2/acornv2.pdf, 2015-08-29.
[5]	H. J. Wu, “ACORN: A lightweight authenticated cipher (v3),” Available at: https://competitions.cr.yp.to/round3/acornv3.pdf, 2016-09-15.
[6]	M. C. Liu and D. D. Lin, “Cryptanalysis of lightweight authenticated cipher ACORN,” Posed on the Crypto-Competition Mailing List, 2014.
[7]	A. A. Siddhanti, S. Maitra, and N. Sinha, “Certain observations on ACORN v3 and the implications to TMDTO attacks,” in 7th International Conference on Security, Privacy, and Applied Cryptography Engineering, Cham, Switzerland, pp. 264–280, 2017.
[8]	M. I. Salam, K. K. H. Wong, H. Bartlett, et al., “Finding state collisions in the authenticated encryption stream cipher ACORN,” in Proceedings of the Australasian Computer Science Week Multiconference, New York, NY, USA, article no. 36, 2016.
[9]	F. Lafitte, L. Lerman, O. Markowitch, et al., “SAT-based cryptanalysis of ACORN,” Cryptology ePrint Archive, Report 2016/521, 2016.
[10]	Y. Todo, T. Isobe, Y. L. Hao, et al., “Cube attacks on non-blackbox polynomials based on division property,” IEEE Transactions on Computers, vol. 67, no. 12, pp. 1720–1736, 2018. doi: 10.1109/TC.2018.2835480
[11]	V. A. Ghafari and H. G. Hu, “A new chosen IV statistical distinguishing framework to attack symmetric ciphers, and its application to ACORN-v3 and Grain-128a,” Journal of Ambient Intelligence and Humanized Computing, vol. 10, no. 6, pp. 2393–2400, 2019. doi: 10.1007/s12652-018-0897-x
[12]	J. C. Yang, M. C. Liu, and D. D. Lin, “Cube cryptanalysis of round-reduced ACORN,” in Information Security, Z. Q. Lin, C. Papamanthou, and M. Polychronakis, Eds. Springer, Cham, Switzerland, pp. 44–64, 2019.
[13]	C. Chaigneau, T. Fuhr, and H. Gilbert, “Full key-recovery on acorn in nonce-reuse and decryption-misuse settings,” Available at: https://groups.google.com/forum/#!topic/crypto-competitions/RTtZvFZay7k, 2015-08-10.
[14]	S. P. Wang, B. Hu, Y. Liu, et al., “Nonce-reuse attack on authenticated cipher ACORN,” in 2016 International Conference on Artificial Intelligence and Computer Science, Lancaster, UK, pp. 379–385, 2016.
[15]	X. J. Zhang and D. D. Lin, “Cryptanalysis of ACORN in nonce-reuse setting,” in 13th International Conference on Information Security and Cryptology, Xi’an, China, pp. 342–361, 2017.
[16]	G. S. Zhang, X. Chen, D. D. Lin, et al., “State recovery attack on ACORN v3 in nonce-reuse setting,” Journal on communications, vol. 41, no. 8, pp. 11–21, 2020. doi: 10.11959/j.issn.1000-436x.2020164
[17]	P. Dey, R. S. Rohit, and A. Adhikari, “Full key recovery of ACORN with a single fault,” Journal of Information Security and Applications, vol. 29, pp. 57–64, 2016. doi: 10.1016/j.jisa.2016.03.003
[18]	E. Dubrova, “Breaking ACORN with a single fault,” Cryptology ePrint Archive, Report 2019/697, 2019.
[19]	K. N. Ambili and J. Jose, “Inapplicability of differential fault attacks against cellular automata based lightweight authenticated cipher,” Cryptology ePrint Archive, Report 2022/042, 2022.
[20]	L. R. Knudsen and V. Rijmen, “Known-key distinguishers for some block ciphers,” in Advances in Cryptology-ASIACRYPT 2007, K. Kurosawa, Ed. Springer, Berlin Heidelberg, Germany, pp. 315–324, 2007.
[21]	C. Blondeau, T. Peyrin, and L. Wang, “Known-key distinguisher on full PRESENT,” in Advances in Cryptology-CRYPTO 2015, R. Gennaro and M. Robshaw, Eds. Springer, Berlin Heidelberg, Germany, pp. 455–474, 2015.
[22]	M. Eichlseder, L. Grassi, R. Lüftenegger, et al., “An algebraic attack on ciphers with low-degree round functions: Application to full MiMC,” in Advances in Cryptology-ASIACRYPT 2020, S. Moriai and H. X. Wang, Eds. Springer, Cham, Switzerland, pp. 477–506, 2020.
[23]	B. Mennink and B. Preneel, “On the impact of known-key attacks on hash functions,” in Advances in Cryptology-ASIACRYPT 2015, T. Iwata and J. H. Cheon, Eds. Springer, Berlin Heidelberg, Germany, pp. 59–84, 2015.
[24]	S. B. Wu, H. J. Wu, T. Huang, et al., “Leaked-state-forgery attack against the authenticated encryption algorithm ALE,” in Advances in Cryptology-ASIACRYPT 2013, K. Sako and P. Sarkar, Eds. Springer Heidelberg, Germany, pp. 377–404, 2013.
[25]	J. S. Mao, D. G. Mu, and X. J. Lai, “A forgery attack on leaked-state authenticated encryption,” in Proceedings of the 2015 International Conference on Electronic Science and Automation Control, Paris, France, pp. 128–131, 2015.