CryptoDB
Vectorial Fast Correlation Attacks
| Authors: |
|
|---|---|
| Download: | |
| Conference: | ASIACRYPT 2025 |
| Abstract: | In this paper, we develop a new framework for vectorial fast correlation attacks, which exploits the vector-wise correlation in a novel and different approach from the previous Goli$\acute{c}$'s attack and gives the complete theoretical predictions of the attack complexities. First, the concept of correlation profile is introduced to characterize both the correlation of some linear approximation and the number of approximations having this correlation, which is not captured by the current notion of capacity or the Squared Euclidean Imbalance (SEI). It is shown how to construct the attack vector by carefully selecting the component-wise linear approximations to make a maximal usage of the inherent correlations. Second, we show how to transform and deliver the secret key information in the constructed vector by sequentially deriving linear subspaces from the original vector when the correlation profile is favorable. We further devise an efficient decoding algorithm to restore the partial secret key information retained in the last linear subspace, which allows for the recovery of the full secret information subsequently. Last, we present improved state recovery attacks on the ISO/IEC 29167-13 standard Grain-128a, the eSTREAM finalists Grain v1 and Sosemanuk, respectively by the new method. We resolve the open problem of detecting the output masks for Grain-like ciphers other than MILP at Crypto 2018 and propose a new algorithm based on graph theory to dissect complicated Boolean functions with many variables and compute its distribution efficiently. For Grain-128a, given around $2^{106.3}$ bits of keystream, the time complexity is $2^{107.7}$, while for Grain v1, given $2^{67.0}$ bits of keystream, the attack has a time complexity of $2^{69.6}$. These attacks are around $2^{12}$ times better than the best published results at Crypto 2018. For Sosemanuk, we propose a flexible assign-and-solve strategy to mount the first attack faster than exhaustive search of the 128-bit secret key. |
BibTeX
@inproceedings{asiacrypt-2025-36165,
title={Vectorial Fast Correlation Attacks},
publisher={Springer-Verlag},
author={Bin Zhang and Ruitao Liu and Willi Meier},
year=2025
}