Re: NSA and crypto



Paul Rubin wrote:
I wouldn't go as far as to say that security must rest on information
theory. The notion is simply that AES may not be as good as we think.
AES-CTR is supposed to be a secure PRNG, which means you hope the
attacker can guess the next bit with exactly 50% probability. Suppose
he can actually guess it with 50.01% probability. Something like that
has already happened with RC4. If your message is a yes-or-no reply
to something (i.e. one bit), xor'd with an AES-CTR bit, the attacker
now knows your answer with better chance than a random guess, but that
..01% advantage is not so useful.

Suppose instead your answer is (figuratively) "yes, yes, a billion
times yes!", or "no, no, a billion times no!", and your attacker knows
that. That is, you send either 1 billion consecutive ones or 1
billion consecutive zeros, encrypted with AES-CTR. The attacker
guesses the AES-CTR bits about 500,100,000 times with standard
deviation around 15,800, so he knows your answer to better than six
sigma certainty.

If you think there is any chance of AES having such a problem, you win
significantly by compressing your billion bit, redundant answer down
to one bit.

Having actually worked these numbers through though (unless I made an
error), I see that the effect is pretty insignificant for the 3x
compression or so that you get from English text, and 50.01% would be
a horrible amount of bias for a cryptographic RNG.

While compression is used to get a message that is more evenly divided among all the bitstrings of the (compressed) message's length, it's not the only way. Wouldn't expansion also work? Represent each bit of the (compressed or uncompressed) message by the ECB ciphertext of a 128-bit block whose low order bit is from the message and whose other 127 bits are completely random. Then encrypt the expanded message using the biased stream cipher. Someone who guessed the keystream bit correctly 75% of the time would make 128 consecutive correct guesses only 0.75**128~2**-53 of the time.
I think the ECB could use a publicly known key. The ECB step's only purpose is to diffuse the message bit among the 128 bits, so that 128 correct guesses are needed to recover the message bit, rather than a single correct guess.

--Mike Amling
.