Extracting unifrom randomness from noisy source

[David Wagner]

Amir Herzberg wrote:
>5. While the extractors described by Nisan (and others) are indeed very
>efficient, I'm not aware of any available implementations. Implementors
>may consider using therefore their favorite block cipher, e.g. AES,
>using a random key. Notice that this random key should be selected
>uniformly but could be part of the software, common to all deployments
>and non-secret; security is only based on the independence of the
>sampled noise in this key. Namely, 
>
>pseudo-random = AES_k (noise) 
>
>Security of this construction follows from the assumption that the block
>cipher (e.g. AES) is a Pseudo-random function; notice that this is a
>standard assumption for block ciphers (and therefore block ciphers are
>cryptoanalysed to meet this assumption). 

Don't use this -- it is broken.

There is an attack: an adversary can distinguish your "pseudorandom"
outputs from a true random source, simply by decrypting the candidate
output under the public AES key and testing whether the result appears
like it could have come from the noise distribution.  If the distribution
of noise is fairly sparse, the attacker can always recognize outputs of
your construction as not truly random.  To me, this suffices to call your
scheme insecure.  (Note that the warranty on pseudorandomness becomes
null and void when the key is publicly known, so the fact that AES is
a PRF when the key is secret seems irrelevant here.)

Observe that simply applying SHA1 to the noise source does not succumb to
this sort of attack.  I believe using SHA1 is superior to your method, and
I believe "use SHA1" is still the correct advice to give to practitioners,
despite the theoretical difficulties inherent in rigorously justifying
any scheme in a reasonable model of computation.

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com