Re: Secure MAC using Block Cipher?

From: Paul Rubin (//phr.cx_at_NOSPAM.invalid)
Date: 03/28/05 

Date: 27 Mar 2005 16:07:58 -0800

daw@taverner.cs.berkeley.edu (David Wagner) writes:
> >Sometimes people use MAC's as keyed hashes.
> What do you mean by "keyed hash"? Do you mean "pseudorandom function"?

Yes.

> >Anyway, in that usage, a birthday collision is when the same MAC
> >labels two different messages.
>
> But you can only find birthday collisions if you know the key ==> birthday
> attacks are not a problem (unless you are using the function in a very
> weird way, I guess).

Let's say you have a database of poems indexed by the contents of the
first line. You don't want to store the database in the clear because
then attackers could see what poems you have. You can't index with an
unkeyed hash of the first line because the attackers could then run
their own list of first lines through the hash and see which ones are
in your database. You can't use a PRP because the lines are of
varying lengths. The answer is to use a PRF. But you want to be sure
that any two distinct first lines map to different "hashes", i.e. that
the PRF output is long enough to make birthday collisions unlikely.

Relevant Pages
Quantcast