[TLS] Koblitz curves [was RE: Curve25519 in TLS]

[Dan Brown <[e-mail]>]

Hi Bodo,

 

Aside: maybe discussion like this should move to CFRG, because its
generality could affect other WGs, and its theoretical what-if nature may
not interest many in TLS WG.  For now, I just changed the subject line.

 

To briefly recap: some people hypothesize (a) existence of an undisclosed
weak curve classes and (b) authorities pushing curves, via seed searches,
into the weak class.  Koblitz curves resist (b).  You said you do not
believe (b).  You raised the point again that Koblitz curves may be hit by
(a) alone.  (I tried to raise this point (a) for Koblitz curves, in the
other thread, noting them to be special, just like Curve25519.) I have said
before Koblitz curves provide evidence against (b) else: Why place a
backdoor on one curve, but not another? My argument was a little vague on
this point, so I will try to clarify it first

 

You are quite right that if Koblitz fall to a different version of (a), then
(b) would remain viable backdoor mechanism for the VR curves, because now
all NIST curves would be weak.  This event essentially presumes two
undisclosed weak classes of curves (or one, which contains both the Koblitz
curves and the all VR curves).  In other words, it assumes a larger class of
weak curves, so it is more unlikely.  It is more far-fetched, albeit only
slightly so.  And everything here is hypothetical, remember. 

 

Ignoring (b) completely is another hypothesis worthy of consideration.  In
this case, a highly informal argument that Koblitz are less likely than VR
curves to be affected by (a) is that the Koblitz curves slightly pre-date
the VR curves, and by virtue of their simple coefficients, are more amenable
to inspirational analysis.  Put another way, the VR curve coefficients are
not easy for a person to manipulate.  So, any human research efforts could
have targeted Koblitz but not VR curves.  Also, research efforts just to
find arbitrary weak classes of curves could be viewed as unlikely of hitting
a VR curve, and thus be viewed as having less incentive (exception: strong
believers in (b) would be much more likely to believe in a weak class
containing the VR curves).  So, it seems, at least to me, the fact that
Koblitz have would have been subjected to more effort, or at least more
incentive. (Indeed, your intuition, which is that a weak class is more
likely to include Koblitz, is an instance of researchers seeing Koblitz
curves as more likely target to achieve research success.)  From the lack of
published attacks, we can infer a lower probability of an undisclosed
attack, because there may be a greater number of samples: attempts to
discover such a class.  But then again, the Suite B VR curves may also
received quite a bit of scrutiny too.

 

Best regards,

 

Dan

 

 

From: [e-mail] [mailto:[e-mail]] On Behalf Of Bodo
Moeller
Sent: Thursday, September 12, 2013 1:42 PM
To: [e-mail]
Subject: Re: [TLS] Curve25519 in TLS

 

 

> Unless NIST can prove that their curves aren't backdoored, I think it's

 

[DB] Five NIST curves are Koblitz curves, which are not backdoored.

 

Personally I don't expect any of the NIST curves to be backdoored, but I
don't agree with the reasoning (which I've seen elsewhere before) that if
you have doubts about the pseudorandom NIST urves due to their unexplained
seeds, the NIST Koblitz curves are less suspect because that degree of
freedom is missing.

 

I won't repeat here why I'm not actually worried about the pseudorandom
curves (I don't think I could add anything to your and Douglas Stebila's
arguments in the thread "Testing consensus for adding curve25519 to the EC
named curve registry"). Now *if* one assumes that there's a (thin-spread but
non-negligible) class of weak curves among them (so that the seeds could
have been chosen to create backdoors), why would it be more far-fetched to
assume that the class of Koblitz curves is weak *in its entirety*?  After
all, these particular curves are known to have extra structure by design!

 

Bodo

 

 

---------------------------------------------------------------------
This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful.