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. >
I'm tempted to say it is impossible, for a bit at a random position at least. Looking at the single bit level: Flipping a bit in the keystream would mean flipping a bit in one of the lfsrs. The lfsr states form a 1:1 mapping, and therefore a chain, so flipping one bit will put you in another path, which you will never be able to offset with a few bitflips here and there. Your best bet would be to keep the lfsrs in their own paths, but shift them a few clocks forwards and/or backwards each. Then pray that the majority clocking will put them in sync again. The first few bits of keystream will then be different, but the rest will exactly be the same. This is the same procedure as we discussed before, but with less constraints on the keystream. 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. Regards, M. _______________________________________________ A51 mailing list [email protected] http://lists.lists.reflextor.com/cgi-bin/mailman/listinfo/a51
