Re: A5/1 not cracked?

Frank Jansen wrote:
>In chapter 5.5 the paper shows that a biased birthday attack is
>effective because red root states with a big green belt are more
>probable than red root states with a small green belt. [...]
>
>But under these circumstances I would also assume that the occur-
>rence of some alphas have a higher probability between bit positions
>101 and 277 than 2^-16. In this case all attacks could be improved
>by using a probable alpha instead of using a randomly choosen alpha.

Interesting idea, but I'm not sure about that. I haven't done
experiments, but I wouldn't have expected a significant bias in favor
of some \alpha's. The attack keeps 2^35 red states on the disk.
Suppose we fix any set of 2^35 initial states, and consider the 177 *
2^35 16-bit outputs obtained by taking any of those 2^35 states and
looking at the window of bit positions 101--277. If each of the 177 *
2^35 observations is uniformly distributed across all 16-bit outputs,
then the number of times any given \alpha occurs should be approximately
Gaussian with mean 177 * 2^35 / 2^16 = 2^26.5 and standard deviation 2^13.
If we pick the most common \alpha and ask how many times it occurs,
the answer might be 4 or 5 standard deviations above the mean (say),
but this is only 2^26.5 + 5 * 2^13, which is not much larger than 2^26.5.
So I don't expect a large bias here.

But of course I haven't done the simulations, so it is always possible
that my intuition has led me astry. Feel free to give it a try and
see if you can find any significant improvement along these lines --
I certainly didn't think of this direction when writing the paper.

>Did anybody for example a monte-carlo simulation to test the
>relativ frequencies of different alphas between bit positions
>101 and 277?

Not that I know of, unfortunately.
Received on Thu Sep 29 21:43:52 2005