ECDLP Can Be Solved in 24-th Root Time | Hacker News Reader

ECDLP Can Be Solved in 24-th Root Time

ellipticnews.wordpress.com

42 pointskushti15 comments

Damn Reddit caught this as April fools much faster than HN https://www.reddit.com/r/crypto/comments/4csvhs/ecdlp_can_be...

> As a result we recommend increasing elliptic curve key sizes from 256 bits to 3072 bits.

Ouch, if true, that's a major blow. I was starting to like these elliptic curves!

edit: April 1st guys:

> Steven Galbraith, April 1, 2016.

April 1st...

The date on the blog says 31st of March, but yes...

Ah, at the bottom it says:

> Steven Galbraith, April 1, 2016.

He got me. I do worry about some future era where encryption is impossible though.

If it's not a joke, it seems it could be related to these:

http://blog.cryptographyengineering.com/2015/10/a-riddle-wra...

https://www.schneier.com/blog/archives/2015/10/why_is_the_ns...

I wish people wouldn't post april fool's crap like this.

First thing I thought, when reading the linked article: "Oh my god".

This is extremely bad. Think what would happen if you deployed RSA with 256-bit keys for HTTPS and SSH (for host and user key-pairs).

If the results reported above are correct, then we are now effectively at such a situation. Many top websites do use ECDHE with 256-bit (or shorter) ephemeral keys. Many people do relay on 256-bit keys for SSH host and user authentication.

People will be able to decrypt new and previously sniffed HTTPS sessions, SSH sessions, will be able to log into your SSH servers, MITM your SSH connections (by computing the private ECDSA host key).

IIRC previously you needed in the order of 2^128 operations to break ECDLP for 256-bit keys (and ECDHE ECDSA). Now that goes down to 2^(256/24), shortening effective key-size 12-fold (resulting in a speedup of factor 2^117).

I'm not an expert in the field, so take these estimations with a large grain of salt. Corrections welcome.

Update: on a second thought, it is April 1st today. Anxiously waiting for confirmation of hoax.

Is this like prior work against the ECDLP which only applied to binary curves? The blog post talks about all crypto systems, but prior index calculus attacks always seem to have not applied to prime curves.

If it really applies to all curves and is not an April Fools joke, then this will hurt the usability of Bitcoin, Keybase and other systems that assume EC keys can be easily encoded as text.

edit: It is confirmed as an April Fools: https://twitter.com/EllipticKiwi/status/715711942531264512 ...

I hope for April 1st prank as this is after I adopted ed25516 ssh keys with the public part consisting of only 80 chars plus comments and the private key taking only 254 characters in base64 so it can realistically be typed manually from a backup printout.

> O(q^(1/24)) ... While still exponential complexity,

I call April's fools!

Lol there are probably less than a dozen people on the planet the fully understand elliptic curves to the point where they could make real progress on the ECDLP problem. This is clearly April Fools

is this true?

Yes. Even worse, because their are elliptic curve methods for factorising products of primes (Lenstra's ECM), there will be a knock-on effect on RSA. RSA keys will now need to be 131,072-bits to maintain their current level of security. This is effectively the Cryptopocalypse: https://www.schneier.com/blog/archives/2013/08/the_cryptopoc...

[commitment: a31500d27e35b23c63287161cb405e20]

And to think that we knew about Leech lattice and E8 (Gosset Lattice) for so many decades already! :)

Reply on news.ycombinator.com