[cryptography] cryptanalysis of 923-bit ECC?

Matthew Green matthewdgreen at gmail.com
Wed Jun 20 11:35:07 EDT 2012


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/52e1fc7f/attachment.html>


More information about the cryptography mailing list