[cryptography] cryptanalysis of 923-bit ECC?

James A. Donald jamesd at echeque.com
Fri Jun 22 04:21:35 EDT 2012


> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
>
> On Jun 20, 2012, at 8:35 AM, Matthew Green wrote:
>
>> 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� :)

On 2012-06-21 7:12 AM, Jon Callas wrote:
> Thanks, anyway, as things seem to be detail-lite where I'm getting them.
>
> Do we have anyone who can speak authoritatively on this? I am also not at all an expert on pairing-friendly curves.
>
> Is this merely a case where 973 bits is equivalent to ~60 bits symmetric?

I am not an authority, but to the extent that I understand this:

923 bits in the paired field is equivalent to 153 bits in the elliptic 
curve (the size of your public key as a compressed point, the size of a 
compressed point on the elliptic curve.

153 bits in the elliptic curve should have been equivalent to 77 bits 
symmetric, but evidently was only equivalent to about ~60 bits 
symmetric, which is disturbing, though hardly a big serious break in 
itself.   But breaks only get better.




More information about the cryptography mailing list