Last month at a conference in Japan a group of Israeli mathematicians led by Adi Shamir announced that they had found a way to crack A5/3, the encryption algorithm used to protect the privacy of 3G calls.
Today the same group released the details of the attack, and it’s pretty amazing. Turns out that during the implementation phase in the 3G standard the encryption algorithm was modified to make it faster on hardware. At the time it was thought those modifications would not have affected security but as it turns out it was not the case.
The attack is based on differential cryptanalysis (basically looking for correlations in ciphertext by changing the encryption key, discovered in the 70s by IBM). The way it was implemented by Shamir is a novel approach in differential cryptanalysis called Sandwich attack. Basically instead of looking at the entire block only the beginning and the end (the bread) and a small chunk in the middle (meat) are attacked.
And this technique is proving incredibly effective. If you want to compare with the previous A5/1 attack it’s 3000 times easier (of course it’s not that straightforward but as a term of reference gives you a rough idea).
You can download the original paper here.
