A generalized birthday approach for efficiently finding linear relations in l-sequences
Wang, Hui ; Stankovski, Paul LU and Johansson, Thomas LU
(2015)
In Designs, Codes and Cryptography
74(1).
p.41-57
- Abstract
- Feedback with carry shift registers (FCSRs) have previously been available in two configurations, the Fibonacci and Galois architectures. Recently, a generalized and unifying FCSR structure and theory was presented. The new ring FCSR model repairs some weaknesses of the older architectures. Most notably, the carry cell bias property that was exploited for an attack on the eSTREAM final portfolio cipher F-FCSR-H v2 is no longer possible for the updated (and unbroken) F-FCSR-H v3 stream cipher. In this paper we show how to exploit a particular set of linear relations in ring FCSR sequences. We show what biases can be expected, and we also present a generalized birthday algorithm for actually realizing these relations. As all prerequisites of... (More)
- Feedback with carry shift registers (FCSRs) have previously been available in two configurations, the Fibonacci and Galois architectures. Recently, a generalized and unifying FCSR structure and theory was presented. The new ring FCSR model repairs some weaknesses of the older architectures. Most notably, the carry cell bias property that was exploited for an attack on the eSTREAM final portfolio cipher F-FCSR-H v2 is no longer possible for the updated (and unbroken) F-FCSR-H v3 stream cipher. In this paper we show how to exploit a particular set of linear relations in ring FCSR sequences. We show what biases can be expected, and we also present a generalized birthday algorithm for actually realizing these relations. As all prerequisites of a distinguishing attack are present, we explicitly show a new such attack on F-FCSR-H v3 with an online time complexity of only 2^{37.2}. The offline time complexity (for finding a linear relation) is 2^{56.2}. This is the first successful attack on F-FCSR-H v3, the first attack to breach the exhaustive search complexity limit. Note that this attack is completely different from that of F-FCSR-H v2. We focus on this particular application in the paper, but the presented algorithm is actually very general. The algorithm can be applied to any FCSR automaton, so linearly filtered FCSRs and FCSR combiners may be particularly interesting targets for cryptanalysis. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/4193615
- author
- Wang, Hui
; Stankovski, Paul
LU
and Johansson, Thomas
LU
- organization
- publishing date
- 2015
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- FCSR, Linear relations, Generalized birthday attack, Distinguisher
- in
- Designs, Codes and Cryptography
- volume
- 74
- issue
- 1
- pages
- 41 - 57
- publisher
- Springer
- external identifiers
-
- wos:000347692400004
- scopus:84921068548
- ISSN
- 1573-7586
- DOI
- 10.1007/s10623-013-9845-0
- language
- English
- LU publication?
- yes
- id
- f4ad7961-65a4-4760-b61f-9924c67d3676 (old id 4193615)
- date added to LUP
- 2016-04-01 09:49:54
- date last changed
- 2023-08-30 10:54:59
@article{f4ad7961-65a4-4760-b61f-9924c67d3676,
abstract = {{Feedback with carry shift registers (FCSRs) have previously been available in two configurations, the Fibonacci and Galois architectures. Recently, a generalized and unifying FCSR structure and theory was presented. The new ring FCSR model repairs some weaknesses of the older architectures. Most notably, the carry cell bias property that was exploited for an attack on the eSTREAM final portfolio cipher F-FCSR-H v2 is no longer possible for the updated (and unbroken) F-FCSR-H v3 stream cipher. In this paper we show how to exploit a particular set of linear relations in ring FCSR sequences. We show what biases can be expected, and we also present a generalized birthday algorithm for actually realizing these relations. As all prerequisites of a distinguishing attack are present, we explicitly show a new such attack on F-FCSR-H v3 with an online time complexity of only 2^{37.2}. The offline time complexity (for finding a linear relation) is 2^{56.2}. This is the first successful attack on F-FCSR-H v3, the first attack to breach the exhaustive search complexity limit. Note that this attack is completely different from that of F-FCSR-H v2. We focus on this particular application in the paper, but the presented algorithm is actually very general. The algorithm can be applied to any FCSR automaton, so linearly filtered FCSRs and FCSR combiners may be particularly interesting targets for cryptanalysis.}},
author = {{Wang, Hui and Stankovski, Paul and Johansson, Thomas}},
issn = {{1573-7586}},
keywords = {{FCSR; Linear relations; Generalized birthday attack; Distinguisher}},
language = {{eng}},
number = {{1}},
pages = {{41--57}},
publisher = {{Springer}},
series = {{Designs, Codes and Cryptography}},
title = {{A generalized birthday approach for efficiently finding linear relations in l-sequences}},
url = {{https://lup.lub.lu.se/search/files/1297948/4193616.pdf}},
doi = {{10.1007/s10623-013-9845-0}},
volume = {{74}},
year = {{2015}},
}