Paper 2023/417

Multivariate Correlation Attacks and the Cryptanalysis of LFSR-based Stream Ciphers

Isaac A. Canales-Martínez, University of Bergen
Igor Semaev, University of Bergen

Cryptanalysis of modern symmetric ciphers may be done by using linear equation systems with multiple right hand sides, which describe the encryption process. The tool was introduced by Raddum and Semaev where several solving methods were developed. In this work, the probabilities are ascribed to the right hand sides and a statistical attack is then applied. The new approach is a multivariate generalisation of the correlation attack by Siegenthaler. A fast version of the attack is provided too. It may be viewed as an extension of the fast correlation attack by Meier and Staffelbach, based on exploiting so called parity-checks for linear recurrences. Parity-checks are a particular case of the relations that we introduce in the present work. The notion of a relation is irrelevant to linear recurrences. We show how to apply the method to some LFSR-based stream ciphers including those from the Grain family. The new method generally requires a lower number of the keystream bits to recover the initial states than other techniques reported in the literature.

Available format(s)
Attacks and cryptanalysis
Publication info
CryptanalysisMultivariate correlation attacksTest-and-extend algorithmStream ciphersLFSRsGrain
Contact author(s)
icanalesm0500 @ gmail com
igor semaev @ uib no
2023-03-24: approved
2023-03-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Isaac A. Canales-Martínez and Igor Semaev},
      title = {Multivariate Correlation Attacks and the Cryptanalysis of LFSR-based Stream Ciphers},
      howpublished = {Cryptology ePrint Archive, Paper 2023/417},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.