Links

Ben Laurie blathering


Primes – or are they?

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;
    }

1 Comment

  1. […] In “Primes, or are they?” I produced a pair of numbers with the same hash, one of which was prime and one of which wasn’t. The snag was that the one that wasn’t wasn’t particularly easy to factor, so it took the fun out of it somewhat. […]

    Pingback by Links » MD5 Collisions and Factorisation — 21 Sep 2005 @ 10:10

RSS feed for comments on this post.

Sorry, the comment form is closed at this time.

Powered by WordPress