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 $\texttt{AES-GCM}$ and $\texttt{ChaCha20Poly1305}$. In ASIACRYPT 2024, Taiyama et al. introduce a novel type of key collision—target-plaintext key collision ($\texttt{TPKC}$) for $\texttt{AES}$. Depending on whether the plaintext is fixed, $\texttt{TPKC}$ can be divided into $\texttt{fixed-TPKC}$ and $\texttt{free-TPKC}$, which can be directly converted into collision attacks and semi-free-start collision attacks on the Davies-Meyer ($\texttt{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 \textit{rebound-friendly} differential characteristics by controlling the probabilities in the inbound and outbound phases, allowing the identified characteristics to be directly used in $\textit{rebound-based}$ key collision attacks. Through our analysis, we demonstrate that the 2-round $\texttt{AES-128}$ $\texttt{fixed-TPKC}$ attack proposed by Taiyama et al. is a $\texttt{free-TPKC}$ attack in fact, while $\texttt{fixed-TPKC}$ attacks are considerably more challenging than $\texttt{free-TPKC}$ attacks. By integrating our improved automatic method with a new rebound attack framework, we successfully identify a new differential characteristic for the 2-round $\texttt{AES-128}$ $\texttt{fixed-TPKC}$ attack and develope the first practical $\texttt{fixed-TPKC}$ attack against 2-round $\texttt{AES-128}$. Additionally, we present practical $\texttt{fixed-TPKC}$ attacks against 5-round $\texttt{AES-192}$ and 3-round $\texttt{Kiasu-BC}$, along with a practical $\texttt{free-TPKC}$ attack against 6-round $\texttt{Kiasu-BC}$. Furthermore, we reduce time complexities for $\texttt{free-TPKC}$ and $\texttt{fixed-TPKC}$ attacks on other $\texttt{AES}$ variants.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Keywords
- Key collisionRebound-based attackAESSATDM hashing modeKiasu-BC
- Contact author(s)
-
jianqiangni0213 @ 163 com
liyx1140 @ 163 com
liu f ad @ m titech ac jp
glwang @ sei ecnu edu cn - History
- 2025-03-12: approved
- 2025-03-12: received
- See all versions
- Short URL
- https://ia.cr/2025/462
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/462, author = {Jianqiang Ni and Yingxin Li and Fukang Liu and Gaoli Wang}, title = {Practical Key Collision on {AES} and Kiasu-{BC}}, howpublished = {Cryptology {ePrint} Archive, Paper 2025/462}, year = {2025}, url = {https://eprint.iacr.org/2025/462} }