Practical Key Collision on AES and Kiasu-BC

The key collision attack was proposed as an open problem in key-committing security in Authenticated Encryption (AE) schemes like AES-GCM and ChaCha20Poly1305. In ASIACRYPT 2024, Taiyama et al. introduce a novel type of key collision—target-plaintext key collision (TPKC) for AES. Depending on whether the plaintext is fixed, TPKC can be divided into fixed-TPKC and free-TPKC, which can be directly converted into collision attacks and semi-free-start collision attacks on the Davies-Meyer (DM) 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 rebound-friendly differential characteristics by controlling the probabilities in the inbound and outbound phases, allowing the identified characteristics to be directly used in rebound-based key collision attacks. Our analysis reveals that the 2-round AES-128 fixed-TPKC attack proposed by Taiyama et al. is, in fact, a free-TPKC attack. This distinction is significant, as fixed-TPKC attacks are substantially more difficult than their free-TPKC counterparts. By integrating our improved automatic method with a new rebound attack framework, we successfully identify a new differential characteristic for the 2-round AES-128 fixed-TPKC attack and develope the first practical fixed-TPKC attack against 2-round AES-128. Additionally, we present practical fixed-TPKC attacks against 5-round AES-192 and 3-round Kiasu-BC, along with a practical free-TPKC attack against 6-round Kiasu-BC. Furthermore, we reduce time complexities for free-TPKC and fixed-TPKC attacks on other AES variants.