Re: [Cfrg] Progress on curve recommendations for TLS WG

Watson Ladd <watsonbladd@gmail.com> Sat, 16 August 2014 02:14 UTC

Return-Path: <watsonbladd@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 4A2AD1A09FE for <cfrg@ietfa.amsl.com>; Fri, 15 Aug 2014 19:14:51 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2
X-Spam-Level:
X-Spam-Status: No, score=-2 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, SPF_PASS=-0.001] autolearn=ham
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id LwRbLsrjl1BK for <cfrg@ietfa.amsl.com>; Fri, 15 Aug 2014 19:14:48 -0700 (PDT)
Received: from mail-qa0-x22a.google.com (mail-qa0-x22a.google.com [IPv6:2607:f8b0:400d:c00::22a]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id B2F171A09E8 for <cfrg@irtf.org>; Fri, 15 Aug 2014 19:14:47 -0700 (PDT)
Received: by mail-qa0-f42.google.com with SMTP id j15so2689301qaq.15 for <cfrg@irtf.org>; Fri, 15 Aug 2014 19:14:46 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=5A7+qsdvZK87idjqgxYcyW0lTon0FGN42GAXt5HeMcU=; b=F6WkJo2zsoZEMY/49pJJqVUBbCPbtLFXTfyqn3ve6NrkJvv3G2Ia9L+vi2C6L+9ipl yGv/H2YvqQPB7IVrBI5JRti7VDB5iug3kOt21Rg1WkPH/er/kxkZxV5iRTW6KMNqkgkm B83+0OLrPyEzXlBctK+7Ujb9uJoLmYYU6asGggKAsRF+4psQVWoPTzAVDUq8lAEWyb2w SA6wzmr30rVGpPhCB7DtsjiVENQuiv28ju5Cwuw8lpQteIxFmC1GkrwS9UK4SiL9Yn0H Ri+RM5jXCKmtBwJy+r1MpxJRzHITuF/XLz0i6qWCqs0ynUmqKHfq/RXD+QCowMGU1h5R Tm7w==
MIME-Version: 1.0
X-Received: by 10.140.25.226 with SMTP id 89mr26677740qgt.62.1408155286631; Fri, 15 Aug 2014 19:14:46 -0700 (PDT)
Received: by 10.140.47.228 with HTTP; Fri, 15 Aug 2014 19:14:46 -0700 (PDT)
In-Reply-To: <810C31990B57ED40B2062BA10D43FBF5CCD182@XMB116CNC.rim.net>
References: <20140801013659.11640.qmail@cr.yp.to> <53EDEB0D.9040304@secunet.com> <925e123f-d396-443f-9fc7-b1f6601bcd4c@email.android.com> <53EE17A9.7080408@secunet.com> <CACsn0c=eS-=6dapjrw07uEbxW0MHqn6=3caftfA6geZNOUcu9w@mail.gmail.com> <53EE3839.7010009@secunet.com> <CACsn0c=hEwPPL_zrXnoXnWfQ6oQPE-U8P3mGCA3a7=djfXAAqw@mail.gmail.com> <810C31990B57ED40B2062BA10D43FBF5CCD0ED@XMB116CNC.rim.net> <CACsn0cndH3hF-hvFFYnik2Bxs3+sm7ALHLTxSPCZNzJ1bLJMjg@mail.gmail.com> <810C31990B57ED40B2062BA10D43FBF5CCD182@XMB116CNC.rim.net>
Date: Fri, 15 Aug 2014 19:14:46 -0700
Message-ID: <CACsn0cnMML_bTnVoXWveRQX7D3BermitxAtkXRRMeiUyK1hDyA@mail.gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
To: Dan Brown <dbrown@certicom.com>
Content-Type: text/plain; charset=UTF-8
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/-cq0hiIBCWhz0vqkwC3LsN-Bq-U
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] Progress on curve recommendations for TLS WG
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Sat, 16 Aug 2014 02:14:51 -0000

On Fri, Aug 15, 2014 at 2:19 PM, Dan Brown <dbrown@certicom.com>; wrote:
> From: Cfrg [mailto:cfrg-bounces@irtf.org] On Behalf Of Watson Ladd
> Sent: Friday, August 15, 2014 2:24 PM
>>On Aug 15, 2014 10:59 AM, "Dan Brown" <dbrown@certicom.com>; wrote:
>>>
>>> Wrong about it being unconvincing: the severity of the attack is what
>>> matters,
>>> not how common it is.  Why would anybody care whether it took six or
>>> one-million trials to a find a weak 56-bit curve?
>>What is it convincing of? If it takes 6 trials all randomly generated curves
>>are likely to fail. If it's 1 in a million, then rigidity or lack thereof is
>>more important to prevent underhandedness.
>
> Only a few small points to be convinced of by the example y^2 = x^3+x^2+x /
> GF(2^255-19), all related to resisting a secret attack of severity and
> distribution about the same as the Pohlig--Hellman (PH) attack:
>
> 1) Rigidity does not help against such a severe attack.
> 2) The rigid example I found happened to fall into a hole covering about
> 1-in-6 of curves, but that hole is very deep rendering the curves in the hole
> feasible to break.  This metaphorical hole for the PH attack does not have a
> sharp edge, but suppose the hole had a sharp edge for the secret attack, for
> the sake of simple example. If users selected their own curves at random, then
> 5-in-6 users would be safe, and 1-in-6 unsafe due to the secret attack.  If
> CFRG selects one universal curve, somehow at random, then with a 5-in-6
> chance, all its users would be safe, but with 1-in-6 chance they'd all be
> unsafe.   Neither solution is great, but what else can we do against such a
> severe secret attack?  A rigid curve could be safe or unsafe, but one has no
> probabilistic argument of its being safe with probability 5-in-6, unless we
> assume a heuristic about the attack, which is a theoretically stronger
> assumption.  (Aside: the BARC example shows that this heuristic assumption is
> not just theoretically strong, it is practically wrong for the PH and MOV
> attacks because one can find PH and MOV weak curves without trial and error
> violating the heuristic assumption.)
> 3) The example I chose was y^2  = x^3 + x^2 + x, but the arguably more rigid
> curve y^2 = x^3 + x resists PH considerably better.  An adversary pushing the
> less secure curve might think up excuses to prefer the former, such as: the
> latter is more fragile, because somebody is more likely implement it with
> older Weierstrass code, which is more liable to have side channels, whereas
> y^2 =x^3 + x^2 + x would encourage people to use a Montgomery ladder.
> Accepting that adversary's argument would turn a 2^99 attack into a 2^56
> attack.  This just shows that one of the attacks we already know, the PH
> attack, is super-sensitive to the extent that there's that rigidity alone does
> not suffice to prevent underhandedness.
>
> Just to be clear, in case you were wondering, the y^2 = x^3+x^2+x/
> GF(2^255-19) example would not serve to convince anybody anything about the
> unexplained-seed used for P256, or even the ANSI curve generation method.

If I tell the method to ignore Polig-Helman, it spits out a curve that
is vulnerable. That's why the only convincing part of your email was
supersingularity, but even that was only convincing me that minimal
parameters could cause some property to be true.
>
>>>
>>> Also, I assume that you are not referring to my BARC example, in which the
>>> largest prime factor is two.   Maybe BARC is unconvincing for another
>>> reason,
>>> which is?
>>The endomorphism ring was shockingly large,
>
> The BARC example was testing the utility of rigidity against secret attacks.
> If you know some (potential) attack using a large endomorphism ring, then just
> pretend that attack was somebody else's secret.  In my view, now BARC should
> be even more convincing that rigidity offers no protection against secret
> attacks of similar ilk, because it falls to a fourth attack.  How can four
> attacks on one rigid curve not be convincing of something?
>
>> NUMS isn't a property of a curve but a generation method, etc.
>
> The BARC example can be extended to other fields: any with p=3 mod 4 and p+1
> smooth, e.g. the field GF(2^521-1), so it is really not a single curve, though
> I guess I should have said that right away.
>
> TLS has asked CFRG to recommend one or two curves. Some proposals for a few
> curves are being made to the IETF.  The NUMS property applies to anything that
> a user wants to trust from somebody else, whether software, hardware, a curve,
> a protocol.  So, it is a property of both the generation method and of the
> curve generated.  Surely, if somebody managed, in some ingenious fashion,
> generated a weak curve maliciously, be it Curve25519, Brainpool, or P256, that
> would be a violation of the NUMS property of others trusted the curve.  So,
> taking a generation method, a plausible setting, and then running some kind of
> execution of the curve generation method, the single curve that it outputs is
> fair game for testing of the NUMS property, because ultimately CFRG will be
> asking IETF to trust us.  If you're saying that nobody is making any NUMS
> property claims for Curve25519, only its generation method, then I'm saying
> it's better to have a curve which has some plausible NUMS property, even if it
> has to invoke some kind of fancy assumptions.

At the risk of making this WG even less effective than it already is:

Mathematical objects exist independently of human perception.
Properties are properties of objects. How NUMS is a random curve I
write in this email? Since you don't know how I made it, you can't
decide, so NUMS isn't a property of the curve. To the extent there is
a NUMS property, it's a property of algorithms A for deciding that a
curve is "acceptable". One set of algorithms applies publically known
criteria, then finds the minimal curve satisfying these criteria.
Another set accept curves with an auxiliary input that shows that they
were made by taking some inputs and hashing them. The second set
accepts manipulatable curves.

All of this machinery is inherent in DJBs paper. Heck, it's defined
there, somewhere between the third and fifth time I laughed.

What you showed is a fairly minimal set of parameters can be
supersingular, which is an obviously special property. It screams 'I'm
special' the way having BADA55 in hex does. But whereas DJB showed
that an algorithm A exists to make BADA55 curves that people think
weren't manipulatable, and that we have A' to get property P, where P
could imply "there exists a circuit with area time product < K and
success probability p in solving the DLP on curve K", you've had much
less freedom in your choice of P: there are very few supersingular
curves, and the other properties you mentioned could trivially have
worked in DJB's attack.

The best you can get is that minimal parameters is no worse than
hashing constants, but I don't think you can even get that. Of course
we could do some sort of S&P 500 related generation, but it's
completely pointless: if a significant fraction of curves are weak,
we're still up the creek, and I'm pretty willing to say you will not
get CurveBADA55 out of whatever generation with primes just above a
power of 2 with bounded c, or Solinas type trinomials and minimal
parameter satisfying the properties at safecurves.cr.yp.to.

>
> If IETF has a proposal or a request for just a generation method in which a
> pair, or larger set, of mutually trusting users generates their own curve,
> then those users could rely solely on the NUMS property of generation method,
> since they control the actual of execution of the generation method.
> (Nothing-up-your-sleeve is a vacuous goal.)
>
> Anyway, the BARC example was trying to show that there is not any direct
> correlation between rigidity and security (whether NUMS or not).  I did say
> however, the rigidity can rule out certain kinds of secret attacks, so I think
> rigidity has some benefits, i.e. is a desideratum.
>
> The BARC example is easily avoided by selecting some kind of randomized curve
> generation method.  Hence it also demonstrates a narrow utility of randomized
> curve generation methods in contributing to the NUMS property: in that it
> protects the user from dial-up weaknesses where the attacker can find weak
> curves without any searching.  In other words, the BARC example serves not
> just a criticism of rigid-only curves, but also as a demo a small degree of
> plausible usefulness for random curves.
>
>> Really the only argument was supersingular curves,
>
> Well, supersingularity is just a property of curves, not an attack.  I'm
> looking for arguments to resist attacks.  The supersingularity alone implies
> the MOV attack, but does not necessarily imply the PH attack.  It's the fact
> that p+1 is smooth plus supersingularity in BARC that leads to the PH attack
> working so well.  Also, I only know how to find supersingular curves when p=3
> mod 4 or p=2 mod 3.  Since p=1 mod 12 for Curve25519, I don't know how to find
> a supersingular curve over GF(2^255-19).  Is this planned?  If not, it is a
> side effect of rigidity, or some kind of non-rigidity?

The existence of efficient public key cryptography implies P!=NP. Any
argument that's actually strong in ruling out attacks would be
evidence for P!=NP. Even something like "an attack on this curve has
to work for a proportion 1/x of non-isogenous curves" would pretty
impressive. We're really, really, bad at lower bounds. We can't even
separate NC from P. We can't show hash functions exist, or even
formalize what a hash function should do. You aren't going to get
anything worthwhile without a lot of struggle, and some luck. To the
extent we have a formalization of anti-manipulation, it's the one DJB
used.

We can't hope to do more than avoid publically known attacks, think
really hard about solving the DLP, think about implementation issues
that have doomed cryptosystems and design standards to avoid them. And
despite that work being done for RSA we've seen steady chopping away
at the complexity of the NFS, together with persistent implementation
issues.

Sincerely,
Watson Ladd

>
> Interestingly, BARC gives an example of an attack in which the field choice
> matters and the rarer field choices (the p+1 smooth ones) are the ones more
> vulnerable.  In other words, it actually lend some plausibility Brainpool's
> choice of random field sizes.
>
>> which I admit being mildly convinced by.
>
> I thought I'd never see this day :-)
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg
>



-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin