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

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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A minor revision of an IACR publication in CRYPTO 2015
DOI
10.1007/978-3-662-47989-6_31
Keywords
Stream ciphersCryptanalysisLarge-unitSNOW 2:0Finite state machine (FSM)Linear feedback shift register (LFSR)
Contact author(s)
willi meier @ fhnw ch
History
2016-03-21: received
Short URL
https://ia.cr/2016/311
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/311,
      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{https://eprint.iacr.org/2016/311}},
      url = {https://eprint.iacr.org/2016/311}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.