Links

Ben Laurie blathering


Smooth(er) MD5 Collisions

Inspired by a comment on one of my posts, I thought of a better way to produce smooth collisions than searching and factoring. The essence of it is this…

Take a bunch of (small) primes, p1, p2, …, pn. Multiply them together, c=p1*p2*…*pn. Then take your colliding pair, n1 and n2. Set o=c-((n1 << ((32+b(c))&~7)) mod c), k1=n1 << ((32+b(c))&~7)+o and k2=n2 << ((32+b(c))&~7)+o, where b(c) is the number of bits in c. That is, k1 is n1 shifted left (bytewise) with an offset, o, added. Note that k1 is divisible by c (and check that k2 isn’t), and, of course, k1 and k2 collide.

Now test k2, k2+c, k2+2c, …, k2+Nc until one is found that is prime. At this point you have a collision, k2+Nc prime and k1+Nc divisible by c (i.e. smooth[ish]).

Using this method, here are two k2+Nc:

D131DD02C5E6EEC4 693D9A0698AFF95C 2FCAB50712467EAB 4004583EB8FB7F89 55AD340609F4B302 83E4888325F1415A 085125E8F7CDC99F D91DBD7280373C5B D8823E3156348F5B AE6DACD436C919C6 DD53E23487DA03FD 02396306D248CDA0 E99F33420F577EE8 CE54B67080280D1E C69821BCB6A88393 96F965AB6FF72A70 00000AD6BF4FE0D1 559E6140208D6D2B A4694335

and

D131DD02C5E6EEC4 693D9A0698AFF95C 2FCAB50712467EAB 4004583EB8FB7F89 55AD340609F4B302 83E4888325F1415A 085125E8F7CDC99F D91DBD7280373C5B D8823E3156348F5B AE6DACD436C919C6 DD53E23487DA03FD 02396306D248CDA0 E99F33420F577EE8 CE54B67080280D1E C69821BCB6A88393 96F965AB6FF72A70 00000085EDE28444 505E3FE8D0F8D68E FF7CF302ECEE5FCC FA78FAE6BF0F8979 57F7CD21

The first collides with a number that has the first 26 primes as factors, and the second with one that has the first 43 as factors.

3 Comments

  1. This is nice but it will still not allow you to achieve your goal of creating two colliding values, one of which is a prime and the other is smooth enough to allow you to compute discrete logs.

    Comment by Cyphrpunk — 24 Oct 2005 @ 19:20

  2. Presumably because they still have a factor which is likely to be approximately 1000 bits long?

    Comment by ben — 25 Oct 2005 @ 12:06

  3. Right, all the factors have to be known and each one has to be small enough that rho or giant/baby or kangaroos will work, all of which are square root time.

    Comment by Cyphrpunk — 28 Oct 2005 @ 4:20

RSS feed for comments on this post.

Sorry, the comment form is closed at this time.

Powered by WordPress