Cryptanalysis of Selected Stream Ciphers
Author
Summary, in English
The aim of this dissertation is to show some cryptanalytical results on a selection of stream ciphers. We have grouped theory and results into three main parts.
The first part focuses on the FCSR-based constructions X-FCSR and F-FCSR-H v3. For the X-FCSR family of stream ciphers we perform a severe state recovery attack. This attack works for both X-FCSR-128 and X-FCSR-256.
We then develop a generalized birthday algorithm for finding linear relations in FCSRs. This algorithm applies to the most recent and general FCSR architecture, the ring FCSR, so it can be used for analyzing the FCSR of any FCSR-based design. We apply the algorithm to produce an efficient distinguisher for F-FCSR-H v3, which was previously unbroken.
The second part of the dissertation covers topics related to the HC family of stream ciphers. First, a very general treatment of sampling methods is presented. Surprisingly, perhaps, a positive result is given. We prove that an efficient sampling method based on sampling vector weights is optimal in a given context. This sampling technique is employed to produce the best known distinguisher for HC-128.
We go on to show a few theoretical results on functions that use word rotation and xor. These results are applied to a modified variant of HC-128, and this application shows how the theory could be used in a cryptanalytical scenario. It also shows the important role of the addition operator in HC-128, without which the cipher would be much less secure.
In the third part of the dissertation we analyze stream ciphers, and block ciphers to a lesser extent, using algebraic methods. We develop a simple and intuitive greedy algorithm for automatic security testing of cryptographic primitives. This is done in a black box fashion, without using any information on the internal structure of the primitives. Despite this, it is shown how structural information is revealed very clearly under certain circumstances. The main features here are some nice results for the well-known stream ciphers Trivium, Grain-128 and Grain v1.
The first part focuses on the FCSR-based constructions X-FCSR and F-FCSR-H v3. For the X-FCSR family of stream ciphers we perform a severe state recovery attack. This attack works for both X-FCSR-128 and X-FCSR-256.
We then develop a generalized birthday algorithm for finding linear relations in FCSRs. This algorithm applies to the most recent and general FCSR architecture, the ring FCSR, so it can be used for analyzing the FCSR of any FCSR-based design. We apply the algorithm to produce an efficient distinguisher for F-FCSR-H v3, which was previously unbroken.
The second part of the dissertation covers topics related to the HC family of stream ciphers. First, a very general treatment of sampling methods is presented. Surprisingly, perhaps, a positive result is given. We prove that an efficient sampling method based on sampling vector weights is optimal in a given context. This sampling technique is employed to produce the best known distinguisher for HC-128.
We go on to show a few theoretical results on functions that use word rotation and xor. These results are applied to a modified variant of HC-128, and this application shows how the theory could be used in a cryptanalytical scenario. It also shows the important role of the addition operator in HC-128, without which the cipher would be much less secure.
In the third part of the dissertation we analyze stream ciphers, and block ciphers to a lesser extent, using algebraic methods. We develop a simple and intuitive greedy algorithm for automatic security testing of cryptographic primitives. This is done in a black box fashion, without using any information on the internal structure of the primitives. Despite this, it is shown how structural information is revealed very clearly under certain circumstances. The main features here are some nice results for the well-known stream ciphers Trivium, Grain-128 and Grain v1.
Department/s
Publishing year
2013
Language
English
Publication/Series
Series of licentiate and doctoral dissertations
Volume
50
Full text
Document type
Dissertation
Publisher
Department of Electrical and Information Technology, Lund University
Topic
- Electrical Engineering, Electronic Engineering, Information Engineering
Keywords
- Stream cipher
- cryptanalysis
- FCSR
- state recovery
- linear relations
- optimal sampling
- distinguisher
- HC
- nonrandomness
- greedy bit set algorithm.
Status
Published
Research group
- Crypto and Security
Supervisor
ISBN/ISSN/Other
- ISSN: 1654-790X
- ISBN: 978-91-7473-526-0 (Online)
- ISBN: 978-91-7473-525-3 (Print)
Defence date
17 June 2013
Defence time
10:15
Defence place
Lecture hall E:1406, Ole Römers väg 3, Lund University Faculty of Engineering
Opponent
- Anne Canteaut (Dr.)