Paper 2016/384

Attacks against Filter Generators Exploiting Monomial Mappings

Anne Canteaut and Yann Rotella

Abstract

Filter generators are vulnerable to several attacks which have led to well-known design criteria on the Boolean filtering function. However, Rønjom and Cid have observed that a change of the primitive root defining the LFSR leads to several equivalent generators. They usually offer different security levels since they involve filtering functions of the form F(x^k) where k is coprime to (2^n-1) and n denotes the LFSR length. It is proved here that this monomial equivalence does not affect the resistance of the generator against algebraic attacks, while it usually impacts the resistance to correlation attacks. Most importantly, a more efficient attack can often be mounted by considering non-bijective monomial mappings. In this setting, a divide-and-conquer strategy applies based on a search within a multiplicative subgroup of F_{2^n}^*. Moreover, if the LFSR length n is not a prime, a fast correlation involving a shorter LFSR can be performed.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published by the IACR in FSE 2016
Keywords
Stream cipherscorrelation attacksLFSRfilter generatornonlinear equivalencemonomial
Contact author(s)
Anne Canteaut @ inria fr
History
2016-04-15: received
Short URL
https://ia.cr/2016/384
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/384,
      author = {Anne Canteaut and Yann Rotella},
      title = {Attacks against Filter Generators Exploiting Monomial Mappings},
      howpublished = {Cryptology ePrint Archive, Paper 2016/384},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/384}},
      url = {https://eprint.iacr.org/2016/384}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.