[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: MAC speeds



Chris Trobridge writes:
> What is the mathematical problem and proof that this MAC relies on?

The security proof for Wegman-Carter MACs is absolute. It doesn't assume
that some problem is hard to solve. It merely assumes that the sender
and receiver share a long enough secret uniform random string.

Here's a simple example. Say messages are strings over a field F of size
2^128. For any element r of F, define h_r(m_0,m_1,...,m_{l-1}) as

   r^{l+1} + m_0 r^l + m_1 r^{l-1} + ... + m_{l-1} r.

The sender and receiver share secret independent uniform random elements
r,k_1,k_2,...,k_N of F, where N is the number of messages. The sender
transmits the nth message m_n as (n,m_n,h_r(m_n)+k_n). The receiver
discards (n',m',s') unless s' = h_r(m') + k_{n'}.

It's easy to prove that an adaptive chosen-plaintext attack on this
system that tries D forgeries has probability at most D(L+1)/2^128 of
fooling the receiver, if the maximum message length is L. The point is
that, for any distinct messages m and m', and for any c in F, there are
at most L+1 choices of r such that h_r(m) - h_r(m') = c. 

Variants:

   * You can use any hash function in place of h_r. The security of the
     system depends on the collision probability of the hash function.
     See section 10 of http://cr.yp.to/papers.html#hash127 for a survey.

   * You can hide the output of the hash function with an encryption
     function other than a one-time pad. The security of the system
     depends on the security of the encryption.

For example, NMAC-MD5 and HMAC-MD5 can be viewed as systems of this
type, with MD5(r,...) as the hash function, MD5(k,...) as the encryption
function, and various methods of generating r and k. There's no proof
that MD5(r,...) has low collision probability, but we think it does. On
the other hand, MD5(r,...) is slower than the state of the art in
128-bit hash functions, and the lack of a nonce in MD5(k,...) means that
the forgery probability grows quadratically with the number of messages.

---Dan




References: