On Jan 15, 2010, at 4:26 AM, M vd S wrote: > On 1/15/10 1:59 AM, Karsten Nohl wrote: >> Number of tables * tables height = 2 TB >> or: n * h * k * 2^l = 2^37 >> => k * l = 2^17.62 >> >> > a few preliminary remarks: > > === storage === > > A hidden parameter here, which isn't listed explicitly in the sheet, > is the amount of storage per chain.
Added this parameter for chain unit size to the Excel. > 2 TB equates to 2^37 chains, so it appears to be 2^4 bytes or 128 > bits - sounds like a start and an end value, of both 64 bits. > > I thought that even in the current tables they are smaller, and > discussions have had place which led to the conclusion that it > should be possible to store: > - only 24 bits of end value (that's 64 bits minus 15 DP zeroes minus > 25 bits of index - the current practice) > - only 30 bits of start value (when mapping an index value through > some start-value generator, where in this case 2^30 should cover the > number of chains, including dropped merges since they have taken up > one index value) > > for a total of 54 bits per chain, or 4.7 Gb for 750m table height > (with less than 250m chains dropped through merges, else add 1 bit). > That would lead to 851 Gb tables total instead of 2 TB. > > (plus the index, which can be cracked down to negligible size) > > === cracking === > > The number of keystream segments is listed in the sheet as > 4*(144-63). (This looks like it should read 114 instead of 144 to > get the familiar 4*51=204 figure.) corrected. > 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. > 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 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). > === 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. > And always start searching from the end of the keystream, it more > than doubles chances of finding a hit. Cheers, -Karsten _______________________________________________ A51 mailing list [email protected] http://lists.lists.reflextor.com/cgi-bin/mailman/listinfo/a51
