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. 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.) 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? 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. === 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. And always start searching from the end of the keystream, it more than doubles chances of finding a hit. Regards, M. _______________________________________________ A51 mailing list [email protected] http://lists.lists.reflextor.com/cgi-bin/mailman/listinfo/a51
