CryptoDB
Guess-and-Determine Rebound: Applications to Key Collisions on AES
| Authors: |
|
|---|---|
| Download: | |
| Conference: | CRYPTO 2025 |
| Abstract: | This paper introduces the guess-and-determine rebound attack that improves Dong et al.'s triangulating rebound attack in CRYPTO 2022 and Taiyama et al.’s key collision attack in ASIACRYPT 2024. The improvement comes from two aspects: The first improvement is to explore related-key differentials to suit for key collision attack, while Dong et al.'s triangulating rebound attack only considered single-key differentials on AES. To avoid the contradictions in the related-key differential, two tricks are proposed to identify valid trails for key collision attacks. The second improvement is to determine the range of Inbound phase flexibly with the guess-and-determine technique, to reduce the overall time complexity of the attack. By dividing the conflicts in the guess-and-determine steps into different types and handling them separately, the Inbound phase is significantly extended and ultimately leads to better or even practical key collision attacks. Finally, we apply our method to the key collisions on AES, and improve the time complexities of all the theoretical key collision attacks on AES proposed by Taiyama et al. into practical ones, i.e., from 2^{49} to our 2^{6} on 2-round AES-128, from 2^{61} to our 2^{21} for 5-round AES-192 and 6-round AES-256. Additionally, a new 3-round practical key collision attack on AES-128 is given, which is assumed to be impossible by Taiyama et al. All the practical attacks are implemented and some example pairs were found instantly on a standard PC. Besides, some quantum key collisions attacks and semi-free-start collision attacks are proposed. |
BibTeX
@inproceedings{crypto-2025-35563,
title={Guess-and-Determine Rebound: Applications to Key Collisions on AES},
publisher={Springer-Verlag},
author={Lingyue Qin and Wenquan Bi and Xiaoyang Dong},
year=2025
}