On 1/13/10 5:17 PM, M vd S wrote: > On 1/13/10 1:11 AM, sascha wrote: > >> if you take the A5/1 state that produced a keystream with >> one bit flipped at a random position in comparison to the keystream >> you observed in the burst, what is the probability of finding a connected >> state that produced the observed keystream? It would mean that we could >> find more hits with the same amount of data. >> >> > > .. > The procedure to do this is in fact quite simple, just forward clock the > entire state N, back clock N, and see what comes out. After bit N the > keystream will be identical. > > >> And if this is indeed possible: Applying the above algorithm many times, >> finding states that produce keystreams more similar to the target keystream, >> you could navigate from a random state to a desired state faster than >> with bruteforce. >> >> > > With the exception that it will only work for the first few bits of > keystream. > > But then, still, it would enlarge the chance of finding a hit. > > By... 6.7% on average when taking any modification to the first 5 bits of keystream, obtained after exploring all states within clocking forward and back 16 times, and assuring that a valid state is produced (i.e. that can be clocked back 100 times).
The distribution of bits flipped in the keystream looks like: 00001 15877 20.3% 00010 6786 8.7% 00011 8755 11.2% 00100 4046 5.2% 00101 2752 3.5% 00110 3517 4.5% 00111 5354 6.8% 01000 2411 3.1% 01001 1723 2.2% 01010 1187 1.5% 01011 1525 1.9% 01100 1810 2.3% 01101 1552 2.0% 01110 2276 2.9% 01111 3036 3.9% 10000 1398 1.8% 10001 1047 1.3% 10010 826 1.1% 10011 930 1.2% 10100 648 0.8% 10101 622 0.8% 10110 684 0.9% 10111 797 1.0% 11000 1048 1.3% 11001 860 1.1% 11010 734 0.9% 11011 853 1.1% 11100 1230 1.6% 11101 1002 1.3% 11110 1266 1.6% 11111 1677 2.1% So in 20% of this 6.7%, or 1.2% of cases, you would find something useful when looking up the keystream^1. M. _______________________________________________ A51 mailing list [email protected] http://lists.lists.reflextor.com/cgi-bin/mailman/listinfo/a51
