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”, Diskretn. Anal. Issled. Oper., 2011, Volume 18, Issue 2,Pages <nobr>51

This article is cited in 2 papers

On reduction of key space of the cipher A5/1 and on reversibility of the next-state function for a stream generator

S. A. Kiselev^a, N. N. Tokareva^ba

^a Novosibirsk State University, Novosibirsk, Russia
^b S. L. Sobolev Institute of Mathematics, SB RAS, Novosibirsk, Russia

Abstract: 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.

UDC: 519.7

Received: 24.06.2010
Revised: 19.02.2011