Cryptology ePrint Archive: Report 2016/311

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

Bin Zhang and Chao Xu and Willi Meier

Abstract: 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 than 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.

Category / Keywords: secret-key cryptography / Stream ciphers, Cryptanalysis, Large-unit, SNOW 2:0, Finite state machine (FSM), Linear feedback shift register (LFSR)

Original Publication (with minor differences): IACR-CRYPTO-2015

Date: received 18 Mar 2016

Contact author: willi meier at fhnw ch

Available format(s): PDF | BibTeX Citation

Version: 20160321:100935 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]