International Association
for Cryptologic Research

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.

In this paper, we present a new algorithm for fast correlation attacks on stream ciphers with improved cryptanalysis results on the Sosemanuk stream cipher, one of the 7 finalists in the eSTREAM project in 2008. The new algorithm exploits the direct sum construction of covering codes in decoding phase which approximates the random vectors to a nearest codeword in a linear code. The new strategy provides large flexibility for the adversary and could reduce the time/memory/data complexities significantly. As a case study, we carefully revisit Sosemanuk and demonstrate a state recovery attack with a time complexity of 2134.8, which is 220 times faster than achievable before by the same kind of attack and is the fastest one among all known attacks so far. Our result indicates an inefficiency in longer keys than 135 bits and depicts that the security margin of Sosemanuk is around 28 for the 128-bit security for the first time.