<html><head><meta http-equiv="Content-Type" content="text/html; charset=us-ascii"><meta name="Generator" content="Microsoft Word 14 (filtered medium)"><style><!--
/* Font Definitions */
@font-face
        {font-family:Helvetica;
        panose-1:2 11 6 4 2 2 2 2 2 4;}
@font-face
        {font-family:Helvetica;
        panose-1:2 11 6 4 2 2 2 2 2 4;}
@font-face
        {font-family:Calibri;
        panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
        {font-family:Tahoma;
        panose-1:2 11 6 4 3 5 4 4 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
        {margin:0in;
        margin-bottom:.0001pt;
        font-size:12.0pt;
        font-family:"Times New Roman","serif";}
a:link, span.MsoHyperlink
        {mso-style-priority:99;
        color:blue;
        text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
        {mso-style-priority:99;
        color:purple;
        text-decoration:underline;}
span.apple-style-span
        {mso-style-name:apple-style-span;}
span.EmailStyle18
        {mso-style-type:personal-reply;
        font-family:"Calibri","sans-serif";
        color:#1F497D;}
.MsoChpDefault
        {mso-style-type:export-only;
        font-size:10.0pt;}
@page WordSection1
        {size:8.5in 11.0in;
        margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
        {page:WordSection1;}
--></style></head><body lang="EN-US" link="blue" vlink="purple"><div class="WordSection1"><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">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)?</span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"> </span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">William</span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"> </span></p><div><div style="border:none;border-top:solid #b5c4df 1.0pt;padding:3.0pt 0in 0in 0in"><p class="MsoNormal">
<b><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif"">From:</span></b><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif""> <a href="mailto:cryptography-bounces@randombit.net">cryptography-bounces@randombit.net</a> [mailto:<a href="mailto:cryptography-bounces@randombit.net">cryptography-bounces@randombit.net</a>] <b>On Behalf Of </b>Matthew Green<br>
<b>Sent:</b> Wednesday, June 20, 2012 11:35 AM<br><b>To:</b> Charles Morris<br><b>Cc:</b> <a href="mailto:cryptography@randombit.net">cryptography@randombit.net</a><br><b>Subject:</b> Re: [cryptography] cryptanalysis of 923-bit ECC?</span></p>
</div></div><p class="MsoNormal"> </p><p class="MsoNormal">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).</p>
<div><p class="MsoNormal"> </p></div><div><p class="MsoNormal">NIST curves don't have this property. In fact, they're specifically chosen so that there's no efficiently-computable pairing.</p></div><div><p class="MsoNormal">
 </p></div><div><p class="MsoNormal">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.</p>
</div><div><p class="MsoNormal"> </p></div><div><p class="MsoNormal">(Apologies to any real ECC experts whose work I've mangled here… :)</p></div><div><div><p class="MsoNormal"> </p></div><div><p class="MsoNormal">Matt</p>
</div><div><p class="MsoNormal"> </p><div><div><p class="MsoNormal">On Jun 20, 2012, at 10:59 AM, Charles Morris wrote:</p></div><p class="MsoNormal"><br><br></p><p class="MsoNormal"><span class="apple-style-span"><span style="font-size:13.5pt;font-family:"Helvetica","sans-serif"">"NIST guidelines state that ECC keys should be twice the length of</span></span><span style="font-size:13.5pt;font-family:"Helvetica","sans-serif""><br>
<span class="apple-style-span">equivalent strength symmetric key algorithms."</span><br><span class="apple-style-span">So according to NIST solving a 923b ECC is like brute-forcing a 461b</span><br><span class="apple-style-span">bit symmetric key (I assume in a perfect cipher?).</span><br>
<br><span class="apple-style-span">Of course there are weak keys in almost any system e.g. badly</span><br><span class="apple-style-span">implemented RSA picking p=q</span><br><br><span class="apple-style-span">I wonder if a weak-key scenario has occurred, or if this is a genuine</span><br>
<span class="apple-style-span">generalized mathematical advance?</span><br><span class="apple-style-span">Comments from ECC experts?</span></span></p></div><p class="MsoNormal"> </p></div></div></div></body></html>