The A5/1 algorithm is one of the ciphers used in GSM networks. It is used to encrypt both voice and signaling data.
In the GSM network, A5/1 is applied both in the handset and the BTS on the corner of the network. The first phase of communication including radio resource allocation and authentication is unencrypted. Dialing and voice is encrypted.
Take a look at the wikipedia page for more information, or view the discussion on Backclocking A5/1 for a comprehensive discussion of A5/1.
The table that is generated is a kind of rainbow table. These data structures can be used to reverse one way functions. The one way function that we are trying to reverse is:
a mapping from the internal state of the A5/1 algorithm (64 bits) to the first 64 bits of keystream that get generated from that initial internal state.
This is because we have access to a few samples of 64 bits of keystream an can, through a number of steps, decrypt the entire conversation when we know the A5/1 state of one burst.
The reduction function is a mapping from the 64 bits of keystream to a new state. the last keystream is shifted into the state registers unmodified and it is not actually reduced in size.
This image shows the distribution of 5.6 million end values from one of our tables. since the picture is 1 million pixels large, each pixel represents 264 - 220 = 244 values of the keyspace. While the picture clearly shows random noise in the view from far above the keyspace, there may be other pictures at different zoom levels or with different coordinate systems that show structures.
Updated by Karsten almost 11 years ago ยท 3 revisions