Extracting uniform randomness from noisy source

[David Wagner]

John Kelsey  wrote:
>b.  The first input block is not a random 128-bit value, and can reliably
>be distinguished from one.  In this case, the input just doesn't have full
>entropy, and any known function you apply to it with a 128-bit output is
>distinguishable from a random output.  A one-way function just makes it
>harder to distinguish these outputs, for a computationally-bounded
>attacker.  But how important this is depends on our assumptions about the
>attacker's abilities; if we assume the attacker can do 110-bit searches,
>then he can generally distinguish the output of *any* known function with
>only 110 bits of entropy with reasonable probability.  

I was assuming that the first block has 80 bits of entropy, and that
the attacker can't do 80-bit exhaustive searches.  In such a scenario,
my attack applies.  The attack does not apply to all scenarios, but in
cryptanalysis we are usually willing to consider the assumptions most
favorable to the attacker, as long as they are at all plausible.

This scenario is one that might arise in practice, and it is one that
SHA gets right while AES-CBC-MAC gets it wrong, I think this is an
argument for preferring SHA over AES-CBC-MAC.  Again, the difference
arises because SHA is preimage-resistant (one-way), while AES-CBC-MAC
isn't (when the key is known).

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