A5/1 Stream CipherWhile we all concentrate on the core IP network, and which has relatively good protection in the transmission over the air, it is the GSM/3G network that could be at risk. The mobile phone network typically uses the A5/1 or A5/2 stream encryption method, but almost on its first day or operation it has been a target for crackers, and the source code to crack A5/2 was released within one month of being made public. While blocked ciphers like AES are robust, the A5/1 stream cipher has been shown to be weak against certain types of attack. There were two main choices for countries with their encryption: A5/1 and A5/2. A5/2 is intentionally weak, so that nation states can easy crack the cipher, but was cracked generally within a month of it being publicly released. A5/1 was meant to be stronger, but, as it has a relatively short key, it can be cracked with powerful computers. There were two main choices for countries with their encryption: A5/1 and A5/2. A5/2 is intentionally weak, so that nation state can easy crack the cipher. A5/1 was meant to be stronger, but it was quickly cracked once the method had been discovered. |
In this example 114 bits of keystream are generated for the A->B direction (30 hex characters), and then also for the B->A direction. The key is 64-bits long (and needs 16 hex characters) and the frame number is 22 bits long (and can have up to 6 hex characters).
Outline
While we all concentrate on the core IP network, and which has relatively good protection in the transmission over the air, it is the GSM/3G network that could be at risk. The mobile phone network typically uses the A5/1 or A5/2 stream encryption method, but almost on its first day or operation it has been a target for crackers, and the source code to crack A5/2 was released within one month of being made public. While blocked ciphers like AES are robust, the A5/1 stream cipher has been shown to be weak against certain types of attack [2].
There were two main choices for countries with their encryption: A5/1 and A5/2. A5/2 is intentionally weak, so that nation states can easy crack the cipher, but was cracked generally within a month of it being publicly released. A5/1 was meant to be stronger, but, as it has a relatively short key, it can be cracked with powerful computers. Currently there are billions of devices around the world using A5/1 for their security, and it is likely that they can be cracked by the NSA.
With A5/1 we use three shift registers with feedback (Figure 1). With a stream cipher, we often generate an infinitely long key stream which is then EX-OR'ed with the data stream.
In the first shift register the bits at positions 18, 17, 16 and 13 are X-OR'ed together to produce a new bit which is put at the end. This pushes all the bits to move one position to the left. The last bit (the one at Position 18) will then be pushed off and X-OR with the output from the other shift registers. The shift registers are 19, 22 and 23 bits long, thus the key used is 64-bits long (19+22+23). In the diagram the bits 8, 10 and 10 are highlighted, and are the clocking bits. These are examined each cycle. In these are will either be more 1's than 0's or more 0's than 1's. The registers with the most popular bit value will advance their bits, and the other will not advance.
Figure 1: [1]
The algorithm itself was help secret while it was installed in 100 million mobile phones, and was part of the GSM (Global System and Mobile Communications) standard, and has since become a standard with 3G (even though it is seen as weak). The US and Europe adopted the strong A5/1 algorithm, but many selected the weaker one. It was finally made public in August 1999, and within a month the A5/2 method had been cracked. For A5/1 it is thought that the NSA can crack it (as they have the computing power to crack 64-bit keys).
The attack typically use known plaintext attacks, but new ones now allow the cipher stream to be decrypted in real-time. When first proposed, in 1982, it is thought that that the A5/1 key would be 128-bits long, but it finalised ended up with a 64-bit key (which can be cracked on expensive hardware using brute force). It is likely that government pressure forced the key to be much shorter. In fact it is thought that the UK wanted just 48 bits, while the West German government of the time pushed for larger key sizes (as they were worried that the East German government would be able to break their ciphers).
A stream cipher allows for automatic synchronisation, and where each bit can be decoded as it is received.
Practical systems
SRLabs (Security Researh Labs) focus on the capture of data from the mobile phone network and the cracking of A5/1 encryption. They take two encrypted known plaintext messages from the communications, and then use their Kraken utility to find the secret key for a 90% success rate with within seconds, using a set of rainbow tables (40 tables of 2TB in total size) [here].
Gendrullis et al [2] cracked A5/1 within hours using a parallel processing system, but these days NVIDIA GPUs running in the Cloud could achieve the same result, but significantly less expensive.
Conclusion
We talk about 128-bit and 256-bit AES encryption, with 2048-bit and 4096-bit RSA encryption for our corporate networks, but we are still stuck with the 64-bit A5/1 method for our voice and data communications over the mobile phone network. Some think that A5/1 has a key equivalent size of just 56-bits too, but is crackable on a standard desktop. So, in 2013, documents leaked by Edward Snowden states that the NSA decrypt A5/1 cipher streams.
It has been quoted that A5/1 comes from the:
Make stuff up and pray no one sees it
school of cryptography design, which is not good as very little can be kept secret on the Internet. Now the rainbow tables for A5/1 are now available through BitTorrent sites, and the cracking at a PC becomes relatively simple. Mobile phone networks do suffer from many other problems, including the setup of rogue base stations, and get client devices to connect. The network has been protected for years, as it is fairly closed, but it is now coming under fire for its sloppy design procedures.
With the power of the CUDA architecture running on NVIDIA cards, the computing power that only agencies like the NSA could get their hands-on, is now available to anyone with Amazon Cloud accounts. How are we going to move on and change ... well ask everyone to hand-back their mobile phone, and give them a new one ... not going to happen any time soon.
Overall it's another example of a compromised design which matches the computing power of the time, but people forget that computers advance too. The current limits for brute-force is around 72 bits, so a 64-bit key is not really a major challenge.
Code
The code is based on: http://www.scard.org/gsm/a51.html. Here is the C code for the key generator:
/* Do the A5/1 key setup. This routine accepts a 64-bit key and a 22-bit frame number. */ void keysetup(byte key[8], word frame) { int i; bit keybit, framebit; /* Zero out the shift registers. */ R1 = R2 = R3 = 0; /* Load the key into the shift registers, * LSB of first byte of key array first, * clocking each register once for every * key bit loaded. (The usual clock * control rule is temporarily disabled.) */ for (i=0; i<64; i++) { clockallthree(); /* always clock */ keybit = (key[i/8] >> (i&7)) & 1; /* The i-th bit of the key */ R1 ^= keybit; R2 ^= keybit; R3 ^= keybit; } /* Load the frame number into the shift * registers, LSB first, * clocking each register once for every * key bit loaded. (The usual clock * control rule is still disabled.) */ for (i=0; i<22; i++) { clockallthree(); /* always clock */ framebit = (frame >> i) & 1; /* The i-th bit of the frame # */ R1 ^= framebit; R2 ^= framebit; R3 ^= framebit; } /* Run the shift registers for 100 clocks * to mix the keying material and frame number * together with output generation disabled, * so that there is sufficient avalanche. * We re-enable the majority-based clock control * rule from now on. */ for (i=0; i<100; i++) { clock(); } }
A sample run of a known test vector of a key of 0x1223456789ABCDEF and a frame number of 0x000134 gives:
Try 1223456789ABCDEF...key: 0x1223456789ABCDEF frame number: 0x000134 observed output: A->B: 0x534EAA582FE8151AB6E1855A728C00 B->A: 0x24FD35A35D5FB6526D32F906DF1AC0
References
[1] https://en.wikipedia.org/wiki/A5/1
[2] Gendrullis, Timo, Martin Novotný, and Andy Rupp. "A real-world attack breaking A5/1 within hours." Cryptographic Hardware and Embedded Systems–CHES 2008. Springer Berlin Heidelberg, 2008. 266-282.