An Efficient State Recovery Attack on the X-FCSR Family of Stream Ciphers
(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:
https://lup.lub.lu.se/record/2701872
- author
- Stankovski, Paul LU ; Hell, Martin LU and Johansson, Thomas LU
- organization
- publishing date
- 2014
- 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}}, }