[cryptography] cryptanalysis of 923-bit ECC?

William Whyte wwhyte at securityinnovation.com
Wed Jun 20 11:39:03 EDT 2012


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:* cryptography-bounces at randombit.net [mailto:
cryptography-bounces at randombit.net] *On Behalf Of *Matthew Green
*Sent:* Wednesday, June 20, 2012 11:35 AM
*To:* Charles Morris
*Cc:* cryptography at randombit.net
*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?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.randombit.net/pipermail/cryptography/attachments/20120620/c95694b8/attachment.html>


More information about the cryptography mailing list