Vectorial Decoding Algorithm for Fast Correlation Attack and Its Applications to Stream Cipher Grain-128a

ZhaoCun Zhou; DengGuo Feng; Bin Zhang

Paper 2021/1435

Vectorial Decoding Algorithm for Fast Correlation Attack and Its Applications to Stream Cipher Grain-128a

ZhaoCun Zhou, DengGuo Feng, and Bin Zhang

Abstract

Fast correlation attacks, pioneered by Meier and Staffelbach, is an important cryptanalysis tool for LFSR-based stream cipher, which exploits the correlation between the LFSR state and key stream and targets at recovering the initial state of LFSR via a decoding algorithm. In this paper, we develop a vectorial decoding algorithm for fast correlation attack, which is a natural generalization of original binary approach. Our approach benefits from the contributions of all correlations in a subspace. We propose two novel criterions to improve the iterative decoding algorithm. We also give some cryptographic properties of the new FCA which allows us to estimate the efficiency and complexity bounds. Furthermore, we apply this technique to well-analyzed stream cipher Grain-128a. Based on a hypothesis, an interesting result for its security bound is deduced from the perspective of iterative decoding. Our analysis reveals the potential vulnerability for LFSRs over generic linear group and also for nonlinear functions with high SEI multidimensional linear approximations such as Grain-128a.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Preprint. MINOR revision.
Contact author(s): zhaocun @ iscas ac cn
martin_zhangbin @ hotmail com
History: 2021-11-22: revised; 2021-10-26: received; See all versions
Short URL: https://ia.cr/2021/1435
License: CC BY

BibTeX

@misc{cryptoeprint:2021/1435,
      author = {ZhaoCun Zhou and DengGuo Feng and Bin Zhang},
      title = {Vectorial Decoding Algorithm for Fast Correlation Attack and Its Applications to Stream Cipher Grain-128a},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/1435},
      year = {2021},
      url = {https://eprint.iacr.org/2021/1435}
}