Paper 2016/311

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

Bin Zhang, Chao Xu, and Willi Meier


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.

Available format(s)
Secret-key cryptography
Publication info
A minor revision of an IACR publication in CRYPTO 2015
Stream ciphersCryptanalysisLarge-unitSNOW 2:0Finite state machine (FSM)Linear feedback shift register (LFSR)
Contact author(s)
willi meier @ fhnw ch
2016-03-21: received
Short URL
Creative Commons Attribution


      author = {Bin Zhang and Chao Xu and Willi Meier},
      title = {Fast Correlation Attacks over Extension Fields, Large-unit Linear Approximation and Cryptanalysis of SNOW 2.0},
      howpublished = {Cryptology ePrint Archive, Paper 2016/311},
      year = {2016},
      doi = {10.1007/978-3-662-47989-6_31},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.