Re: [hybi] AES-CTR is darned fast (was Re: Masking overhead with measurements and code)

[Willy Tarreau <[e-mail]>]

On Sun, Jan 09, 2011 at 12:34:37PM -0800, Maciej Stachowiak wrote:
> 
> On Jan 9, 2011, at 12:28 PM, Willy Tarreau wrote:
> 
> > On Sun, Jan 09, 2011 at 12:22:22PM -0800, Maciej Stachowiak wrote:
> >> I think your conclusion here is wrong. AES-CTR does not repeat the key
> >> schedule on any fixed cycle, as I understand it.
> > 
> > I've never said that. The fact that it *does not* repeat the key
> > precisely is what makes it harder to get the expected pattern.
> > 
> >> It generates a psuedorandom non-repeating keystream.
> > 
> > Exactly. And in a pseudorandom keystream, a given 32-bit pattern
> > will appear once in 16GB, and could appear once in a cleaverly
> > built 4GB stream too.
> 
> There's no way to guarantee that a chosen 32-bit pattern will appear anywhere in AES-CTR output for an attacker-controlled input. It could appear 0 times, no matter what the input is. So your claim is false.

That's the principle of randomness. A typical pseudo-random should make
any pattern appear. Of course it is possible that it does not appear, but
the probability to see the pattern at least once in a perfectly random
series of 2^32 patterns is of 1-(1-1/(2^32))^(2^32) = 1-1/e = 63%. It's
already 39% in half the patterns and becomes 86% in the double of the
patterns.

Regards,
Willy