4 ms·
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 f
by djmdjm 12y ago
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.
- BoppreH 12y agoWhat 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.
- mindcrime 12y agoI'm guessing typo that was meant to be be ECDH? http://en.wikipedia.org/wiki/Elliptic_curve_Diffie%E2%80%93Hellman http://en.wikipedia.org/wiki/Elliptic_curve_Diffie%E2%80%93H...
- tptacek 12y agoI 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. See also https://news.ycombinator.com/item?id=7759441 https://news.ycombinator.com/item?id=7759441 --- who, as always, knows what he's talking about. † Edit: 'pbsd suggests there may not be one.
- olalonde 12y ago> This actually came out about half-way through last year. What do you mean? I don't doubt you are right but the article doesn't seem to mention that anywhere.
- deleted 12y ago[deleted]
- koios 12y agoHe's referring to the previous work of Joux, such as this: https://eprint.iacr.org/2013/095.pdf https://eprint.iacr.org/2013/095.pdf. "Today's" result is an improvement over that and previous works. So what we know is that attacks on curves over GF_{2^m} are getting better.
- SaveTheRbtz 12y agoAnd 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. [FIPS186-2] http://csrc.nist.gov/publications/fips/archive/fips186-2/fips186-2.pdf http://csrc.nist.gov/publications/fips/archive/fips186-2/fip... [SEC-2v2] http://www.secg.org/download/aid-784/sec2-v2.pdf http://www.secg.org/download/aid-784/sec2-v2.pdf [safecurves] http://safecurves.cr.yp.to/index.html http://safecurves.cr.yp.to/index.html [Curve25519] http://cr.yp.to/ecdh.html http://cr.yp.to/ecdh.html
- djmdjm 12y agoI 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).
- SaveTheRbtz 12y agoDJB 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. [1] http://safecurves.cr.yp.to/field.html http://safecurves.cr.yp.to/field.html
- zaroth 12y agoBitcoin 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. [1] - http://www.secg.org/collateral/sec2_final.pdf http://www.secg.org/collateral/sec2_final.pdf
- djmdjm 12y agooh, thanks - I stand corrected.
- petermonsson 12y agoWe mainly use GF(2^m) in embedded systems for error correction (FEC, Scrambling, etc.).