Is this crypto paper real or fake?

[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


> [1]
> https://en.wikipedia.org/w/index.php?title=Discrete_logarithm_records&oldid=663284373#Elliptic_curves