Advanced

A Survey on Fast Correlation Attacks

Ågren, Martin LU ; Löndahl, Carl LU ; Hell, Martin LU and Johansson, Thomas LU (2012) In Cryptography and Communications 4(3-4). p.173-202
Abstract
Fast correlation attacks, pioneered by Meier and Staffelbach in 1988, constitute an important class of attacks on stream ciphers. They exploit a correlation between the keystream and the output of a linear feedback shift register (LFSR) within the cipher. Several factors affect the feasibility of such an attack, e.g., the amount of available keystream and the number of taps in the LFSR. Notably, for a fixed number of taps, the length of the LFSR does not affect the complexity of the attack. When the register does not have a sufficiently small number of taps, however, the attacker will try to find parity check equations of low weight, at which point the length of the register does matter. In this paper, we go through the significant... (More)
Fast correlation attacks, pioneered by Meier and Staffelbach in 1988, constitute an important class of attacks on stream ciphers. They exploit a correlation between the keystream and the output of a linear feedback shift register (LFSR) within the cipher. Several factors affect the feasibility of such an attack, e.g., the amount of available keystream and the number of taps in the LFSR. Notably, for a fixed number of taps, the length of the LFSR does not affect the complexity of the attack. When the register does not have a sufficiently small number of taps, however, the attacker will try to find parity check equations of low weight, at which point the length of the register does matter. In this paper, we go through the significant contributions to this field of cryptanalysis, reiterating the various algorithms that have been developed for finding parity check equations and performing the online stage on received keystream. We also suggest some new generalizations of Meier-Staffelbach's original formulations. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
fast correlation attacks, stream ciphers, cryptanalysis
in
Cryptography and Communications
volume
4
issue
3-4
pages
173 - 202
publisher
Springer
external identifiers
  • wos:000208851200003
  • scopus:84867483276
ISSN
1936-2455
DOI
10.1007/s12095-012-0062-x
language
English
LU publication?
yes
id
881e23d2-7a8b-454c-a89d-826463d0ca19 (old id 3051813)
date added to LUP
2012-09-12 12:32:56
date last changed
2017-09-17 03:02:42
@article{881e23d2-7a8b-454c-a89d-826463d0ca19,
  abstract     = {Fast correlation attacks, pioneered by Meier and Staffelbach in 1988, constitute an important class of attacks on stream ciphers. They exploit a correlation between the keystream and the output of a linear feedback shift register (LFSR) within the cipher. Several factors affect the feasibility of such an attack, e.g., the amount of available keystream and the number of taps in the LFSR. Notably, for a fixed number of taps, the length of the LFSR does not affect the complexity of the attack. When the register does not have a sufficiently small number of taps, however, the attacker will try to find parity check equations of low weight, at which point the length of the register does matter. In this paper, we go through the significant contributions to this field of cryptanalysis, reiterating the various algorithms that have been developed for finding parity check equations and performing the online stage on received keystream. We also suggest some new generalizations of Meier-Staffelbach's original formulations.},
  author       = {Ågren, Martin and Löndahl, Carl and Hell, Martin and Johansson, Thomas},
  issn         = {1936-2455},
  keyword      = {fast correlation attacks,stream ciphers,cryptanalysis},
  language     = {eng},
  number       = {3-4},
  pages        = {173--202},
  publisher    = {Springer},
  series       = {Cryptography and Communications},
  title        = {A Survey on Fast Correlation Attacks},
  url          = {http://dx.doi.org/10.1007/s12095-012-0062-x},
  volume       = {4},
  year         = {2012},
}