Fast Correlation Attacks over Extension Fields, Large-Unit Linear Approximation and Cryptanalysis of SNOW 2.0

摘要

Several improvements of fast correlation attacks have been proposed during the past two decades, with a regrettable lack of a better generalization and adaptation to the concrete involved primitives, especially to those modern stream ciphers based on word-based LFSRs. In this paper, we develop some necessary cryptanalytic tools to bridge this gap. First, a formal framework for fast correlation attacks over extension fields is constructed, under which the theoretical predictions of the computational complexities for both the offline and online/decoding phase can be reliably derived. Our decoding algorithm makes use of Fast Walsh Transform (FWT) to get a better performance. Second, an efficient algorithm to compute the large-unit distribution of a broad class of functions is proposed, which allows to find better linear approximations than the bitwise ones with low complexity in symmetric-key primitives. Last, we apply our methods to SNOW 2.0, an ISO/IEC 18033-4 standard stream cipher, which results in the significantly reduced complexities all below 2~(164.15). This attack is more tnan 2~(49) times better than the best published result at Asiacrypt 2008. Our results have been verified by experiments on a small-scale version of SNOW 2.0.