Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

New algorithm shakes up cryptography

sciencedaily.com

Post reply on HN
Print view View original

11–20 of 34 posts

Re: New algorithm shakes up cryptography

#11

Post by pbsd »

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.

Here are some previous threads on the subject: https://news.ycombinator.com/item?id=6240434

Re: New algorithm shakes up cryptography

#12

Post by [deleted] »

olalonde wrote: post #9
djmdjm wrote: post #7

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. 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.

[deleted]

Re: New algorithm shakes up cryptography

#13

Post by zaroth »

djmdjm wrote: post #7

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. Rel…

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.
[1] - http://www.secg.org/collateral/sec2_final.pdf

Re: New algorithm shakes up cryptography

#14

Post by djmdjm »

SaveTheRbtz wrote: post #10
djmdjm wrote: post #7

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. 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 s…

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).

Re: New algorithm shakes up cryptography

#15

Post by djmdjm »

zaroth wrote: post #13
djmdjm wrote: post #7

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. Rel…

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 posse…

oh, thanks - I stand corrected.

Re: New algorithm shakes up cryptography

#16

Post by petermonsson »

djmdjm wrote: post #7

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. Rel…

We mainly use GF(2^m) in embedded systems for error correction (FEC, Scrambling, etc.).

Re: New algorithm shakes up cryptography

#17

Post by DCKing »

pbsd wrote: post #11

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. Here are…

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?

Re: New algorithm shakes up cryptography

#18

Post by SaveTheRbtz »

djmdjm wrote: post #14
SaveTheRbtz wrote: post #10

Earlier quoted context omitted.

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 s…

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.
[1] http://safecurves.cr.yp.to/field.html
Post reply on HN