Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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

Stankovski, Paul LU ; Hell, Martin LU and Johansson, Thomas LU orcid (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
; and
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
2016-04-01 09:48:17
date last changed
2023-08-30 10:10:45
@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}},
  keywords     = {{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          = {{https://lup.lub.lu.se/search/files/1269539/2701873.pdf}},
  doi          = {{10.1007/s00145-012-9130-9}},
  volume       = {{27}},
  year         = {{2014}},
}