Geodesic
On reduction of key space of the cipher A5/1 and on reversibility of the next-state function for a stream generator
Diskretnyj analiz i issledovanie operacij, Tome 18 (2011) no. 2, pp. 51-63 
S. A. Kiselev; N. N. Tokareva. On reduction of key space of the cipher A5/1 and on reversibility of the next-state function for a stream generator. Diskretnyj analiz i issledovanie operacij, Tome 18 (2011) no. 2, pp. 51-63. http://geodesic.mathdoc.fr/item/DA_2011_18_2_a4/
@article{DA_2011_18_2_a4,
     author = {S. A. Kiselev and N. N. Tokareva},
     title = {On reduction of key space of the cipher {A5/1} and on reversibility of the next-state function for a~stream generator},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {51--63},
     year = {2011},
     volume = {18},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2011_18_2_a4/}
}
TY  - JOUR
AU  - S. A. Kiselev
AU  - N. N. Tokareva
TI  - On reduction of key space of the cipher A5/1 and on reversibility of the next-state function for a stream generator
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2011
SP  - 51
EP  - 63
VL  - 18
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DA_2011_18_2_a4/
LA  - ru
ID  - DA_2011_18_2_a4
ER  - 
%0 Journal Article
%A S. A. Kiselev
%A N. N. Tokareva
%T On reduction of key space of the cipher A5/1 and on reversibility of the next-state function for a stream generator
%J Diskretnyj analiz i issledovanie operacij
%D 2011
%P 51-63
%V 18
%N 2
%U http://geodesic.mathdoc.fr/item/DA_2011_18_2_a4/
%G ru
%F DA_2011_18_2_a4

Voir la notice de l'article provenant de la source Math-Net.Ru

We study stream ciphers based on feedback shift registers. For a stream generator (in general form) we prove that reversibility of its next-state function is closely connected to the recurrency of the shift control function. Then we study generator for the stream cipher А5/1 used in GSM cellular telephone standard. For this generator we count the number of states that can be obtained after $t$ cycles from an initial state without predecessors and cannot be obtained in this way after the smaller number of cycles. We show how to exponentially reduce the key space of A5/1 while clocking. The results can be directly used in cryptanalysis of A5/1. Ill. 5, tab. 1, bibliogr. 8.

[1] Kiselëv S. A., “O sokraschenii klyuchevogo prostranstva potochnogo shifra A5/1 pri taktirovanii”, Prikl. diskret. matematika, 2010, prilozhenie No 3, 21–23

[2] Anderson R., Subject: A5, posting to Newsgroups: sci.crypt, alt.security, uk.telecom, 17 June 1994

[3] Biryukov A., Shamir A., Wagner D., “Real time cryptanalysis of A5/1 on a PC”, Fast Software Encryption Workshop, FSE' 2000 (New York, April 10–12, 2000), Proc., Lect. Notes Comput. Sci., 1978, Springer–Verl., Berlin, 2001, 1–18 | Zbl

[4] Chambers W. G., “On random mappings and random permutations”, Fast Software Encryption Workshop, FSE' 1994 (Leuven, December 14–16, 1994), Proc., Lect. Notes Comput. Sci., 1008, Springer-Verl., Berlin, 1995, 22–28 | Zbl

[5] Golic J., “Cryptanalysis of alleged A5 stream cipher”, Adv. Cryptology, Workshop on the theory and application of cryptographic techniques EUROCRYPT' 97 (Konstanz, May 11–15, 1997), Proc., Lect. Notes Comput. Sci., 1233, Springer-Verl., Berlin, 1997, 239–255 | MR

[6] Semenov A., Zaikin O., Bespalov D., Posypkin M., Parallel algorithms for SAT in applocation to discrete functions inversion problems, arXiv: 1102.3563v1

[7] Shepherd S. J., “Cryptanalysis of the GSM A5 cipher algorithm”, IEEE Colloquium on Security and Cryptography Applications to Radio Systems, Digest No. 1994/141 (Savoy Place, London, June 3, 1994)

[8] Wagner D. et al., “The real-time cryptanalysis of A5/2”, Crypto' 99 (Santa Barbara, August 15–19, 1999), Proc., Springer-Verl., Berlin, 1999, 12–21