A structural analysis of the A5/1 state transition graph

Andreas Beckmann
(Goethe-Universität Frankfurt)
Jaroslaw Fedorowicz
(Goethe-Universität Frankfurt)
Jörg Keller
(FernUniversität in Hagen)
Ulrich Meyer
(Goethe-Universität Frankfurt)

We describe efficient algorithms to analyze the cycle structure of the graph induced by the state transition function of the A5/1 stream cipher used in GSM mobile phones and report on the results of the implementation. The analysis is performed in five steps utilizing HPC clusters, GPGPU and external memory computation. A great reduction of this huge state transition graph of 2^64 nodes is achieved by focusing on special nodes in the first step and removing leaf nodes that can be detected with limited effort in the second step. This step does not break the overall structure of the graph and keeps at least one node on every cycle. In the third step the nodes of the reduced graph are connected by weighted edges. Since the number of nodes is still huge an efficient bitslice approach is presented that is implemented with NVIDIA's CUDA framework and executed on several GPUs concurrently. An external memory algorithm based on the STXXL library and its parallel pipelining feature further reduces the graph in the fourth step. The result is a graph containing only cycles that can be further analyzed in internal memory to count the number and size of the cycles. This full analysis which previously would take months can now be completed within a few days and allows to present structural results for the full graph for the first time. The structure of the A5/1 graph deviates notably from the theoretical results for random mappings.

In Anton Wijs, Dragan Bošnački and Stefan Edelkamp: Proceedings First Workshop on GRAPH Inspection and Traversal Engineering (GRAPHITE 2012), Tallinn, Estonia, 1st April 2012, Electronic Proceedings in Theoretical Computer Science 99, pp. 5–19.
Published: 23rd October 2012.

ArXived at: http://dx.doi.org/10.4204/EPTCS.99.4 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org