Links

Ben Laurie blathering

29 Dec 2004

Primes – or are they?

Filed under: Crypto — Ben @ 8:18

For some time I’ve been having a discussion with Dan Kaminsy and others about whether it is possible to use Wang’s MD5 collisions to mount a practical attack. Dan says it is but my point was that in order to mount the attack described, you would need to be in a position where you could already feed your victim bad code, so the MD5 collision was nothing more than a parlour trick.

Anyway, the upshot was that after much confused discussion, John Kelsey finally suggested an attack that works. This involves producing a pair of numbers, one prime, one not, whose MD5 hashes collide. One then publishes a program that does, say Diffie-Hellman, using the prime. Once it has been reviewed and deemed good, replace the prime with the non-prime, and, presto, future conversations are weak, but the MD5 hash remains the same.

17 minutes after reading his mail, I had such a pair:

D131DD02C5E6EEC4693D9A0698AFF95C2FCAB58712467EAB4004583EB8
FB7F8955AD340609F4B30283E488832571415A085125E8F7CDC99FD91DB
DF280373C5BD8823E3156348F5BAE6DACD436C919C6DD53E2B487DA03F
D02396306D248CDA0E99F33420F577EE8CE54B67080A80D1EC69821BCB
6A8839396F9652B6FF72A700000000000000000000000000000001B

is prime.

D131DD02C5E6EEC4693D9A0698AFF95C2FCAB50712467EAB4004583EB8
FB7F8955AD340609F4B30283E4888325F1415A085125E8F7CDC99FD91DB
D7280373C5BD8823E3156348F5BAE6DACD436C919C6DD53E23487DA03F
D02396306D248CDA0E99F33420F577EE8CE54B67080280D1EC69821BCB
6A8839396F965AB6FF72A700000000000000000000000000000001B

is not prime.

All that remains is to factor the non-prime – which turns out to be non-trivial.

Here’s the code I used to produce the collision:


#include <openssl/bn.h>
#include <unistd.h>

unsigned char v1[]={
0xd1,0x31,0xdd,0x02,0xc5,0xe6,0xee,0xc4,0x69,0x3d,0x9a,0x06,0x98,0xaf,0xf9,0x5c,
0x2f,0xca,0xb5,0x87,0x12,0x46,0x7e,0xab,0x40,0x04,0x58,0x3e,0xb8,0xfb,0x7f,0x89,
0x55,0xad,0x34,0x06,0x09,0xf4,0xb3,0x02,0x83,0xe4,0x88,0x83,0x25,0x71,0x41,0x5a,
0x08,0x51,0x25,0xe8,0xf7,0xcd,0xc9,0x9f,0xd9,0x1d,0xbd,0xf2,0x80,0x37,0x3c,0x5b,
0xd8,0x82,0x3e,0x31,0x56,0x34,0x8f,0x5b,0xae,0x6d,0xac,0xd4,0x36,0xc9,0x19,0xc6,
0xdd,0x53,0xe2,0xb4,0x87,0xda,0x03,0xfd,0x02,0x39,0x63,0x06,0xd2,0x48,0xcd,0xa0,
0xe9,0x9f,0x33,0x42,0x0f,0x57,0x7e,0xe8,0xce,0x54,0xb6,0x70,0x80,0xa8,0x0d,0x1e,
0xc6,0x98,0x21,0xbc,0xb6,0xa8,0x83,0x93,0x96,0xf9,0x65,0x2b,0x6f,0xf7,0x2a,0x70,
};

int main()
    {
    BIGNUM *bn=NULL;
    int n;

    bn=BN_bin2bn(v1,sizeof v1,NULL);
    BN_lshift(bn,bn,128);
    BN_add_word(bn,1);
    for(n=0 ; ; ++n)
	{
	if((n%100) == 0)
	    write(1,".",1);
	if(BN_is_prime(bn,5,NULL,NULL,NULL))
	    break;
	BN_add_word(bn,2);
	}
    BN_print_fp(stdout,bn);
    return 0;
    }

Powered by WordPress