Advanced

An Efficient State Recovery Attack on the X-FCSR Family of Stream Ciphers

Stankovski, Paul LU ; Hell, Martin LU and Johansson, Thomas LU (2014) In Journal of Cryptology 27(1). p.1-22
Abstract
We describe a state recovery attack on the X-FCSR family of stream ciphers. In this attack we analyse each block of output keystream and try to solve for the state. The solver will succeed when a number of state conditions are satisfied.

For X-FCSR-256, our best attack has a computational complexity of only 2^{4.7} table lookups per block of keystream, with an expected 2^{44.3} such blocks before the attack is successful. The precomputational storage requirement is 2^{33}.

For X-FCSR-128, the computational complexity of our best attack is 2^{16.3} table lookups per block of keystream, where we expect 2^{55.2} output blocks before the attack comes through. The precomputational storage requirement for X-FCSR-128 is 2^{67}.
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
stream cipher, FCSR, X-FCSR, cryptanalysis, state recovery
in
Journal of Cryptology
volume
27
issue
1
pages
1 - 22
publisher
Springer
external identifiers
  • wos:000329628000001
  • scopus:84894903289
ISSN
1432-1378
DOI
10.1007/s00145-012-9130-9
language
English
LU publication?
yes
id
13a80ffa-d58d-42a1-a601-00f20837336a (old id 2701872)
date added to LUP
2012-06-07 14:20:58
date last changed
2017-01-01 03:00:36
@article{13a80ffa-d58d-42a1-a601-00f20837336a,
  abstract     = {We describe a state recovery attack on the X-FCSR family of stream ciphers. In this attack we analyse each block of output keystream and try to solve for the state. The solver will succeed when a number of state conditions are satisfied.<br/><br>
For X-FCSR-256, our best attack has a computational complexity of only 2^{4.7} table lookups per block of keystream, with an expected 2^{44.3} such blocks before the attack is successful. The precomputational storage requirement is 2^{33}.<br/><br>
For X-FCSR-128, the computational complexity of our best attack is 2^{16.3} table lookups per block of keystream, where we expect 2^{55.2} output blocks before the attack comes through. The precomputational storage requirement for X-FCSR-128 is 2^{67}.},
  author       = {Stankovski, Paul and Hell, Martin and Johansson, Thomas},
  issn         = {1432-1378},
  keyword      = {stream cipher,FCSR,X-FCSR,cryptanalysis,state recovery},
  language     = {eng},
  number       = {1},
  pages        = {1--22},
  publisher    = {Springer},
  series       = {Journal of Cryptology},
  title        = {An Efficient State Recovery Attack on the X-FCSR Family of Stream Ciphers},
  url          = {http://dx.doi.org/10.1007/s00145-012-9130-9},
  volume       = {27},
  year         = {2014},
}