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