Paper 2025/462

Practical Key Collision on AES and Kiasu-BC

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.