This actually came out about half-way through last year. It's a good attack on DLP-based cryptosystems, like ECDSA and ECDA when they use small-characteristic fields.
Most EC crypto in use uses large-characteristic prime curve fields (often abbreviated as GFp) and is unaffected by these attacks.
Small-characteristic GF2^m curve fields seems a little more popular in embedded hardware, but I don't know any details. Relatively little software uses GF2^m curve fields either, though a notable exception is Bitcoin (I have no idea what this result meant for them).
Notably, the EC used in SSH and common SSL deployments use GFp keys and aren't affected by this result. It does make one wonder whether the DLP will fall more generally - it is only believed to be "hard" and AFAIK there is no proof that it is.
Bitcoin uses secp256k1 which is over Fp, not F2m. secp256k1 is a Koblitz curve which is usually over F2m, but I think not in this case.
From the SEC spec:
Parameters associated with a Koblitz curve admit especially efficient
implementation. The name Koblitz curve is best-known when used to describe
binary anomalous curves over F2m which have a,b {0,1}. Here it is
generalized to refer also to curves over Fp which possess an efficiently
computable endomorphism.
And what does it mean in Standard [FIPS186-2] [SEC-2v2] terms?
That one should avoid using sect{163,233,239,283,409,571}k1 and sect{163,233,239,283,409,571}r1 curves?
But there are also rumors that secp{192,224,256,384,521}r1 are backdoored by NSA.
This leaves only secp{192,224,256,384,521}k1 which are considered "unsafe" by Daniel J. Bernstein [safecurves].
So the only hope is to wait for [Curve25519] to be widely supported?
PS. Bitcoin using secp256k1 which is Koblitz GFp curve.
I haven't heard anyone recommending against the GF2m curve fields recommended by the IETF and NIST standards.
Take this with an appropriately large grain of salt - I haven't followed the fallout of Joux' work very closely (because I don't use anything that uses GF2m fields).
DJB says following about all non-prime fields [1]:
> Is ECDLP broken for non-prime fields?
No. However, the security story for non-prime fields
(e.g., binary extension fields) is more complicated and
less stable than the security story for prime fields, as
illustrated by 1998 Frey, 2002 Gaudry–Hess–Smart, 2009
Gaudry, and 2012 Petit–Quisquater.
2006 Bernstein stated that prime fields "have the virtue
of minimizing the number of security concerns for
elliptic-curve cryptography". Similarly, the Brainpool
standard and NSA's Suite B standards require prime fields.
There is general agreement that prime fields are the safe,
conservative choice for ECC.
I haven't read the new paper†, but the original Joux paper that this refines didn't apply to the ECDLP. ECDSA and ECDH don't rely on the hardness of the DLP; they rely on the hardness of the ECDLP. Part of the point of the ECDLP is that it is less amenable to classical lines of attack on the DLP, like index calculus, from which this algorithm is derived.
What is ECDA? I've not heard of it, search results turn up nothing and I can't think of a good set of words to fill that acronym. And more telling this post is #2 in google for "ECDA crypto" so maybe it is just a typo.
There's some confusion going on here. This algorithm:
- Has nothing to do with elliptic curves.
- Has virtually zero repercussions in any real-world cryptosystem.
- Is a mostly theoretical refinement of the 'cryptopocalypse' Joux algorithm, which only affects some special kinds of fields (namely small characteristic).
- Is only being reported again now because the paper has just been presented at Eurocrypt.
- As mentioned elsewhere in the discussion, the algorithm does have an impact on some elliptic curve-based cryptosystems, but it is an indirect one. The attack is against the discrete logarithm problem in small characteristic finite fields; that isn't a security concern for the elliptic curve DLP (even over fields of small characteristic), except in the special case when ECDLP reduces to finite field DLP. That reduction is called the Menezes-Okamoto-Vanstone attack, and only applies to a restricted class of elliptic curves: so-called "pairing-friendly" curves, which are used in pairing-based crypto.
- In particular, the attack has no impact on even small characteristic NIST curves, or basically on any curve used for "traditional" (as opposed to "pairing-based") elliptic curve cryptosystems, including ECDH, ECDSA, ECIES, etc.
- On the other hand, the paper is a huge deal for people interested in the implementation of pairing-based crypto / cryptographic bilinear groups, because small characteristic fields (mainly supersingular curves over GF(3^m)) were the preferred approach for implementation in hardware, and even in software if you wanted symmetric pairings. Joux's original L(1/4) paper meant that people had to take a closer look at the trade-off between characteristic 3 and large characteristic in hardware (and it was also very important as the most significant algorithmic advance on the DLP since GNFS), but it wasn't quite "apocalyptic". This paper, on the other hand, has a quasi-polynomial attack, which means pairing-based crypto in small characteristic is dead (and more generally, symmetric pairings have become very unattractive).
- Whether this affects "real-world crypto" depends on were you set the limits of the real world. SSL connections and credit cards are unaffected, sure, but there are limited deployments of things like group signatures that have to take a close look at the math used in their implementation.
- The first preprint did appear publicly last summer, so it's true that this is not fresh news to the community, although I think it's great that this result gets some publicity beyond academic circles (and IMHO it fully deserves its best paper award).
We're getting way past my comfort level, but the impact of the recent DLP attacks on pairing curves is because they involve mapping the curve problem into a multiplicative finite field, right? The DLP attacks themselves don't directly impact the ECDLP.
None of the terminology or mathematics used seems to be specific to integer groups to my limited understanding. Could you explain why this has nothing to do with elliptic curve groups?
Alternative interpretation: Gotta love how European research funded by tax-payer euros enters the public domain — as it should.
Fwiw, on this side of the pond some are somewhat bemused by how e.g. US big pharma firms are allowed to patent research results that were funded by tax-payer dollars.
Not terribly, at first glance. Crypto generally uses fields with no subfields and large characteristic, whereas these attacks seem to generally be limited to fields with subfields and small characteristic.
It's interesting work, but not immediately alarming.
For the time being, it only applies to elliptic curves. However, the curves in actual use are over fields of large characteristic, so this result does not break them.
Obviously, any advance in understanding the discrete logarithm problem may be a step forward in breaking elliptic curves, but as far as I know, this is not a reason to change anything for the time being - at least for non-cryptographers.
Most EC crypto in use uses large-characteristic prime curve fields (often abbreviated as GFp) and is unaffected by these attacks.
Small-characteristic GF2^m curve fields seems a little more popular in embedded hardware, but I don't know any details. Relatively little software uses GF2^m curve fields either, though a notable exception is Bitcoin (I have no idea what this result meant for them).
Notably, the EC used in SSH and common SSL deployments use GFp keys and aren't affected by this result. It does make one wonder whether the DLP will fall more generally - it is only believed to be "hard" and AFAIK there is no proof that it is.