Abstract
A5/1 is the strong version of the encryption algorithmon GSM (Global System for Mobile communications) used inmany countries. It is constructed of a combination of threeLFSRs (Linear Feedback Shift Registers) with irregular clockingmanner. One of the most practical attacks against this algorithmis time-memory trade-off attack, which is based on birthdayparadox. The goal of this attack is to find any intersectionbetween precomputed LFSRs states set and set of statesgenerating the output bits in the actual execution of thealgorithm. In order to increase feasibility of this attack, thebiased birthday attack was introduced. In this attack specialstates producing a specific pattern in output bits are sampled andonly a fraction of the special states with higher probability ofoccurrence are stored. By using a 16-bit pattern of data there are248 parallelizable preparation stages. This attack requires about150 GB of memory and two minutes of conversation. Under theseconditions, the probability of collision is about 0.61. In this paperan improvement in the collision probability is introduced withoutchanging the available memory capacity and duration ofconversation. Our approach is based on using multiple datapatterns instead of using a single one. This approach leads toincrement of the preprocessing and the collision probability. It isshown that there is a trade-off between the collision probabilityand the preprocessing complexity.Keywords-stream cipher; A5/1; time memory tradeoff attack;birthday paradox
I. INTRODUCTION
A5/1 is a stream cipher algorithm used to encrypt theconversation in GSM (Global System for Mobilecommunications) in many countries. This algorithm consists ofthree LFSRs (Linear Feedback Shift Registers) that are clockedin a stop/go manner [5]. Because these LFSRs have a shortlength and the clocking control bits are placed approximately inthe middle of each LFSR, the algorithm is vulnerable againstmany kinds of attacks like time-memory tradeoff attacks [1],[2] and [4].Time-memory tradeoff attack is based on birthday paradox,in which the goal of cryptanalysis is to find any intersectionbetween states of the LFSRs happening in the actualconversation and the states stored in the memory at thepreprocessing phase.Eli Biham et al. [1] published an attack on A5/1. The mainidea of their attack is to wait until an event occurs, which leaksa large amount of information about the key. This event is onewhich the largest register does not clock for 10 cyclesconsecutively while the others clock. Although this methodreduces complexity, the attacker has to wait until this eventoccurs since the attack is based on a special event.In [4], Golić presented a time-memory tradeoff attackagainst A5/1. The time complexity and computationalcomplexity of the attack is so large that they make it infeasibleto run on a regular PC (Personal Computer).In [2], Biryukov et al. presented an improvement to theGolić's time-memory tradeoff attack and named it biasedbirthday attack. In this method, the data stored in memory arenot selected with uniform probability, but they are chosen insome way to increase the intersection probability betweenoccurred states of the LFSRs and the states stored in thememory. In Golić's time-memory attack [4] all of the observedstates should be probed in the memory. Because the access todisk is a time consuming task, the needed time for Golić’sattack makes it impractical. In the biased birthday attack [2], inorder to increase the feasibility of the attack only the states thatproduce a certain pattern α at the beginning of the output bitsare stored in the memory. In the attack phase, we only probe inthe memory when encountering the pattern α in the bit stream.Based on the weakness of the structure of A5/1, placing thecontrol taps in the middle of registers, these kinds of states canbe extracted without trial and error method.In [2], it is shown that by using one pattern α and storing235 of the most probable states the probability of collision isabout 0.6. In our approach, in order to improve this probabilitywe use multiple patterns of α. In our method the neededmemory and conversation are unchanged, but the preprocessingstages and time of attack are increased. In the proposedapproach, it is shown that there is a tradeoff betweenprobability of collision, preprocessing time, and attack time.This paper is organized as follows. In section 2, A5/1algorithm is described briefly. The biased birthday attack,which was proposed in [2], is presented in section 3. Ourproposed scheme, which is utilizing multiple patterns of α, isgiven in section


Download full report
http://ieeexplore.ieeeiel5/5477033/54833...er=5483496