Subject: [Cfrg] random curves by lenstra ...

From: Dan Brown <[email-masked]>
Date: Fri, 24 Apr 2015 18:46:14 +0000

Dear CFRG list,

A recent IACR eprint report [LW], by A. Lenstra and B. Wesolowski,

http://eprint.iacr.org/2015/366

suggests how to generate trustworthy random elliptic curves.  

The how (briefly): multiple parties contribute to a protocol that involves
puzzles to prevent cheating.

The why: The report [LW] supports the case for random elliptic curves based,
in part, on the argument that freshly-generated curves, unlike stale curves
(such as P256, Brainpool or Curve22519), have not been lingering around and
potentially exposed to cryptanalysis.  

Intuitively speaking, the freshness argument contradicts the maturity
argument (which is that an algorithm has a security assurance that increases
over time provided all known cryptanalysis has failed): preferring new over
old, instead of old over new (all else the same).  Practically speaking,
fresh curves might not work so nicely in long-term applications.
Theoretically speaking, most of the risk that fresh curves prevent does not
seem to be prevented in the forward secrecy context: if short-order
curve-specific cryptanalysis is viable, it could likely be applied to
compromise forward secrecy.  Yet more theoretically, it is quite a mature
belief that effort spent on Pollard rho on one curve, cannot be re-used on a
different curve, but instead of trying to relying on this belief, one
usually just chooses a curve size in which a single Pollard rho is
infeasible.

Most of my past arguments to CFRG (and TLS) for pseudorandom elliptic curves
were different from the freshness argument.  I've argued that pseudorandom
curves would have prevented the MOV and SASS attacks, had those attacks
remained secret (especially compared to malicious special curves designed to
make those attacks work - such curves were proposed academically before the
attacks, presumably non-maliciously).  So, the small risk that there exists
similar secret attacks can be protected against by choosing pseudorandom
curves.  

I hope to complete a report in a couple months with my own views (different
from [LW]) on the how and why of generating pseudorandom elliptic curves.

Best regards,

Daniel Brown

Certicom / BlackBerry

---

From: Damien Miller <[email-masked]>
Date: Wed, 29 Apr 2015 09:00:32 +1000 (AEST)

> potentially exposed to cryptanalysis. 

The converse argument applies too: that bespoke curves have not
been analysed for cryptanalytic weakness.

-d

---

From: David Leon Gil <[email-masked]>
Date: Wed, 29 Apr 2015 14:10:58 +0000

I take a very different view of this, which I think I have stated on
another list: Suppose that some fraction of elliptic curves are weak under
some, as yet unknown, attack. Choosing a set of curves that we believe to
be uniformly distributed with respect to unknown attacks does not change
the *expected* cost of the curve being weak (in decrypted messages, say),
but does decrease the variance of the expectation.

And most people do have roughly minimax cost functions (insurance &c.), so
they'd be better off if we picked (a fairly large) set of curves.

I'd note that this argument does not weigh in favor of 'random' curves: An
equally legitimate way of doing this might be to just choose the N
SafeCurves with minimal parameter.

--

The unstated assumption -- which Daniel Bernstein has pointed out both more
eloquently and argumentatively -- of people arguing for pseudorandomly
generated curves (for application on the Internet, at least) seems to be
that there may be some correlation between small/rigid curve parameters and
some weakness.

As I am utterly unqualified to have any opinion on that, I will say no more
but that I wish people would address the question more directly:

Set Smallest: Choose the first N safe curves with smallest parameter.
Set Random: Choose N safe curves with pseudorandomly generated parameter.

Is there a reason to believe that these two sets have different
distributions with respect to some (possibly known but probably) unknown
property?

On Tue, Apr 28, 2015 at 4:00 PM Damien Miller <[email-masked]> wrote:

> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Stephen Farrell <[email-masked]>
Date: Wed, 29 Apr 2015 15:58:24 +0100

> they'd be better off if we picked (a fairly large) set of curves.

I'm not sure I agree there. IMO the larger the set of curves
the less likely we have interop, and the more likely we have
bad implementations and hence the more likely we fall back to
less good things such as cleartext.

Fallbacks like that are overwhelmingly mind-bogglingly astoundingly
and generally much much much more likely than cryptographically weak
curves would be my guess.

In other words: don't buy your insurance from a cryptographer,
buy it from an insurance company:-)

S.

---

From: Nico Williams <[email-masked]>
Date: Wed, 29 Apr 2015 12:07:20 -0500

> curves would be my guess.

I think the intention with random curves is to have "servers" generate
them and "clients" accept them no-questions-asked.  If generation is
slow then in practice we'd not get so very many curves because most
servers would then use a known set generated once, which defeats the
idea.

To use randomly-generated curves the generation algorithm had better be
cheap enough that we generate lots of them -- ideally one per-DH key
exchange (and what about signatures?).

> buy it from an insurance company:-)

:)

---

From: David Leon Gil <[email-masked]>
Date: Thu, 30 Apr 2015 04:50:27 +0000

(There was an implicit ceteris paribus in my previous mail to the list.)

I mostly agree. But I'd note that an implementation of scalar
multiplication on an arbitrary curve over a *fixed* prime field is actually
*simpler* than the more optimized implementations possible for fixed
parameters.
On Wed, Apr 29, 2015 at 7:58 AM Stephen Farrell <[email-masked]>

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 30 Apr 2015 11:55:53 -0400

Do we really need to get into discussion of known unknowns?

The short answer to the problem is that if you are at all worried
about the risk of an algorithm compromise then use Goldilocks instead
of Curve25519. The only tool we have for dealing with algorithm
concerns is to add more bits.

For 99% of applications RSA1024 is sufficiently secure even today and
for at least 90%, the work factor of RSA512 is sufficient to deter
attack. For cryptanalysis to be worth doing, the cryptography has to
be exceptionally weak or the reward has to be exceptionally great.

The security issues here are not what most folk here think they are.
The issue is not deterring attack, it is confidence. And confidence is
affected by a weird mix of cultural factors.

Let us imagine for the sake of argument that the NSA has an attack
that breaks 50% of curves and that we have picked one by accident
using our rigid rules. That would not worry me personally in the
slightest as there is absolutely no chance that such a high value
attack would be wasted on someone like me. It is the cryptographic
equivalent of a nuclear weapon - a weapon so powerful that it cannot
be used.

Since by definition we have no idea what an unknown attack might be,
the probability of some sort of weakness is exactly the same for a
random curve selected through a verifiably fair ceremony and for a
fast prime.

The reason we are going for fast primes is that they are fast and
there is absolutely no possibility of a backdoor known to just one
party. The NSA does not and cannot have special knowledge of a Mersene
prime that it can expect will not become known to the FSB. But the
NIST curves could conceivably have been generated with some sort of
backdoor.

It is almost certainly the case that Curve25519 is going to be secure
enough for all applications. The only reason for building the WebPKI
on goldilocks are:

1) Curve25519 is not sufficiently more secure than RSA2048 to justify
the transition cost.
2) The WebPKI contains many concentrations of trust that do justify an
exceptional cryptanalytic effort.

The CFRG curves are definitely backdoor free. The only possibility is
a systemic weakness in the algorithm that anyone could exploit that
depends on the choice of curve. So to consider that possibility we
need to look at how crypto systems fail and how our existing attacks
reduce work factor. So far we have not seen an attack that reduces the
work factor over the previously best known attack more effectively
than the meet in the middle attack, i.e. WF' = WF^0.5 [Yes, I am aware
of Shamir's orthogonality attacks but these are just generalizing meet
in the middle and finding a way to apply it multiple times]

The reason I was arguing for 512 bit prime is that if the WF=2^256,
then WF'=2^128 which is agreed to be 'infeasible'. However even with
Goldilocks, WF'=2^112 which is generally considered ample.

While there may be an attack that defeats Goldilocks and results in
WF'<<2^112 then all bets are off anyway. ECC is finished. We have to
do something else entirely like move to Kerberos.

If people are really, really really concerned, then we should define a
'last gasp' curve with a  really big prime. And given that we are
using fast primes for regular ECC, an argument could be made to do
random. But it would have to be an incredibly big prime to be worth
doing, 1024 or 2048 bits. And it would only be used for management of
CTLs and such.

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Thu, 30 Apr 2015 14:44:10 -0400

> equivalent of a nuclear weapon - a weapon so powerful that it cannot

This analogy doesn't hold unless using the weapon is detectable by those
it is used against.  A cryptoanalytic attack could be held and used in
secret even if it is of the caliber described.  It is not "a weapon so
powerful that it cannot be used" as long as it stays hidden.

       --dkg

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 30 Apr 2015 15:21:43 -0400

> powerful that it cannot be used" as long as it stays hidden.

That is true when it comes to the likes of Al Qaeda and enemy powers. But
even then, any use of cryptanalytic product has to be performed with extreme
caution and the risk/reward carefully considered at each stage.

If more than five people in an organization know something then it is not
going to remain a secret. If the number is more than fifty then it is not going
to be kept secret very long. It would be really hard to make use of a
cryptanalytic attack for pervasive surveillance without hundreds knowing.

The NSA term of art for this is NOBUS - nobody but us. What that means is
they will use a capability if they think nobody else is going to be able to use
it which in turn means nobody else finding out.

The US used a cryptographic attack on the Iranian diplomatic cipher and
then lost the capability after one of the neocons told an Iranian agent about
it.