[A51] Cracks beginning to show in A5/1...

Frank A. Stevenson frank at hvitehus.no
Sat May 1 15:06:26 CEST 2010


We have had very good progress with table computation and lookup on ATI
cards lately. Currently we have found 40 keys from frames in a test set
of 1000 frames. The test set have been generated the same way that
keystream for the GSM downlink is generated, with the exception of the
mixing stages. Random keys are take from /dev/urandom and clocked, 100
bits are discarded, and 114 bits are output to disk. The key is then
thrown away, so that the only way to recover it is by cracking A5/1.

Each "hit" will actually produce several candidates. I have placed a
complete list here, which will be updated as more tables are added:

http://traxme.net/a5/found2.txt

Tools for verifying the results have also been made:
tmto-svn/tinkering/A5Util (just run make here)

For instance from found2.txt :

#### Found potential key (bits: 1)####
e1db7f766893b1e4
#### Stepping back to mix ####
cb5c26fa821c8cbb -> cb5c26fa821c8cbb
Candidate: 1c3b6eecd12f63c9
Candidate: 3876df76689763c9
Candidate: 1c3b6f76689763c9
### Frame is 908 ###

Means that frame 908 was "cracked", the keystream can be found:

frank at quant:~/gsm/tmto-svn/tinkering/A5Util$ ./extract 908
0e 0f da e0 df e2 47 7a 74 38 9f 8e c0 ef c0 

The keystream matched from "bit 1" (i.e. the second bit and 64 bits
forwards). The candidates can be inspected this way:

frank at quant:~/gsm/tmto-svn/tinkering/A5Util$ ./simpletest 1
e1db7f766893b1e4
Start: e1db7f766893b1e4
Stepping back 100 + 1 ticks.
cb5c26fa821c8cbb
cb5c26fa821c8cbb -> cb5c26fa821c8cbb
Candidate: 1c3b6eecd12f63c9
Candidate: 3876df76689763c9
Candidate: 1c3b6f76689763c9
1c3b6f76689763c9
0e 0f da e0 df e2 47 7a 74 38 9f 8e c0 ef c0 
3876df76689763c9
0e 0f da e0 df e2 47 7a 74 38 9f 8e c0 ef c0 
1c3b6eecd12f63c9
0e 0f da e0 df e2 47 7a 74 38 9f 8e c0 ef c0 

The first argument to simpletest is the bit offset, and the second is
the key(state) after the mixing stage. The program then clocks forwards
100 bits to where the cipherstream output matches, and back 100+bits to
find the possible candidates, and then prints the output cipherstream
for each candidate in turn. As can be seen in this example, all 3
candidate keys produce the same keystream.

This is a pretty exciting development, and I think that it is now time
to shift more of our efforts over on the airprobe project. Without the
ability to capture known plaintext from the air interface, our tables
will just be useless piles of random bits :-)

cheers,

Frank A. Stevenson




More information about the A51 mailing list