# Re: NSA and crypto

*From*: Mike Amling <nospam@xxxxxxxxxx>*Date*: Sat, 20 May 2006 17:44:59 GMT

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

.

**Follow-Ups**:**Re: NSA and crypto***From:*Mike Amling

**References**:**NSA and crypto***From:*David A. Scott

**Re: NSA and crypto***From:*Ed Weir \(ComCast\)

**Re: NSA and crypto***From:*tomstdenis

**Re: NSA and crypto***From:*Paul Rubin

**Re: NSA and crypto***From:*David Wagner

**Re: NSA and crypto***From:*Paul Rubin

- Prev by Date:
**Re: Compression and crypto** - Next by Date:
**Re: NSA and crypto** - Previous by thread:
**Re: NSA and crypto** - Next by thread:
**Re: NSA and crypto** - Index(es):