On 1/10/10 8:41 PM, sascha wrote: > On Sun, Jan 10, 2010 at 05:15:46PM +0100, M vd S wrote: > >> Apart from the optimization, we can also observe that the state >> space converges to 2^64 * (1-84%) before generating the keystream. >> This must also mean that only 16% of 2^64 possible 64 bit keystream >> can exist. I wouldn't know how this can be of value to us right now, >> but it is worth noting. >> > > well it is of great value: our tables need only be 16% the size they were > before. at the cost of 2-3 times more computational effort. > > I aimed at the fact that we will not see all possible 64 bit keystreams in practice. So there's some redundancy hidden in there.
Looking at the last 64 bits of keystream used to cipher the first 114 bits, one in ten combinations don't exist. That's a weakness of the cipher in itself, as if we would know that bits A B and C are always one. Which - if it were that simple - would allow us to say something about the contents of the burst. But it's hard to identify the "impossible" cipherstreams, since they don't necessarily relate to invalid states. Any ideas are welcome. >>> Our keyspace shrinks down to 2^64 * 0.4, provided that we can eliminate the >>> illegal states. 16 extra forward clockings would slow down the table >>> generation by 25%, do you think this would rule out the majority of the >>> illegal states? I think backclocking is out of the question for the table >>> generation, as it would slow down everything too much. >>> >> There is no real need for backclocking to find illegal states. A >> 32kb lookup table will suffice to know if a state can be clocked >> back 6 times (2^(3*6) bits = 2^15 bytes). This would rule out some >> 47% of states as illegal, leaving 37% illegal states alongside 16% >> legal states. This would be a factor 2 improvement at the cost of >> 32kb of memory and a fairly simple lookup. But for bitsliced >> implementations this maybe isn't so easy at all. >> >> Forward clocking to sanitize the state is something I tried, but we >> must be sure that doesn't lead to another subset of state space >> which does not encompass the actual observed state space in >> practice. >> >> Since there is no need to generate keystream for these forward >> clockings, the cost might be slightly less than that for >> keystream-generating clocking. Sanitizing only illegal states by >> forward clocking doesn't sound like a great idea. >> >> >> Simply clocking forward N times modifies the 96 backclock figure as follows: >> N S (96 back illegal states) >> 0 84% >> 1 75% >> 2 72% >> 4 68% >> 8 63% >> 16 53% >> 32 37% >> 64 12% >> 96 0% >> >> defining cpu cost factor as (1+N/64), and table efficiency factor as >> (1-S(N))/(1-S(0)) (so for N=4 we get 32% legal states which is twice >> 16% at N=0, and thus eff.factor=2) >> >> and taking total efficiency as (1-S(N))/(1-S(0)) / (1+N/64), we get: >> N S cpu cost table eff total eff >> 0 84% 1.00 1.00 1.00 >> 1 75% 1.02 1.56 1.54 >> 2 72% 1.03 1.75 1.70 >> 4 68% 1.06 2.00 1.88 >> 8 63% 1.13 2.31 2.06 >> 16 53% 1.25 2.94 2.35 >> 32 37% 1.50 3.94 2.63 >> 64 12% 2.00 5.50 2.75 >> 96 0% 2.50 6.25 2.50 >> > > the extra time needed is > N factor > 32 1.47 > 64 1.89 > 96 2.3 > not xoring, not storing in the extra rounds. > total execution time of a 8192 operations kernel taken as basis. > Thanks. I was thinking that other more powerful optimizations are possible when not saving cipherstream. You could take a lookup table to determine the number of shifts per lfsr, and shift per bunch of places instead of the one-by-one shift you would normally do to get the xorring right. I.e. the exact order of shifting doesn't matter anymore. Anyway. The table now looks like: N S cpu cost table eff total eff 0 84% 1.00 1.00 1.00 1 75% 1.02 1.56 1.54 2 72% 1.03 1.75 1.70 4 68% 1.06 2.00 1.88 8 63% 1.13 2.31 2.06 16 53% 1.25 2.94 2.35 32 37% 1.47 3.94 2.68 64 12% 1.89 5.50 2.91 96 0% 2.30 6.25 2.72 So I would say we should restate our cracking goal from: "a mapping from the internal state of the A5/1 algorithm (64 bits) to the first 64 bits of keystream that get generated from that initial internal state. " to "a mapping from the internal state of the A5/1 algorithm (64 bits) _after the loading of Kc and the frame number_ to the first 64 bits of keystream that get generated from that initial internal state. " i.e. take N=100. For implementation efficiency maybe better take a multiple of 8, so N=92. When cracking, you should then of course still forward N times and then clockback again to find all sibling states leading to the same cipherstream. M. _______________________________________________ A51 mailing list [email protected] http://lists.lists.reflextor.com/cgi-bin/mailman/listinfo/a51
