A*STAR Singapore shows how easy it is
The crypto scheme applied to second generation (2G) mobile phone data can be hacked within seconds, security researchers have demonstrated.
The work by researchers from the Agency for Science, Technology and Research (A*STAR), Singapore shows that breaking the A5/1 stream cipher used by 2G is possible using commodity hardware.
Security experts have known the A5/1 was breakable since 2009, so what the Singapore team has done is illustrate the ease with which this is now possible, re-emphasizing the need to update remaining 2G-based mobile communications networks.
“GSM uses an encryption scheme called the A5/1 stream cipher to protect data,” said 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.”
Weaknesses in the ageing A5/1 cipher, combined with the improved performance of number-crunching hardware, have rendered the crypto system crackable.
The approach adopted by the Singapore-based researchers is more sophisticated than a vanilla brute force (try every possible combination) attack.
By harnessing two security weaknesses, the boffins were able to compute a look-up table using commodity hardware in 55 days.
Armed with this 984GB rainbow table, determining the secret key used to encrypt communications is possible in as little as nine seconds.
“We used a rainbow table, which is constructed iteratively offline as a set of chains relating the secret key to the cipher output,” Lu explained, phys.org reports.
“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 researchers used a cracking rig made up of a general-purpose graphics processing unit computer with three NVIDIA GeForce GTX 690 cards, costing about $15K.
More details of the research can be found in a 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. ®