Paper 2025/462
Practical Key Collision on AES and Kiasu-BC
Jianqiang Ni, Shanghai Key Laboratory of Trustworthy Computing, School of Cryptology, Software Engineering Institute, East China Normal University, Shanghai, China
Yingxin Li, Shanghai Key Laboratory of Trustworthy Computing, School of Cryptology, Software Engineering Institute, East China Normal University, Shanghai, China
Fukang Liu, Institute of Science Tokyo, Tokyo, Japan
Gaoli Wang, Shanghai Key Laboratory of Trustworthy Computing, School of Cryptology, Software Engineering Institute,East China Normal University, Shanghai, Chin
Abstract
The key collision attack was proposed as an open problem in key-committing security in Authenticated Encryption (AE) schemes like and . In ASIACRYPT 2024, Taiyama et al. introduce a novel type of key collision—target-plaintext key collision () for . Depending on whether the plaintext is fixed, can be divided into and , which can be directly converted into collision attacks and semi-free-start collision attacks on the Davies-Meyer () hashing mode.
In this paper, we propose a new rebound attack framework leveraging a time-memory tradeoff strategy, enabling practical key collision attacks with optimized complexity. We also present an improved automatic method for finding \textit{rebound-friendly} differential characteristics by controlling the probabilities in the inbound and outbound phases, allowing the identified characteristics to be directly used in key collision attacks. Through our analysis, we demonstrate that the 2-round attack proposed by Taiyama et al. is a attack in fact, while attacks are considerably more challenging than attacks. By integrating our improved automatic method with a new rebound attack framework, we successfully identify a new differential characteristic for the 2-round attack and develope the first practical attack against 2-round . Additionally, we present practical attacks against 5-round and 3-round , along with a practical attack against 6-round . Furthermore, we reduce time complexities for and attacks on other variants.