Reduced Complexity Attacks on the Alternating Step Generator
In this paper, we present some reduced complexity attacks on the Alternating Step Generator (ASG ). The attacks are based on a quite general framework and mostly benefit from the low sampling resistance of the ASG , and of an abnormal behavior related to
- PDF / 359,900 Bytes
- 16 Pages / 430 x 660 pts Page_size
- 38 Downloads / 180 Views
EPFL, Lausanne, Switzerland FHNW, Windisch, Switzerland
Abstract. In this paper, we present some reduced complexity attacks on the Alternating Step Generator (ASG). The attacks are based on a quite general framework and mostly benefit from the low sampling resistance of the ASG, and of an abnormal behavior related to the distribution of the initial states of the stop/go LFSR’s which produce a given segment of the output sequence. Our results compare well with previous results as they show a greater flexibility with regard to known output of the ASG, which amounts in reduced complexity. We will also give a closed form for the complexity of attacks on ASG (and SG) as presented in [13]. Keywords: Stream Cipher, Clock-Controlled Generator, Alternating Step Generator.
1
Introduction
The Alternating Step Generator (ASG), a well-known stream cipher proposed in [11], consists of two stop/go clocked binary LFSR’s, LFSRX and LFSRY , and a regularly clocked binary LFSR, LFSRC of which the clock-control sequence is derived. The original description of ASG [11] is as follows. At each time, the clock-control bit determines which of the two stop/go LFSR’s is clocked, and the output sequence is obtained as bit-wise sum of the two stop/go clocked LFSR sequences. It is known [13, 8, 12] that instead of working with the original definition of ASG we can consider a slightly different description for which the output is taken from the stop/go LFSR which has been clocked. More precisely, at each step first LFSRC is clocked; then if the output bit of LFSRC is one, LFSRX is clocked and its output bit is considered as the output bit of the generator, otherwise LFSRY is clocked and the output bit of the generator is taken from this LFSR. Since in a cryptanalysis point of view these two generators are equivalent, we use the later one all over this paper and for simplicity we still call it ASG. Several attacks have been proposed on ASG in the literature. Most of these attacks are applied in a divide-and-conquer based procedure targeting one or two of the involved LFSR’s. We will focus on a divide-and-conquer attack which targets one of the two stop/go LFSR’s. A correlation attack on individual LFSRX or LFSRY which is based on a specific edit probability has been introduced in [10]. The amount of required keystream is linear in terms of the length of the targeted LFSR and the correct initial state C. Adams, A. Miri, and M. Wiener (Eds.): SAC 2007, LNCS 4876, pp. 1–16, 2007. c Springer-Verlag Berlin Heidelberg 2007
2
S. Khazaei, S. Fischer, and W. Meier
of the targeted LFSR is found through an exhaustive search over all possible initial states. In [13] some reduced complexity attacks on ASG and SG (Shrinking Generator, see [2]) were presented and the effectiveness of the attacks was verified numerically for SG while only few general ideas were proposed for ASG without any numerical or theoretical analysis. These methods avoid exhaustive search over all initial states, however, the amount of needed keystream is exponential in terms of the leng
Data Loading...
