Improving algebraic attacks on stream ciphers based on linear feedback shifter registers over $F_{2^k}$

Sondre Rønjom

Paper 2015/495

Improving algebraic attacks on stream ciphers based on linear feedback shifter registers over $F_{2^k}$

Sondre Rønjom, Department of Informatics, University of Bergen, Bergen

Abstract

In this paper we investigate univariate algebraic attacks on filter generators over extension fields $F_q=F_{2^n}$ with focus on the Welch-Gong (WG) family of stream ciphers. Our main contribution is to break WG-5, WG-7, WG-8 and WG-16 by combining results on the so-called spectral immunity (minimum distance of certain cyclic codes) with properties of the WG type stream cipher construction. The spectral immunity is the univariate analog of algebraic immunity and instead of measuring degree of multiples of a multivariate polynomial, it measures the minimum number of nonzero coefficients of a multiple of a univariate polynomial. Based on the structure of the general WG-construction, we deduce better bounds for the spectral immunity and the univariate analog of algebraic attacks.

Note: Presented at WCC 2015.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Published elsewhere. WCC 2015
Keywords: stream ciphers algebraic attacks subspace polynomials
Contact author(s): sondre ronjom @ uib no
History: 2022-09-07: last of 3 revisions; 2015-05-25: received; See all versions
Short URL: https://ia.cr/2015/495
License: CC BY

BibTeX

@misc{cryptoeprint:2015/495,
      author = {Sondre Rønjom},
      title = {Improving algebraic attacks on stream ciphers based on linear feedback shifter registers over $F_{2^k}$},
      howpublished = {Cryptology {ePrint} Archive, Paper 2015/495},
      year = {2015},
      url = {https://eprint.iacr.org/2015/495}
}