Powers of Subfield Polynomials and Algebraic Attacks on Word-Based Stream Ciphers

Sondre Rønjom

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

Available format(s)
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
stream ciphersalgebraic attacksWelch-Gong
Contact author(s)
sondrer @ gmail com
History
2015-06-02: revised
See all versions
Short URL
https://ia.cr/2015/495

CC BY

BibTeX

@misc{cryptoeprint:2015/495,
author = {Sondre Rønjom},
title = {Powers of Subfield Polynomials and Algebraic Attacks on Word-Based Stream Ciphers},
howpublished = {Cryptology ePrint Archive, Paper 2015/495},
year = {2015},
note = {\url{https://eprint.iacr.org/2015/495}},
url = {https://eprint.iacr.org/2015/495}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.