Re: A hole in esp-stream-01

[David Wagner <[e-mail]>]

In article <[e-mail]>,  <[e-mail]> wrote:
> >When using ESP with DES or 3DES, why do I need a cryptographically
> >strong hash function since the hash is encrypted? In order to be able to
> >successfully modify the packet and still create a valid hash would
> >require breaking the encryption. We are not actually talking about a
> >non-repudiation issue with a digital signature; a cryptographically
> >secure hash appears to be overkill and using a keyed hash even more so.
> 
> Actually, I think this general idea (hash the data, then encrypt the
> hash) has been discussed a few times as a valid MAC design.  I can
> see a couple possible problems with it, off the top of my head:
> 
> 1.   If you can cause collisions in the hash function (i.e., MD5),
> then you can cause collisions in the MAC, as well.  (I don't think
> this is all that upsetting--once your hash function has stopped
> resisting collisions, it's time to retire it.)  More to the point,
> collision values can be found offline--they don't require interaction
> with the user.  Admittedly, getting the pair of collision values
> into encrypted form is still going to be pretty complicated.
> 
> 2.   I think doing this in CBC-mode may add some complications to
> the analysis.  Among other things, we have to make sure the IV gets
> hashed along with the data.
> 
> Does anyone else know of cryptanalysis of this kind of scheme?

I remember discussing this approach a while ago (though it may well have
been in private email?).  It seemed promising at the time, but it never
really got anywhere, as I recall.  (Someone correct me if I'm wrong here.)

The idea of appending a MD5 hash of the data, then encrypting, can fall
to chosen-plaintext attacks: I request the encryption of the message
	M' = M || MD5(M) || foo.
from you.  You send
	C = CBC-Encrypt(M || MD5(M) || foo || MD5(M')).
Recall that CBC encryption has the property that decrypting a prefix of
the ciphertext yields a prefix of the plaintext.  So I now (in an active
attack) truncate C at the boundary between the CBC-encryption of MD5(M)
and foo, thus obtaining the ciphertext
	CBC-Encrypt(M || MD5(M)),
which the receiver will interpret as a valid, authentic encryption of the
message M.  Therefore simply appending an unkeyed hash prior to encryption
does not always protect message integrity.  (I'm probably forgetting who
initially discovered this attack; apologies for the lack of attribution.)

It was also suggested to append a CRC of the data before encrypting; I
remember finding a known-plaintext attack on that.  (The problem is that
the CRC is too linear.)  I will look up my old correspondence and forward
you the technical details of the attack, but the exact nitty-gritty details
probably aren't so interesting, so I won't bother the list with it.

I think using a well-studied MAC, like HMAC, is the most robust way to go.

Designing roll-your-own message integrity schemes seems fairly subtle &
easy to get wrong.  (But a ultra-fast secure MAC would be good to have.)