Is this crypto paper real or fake?
Found this from a DJB paper: http://www.scs.carleton.ca/~paulv/papers/JoC97.pdf Parallel Collision Search with Cryptanalytic Applications Paul C. van Oorschot and Michael J. Wiener CHECK THE DATE: 1996 September 23 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... --- 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: http://link.springer.com/article/10.1007%2FPL00003816 Journal of Cryptology January 1999, Volume 12, Issue 1, pp 1-28
Dnia niedziela, 20 września 2015 16:53:50 Georgi Guninski pisze:
Michael J. Wiener
Hummm... Let's see: https://scholar.google.com/scholar?hl=pl&q=Michael+J.+Wiener&btnG=&lr= Well, at least this guys seems legit, as surprising as it may be. -- Pozdrawiam, Michał "rysiek" Woźniak Zmieniam klucz GPG :: http://rys.io/pl/147 GPG Key Transition :: http://rys.io/en/147
On 20/09/15 14:53, Georgi Guninski wrote:
Found this from a DJB paper:
http://www.scs.carleton.ca/~paulv/papers/JoC97.pdf
Parallel Collision Search with Cryptanalytic Applications
Paul C. van Oorschot and Michael J. Wiener
CHECK THE DATE:
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 happens. 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: http://link.springer.com/article/10.1007%2FPL00003816 Journal of Cryptology
January 1999, Volume 12, Issue 1, pp 1-28
On Sun, Sep 20, 2015 at 11:26:23PM +0100, Peter Fairbrother wrote:
On 20/09/15 14:53, Georgi Guninski wrote:
Found this from a DJB paper:
http://www.scs.carleton.ca/~paulv/papers/JoC97.pdf
Parallel Collision Search with Cryptanalytic Applications
Paul C. van Oorschot and Michael J. Wiener
CHECK THE DATE:
1996 September 23
Both authors are well-known.
Google says the paper was published in the Journal of Cryptology in 1999.
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.
Thanks for the answer. So the DLOG records (Wikipedia gives 113 bits [1] as of 2010) break these in libressl/openssl: $ ./inst/libressl-2.2.3/apps/openssl ecparam -list_curves secp112r1 : SECG/WTLS curve over a 112 bit prime field secp112r2 : SECG curve over a 112 bit prime field And these are in quite gray area? secp128r1 : SECG curve over a 128 bit prime field secp128r2 : SECG curve over a 128 bit prime field And what is the computational power of the Bitcoin network (Allegedly they do 2^80 SHA hashes per week) in terms of DSA/ECC operations? AFAIK, for DSA this is just multiplication/squaring modulo prime for rho. [1] https://en.wikipedia.org/w/index.php?title=Discrete_logarithm_records&oldid=663284373#Elliptic_curves
I'd guess Oorschot and Wiener got something in the numbers wrong. It happens.
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
On 21/09/15 06:29, Georgi Guninski wrote:
On Sun, Sep 20, 2015 at 11:26:23PM +0100, Peter Fairbrother wrote:
On 20/09/15 14:53, Georgi Guninski wrote:
Found this from a DJB paper:
http://www.scs.carleton.ca/~paulv/papers/JoC97.pdf
Parallel Collision Search with Cryptanalytic Applications
Paul C. van Oorschot and Michael J. Wiener
The present day open ECC dlog record stands at about 114 bits, iirc: that method used ~2014 custom hardware, but not $10 million worth.
Thanks for the answer.
So the DLOG records (Wikipedia gives 113 bits [1] as of 2010)
break these in libressl/openssl:
$ ./inst/libressl-2.2.3/apps/openssl ecparam -list_curves secp112r1 : SECG/WTLS curve over a 112 bit prime field secp112r2 : SECG curve over a 112 bit prime field
Yes. Pwnable.
And these are in quite gray area?
secp128r1 : SECG curve over a 128 bit prime field secp128r2 : SECG curve over a 128 bit prime field
Yes. Dodgy at best, likely pwnable, either now or soon. Note, from the Wikipedia page, that in 2002 breaking a 109-bit prime curve took nearly two years, using presumably general purpose hardware. By 2015 breaking 113 bit prime curves took 84 days on $15k worth of FPGAs. If specialised hardware chips are developed (and they may well be in the pipeline, or even in use), then following the example of Bitcoin mining, that would become minutes or even seconds. 155 and 160 bit curves would be toast, at $10 million in today's money: and I'd be a little worried about 192-bit curves, especially for long-term security. Plus, you can do a lot of the math for breaking a curve beforehand, once and only once, just from knowing only the curve details: and these results will be useful for all the points/numbers you might later want to find dlogs for on that curve. So the second and subsequent dlogs on the same curve will be a whole lot cheaper than the first dlog/break. Unfortunately, it is impractical to generate a new curve for each transaction; and it is not easy to generate and change curves very often, eg every day. As a rule of thumb, the prime should be double the size of the security parameter - eg for 128-bit security you should have p = 256 bits or so - hence curve25519 (where p=2^255 - 19) etc. For real unbreakable [excepting quantum computers] security I would not recommend anything less than 256-bit prime order fields. In general, the field should be of prime order: extension fields are no longer generally considered secure (but see below). I'm not a big fan of DJB's curve25519. You can do fast math in it - but then so can an attacker. And what if that extra structure, which allows fast computation, also introduces a weakness? Wild speculation some would say, and it is - but that's pretty much what happened with extension fields. the extra structure in the field made some otherwise unimportant attacks easier. I'd prefer a 256-bit prime chosen verifiably at random, with no "special" fast properties, and less exploitable structure. If your hardware can't cope with that, don't expect whatever crypto you do use to be secure. There is a fairly new curve from Microsoft, called FourQ (and FourQ to you too, Microsoft! :) which uses an extension field of p=(2^127 -1)^2, ie 254 bits. I won't go into why here, but like extension fields and curve25517, I don't trust it. Stick to verifiably randomly chosen 256-bit prime field curves. Be safe. Don't be sorry. -- Peter Fairbrother
participants (3)
-
Georgi Guninski -
Peter Fairbrother -
rysiek