A5/1 breaks with GPU and Rainbow Tables

[Frank A. Stevenson]

I hope the crosslinking is OK:

http://lists.lists.reflextor.com/pipermail/a51/2010-May/000605.html

Time memory tradeoffs attacks against A5/1, the most commonly used
encryption in GSM, have been known for over a decade. But older
proposals were limited to period hardware. The tables would be a few
tens of gigabytes, and the precomputational effort were restricted to
100-1000 CPU years with PCs of the era. Consequently the plaintext
requirements were impractically high, typically several minutes of
conversation.

The A5/1 TMTO project couples Rainbow tables with modern GPUs, and cheap
terabytes disks or fast flash storage, and gains leverage from "keyspace
compression", a side effect of "warming up" the lfsrs. Recently results
have been announced, in the form of keys recovered from test data,
together with dramatic reduction in preprocessing and plaintext
requirements.

For instance 20 days computation on just one high end graphics card (ATI
Radeon HD 5970) seems to yield 4% chance of key recovery given a single
GSM frame (114 bits) of known plaintext. The tables will be computed to
a height of 2TB in a matter of months, reducing the plaintext
requirements to just a handful of GSM frames.

I should stress that the project has not made an actual intercept
coupled with a break of a GSM call yet. But given how few GSM frames
will be needed, this could be expected in the near term.

Frank A. Stevenson



---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com