Advanced

Predicting the shrinking generator with fixed connections

Ekdahl, Patrik LU ; Meier, W and Johansson, Thomas LU (2003) EUROCRYPT 2003: International Conference on the Theory and Applications of Cryptographic Techniques In Advances in Cryptology / Lecture Notes in Computer Science 2656. p.330-344
Abstract
We propose a novel distinguishing attack on the shrinking generator with known feedback polynomial for the generating LFSR. The attack can e.g. reliably distinguish a shrinking generator with a weight 4 polynomial of degree as large as 10000, using 2(32) output bits. As the feedback polynomial of an arbitrary LFSR is known to have a polynomial multiple of low weight, our distinguisher applies to arbitrary shrunken LFSR's of moderate length. The analysis can also be used to predict the distribution of blocks in the generated keystream.
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
in
Advances in Cryptology / Lecture Notes in Computer Science
volume
2656
pages
330 - 344
publisher
Springer
conference name
EUROCRYPT 2003: International Conference on the Theory and Applications of Cryptographic Techniques
external identifiers
  • wos:000183540000020
  • scopus:35248859228
ISSN
1611-3349
0302-9743
DOI
10.1007/3-540-39200-9_20
language
English
LU publication?
yes
id
dd8a1fb3-7ea8-469b-8acc-33bac3b36281 (old id 308750)
date added to LUP
2007-08-29 13:58:27
date last changed
2018-07-08 03:20:49
@inproceedings{dd8a1fb3-7ea8-469b-8acc-33bac3b36281,
  abstract     = {We propose a novel distinguishing attack on the shrinking generator with known feedback polynomial for the generating LFSR. The attack can e.g. reliably distinguish a shrinking generator with a weight 4 polynomial of degree as large as 10000, using 2(32) output bits. As the feedback polynomial of an arbitrary LFSR is known to have a polynomial multiple of low weight, our distinguisher applies to arbitrary shrunken LFSR's of moderate length. The analysis can also be used to predict the distribution of blocks in the generated keystream.},
  author       = {Ekdahl, Patrik and Meier, W and Johansson, Thomas},
  booktitle    = {Advances in Cryptology / Lecture Notes in Computer Science},
  issn         = {1611-3349},
  language     = {eng},
  pages        = {330--344},
  publisher    = {Springer},
  title        = {Predicting the shrinking generator with fixed connections},
  url          = {http://dx.doi.org/10.1007/3-540-39200-9_20},
  volume       = {2656},
  year         = {2003},
}