Securing 'pickle'

[Paul Rubin]

Dave Cole <djc at object-craft.com.au> writes:
> I have been googling for information on the "appending" attack against
> md5 and cannot find anything that clearly describes it.  Do you have
> any links handy?

I think RFC 2104 (the HMAC spec) might describe it.  Basically, think
about how md5 works.  You load the md5 context with the secret key
(say 20 bytes) then your data (say 20 bytes), then some padding to
fill the 64 byte context, and run the compression function:

  md5_compress(key + data + 24 bytes of padding)

Call the 24 padding bytes P.  They are just 16 0's plus an 8 byte
length, iirc.

The hash output is just the md5 chaining variables after running the
compression function.

Now look at the 100 byte string 

  E = your data + P (same as above) + 36 bytes of evil stuff

Even without knowing your secret key, if the attacker knows your data
(which may not be secret), and md5(key+data) (which you've included in
the cookie), he can compute the signature of E.  It's just the result
of running the compression function on his evil stuff plus appropriate
additional padding, with the chaining variables set to the original
md5 hash that you already sent him.

This is not really a failure of md5, which is supposed to be a message
digest algorithm, not a MAC.  Rather, the authentication fails because
md5 is being used in a way it was not intended to be used.

The solution is to use HMAC.  See RFC 2104 for details.