New Related-Tweakey Boomerang Attacks and Distinguishers on Deoxys-BC

LIU Jiamei; TAN Lin; XU Hong

doi:10.23919/cje.2022.00.383

Volume 33 Issue 3

May 2024

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2024 > 33(3): 683-693

Jiamei LIU, Lin TAN, and Hong XU, “New Related-Tweakey Boomerang Attacks and Distinguishers on Deoxys-BC,” Chinese Journal of Electronics, vol. 33, no. 3, pp. 683–693, 2024 doi: 10.23919/cje.2022.00.383

Citation:

Jiamei LIU, Lin TAN, and Hong XU, “New Related-Tweakey Boomerang Attacks and Distinguishers on Deoxys-BC,” Chinese Journal of Electronics, vol. 33, no. 3, pp. 683–693, 2024 doi: 10.23919/cje.2022.00.383

Citation:

PDF( 2937 KB)

New Related-Tweakey Boomerang Attacks and Distinguishers on Deoxys-BC

doi: 10.23919/cje.2022.00.383

1.
PLA Strategic Support Force Information Engineering University, Zhengzhou 450001, China

More Information

Author Bio:
Jiamei LIU was born in Anhui Province, China, in 1999. She received the B.E. degree in cryptography from PLA Strategic Support Force Information Engineering University in 2020 and is currently pursuing the M.S. degree in cryptography. Her research field is cryptography. (Email: liujiamei182@163.com)

Lin TAN was born in Hubei Province, China, in 1983. He received the Ph.D. degrees in cryptography from Information Engineering University, Zhengzhou, China, in 2012. His research field is cryptography. (Email: tanlin100@163.com)

Hong XU was born in Hubei Province, China, in 1979. She received the Ph.D. degrees in cryptography from Information Engineering University, Zhengzhou, China, in 2007. Her research field is cryptography. (Email: xuhong0504@163.com)
Corresponding author: Email: tanlin100@163.com
Received Date: 2022-11-09
Accepted Date: 2023-03-22

Available Online: 2023-07-15

Publish Date: 2024-05-05

Abstract

Abstract

Deoxys-BC is the primitive tweakable block cipher of the Deoxys family of authenticated encryption schemes. Based on existing related-tweakey boomerang distinguishers, this paper improves the boomerang attacks on 11-round Deoxys-BC-256 and 13-round Deoxys-BC-384 by the optimized key guessing and the precomputation technique. It transfers a part of subtweakey guess in the key-recovery phase to the precomputation resulting in a significant reduction of the overall time complexity. For 11-round Deoxys-BC-256, we give a related-tweakey boomerang attack with time/data/memory complexities of $2^{218.6}/2^{125.7}/2^{125.7}$, and give another attack with the less time complexity of $2^{215.8}$ and memory complexity of $2^{120}$ when the adversary has access to the full codebook. For 13-round Deoxys-BC-384, we give a related-tweakey boomerang attack with time/data/memory complexities of $2^{k-96}+2^{157.5}/2^{120.4}/2^{113}$. For the key size $k=256$, it reduces the time complexity by a factor of $2^{31}$ compared with the previous 13-round boomerang attack. In addition, we present two new related-tweakey boomerang distinguishers on 11-round Deoxys-BC-384 with the same probability as the best previous distinguisher.
- Block cipher,
- Tweakable block cipher,
- Boomerang attack,
- Related-tweakey

FullText(HTML)

References(30)

References

[1]	“CAESAR: Competition for authenticated encryption: Security, applicability, and robustness, 2014,” Available at: http://competitions.cr.yp.to/caesar.html, 2019-02-20.
[2]	“NIST lightweight cryptography project,” Available at: https://csrc.nist.gov/Projects/Lightweight-Cryptography, 2015.
[3]	M. D. Liskov, R. L. Rivest, and D. A. Wagner, “Tweakable block ciphers,” in Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, Santa Barbara, CA, USA, pp.31–46, 2002.
[4]	J. Jean, I. Nikolić, and T. Peyrin, “Tweaks and keys for block ciphers: The TWEAKEY framework,” in Proceedings of the 20th International Conference on Advances in Cryptology, Kaoshiung, China, pp.274–288, 2014.
[5]	J. Jean, I. Nikolić, T. Peyrin, et al., “The Deoxys AEAD family,” Journal of Cryptology, vol. 34, no. 3, article no. articleno.31, 2021. doi: 10.1007/s00145-021-09397-w
[6]	D. Wagner, “The boomerang attack,” in Proceedings of the 6th International Workshop on Fast Software Encryption, Rome, Italy, pp.156–170, 1999.
[7]	J. Kelsey, T. Kohno, and B. Schneier, “Amplified boomerang attacks against reduced-round MARS and serpent,” in Proceedings of the 7th International Workshop on Fast Software Encryption, New York, NY, USA, pp.75–93, 2001.
[8]	E. Biham, O. Dunkelman, and N. Keller, “The rectangle attack - rectangling the Serpent,” in Proceedings of the International Conference on Advances in Cryptology, Innsbruck, Austria, pp.340–357, 2001.
[9]	E. Biham, O. Dunkelman, and N. Keller, “Related-key boomerang and rectangle attacks,” in Proceedings of the 24th Annual International Conference on Advances in Cryptology, Aarhus, Denmark, pp.507–525, 2005.
[10]	E. Biham, O. Dunkelman, and N. Keller, “A related-key rectangle attack on the full KASUMI,” in Proceedings of the 11th International Conference on Advances in Cryptology, Chennai, India, pp.443–461, 2005.
[11]	O. Dunkelman, N. Keller, and A. Shamir, “A practical-time related-key attack on the KASUMI cryptosystem used in GSM and 3g telephony,” in Proceedings of the 30th Annual Cryptology Conference on Advances in Cryptology, Santa Barbara, CA, USA, pp.393–410, 2010.
[12]	A. Biryukov and D. Khovratovich, “Related-key cryptanalysis of the full AES-192 and AES-256,” in Proceedings of the 15th International Conference on Advances in Cryptology, Tokyo, Japan, pp.1–18, 2009.
[13]	X. Y. Dong, L. Y. Qin, S. W. Sun, et al., “Key guessing strategies for linear key-schedule algorithms in rectangle attacks,” in Proceedings of the 41st Annual International Conference on Advances in Cryptology, Trondheim, Norway, pp.3–33, 2022.
[14]	G. Z. Liu, M. Ghosh, and L. Song, “Security analysis of SKINNY under related-tweakey settings (long paper),” IACR Transactions on Symmetric Cryptology, vol. 2017, no. 3, pp. 37–72, 2017. doi: 10.13154/tosc.v2017.i3.37-72
[15]	B. X. Zhao, X. Y. Dong, W. Meier, et al., “Generalized related-key rectangle attacks on block ciphers with linear key schedule: Applications to SKINNY and GIFT,” Designs, Codes and Cryptography, vol. 88, no. 6, pp. 1103–1126, 2020. doi: 10.1007/s10623-020-00730-1
[16]	C. Cid, T. Huang, T. Peyrin, et al., “A security analysis of Deoxys and its internal tweakable block ciphers,” IACR Transactions on Symmetric Cryptology, vol. 2017, no. 3, pp. 73–107, 2017. doi: 10.13154/tosc.v2017.i3.73-107
[17]	Y. Sasaki, “Improved related-tweakey boomerang attacks on Deoxys-BC,” in Proceedings of the 10th International Conference on Progress in Cryptology, Marrakesh, Morocco, pp.87–106, 2018.
[18]	C. Cid, T. Huang, T. Peyrin, et al., “Boomerang connectivity table: A new cryptanalysis tool,” in Proceedings of the 37th Annual International Conference on Advances in Cryptology, Tel Aviv, Israel, pp.683–714, 2018.
[19]	H. Y. Wang and T. Peyrin, “Boomerang switch in multiple rounds. Application to AES variants and Deoxys,” IACR Transactions on Symmetric Cryptology, vol. 2019, no. 1, pp. 142–169, 2019. doi: 10.13154/tosc.v2019.i1.142-169
[20]	B. X. Zhao, X. Y. Dong, and K. T. Jia, “New related-tweakey boomerang and rectangle attacks on Deoxys-BC including BDT effect,” IACR Transactions on Symmetric Cryptology, vol. 2019, no. 3, pp. 121–151, 2019. doi: 10.13154/tosc.v2019.i3.121-151
[21]	B. X. Zhao, X. Y. Dong, K. T. Jia, et al., “Improved related-tweakey rectangle attacks on reduced-round Deoxys-BC-384 and Deoxys-I-256-128,” in Proceedings of the 20th International Conference on Progress in Cryptology, Hyderabad, India, pp.139–159, 2019.
[22]	L. Song, N. N. Zhang, Q. Q. Yang, et al., “Optimizing rectangle attacks: A unified and generic framework for key recovery,” in Proceedings of the 28th International Conference on Advances in Cryptology, Taipei, China, pp.410–440, 2022.
[23]	A. Mehrdad, F. Moazami, and H. Soleimany, “Impossible differential cryptanalysis on Deoxys-BC-256,” The ISC International Journal of Information Security, vol. 10, no. 2, pp. 93–105, 2018. doi: 10.22042/isecure.2018.114245.405
[24]	R. Zong, X. Y. Dong, and X. Y. Wang, “Related-tweakey impossible differential attack on reduced-round Deoxys-BC-256,” Science China Information Sciences, vol. 62, no. 3, article no. 32102, 2019. doi: 10.1007/s11432-017-9382-2
[25]	Y. Liu, B. Shi, D. W. Gu, et al., “Improved meet-in-the-middle attacks on reduced-round Deoxys-BC-256,” The Computer Journal, vol. 63, no. 12, pp. 1859–1870, 2020. doi: 10.1093/comjnl/bxaa028
[26]	M. M. Li and S. Z. Chen, “Improved meet-in-the-middle attacks on reduced-round tweakable block cipher Deoxys-BC,” The Computer Journal, vol. 65, no. 9, pp. 2411–2420, 2022. doi: 10.1093/comjnl/bxab076
[27]	R. J. Li and C. H. Jin, “Meet-in-the-middle attacks on round-reduced tweakable block cipher Deoxys-BC,” IET Information Security, vol. 13, no. 1, pp. 70–75, 2019. doi: 10.1049/iet-ifs.2018.5091
[28]	J. Daemen and V. Rijmen, The Design of Rijndael: AES - The Advanced Encryption Standard. Springer, Berlin, 2002.
[29]	A. A. Selçuk, “On probability of success in linear and differential cryptanalysis,” Journal of Cryptology, vol. 21, no. 1, pp. 131–147, 2008. doi: 10.1007/s00145-007-9013-7
[30]	A. Bar-On, O. Dunkelman, N. Keller, et al., “Improved key recovery attacks on reduced-round AES with practical data and memory complexities,” in Proceedings of the 38th Annual International Cryptology Conference on Advances in Cryptology, Santa Barbara, CA, USA, pp.185–212, 2018.