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 majord...@metzdowd.com