International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Zhaocun Zhou , Trusted Computing and Information Assurance Laboratory, Institute of Software, Chinese Academy of Sciences, Beijing, China; University of Chinese Academy of Sciences, Beijing, China
Dengguo Feng , State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing, China
Bin Zhang , Trusted Computing and Information Assurance Laboratory, Institute of Software, Chinese Academy of Sciences, Beijing, China
Download:
DOI: 10.46586/tosc.v2022.i2.322-350
URL: https://tosc.iacr.org/index.php/ToSC/article/view/9723
Search ePrint
Search Google
Abstract: Fast correlation attack, 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 the original binary approach. Our approach benefits from the contributions of all correlations in a subspace. We propose two novel criteria 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 the 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 matrix ring and also for nonlinear functions with biased multidimensional linear approximations such as Grain-128a.
BibTeX
@article{tosc-2022-32088,
  title={Vectorial Decoding Algorithm for Fast Correlation Attack and Its Applications to Stream Cipher Grain-128a},
  journal={IACR Transactions on Symmetric Cryptology},
  publisher={Ruhr-Universität Bochum},
  volume={2022, Issue 2},
  pages={322-350},
  url={https://tosc.iacr.org/index.php/ToSC/article/view/9723},
  doi={10.46586/tosc.v2022.i2.322-350},
  author={Zhaocun Zhou and Dengguo Feng and Bin Zhang},
  year=2022
}