Advanced

On the Design and Analysis of Stream Ciphers

Hell, Martin LU (2007)
Abstract
This thesis presents new cryptanalysis results for several different stream cipher constructions. In addition, it also presents two new stream ciphers, both based on the same design principle.



The first attack is a general attack targeting a nonlinear combiner. A new class of weak feedback polynomials for linear feedback shift registers is identified. By taking samples corresponding to the linear recurrence relation, it is shown that if the feedback polynomial has taps close together an adversary to take advantage of this by considering the samples in a vector form.



Next, the self-shrinking generator and the bit-search generator are analyzed. Both designs are based on irregular decimation. For the... (More)
This thesis presents new cryptanalysis results for several different stream cipher constructions. In addition, it also presents two new stream ciphers, both based on the same design principle.



The first attack is a general attack targeting a nonlinear combiner. A new class of weak feedback polynomials for linear feedback shift registers is identified. By taking samples corresponding to the linear recurrence relation, it is shown that if the feedback polynomial has taps close together an adversary to take advantage of this by considering the samples in a vector form.



Next, the self-shrinking generator and the bit-search generator are analyzed. Both designs are based on irregular decimation. For the self-shrinking generator, it is shown how to recover the internal state knowing only a few keystream bits. The complexity of the attack is similar to the previously best known but uses a negligible amount of memory. An attack requiring a large keystream segment is also presented. It is shown to be asymptotically better than all previously known attacks. For the bit-search generator, an algorithm that recovers the internal state is given as well as a distinguishing attack that can be very efficient if the feedback polynomial is not carefully chosen.



Following this, two recently proposed stream cipher designs, Pomaranch and Achterbahn, are analyzed. Both stream ciphers are designed with small hardware complexity in mind. For Pomaranch Version 2, based on an improvement of previous analysis of the design idea, a key recovery attack is given. Also, for all three versions of Pomaranch, a distinguishing attack is given. For Achterbahn, it is shown how to recover the key of the latest version, known as Achterbahn-128/80.



The last part of the thesis introduces two new stream cipher designs, namely Grain and Grain-128. The ciphers are designed to be very small in hardware. They also have the distinguishing feature of allowing users to increase the speed of the ciphers by adding extra hardware. (Less)
Please use this url to cite or link to this publication:
author
supervisor
opponent
  • Dr Robshaw, Matthew, France Telecom Research and Development, France
organization
publishing date
type
Thesis
publication status
published
subject
keywords
weak feedback polynomials, bit-search generator, self-shrinking generator, Achterbahn, Pomaranch, Grain-128, Grain, stream ciphers, cryptography, cryptanalysis, Informatics, systems theory, Informatik, systemteori
pages
172 pages
publisher
Department of Electrical and Information Technology, Lund University
defense location
Room E:1406, E-building, Ole Römers väg 3, Lund University Faculty of Engineering
defense date
2007-09-13 13:15
external identifiers
  • Other:LUTEDX/TEIT-07/1039-SE
ISBN
91-7167-043-2
language
English
LU publication?
yes
id
4baca05f-6e67-47bb-b8f0-5c76d18fd950 (old id 548935)
date added to LUP
2007-11-13 07:59:05
date last changed
2016-09-19 08:45:15
@misc{4baca05f-6e67-47bb-b8f0-5c76d18fd950,
  abstract     = {This thesis presents new cryptanalysis results for several different stream cipher constructions. In addition, it also presents two new stream ciphers, both based on the same design principle.<br/><br>
<br/><br>
The first attack is a general attack targeting a nonlinear combiner. A new class of weak feedback polynomials for linear feedback shift registers is identified. By taking samples corresponding to the linear recurrence relation, it is shown that if the feedback polynomial has taps close together an adversary to take advantage of this by considering the samples in a vector form.<br/><br>
<br/><br>
Next, the self-shrinking generator and the bit-search generator are analyzed. Both designs are based on irregular decimation. For the self-shrinking generator, it is shown how to recover the internal state knowing only a few keystream bits. The complexity of the attack is similar to the previously best known but uses a negligible amount of memory. An attack requiring a large keystream segment is also presented. It is shown to be asymptotically better than all previously known attacks. For the bit-search generator, an algorithm that recovers the internal state is given as well as a distinguishing attack that can be very efficient if the feedback polynomial is not carefully chosen.<br/><br>
<br/><br>
Following this, two recently proposed stream cipher designs, Pomaranch and Achterbahn, are analyzed. Both stream ciphers are designed with small hardware complexity in mind. For Pomaranch Version 2, based on an improvement of previous analysis of the design idea, a key recovery attack is given. Also, for all three versions of Pomaranch, a distinguishing attack is given. For Achterbahn, it is shown how to recover the key of the latest version, known as Achterbahn-128/80.<br/><br>
<br/><br>
The last part of the thesis introduces two new stream cipher designs, namely Grain and Grain-128. The ciphers are designed to be very small in hardware. They also have the distinguishing feature of allowing users to increase the speed of the ciphers by adding extra hardware.},
  author       = {Hell, Martin},
  isbn         = {91-7167-043-2},
  keyword      = {weak feedback polynomials,bit-search generator,self-shrinking generator,Achterbahn,Pomaranch,Grain-128,Grain,stream ciphers,cryptography,cryptanalysis,Informatics,systems theory,Informatik,systemteori},
  language     = {eng},
  pages        = {172},
  publisher    = {ARRAY(0x9ed4a40)},
  title        = {On the Design and Analysis of Stream Ciphers},
  year         = {2007},
}