Friday, August 8, 2008

Long Tail of Vulnerability for A5/1

Stream ciphers are a special class of cipher, often used for fast encryption of data streams such as dedicated network links or fax lines. Stream ciphers produce a key stream that is simply added (XOR-ed) with the data stream to produce ciphertext, and as such can achieve high encryption rates especially if implemented in hardware.

Below is a diagram of the A5/1 stream cipher, invented in 1987 to protect GSM voice and data traffic. A5/1 loads a 64-bit secret key into its 3 shift registers, which are then clocked and combined with a frame vector to produce an initial state. A5/1 is then clocked as required to produce keystream bits to encrypt the next 114 bit GSM frame.

For over 10 years theoretical attacks on A5/1 have been postulated that lower the cost of attack significantly over searching the 64-bit key space directly. Amongst cryptographers and mobile security people, A5/1 is considered to be insecure and its 64-bit key size woefully inadequate by today's standards.

In February David Hulton, director of applications for the high-performance computing company Pico, and Steve Muller, a researcher for mobile security firm CellCrypt, announced new results which claim that A5/1 keys can be recovered in 30 minutes for $1000. The attack is both passive (no network injection or basestation masquerading) and can be executed remotely (no proximity to the target device required). Further, Hulton & Muller (H&M) are patenting their optimizations and intend to sell an A5/1 key recovery tool commercially. Cell call snooping may soon be affordable by many groups and people, not just well-resourced intelligence agencies.

The attack is based on pre-computing rainbow tables that enable the direct "lookup" of A5/1 keys when indexed by a small amount of observed traffic (3 to 4 GSM frames). While it remains impractical to create a rainbow table that has one entry for each each of the possible 2^(64) A5/1 keys, H&M have devised a method that only requires a table of size 2^(58). Dedicated FPGA devices are currently being deployed to speed up the required rainbow table computations, and are expected to be completed by the end of March. By way of comparison, it is estimated that attempting the same computation on a lone PC would take 33 thousand years.

The resulting rainbow tables will be several terabytes in size, and will be made available to the public. H&M also intend to sell a fast cracking version of the software that can break GSM encryption in just 30 seconds, charging between $200,000 and $500,000 for this privilege. Perhaps they will also offer service of recovering of GSM keys based on submitted traffic samples, giving rise to a instance of cryptanalysis-as-a-service (CaaS).

While researchers and security professionals view the H&M approach as cheaper and more efficient than previous attacks, the attack itself comes as no surprise given the known weaknesses of A5/1. The practicality of the H&M approach should be the final piece of evidence to convince operators to move off A5/1 as a basis for secure and private for GSM communication. David Pringle, a spokesperson for the GSM Association (GSMA), has declined to comment on the H&M attack until further details are known.

A5/1 has operated unchanged for the last 21 years but it has now reached its cryptographic end-of-life, engulfed by the march of Moore's Law. However, the operational end-of-life of A5/1 may still be decades away as there are approximately 2 billion GSM subscribers, commanding about 80% of the global mobile market. This would be a tough product recall indeed. A5/1 is well-positioned to become the NT of the mobile crypto world, and I see the makings of a long tail of GSM vulnerability.

You can find the research used to produce this post as a FreeMind mindmap rendered into Flash here.

Related Posts


olj said...

If you look at people using cell phones in public space, it seems that they even there don't care who is listening in. So encrytion is most likely not needed for them.
But if you're more concerned, this means that simple controls (using closed space) are no longer sufficient. Finally we might need additional products to ensure our message privacy.

ac3bf1 said...

What happend to the tables?
project seems to have been "hijacked"


Dr. Luke O'Connor said...

Hi John, I have not heard any announcements. Maybe google knows


ac3bf1 said...

google seems to be unaware of any terabyte-sized rainbow tables for A5...

Dr. Luke O'Connor said...

I will the main author an email


Dr. Luke O'Connor said...

send me your email and I can cc you

I would be sending to


akalili said...

how to improve the vulnerability of A5/1 Stream cipher?

boy labyog said...

very interesting thanks for posting,how cellphone give traffic to us?

Laby[big suits for men]

Fikri Ferdiansyah said...

I think more updates and will be returning. I have filtered for qualified edifying substance of this calibre all through the past various hours.
Cara Tepat Merawat Jantung Agar Tetap Sehat Cara untuk Menyembuhkan Penyakit Kudis Obat Multiple Sclerosis (MS) Herbal Obat Impetigo Cara Mengobati Penyakit Herpes Zoster

adelia lia said...

Thank you for another wonferdul article. Where else could anyone ge t t ha t kind of information in such an ideal way of writing? I have a presenta tion next week, and I am on the look for such information.

Adeline Niesha said...

I know where I'm going and I know the truth, and I don't have to be what you want me to be. I'm free to be what I want.Thankyou i really love it

Michael Husen said...

Thank you for another oondorful article. where else could anyone ge t t ha t kind of information in such an ideal way of writing? I have a presentation next week, and I am on the look for such information.

Syka ika said...

I really liked this part of the article, with a nice and interesting topics have helped a lot of people who do not challenge things people should know... you need more publicize this so many people who know about it are rare for people to know this, Success for you. . . . . . . ....

Syka ika said...

Thanks for sharing that AVG 2016 |AVG 2016 | AVG 2016AVG 2016 |AVG 2016 | AVG 2016AVG 2016 |AVG 2016 | AVG 2016AVG 2016 |AVG 2016 | AVG 2016

El Taufan said...

Thanks for Sharing That... Sucses for You