Does anyone know if this attack took the expected amount of time (confirming the strength of this particular curve), or significantly less (in which case it’s something to be concerned about)?
William *From:* [email protected] [mailto: [email protected]] *On Behalf Of *Matthew Green *Sent:* Wednesday, June 20, 2012 11:35 AM *To:* Charles Morris *Cc:* [email protected] *Subject:* Re: [cryptography] cryptanalysis of 923-bit ECC? I'm definitely /not/ an ECC expert, but this is a pairing-friendly curve, which means it's vulnerable to a type of attack where EC group elements can be mapped into a field (using a bilinear map), then attacked using an efficient field-based solver. (Coppersmith's). NIST curves don't have this property. In fact, they're specifically chosen so that there's no efficiently-computable pairing. Moreover, it seems that this particular pairing-friendly curve is particularly tractable. The attack they used has an estimated running time of 2^53 steps. While the 'steps' here aren't directly analogous to the operations you'd use to brute-force a symmetric cryptosystem, it gives a rough estimate of the symmetric-equivalent key size. (Apologies to any real ECC experts whose work I've mangled here… :) Matt On Jun 20, 2012, at 10:59 AM, Charles Morris wrote: "NIST guidelines state that ECC keys should be twice the length of equivalent strength symmetric key algorithms." So according to NIST solving a 923b ECC is like brute-forcing a 461b bit symmetric key (I assume in a perfect cipher?). Of course there are weak keys in almost any system e.g. badly implemented RSA picking p=q I wonder if a weak-key scenario has occurred, or if this is a genuine generalized mathematical advance? Comments from ECC experts?
_______________________________________________ cryptography mailing list [email protected] http://lists.randombit.net/mailman/listinfo/cryptography
