On 1/15/10 6:17 AM, Karsten Nohl wrote: >> http://reflextor.com/trac/a51/wiki/GSMBasics talks about 3 bursts we >> know. >> >> I can't find out where these 3 or 4 bursts of known plaintext >> exactly originate. Have we identified 4 individual bursts of known >> plaintext, or are these connected, in the sense that two bursts are >> a reply to the other? >> > > Bursts always come in groups of four aka a 'packet'. The number of > packets with guessable plaintext is greater than one in all scenarios > I can think of. But, even a few bit errors make the packet unusable > for our purposes; so I'm conservatively assuming that we capture only > one error-free packet. > > clear.
>> If so, two strings of 114 bits cipher are generated from one state, >> one for the burst BTS-->MS and one for the way back. >> >> Since in between appearantly nothing happens to the cipher, I'm >> tempted to think that for 4 bursts (2 up, 2 down) we have >> 2*((2*114)-63)=330 chances of finding a 64 bit keystream. >> > > Each packet is produced under a different session key, which then > encrypts the four bursts. The key streams of these bursts are > separated by idle clocking, however, leaving separate 114 bits > Do we have exact information on this? I've seen several explanations. Let's try to get the picture complete, this is just a suggestion: clock_in(Kc,64) clock_in(FN,22) clock(100) KS1 = clock_out(114) (downlink) clock(100) KS2 = clock_out(114) (uplink) clock(100) KS3 = clock_out(114) (downlink) clock(100) KS4 = clock_out(114) (uplink) ?? where downlink = BTS --> MS. Uplink is harder to capture than downstream - I presume because the antenna on the BTS is of somewhat higher quality and easier to pinpoint. http://en.wikipedia.org/wiki/A5/1 doesn't say that KS3 and KS4 are generated from this state, and does say there is no idle clocking between KS1 and KS2. An older paper I read (sorry, no link) mentioned 100 idle clockings - but that was in the days that they hadn't confirmed yet that the description of a5/1 was correct. This all is of interest because of the size of the keyspace. After 100+(114+100)*n, not much of it is left. There could be an optimum post-N-round part of keyspace to aim for. If someone could confirm the scheme above, I'll try to provide the numbers. If the picture above were correct, we could maybe better focus on post-528 round space which is <4%, so 4 times smaller than post-100 round space. > segments of key stream for all practical matters. Furthermore, we > don't assume we can capture the uplink error free. (We can decode the > upstream and run the error correction, however, once we have the key). > > clear. These are important points which should be put on the wiki when sorted out. >> === attack time === >> >> The (CPU) attack time is calculated as if the distribution of >> keystreams we encounter is random. It isn't. There are preferred >> states. The same goes for our new tables. I don't dare to give an >> exact estimation, but if the time is more than halved I wouldn't be >> surprised. >> > > Most of the time is spent on computing lookups that never lead to a > result. In fact, millions of chains worth of lookups are computed > until one hits. I believe that cancels the effect you are describing. > > I was aiming at the S (keystream segments) in the formula: T= S * n * k(k+1)/2 * l This worst-case formula presumes that you'll have to process all keystream segments before finding a hit. I'm saying that keystream segments at the far end have a higher probability of turning up in our tables. (and although you can do parallel processing, you would still focus on one segment at the time since there's enough parallel work for that (namely: n*k(k+1)/2) But I realized only now that you're actually calculating the worst-case T, where I'm thinking about the expected T, which is way less than maxT/2. (same holds for HD seeks) Regards, M. _______________________________________________ A51 mailing list [email protected] http://lists.lists.reflextor.com/cgi-bin/mailman/listinfo/a51
