|
|
|
|
|
|
|
|
|
|
|
|
| home | help | back | first | fref | pref | prev | next | nref | lref | last | post |
To: cryptography@c2.net From: iang@cs.berkeley.edu (Ian Goldberg) Date: 14 Apr 1998 15:44:26 GMT In article <v03110700b158a9585073@[207.94.249.206]>, Bill Frantz <frantz@netcom.com> wrote: >At 5:03 PM -0800 4/13/98, Marc Briceno wrote: >>On Mon, 13 Apr 1998, Steve Bellovin wrote: >>> The attack as carried out requires physical access to the SIM. It's >>> an open question if an active attack -- that is, with a radio transmitter >>> impersonating a base station -- would succeed. A critical question is >>> the rate at which challenges can be sent -- given the timing, it's >>> probably not practical except by concerted attack. >> >>Since I am not a radio engineer, I would love to hear the opinion of >>someone who is. How fast could a rogue base station collect challenge >>resonse pairs? > >At 4:53 PM -0800 4/13/98, Steve Bellovin wrote: >>The attack requires over 4000 challenge/response pairs; using the >>hard-wired reader, that took 8 hours. There's a quadratic factor >>in there, so the probability of a break is not linear in the time >>spent. > >My question is how many challenge/response pairs are needed to pare the >keysize down enough to make brute force a reasonable attack? Actually, the quadratic factor is in the precomputation required to build a certain table. But we've finished that, so it's irrelevant now. Here's what the break requires, to a first approximation: o Posession of a SIM, hooked up to a smartcard reader o Expected 175000 chosen queries to the SIM, performing trivial work on the results. (We can query the SIM we've got at 6.25 per second, which works out to a little under 8 hours.) o Expected 2^15 brute force queries to the COMP128 algorithm. (We can do about 7000 per second on a single PC, which works out to about 5 seconds.) The last two numbers have a limited tradeoff: for every expected reduction of 25000 queries in the first phase, you multiply the brute force phase by 2^16. This means that you can reduce the amount of time you need to be holding the SIM to under 7 hours if you spend 85 hours bruting in the second phase (but note that the second phase is parallelizable). The above assumes that the key in the SIM is a "weak" key for COMP128. Luckily, over 90% of keys are weak. If the GSM providers were to clue in and only choose the strongest keys, it would require (I'm not positive about this) expected 1.4M queries and a 38-bit bruting. (Of course, they could do other things, too, like limit the number of times or the rate at which the SIM can be queried, and whatnot, or just use a better hash function. Note that that's all COMP128 was supposed to be: a hash function, not encryption. It turned out to have frequent collisions, and that's what we exploited.) See http://www.isaac.cs.berkeley.edu/isaac/gsm.html for more info. - Ian queries
|
|
|
|
|
|
|
|
|
|
|
|
| home | help | back | first | fref | pref | prev | next | nref | lref | last | post |