Subject: [Cfrg] Cheeky elliptic curves

From: Dan Brown <[email-masked]>
Date: Wed, 11 Jun 2014 18:36:35 +0000

Hi All,

An instructive commentary on curve selection can be found at:

http://safecurves.cr.yp.to/bada55.html

I think this site illustrates well the fact that it is quite difficult it is
to demonstrate a "nothing up my sleeve" (NUMS) property of a cryptographic
algorithm.

As a similar proof-of-a-point example: suppose that instead of having string
bada55 appearing somewhere in one of its EC coefficients, why not have
string 00000, or even longer, appear in all of the curve coefficients? To
arrange for this, abandon the VR/VPR approach, and use some other criteria,
e.g. similar to that of Curve25519.  Just as the site above does not claim
the bada55 curves to be weak, I'm not saying any such 000000,000000 curves
are weak.  Rather, they merely demonstrate that if a malicious entity
selecting the curve knows of a one-in-a-trillion weakness, they may be able
select curves vulnerable to that weakness, and yet persuade others that the
curves are benign, perhaps via some of kind of "rigidity" argument.  In
other words, Curve25519 does not provide full-proof NUMS either.  By the
way, I personally trust that Curve25519 is not maliciously selected, agree
that Curve25519 seems provide better rigidity (and even NUMS) than most VPR
curves, but the main reason I consider Curve25519 DLP-safe is the lack of
any successful cryptanalysis on ECDLP (that would apply to it).  Plus, the
side-channel resistance and implementation-simplicity is another good reason
to like Curve25519.

Minor point: The site above incidentally illustrates that "VPR", though not
ideal for the purposes of NUMS, is a significant improvement over the "VR"
for demonstrating NUMS, because: it shows fewer "VPR" curves and it places
the chosen bada55 string farther from the beginning of the string and it
provides a weak NUMS argument for selecting cos(1). 

Clarifying some of my previous email: the web site above emphasizes the
difficulty of VPR to provide NUMS, which is orthogonal to what I've (at
least most recently) tried to argue, at least most recently. My recent
arguments on CFRG and TLS for random curves were they that help provide a
"nothing up their sleeves" (NUTS) property, which is related to, but
different from, the NUMS property.    Just in case my argument was wrong or
misunderstood, I will repeat my it briefly. Suppose that P224 was selected
to have a one-in-a-million (OIAM) weakness.  Our first step to avoid this
OIAM weakness is to select our own curve.   A random curve has a
one-in-a-million chance of having the OIAM weakness.  For a non-random
curve, we have to argue, as I see it, some kind of independence between the
OIAM weakness and the non-randomness of our selection, and therefore we get
less assurance.  I concede that this distinction is a theoretical: much like
provable security it is trying to argue about a class of unknown attacks,
and a narrow class of attacks.   As I now see it, the main benefit of using
VPR is an attempt to demonstrate the NUTS property, as a decent
approximation of randomness, and at the same time to provide a NUMS
property, albeit rather weakly (as illustrate by the bada55 site).  The
connection between NUMS and NUTS is the OIAM weakness.  If you don't believe
in the OIAM weakness, they you about neither NUMS nor NUTS, and can write it
all off as fear (of a mere spectre).  If you think that OIAM is plausible,
then it makes to go for both NUMS and NUTS.

I am sorry that nothing I've said above is constructive.  I am considering a
more constructive proposal.  This may well involve other theoretical issues
like reductionist security arguments between DLP and CDHP, and static
versions thereof, issues which are orthogonal to (or perhaps more important
than) the pseudorandom v non-random issue. 

Best regards,

Dan

PS: If you have already implemented NIST P224 EC curve but recently have
become worried that P224 was selected maliciously, and furthermore, your
implementation luckily permits a simple data change: to the a and b
coefficients, the curve order n, and a base point (e.g. as a patch applied
to both of the corresponding parties) but your implementation is unluckily
limited to just those types of changes (e.g. cannot be patched with new
arithmetic, etc), then BADA55-VPR-224, despite its humble origin as a mere
proof-of-a-point, seems to conveniently and largely remedy the worry about
P224 being malign.

---

From: Andy Lutomirski <[email-masked]>
Date: Mon, 23 Jun 2014 14:52:36 -0700

[resent now that I'm subscribed]

On 06/11/2014 11:36 AM, Dan Brown wrote:
> I think this site illustrates well the fact that it is quite difficult
> it is to demonstrate a “nothing up my sleeve” (NUMS) property of a
> cryptographic algorithm.
> 

I may be missing something, but isn't there a much bigger hole here?
Specifically, the slides say that S is random, subject to some
moderately expensive conditions.  Why should anyone trust that you
didn't mount a massively parallel search to choose a malicious but
acceptable value of S?

I'd distrust this less if S were a very small number of approximately
the expected magnitude for the first acceptable value.  And I could even
(in principle) regenerate S myself.

Note that I have exactly the same objection to the NIST curves.

--Andy