CryptoDB
Divide-and-Conquer Trail Enumeration Puncturing: Application to Salsa and ChaCha
| Authors: |
|
|---|---|
| Download: | |
| Conference: | ASIACRYPT 2025 |
| Abstract: | At Eurocrypt 2025, a new key recovery method for attacks against ChaCha was proposed. It uses bit puncturing to approximate the key recovery map with a simpler pseudoboolean function which is highly correlated. This approximation is obtained by examining the Walsh spectrum of the key recovery map: in trail enumeration puncturing, this is done by considering a limited set of linear trails. There are limitations to this approach. First, running trail enumeration in practice sometimes requires simplifications which lead to inefficient attacks, as with the 7.5-round ChaCha attack of the previous work. Second, the attacks are often limited by their offline complexity, as is the case when applying the technique to Salsa. Finally, trail enumeration puncturing relies on assumptions which are often impossible to verify in practice by checking the correlation due to the huge offline complexity. To solve these problems, we propose a divide-and-conquer approach which leverages some properties of the Walsh spectrum and can construct the pseudoboolean function with practical time and memory. We improve the complexity of attacks on 7 and 8.5-round Salsa and 7.5-round ChaCha and propose the first attack on 8-round Salsa with 128-bit key, which is the first improvement to the number of rounds since Aumasson et al.'s 2008 work. |
BibTeX
@inproceedings{asiacrypt-2025-36078,
title={Divide-and-Conquer Trail Enumeration Puncturing: Application to Salsa and ChaCha},
publisher={Springer-Verlag},
author={Antonio Flórez-Gutiérrez and Yosuke Todo},
year=2025
}