Extracting uniform randomness from noisy source
Amir Herzberg
amir at herzberg.name
Mon Aug 5 04:45:47 EDT 2002
At 21:02 04/08/2002, David Wagner wrote:
>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)
>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
Oops, sorry, I wasn't clear above; AES_k is of course using the CBC_MAC
using AES. When my message is interpreted to use simply AES as a block
cipher, you simply don't get any compression, and therefore the output is
also not uniform, as you illustrated nicely above... You must do CBC_MAC to
sufficient number of blocks of noise, containing enough entropy, to get the
pseudo-random output.
Also, I didn't mention another simple secure solution, which is to use
universal hash function h_k(noise), where again k is a random key (again,
such a key is necessary, but can be `burned into` the hardware). Universal
hash functions are easy to implement and very efficient (much more than
crypto hash functions).
Using SHA1 or other crypto-hash, I think relies on it being, intuitively,
`as good as` a random universal hash function. If you somehow key the
crypto-hash, e.g. by using the IV as a key or by externally keying (e.g.
use SHA1(k,noise)), you could test the function for universal hashing
property; it makes sense that such tests were done to standard hash
functions. Does anyone know if that was done (and published)? However, even
if this was done, I am not sure that you gain anything compared to using a
(more efficient) universal hash function.
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com
More information about the cryptography
mailing list