On the Design and Analysis of Stream Ciphers
(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:
https://lup.lub.lu.se/record/548935
- author
- Hell, Martin LU
- supervisor
- opponent
-
- Dr Robshaw, Matthew, France Telecom Research and Development, France
- organization
- publishing date
- 2007
- 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:00
- 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
- 2016-04-04 12:20:00
- date last changed
- 2018-11-21 21:10:20
@phdthesis{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}},
keywords = {{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}},
publisher = {{Department of Electrical and Information Technology, Lund University}},
school = {{Lund University}},
title = {{On the Design and Analysis of Stream Ciphers}},
url = {{https://lup.lub.lu.se/search/files/5980979/598772.pdf}},
year = {{2007}},
}