Is this crypto paper real or fake?

Peter Fairbrother peter at
Sun Sep 20 15:26:23 PDT 2015

On 20/09/15 14:53, Georgi Guninski wrote:
> Found this from a DJB paper:
> Parallel Collision Search with Cryptanalytic Applications
> Paul C. van Oorschot and Michael J. Wiener
> 1996 September 23

Both authors are well-known.

Google says the paper was published in the Journal of Cryptology in 1999.

> p.1
> The practical significance of the technique is illustrated by giving the
> design for three $10 million custom machines which could be built with
> current technology: one finds elliptic curve logarithms in GF(2^155)
> thereby defeating a proposed elliptic curve cryptosystem in expected
> time 32 days, the second finds MD5 collisions in expected time 21
> days...

The present day open ECC dlog record stands at about 114 bits, iirc: 
that method used ~2014 custom hardware, but not $10 million worth.

I'd guess Oorschot and Wiener got something in the numbers wrong. It 

However the parallel collision search technique they describe is very 
real, and has been used to effect. At a guess, the ECC dlog record above 
probably used it, as will most modern collision search algorithms.

As DJB quoted them, I'd guess that they invented the technique (though I 
knew of the technique, I thought Knuth described/invented it).

It's one of those things which are obvious in hindsight; but which can 
be dev'lishly hard to come up with in the first place.

-- Peter Fairbrother

> ---
> I know the dollar is not what it used to be, but same applies to
> hardware IMHO
> Metadata of the PDF is in the future, suggests windows.
> This is paywalled:
> Journal of Cryptology
> January 1999, Volume 12, Issue 1, pp 1-28

More information about the cypherpunks mailing list