Chosen-Key Distinguishing Attacks on Full AES-192, AES-256, Kiasu-BC, and More

Xiaoyang Dong; Jian Guo; Shun Li; Phuong Pham

Paper 2023/1095

Chosen-Key Distinguishing Attacks on Full AES-192, AES-256, Kiasu-BC, and More

Xiaoyang Dong, Tsinghua University, Beijing, P.R.China, Zhongguancun Laboratory, Beijing, P.R.China, State Key Laboratory of Cryptography and Digital Economy Security, Tsinghua University, Beijing, P.R.China

Jian Guo, Nanyang Technological University

Shun Li, University of Chinese Academy of Sciences, Nanyang Technological University

Phuong Pham, Huawei International Pte Ltd., Nanyang Technological University

Abstract

At CRYPTO 2020, Liu et al. demonstrated that many differentials on Gimli are, in fact, incompatible. Similar incompatibilities also arise in related-key differentials on AES, which are typically addressed in an ad-hoc manner by incorporating additional constraints into the searching models. However, such ad-hoc methods are insufficient to eliminate all incompatibilities and may still produce false positive related-key differentials. At CRYPTO 2022, a novel approach was introduced that combines a Constraint Programming (CP) tool with a triangulation algorithm to search for rebound attacks against AES-like hashings. In this paper, we extend and unify these techniques to develop a comprehensive related-key differential search model. Our model not only identifies valid related-key differentials for AES and similar ciphers, but also enables immediate verification of the existence of at least one key pair satisfying the differentials. Using this enhanced automatic tool, we discover new related-key differentials for full-round AES-192, AES-256, Kiasu-BC, and for round-reduced Deoxys-BC. Based on these findings, we present full-round limited-birthday chosen-key distinguishing attacks on AES-192, AES-256, and Kiasu-BC, as well as the first chosen-key distinguisher on reduced-round Deoxys-BC. Furthermore, we identify, for the first time, a limited-birthday distinguisher on 9-round Kiasu-BC with practical complexities.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Published by the IACR in TOSC 2025
Keywords: Related-key Chosen-key Triangulation algorithm Constraint Programming Rebound techniques
Contact author(s): xiaoyangdong @ tsinghua edu cn
guojian @ ntu edu sg
lishun @ ucas ac cn
pham0079 @ e ntu edu sg
History: 2025-09-08: last of 3 revisions; 2023-07-14: received; See all versions
Short URL: https://ia.cr/2023/1095
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1095,
      author = {Xiaoyang Dong and Jian Guo and Shun Li and Phuong Pham},
      title = {Chosen-Key Distinguishing Attacks on Full {AES}-192, {AES}-256, Kiasu-{BC}, and More},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1095},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1095}
}