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...
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.
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
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.
16 comments
[ 85.2 ms ] story [ 1246 ms ] threadOuch, if true, that's a major blow. I was starting to like these elliptic curves!
edit: April 1st guys:
> Steven Galbraith, April 1, 2016.
> Steven Galbraith, April 1, 2016.
He got me. I do worry about some future era where encryption is impossible though.
[commitment: a31500d27e35b23c63287161cb405e20]
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.
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 ...
http://blog.cryptographyengineering.com/2015/10/a-riddle-wra...
https://www.schneier.com/blog/archives/2015/10/why_is_the_ns...
I call April's fools!