International Association
for Cryptologic Research

The complexity of fast correlation attack is fundamentally determined by the correlations of the linear approximations used. Conventional fast correlation attacks either rely on a single dominant linear approximation or use the lower bound to evaluate the resulting correlation of multiple linear approximations, which have the same output mask and distinct input masks. How to exploit multiple linear approximations with distinct output masks remains an open problem. In this paper, we propose a framework of fast correlation attack exploiting multiple linear approximations called \texttt{MultLA} to solve this problem. \texttt{MultLA} utilizes the arithmetic mean of the absolute correlations of linear approximations, rather than the lower bound of that. For SNOW 5G, our attack has time/memory/data complexities of ${{2}^{279.25}}/{{2}^{265.03}}/{{2}^{263.62}}$, which are all better than those of the existing work. When the time and memory complexities are slightly better than those of the existing work, the data complexity is significantly reduced from ${{2}^{265.4}}$ to ${{2}^{261.21}}$. To the best of our knowledge, our attacks achieve the best known cryptanalytic results of SNOW 5G up to now.