[cryptography] cryptanalysis of 923-bit ECC?

jd.cypherpunks jd.cypherpunks at gmail.com
Wed Jun 20 14:32:48 EDT 2012


was much less than expected: http://www.techweekeurope.co.uk/news/fujitsu-cryptography-standard-83185

--Michael

Am 20.06.2012 um 17:39 schrieb William Whyte <wwhyte at securityinnovation.com>:

> 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?
>  
> _______________________________________________
> cryptography mailing list
> cryptography at randombit.net
> http://lists.randombit.net/mailman/listinfo/cryptography
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.randombit.net/pipermail/cryptography/attachments/20120620/fd3b3ca9/attachment.html>


More information about the cryptography mailing list