Paper 2018/522

Fast Correlation Attack Revisited --Cryptanalysis on Full Grain-128a, Grain-128, and Grain-v1

Yosuke Todo, Takanori Isobe, Willi Meier, Kazumaro Aoki, and Bin Zhang

Abstract

A fast correlation attack (FCA) is a well-known cryptanalysis technique for LFSR-based stream ciphers. The correlation between the initial state of an LFSR and corresponding key stream is exploited, and the goal is to recover the initial state of the LFSR. In this paper, we revisit the FCA from a new point of view based on a finite field, and it brings a new property for the FCA when there are multiple linear approximations. Moreover, we propose a novel algorithm based on the new property, which enables us to reduce both time and data complexities. We finally apply this technique to the Grain family, which is a well-analyzed class of stream ciphers. There are three stream ciphers, Grain-128a, Grain-128, and Grain-v1 in the Grain family, and Grain-v1 is in the eSTREAM portfolio and Grain-128a is standardized by ISO/IEC. As a result, we break them all, and especially for Grain-128a, the cryptanalysis on its full version is reported for the first time.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in CRYPTO 2018
Keywords
Fast correlation attackStream cipherLFSRFinite fieldMultiple linear approximationsGrain-128aGrain-128Grain-v1
Contact author(s)
todo yosuke @ lab ntt co jp
ysktodo @ gmail com
takanori isobe @ ai u-hyogo ac jp
willi meier @ fhnw ch
aoki kazumaro @ lab ntt co jp
martin_zhangbin @ hotmail com
History
2018-09-19: revised
2018-06-04: received
See all versions
Short URL
https://ia.cr/2018/522
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/522,
      author = {Yosuke Todo and Takanori Isobe and Willi Meier and Kazumaro Aoki and Bin Zhang},
      title = {Fast Correlation Attack Revisited --Cryptanalysis on Full Grain-128a, Grain-128, and Grain-v1},
      howpublished = {Cryptology ePrint Archive, Paper 2018/522},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/522}},
      url = {https://eprint.iacr.org/2018/522}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.