Re: [A51] 5.6x efficiency increase by removing illegal states

[M vd S]

On 1/12/10 10:39 AM, sascha wrote: Clocking forward 100 times opens up 12 alternative pathways on average, so there's ways around this. In 2.7% of cases (see above) you would hit on the exact state you came from. In other cases there's a chance to get around the illegal state. So this chance is small*small. With reference to the mail I sent yesterday, this is also a method to get even more states which in the end generate the same keystream: clock forward 101 times, clock back 1 time into another path while checking if the same bit of keystream had been generated. With roughly a 5% chance of finding more states leading to the same keystream. (and do the same clocking forward 100+N times for N=2..16 to get even more sibling states) If you start from a random state and do the above in a loop with N->large, (i.e. as much keystream as we have in a burst) how many "connected" states are you going to find producing the same keystream? This is the data we need to explain the number of mergers observed at the present time as well. I tested clocking forward N times and back N again. Then taking keystream and comparing to expected keystream. Tested as well: clocking forward N+1 and N back, and fw N and N+1 back. In theory this could work, but in practice it never happens. N=1, S=100k #siblstates    #F/B    #F/B+-1 0    0    100000 1    40819    0 2    18841    0 3    27842    0 4    12498    0 AVG:    2.12    0.00 (This said: there were 12498 states which had 4 siblings (i.e. 3 *other* states) generating the same keystream) N=4, S=100k #siblstates    #F/B    #F/B+-1 0    0    100000 1    37358    0 2    12330    0 3    31909    0 4    14200    0 5    2862    0 6    799    0 7    479    0 8    24    0 9    21    0 10    18    0 AVG:    2.38    0.00 N=16, S=100k #siblstates    #F/B    #F/B+-1 0    0    100000 1    37266    0 2    12514    0 3    30986    0 4    14392    0 5    2991    0 6    1005    0 7    670    0 8    70    0 9    58    0 10    29    0 11    5    0 12    8    0 13    3    0 14    1    0 15    1    0 24    1    0 AVG:    2.40    0.00 N=32, S=1M #siblstates    #F/B 1    371043 2    125978 3    310892 4    144587 5    29438 6    9898 7    6293 8    765 9    573 10    405 11    28 12    60 13    14 14    6 15    14 16    5 25    1 AVG:    2.40 (numbers are stable) Note that the #siblstates includes the original state as well. So it seems like a viable strategy for cracking, giving 2.4 times the chance of hitting on the actual state you're looking for. And appearantly the 64 bit keystream space of a purely random state is 2.4 times smaller than 2^64. Now we have the numbers, who wants to do the math? A first attempt: A chain with 32k values has 79k state values which may collide with another chain's 32k values. That's a 79k/2^64 = 4.3e-15 chance per chain value, or roughly 1.4e-10 chance of chain-chain collision. (see figure for real world data) With 1 Gchain, the number of chain combinations is 1G*1G/2. The expected number of collisions per such combination is 1.4e-10. The expected number of collisions is then 1.4e-10*1G*1G/2 = 80M, or 1.4e-10*1G*1G/2/1G = 7.5%. Considering that a chain merger finds it's origin in "degenerate" states, we can also say that a chain with 32k values has 79k-(37%*32k)=67k values which may collide with another chain's 32k values*. That would give 6.3% collisions. The observed value is between 4.5 and 5%. *of course of those 32k values only (1-37.1%)=63% are related to a degenerate state, which would lower the figure to 4.0%. And the convergence due to the fact that 2^64/2.4 states can only generate 2^64/2.4 possible new states is not taken into account as well. The linear relation observed in the plot I sent yesterday at least follows from this analysis as well. The chain-chain collision probability (assuming *that* part of the analysis can hardly be wrong) of Sacha's data looks like: P[merge ch-ch] = %merge * 2 / numch Not sure if I see an upward trend here. === For 100-forward clocked valid states, the numbers are different. The average starts at 1.6 for N=1 and converges to 1.82 for N=16 and N=32. So the number of ancestor states leading to the same keystream after 100 clocks now amounts to some 1.8*13=23. So I'd expect a 10 times higher merger rate, or 50%. That shouldn't be too hard to verify... By the way: to verify if a state is in fact the state that led up to the keystream, you would only have to generate the rest of the keystream and match it against the actual keystream. The same holds for discarding streams after 100+N clockings, where you would match bits generated before the bits you've looked up. Considering the growth of ancestor states (some 5% per clock max) and the information in the keystream (50% per clock) you can be sure to have the right Kc even before looking at another burst of the conversation. ...if the real state is indeed conntected to the one you looked up. but I was wrong anyway - you can know that you know the right state that leads to the keystream. You still don't know which of the 13 ancestors was the actual one generated from Kc+Frame Number. So you will need another burst of which you can verify the contents (i.e. with cleartext, error correction, ... anything with some redundancy) Regards, M

_______________________________________________
A51 mailing list
A51@lists.reflextor.com
http://lists.lists.reflextor.com/cgi-bin/mailman/listinfo/a51