[cryptography] cryptanalysis of 923-bit ECC?

[Matthew Green]

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 hereb& :)

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
cryptography at randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography


----- End forwarded message -----
-- 
Eugen* Leitl <a href="http://leitl.org">leitl</a> http://leitl.org
______________________________________________________________
ICBM: 48.07100, 11.36820 http://www.ativel.com http://postbiota.org
8B29F6BE: 099D 78BA 2FD3 B014 B08A  7779 75B0 2443 8B29 F6BE