On the Design and Analysis of Stream Ciphers
Författare
Summary, in English
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.
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.
Publiceringsår
2007
Språk
Engelska
Fulltext
Dokumenttyp
Doktorsavhandling
Förlag
Department of Electrical and Information Technology, Lund University
Ämne
- Electrical Engineering, Electronic Engineering, Information Engineering
Nyckelord
- weak feedback polynomials
- bit-search generator
- self-shrinking generator
- Achterbahn
- Pomaranch
- Grain-128
- Grain
- stream ciphers
- cryptography
- cryptanalysis
- Informatics
- systems theory
- Informatik
- systemteori
Status
Published
Handledare
ISBN/ISSN/Övrigt
- ISBN: 91-7167-043-2
- LUTEDX/TEIT-07/1039-SE
Försvarsdatum
13 september 2007
Försvarstid
13:15
Försvarsplats
Room E:1406, E-building, Ole Römers väg 3, Lund University Faculty of Engineering
Opponent
- Matthew Robshaw (Dr)