New algorithm shakes up cryptography
sciencedaily.com
New algorithm shakes up cryptography
1–10 of 34 posts
Re: New algorithm shakes up cryptography
#2The journal article in question (PDF):
Re: New algorithm shakes up cryptography
#3Question to someone capable of understanding the paper; how screwed is ECDSA?
Re: New algorithm shakes up cryptography
#4So what does this mean exactly?
> it is likely to have repercussions especially on the cryptographic applications of smart cards, RFID chips (2), etc.
It will be easier to bruteforce RSA/DSA?
Re: New algorithm shakes up cryptography
#5Question to someone capable of understanding the paper; how screwed is ECDSA?
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.
Re: New algorithm shakes up cryptography
#6So what does this mean exactly? > it is likely to have repercussions especially on the cryptographic applications of smart cards, RFID chips (2), etc. It will be easier to bruteforce RSA/DSA?
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.
Re: New algorithm shakes up cryptography
#7This 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.
Re: New algorithm shakes up cryptography
#8Gotta love these researchers who out their painstaking work in publications and papers rather than patents.
Re: New algorithm shakes up cryptography
#9This 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. Rel…
> 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.
Re: New algorithm shakes up cryptography
#10This 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. Rel…
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.
[FIPS186-2] http://csrc.nist.gov/publications/fips/archive/fips186-2/fip...
[SEC-2v2] http://www.secg.org/download/aid-784/sec2-v2.pdf
[safecurves] http://safecurves.cr.yp.to/index.html
[Curve25519] http://cr.yp.to/ecdh.html