HMAC?

[Hal Finney]

More on the question of HMAC.  As mentioned before, the potential attack
would be to find a collision on the inner hash, even without knowing the
key.  Since the key is exactly one hash block in length, the effect is
identical to finding a hash collision without knowing the IV.

Discussing this issue with Niels Ferguson, he pointed out that it
might turn out that the new attacks do provide some slight advantage for
guessing a hash collision even without knowing the IV values.  There might
be some differential, and conceivably even some choice of inputs, which
would have an enhanced collision probability.  If that were greater than
the one in 2^64 chance of a collision one would ordinarily expect with,
say, MD5, then technically that would be called a break of HMAC-MD5,
even if it were not possible to exploit it in practice.

Another point that was mentioned in the presentation on the new MD4
collisions was that they were so easy to find that the work factor was in
the range from 4 to 64.  It's not entirely clear what that means, but the
claim was that the work was so simple that it could be completed by hand.

I thought it was conceivable that this meant that some substantial
fraction of random inputs to MD4 would collide when using the differential
described in the eprint posting, so I tested that.  I wrote some code
to choose a random 512 bit block and then hash both it and a block
with the published differentials using MD4, and check for a collision.
I let it run for 1.7 billion tries without finding any.  The code is
below, but note that it will only run on a little-endian machine since
their differentials are for 32-bit blocks in that form.

So at least it's not just a matter of finding the right differential.
You've got to be somewhat smart in choosing the data values, which would
make it harder to attack HMAC since you presumably would not be able to
choose the data without knowing the IV.  It may still be that you could
do something with HMAC built on one of the broken ciphers, but we will
have to wait for a fuller description of the technique.

Hal Finney

===

/* Experiment with random MD4 values to see if the Wang differentials
 * work just getting lucky.
 */

#include <stdio.h>
#include <string.h>
#include "openssl/rand.h"
#include "openssl/md4.h"

typedef unsigned char uchar;

unsigned wang[16] = {
	0x4d7a9c83, 0x56cb927a, 0xb9d5a578, 0x57a7a5ee, 0xde748a3c, 0xdcc366b3, 0xb683a020, 0x3b2a5d9f,
	0xc69d71b3, 0xf9e99198, 0xd79f805e, 0xa63bb2e8, 0x45dd8e31, 0x97e31fe5, 0x2794bf08, 0xb9e8c3e9
};

unsigned buf1[16];
unsigned buf2[16];

uchar md1[16];
uchar md2[16];

void
memdump (unsigned char *buf, int buflen)
{
	int i;
	for (i=0; i<buflen; i++)
		printf ("%02x%s", buf[i], ((i+1)%16)==0?"\n":" ");
	if (buflen%16)
		printf ("\n");
}

main ()
{
	int i;
	int d1, d2, d12;

	d1 = 1UL<<31;
	d2 = (1UL<<31) - (1<<28);
	d12 = -(1<<16);

	/* Try an actual Wang collision the first time through for testing */
	memcpy (buf1, wang, sizeof(buf1));

	for (i=0; ; i++)
	{
		memcpy (buf2, buf1, sizeof(buf1));
		buf2[1] += d1;
		buf2[2] += d2;
		buf2[12] += d12;
		MD4 ((unsigned char *)buf1, sizeof(buf1), md1);
		MD4 ((unsigned char *)buf2, sizeof(buf2), md2);
		if (memcmp (md1, md2, sizeof(md1)) == 0)
		{
			printf ("Collision on iteration %d\n", i);
			memdump ((unsigned char *)buf1, sizeof(buf1));
			printf ("\n");
			memdump ((unsigned char *)buf2, sizeof(buf2));
			if (i > 0)
				exit (0);
		}
		if (i % 100000 == 0)
		{
			printf ("Iteration %d\n", i);
		}
		RAND_bytes ((unsigned char *)buf1, sizeof(buf1));
	}
}

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