Hacking GSM A5 crypto algorithm by using commodity hardware
25.10.2016 securityaffairs Mobil

Researchers demonstrated how to crack GSM A5/1 Stream Cipher using a general-purpose graphics processing unit computer with 3 NVIDIA GeForce GTX690 cards.
A group of security researchers from the Agency for Science, Technology and Research (A*STAR), demonstrated that the crypto scheme used in the GSM mobile phone data can be easily hacked within seconds. Actually, it was already known that the A5/1 is vulnerable, at least since 2009.

Weaknesses in crypto algorithms (A3 algorithm for authentication, A5 algorithm for encryption, A8 algorithm for key generation) that were not submitted to peer review due to non-disclosure are the main security issued for 2G implementations.

GSM only authenticates the user to the network and not vice versa. The security model, therefore, offers confidentiality and authentication, but limited authorization capabilities, and has no non-repudiation features. GSM uses several cryptographic algorithms for security. The A5/1 and A5/2 stream ciphers are used for ensuring over-the-air voice privacy. Both algorithms have been exploited:

A5/2 is exploitable with a real-time a ciphertext-only attack
A5/1 with a rainbow table attack.
Main security concerns regarding with GSM are :
Communications and signaling traffic in the fixed network are not protected.
Does not address active attacks, whereby some network elements (e.g. BTS: Base Station)
Only as secure as the fixed networks to which they connect
Lawful interception only considered as an after-thought
Terminal identity cannot be trusted
From a purely technological perspective 3G networks use the KASUMI block crypto instead of the older A5/1 stream cipher, but also KASUMI cipher is affected by several serious weaknesses.

Now the researchers from the A*STAR, Singapore, have demonstrated how to break the A5/1 stream cipher implemented by 2G by using commodity hardware.

“GSM uses an encryption scheme called the A5/1 stream cipher to protect data,” explained Jiqiang Lu from the A*STAR Institute for Infocomm Research. “A5/1 uses a 64-bit secret key and a complex key-stream generator to make it resistant to elementary attacks such as exhaustive key searches and dictionary attacks.”

The researchers have exploited two security weaknesses to compute a look-up table using commodity hardware in 55 days. Once calculated the rainbow table, that has a side of 984GB, they are able to determine the secret key used to encrypt communications in just nine seconds.

The new method improves the classic brute force attack drastically reducing the time required for computation.

“We used a rainbow table, which is constructed iteratively offline as a set of chains relating the secret key to the cipher output,” added Lu.

“When an output is received during an attack, the attacker identifies the relevant chain in the rainbow table and regenerates it, which gives a result that is very likely to be the secret key of the cipher.”

The experts used an equipment composed of a general-purpose graphics processing unit computer with three NVIDIA GeForce GTX 690 cards, for a total cost of about $15,000.

“On a general-purpose graphics processing unit (GPGPU) computer with 3 NVIDIA GeForce GTX690 cards that cost about 15,000 United States dollars in total, we made a unified rainbow table of 984 GB in about 55 days, and implemented a unified rainbow table attack that had an online attack time of 9 s with a success probability of 34 % (or 56 %) when using 4 (respectively, 8) known keystreams (of 114 bits long each).” reads the white paper entitled Time–Memory Trade-Off Attack on the GSM A5/1 Stream Cipher Using Commodity GPGPU in the journal Applied Cryptography and Network Security. “If two such tables of 984 GB were generated, the attack would have an online attack time of 9 s with a success probability of 81 % when using 8 known keystreams. The practical results show again that nowadays A5/1 is rather insecure in reality and GSM should no longer use it.”