Bin Zhang
University of Chinese Academy of Sciences, China; State Key Laboratory of Cryptology, China; Trusted Computing and Information Assurance Laboratory, State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, China; Guizhou shujubao Network Technology Co., Ltd., China; Hefei National Laboratory, China

Ruitao Liu
University of Chinese Academy of Sciences, China; Trusted Computing and Information Assurance Laboratory, State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, China; Zhongguancun Laboratory, China

Willi Meier
University of Applied Sciences and Arts Northwestern Switzerland, Switzerland

Siwei Sun
University of Chinese Academy of Sciences, China;

Dengguo Feng
University of Chinese Academy of Sciences, China; State Key Laboratory of Cryptology, China; Trusted Computing and Information Assurance Laboratory, State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, China; Zhongguancun Laboratory, China

Wenling Wu
University of Chinese Academy of Sciences, China; Trusted Computing and Information Assurance Laboratory, State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, China; Zhongguancun Laboratory, China

Keywords:

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ć'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¹² 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.