Advanced

Some results on fast correlation attacks

Jönsson, Fredrik LU (2002)
Abstract
This thesis presents new results on fast correlation attacks on stream ciphers. In particular, fast correlation attacks on stream ciphers containing linear shift registers with an arbitrary number of taps, are considered.



A general introduction to stream ciphers and correlation attacks is given. The introduction also presents standard properties of linear feedback shift registers and Boolean functions.



Three different algorithms for fast correlation attacks are presented. The first algorithm transforms a part of the code stemming from the LFSR sequence into a convolutional code, and decodes the convolutional code using the Viterbi algorithm. A theoretical analysis for the algorithm is performed, using... (More)
This thesis presents new results on fast correlation attacks on stream ciphers. In particular, fast correlation attacks on stream ciphers containing linear shift registers with an arbitrary number of taps, are considered.



A general introduction to stream ciphers and correlation attacks is given. The introduction also presents standard properties of linear feedback shift registers and Boolean functions.



Three different algorithms for fast correlation attacks are presented. The first algorithm transforms a part of the code stemming from the LFSR sequence into a convolutional code, and decodes the convolutional code using the Viterbi algorithm. A theoretical analysis for the algorithm is performed, using a random coding bound for convolutional codes. This algorithm is then modified by using Turbo code techniques. The third algorithm is based on a method to recover multivariate linear polynomials.



An overview and a comparison of recently proposed algorithms for fast correlations attacks, is given.



The LILI-128 keystream generator, a recent stream cipher proposal, is attacked by a fast correlation attack.



Several stream ciphers working over an extension field have been proposed in the last few years. Most algorithms for fast correlation attacks are described over the binary alphabet. An algorithm is presented that generalizes previous work to an attack over any field.



This thesis also propose a new algorithm for decoding a general linear code. This decoding problem have several applications in cryptology, such as the McEliece public key cryptosystem, the Stern identification scheme, and also in correlation attacks. (Less)
Please use this url to cite or link to this publication:
author
opponent
  • Prof Meier, Willie, Schweiz
organization
publishing date
type
Thesis
publication status
published
subject
keywords
Technological sciences, stream ciphers, linear feedback shift registers, cryptology, correlation attacks, cryptanalysis, Teknik, Informatics, systems theory, Informatik, systemteori
pages
151 pages
publisher
Department of Information Technology, Lund Univeristy
defense location
E:1406, E-huset, Lunds Tekniska Högskola
defense date
2002-05-24 13:15
ISBN
91-7167-024-6
language
English
LU publication?
yes
id
c99e7bfa-5843-44c3-bc7d-69c0146b9791 (old id 20543)
date added to LUP
2007-05-28 09:38:32
date last changed
2016-09-19 08:45:13
@phdthesis{c99e7bfa-5843-44c3-bc7d-69c0146b9791,
  abstract     = {This thesis presents new results on fast correlation attacks on stream ciphers. In particular, fast correlation attacks on stream ciphers containing linear shift registers with an arbitrary number of taps, are considered.<br/><br>
<br/><br>
A general introduction to stream ciphers and correlation attacks is given. The introduction also presents standard properties of linear feedback shift registers and Boolean functions.<br/><br>
<br/><br>
Three different algorithms for fast correlation attacks are presented. The first algorithm transforms a part of the code stemming from the LFSR sequence into a convolutional code, and decodes the convolutional code using the Viterbi algorithm. A theoretical analysis for the algorithm is performed, using a random coding bound for convolutional codes. This algorithm is then modified by using Turbo code techniques. The third algorithm is based on a method to recover multivariate linear polynomials.<br/><br>
<br/><br>
An overview and a comparison of recently proposed algorithms for fast correlations attacks, is given.<br/><br>
<br/><br>
The LILI-128 keystream generator, a recent stream cipher proposal, is attacked by a fast correlation attack.<br/><br>
<br/><br>
Several stream ciphers working over an extension field have been proposed in the last few years. Most algorithms for fast correlation attacks are described over the binary alphabet. An algorithm is presented that generalizes previous work to an attack over any field.<br/><br>
<br/><br>
This thesis also propose a new algorithm for decoding a general linear code. This decoding problem have several applications in cryptology, such as the McEliece public key cryptosystem, the Stern identification scheme, and also in correlation attacks.},
  author       = {Jönsson, Fredrik},
  isbn         = {91-7167-024-6},
  keyword      = {Technological sciences,stream ciphers,linear feedback shift registers,cryptology,correlation attacks,cryptanalysis,Teknik,Informatics,systems theory,Informatik,systemteori},
  language     = {eng},
  pages        = {151},
  publisher    = {Department of Information Technology, Lund Univeristy},
  school       = {Lund University},
  title        = {Some results on fast correlation attacks},
  year         = {2002},
}