Re: [Cfrg] Progress on curve recommendations for TLS WG
Dan Brown <dbrown@certicom.com> Fri, 15 August 2014 21:19 UTC
Return-Path: <dbrown@certicom.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 6367E1A06C3 for <cfrg@ietfa.amsl.com>; Fri, 15 Aug 2014 14:19:45 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.9
X-Spam-Level:
X-Spam-Status: No, score=-1.9 tagged_above=-999 required=5 tests=[BAYES_00=-1.9] 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 LcIUA10_pX-J for <cfrg@ietfa.amsl.com>; Fri, 15 Aug 2014 14:19:43 -0700 (PDT)
Received: from smtp-p01.blackberry.com (smtp-p01.blackberry.com [208.65.78.88]) by ietfa.amsl.com (Postfix) with ESMTP id E120A1A066D for <cfrg@irtf.org>; Fri, 15 Aug 2014 14:19:42 -0700 (PDT)
Received: from xct101cnc.rim.net ([10.65.161.201]) by mhs212cnc.rim.net with ESMTP/TLS/AES128-SHA; 15 Aug 2014 17:19:42 -0400
Received: from XCT114CNC.rim.net (10.65.161.214) by XCT101CNC.rim.net (10.65.161.201) with Microsoft SMTP Server (TLS) id 14.3.174.1; Fri, 15 Aug 2014 17:19:41 -0400
Received: from XMB116CNC.rim.net ([fe80::45d:f4fe:6277:5d1b]) by XCT114CNC.rim.net ([::1]) with mapi id 14.03.0174.001; Fri, 15 Aug 2014 17:19:40 -0400
From: Dan Brown <dbrown@certicom.com>
To: "'cfrg@irtf.org'" <cfrg@irtf.org>
Thread-Topic: [Cfrg] Progress on curve recommendations for TLS WG
Thread-Index: AQHPrSkVFDDUD0tW0keHIpwhcB27wpvR3EOAgAAXPgCAAB3vgIAAAdUAgAAk/YCAAAckgP//yDWQgABNSQD//73osA==
Date: Fri, 15 Aug 2014 21:19:40 +0000
Message-ID: <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>
In-Reply-To: <CACsn0cndH3hF-hvFFYnik2Bxs3+sm7ALHLTxSPCZNzJ1bLJMjg@mail.gmail.com>
Accept-Language: en-CA, en-US
Content-Language: en-US
X-MS-Has-Attach: yes
X-MS-TNEF-Correlator:
x-originating-ip: [10.65.160.249]
Content-Type: multipart/signed; protocol="application/x-pkcs7-signature"; micalg="SHA1"; boundary="----=_NextPart_000_0115_01CFB8AD.18CFFA90"
MIME-Version: 1.0
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/r_H-fnuLHGM57pNYjcR6P0AGTOc
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: Fri, 15 Aug 2014 21:19:45 -0000
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. >> >> 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. 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? 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] Progress on curve recommendations for TLS … Paterson, Kenny
- Re: [Cfrg] Progress on curve recommendations for … Watson Ladd
- Re: [Cfrg] Progress on curve recommendations for … Russ Housley
- Re: [Cfrg] Progress on curve recommendations for … D. J. Bernstein
- Re: [Cfrg] Progress on curve recommendations for … Dan Brown
- Re: [Cfrg] Progress on curve recommendations for … Ilari Liusvaara
- Re: [Cfrg] Progress on curve recommendations for … Robert Ransom
- Re: [Cfrg] Progress on curve recommendations for … Johannes Merkle
- Re: [Cfrg] Progress on curve recommendations for … Johannes Merkle
- Re: [Cfrg] Progress on curve recommendations for … Alyssa Rowan
- Re: [Cfrg] Progress on curve recommendations for … Johannes Merkle
- Re: [Cfrg] Progress on curve recommendations for … Watson Ladd
- Re: [Cfrg] Progress on curve recommendations for … Dan Brown
- Re: [Cfrg] Progress on curve recommendations for … Johannes Merkle
- Re: [Cfrg] Progress on curve recommendations for … Watson Ladd
- Re: [Cfrg] Progress on curve recommendations for … Dan Brown
- Re: [Cfrg] Progress on curve recommendations for … Dan Brown
- Re: [Cfrg] Progress on curve recommendations for … Watson Ladd
- Re: [Cfrg] Progress on curve recommendations for … Andy Lutomirski
- Re: [Cfrg] Progress on curve recommendations for … Dan Brown
- Re: [Cfrg] Progress on curve recommendations for … Mike Hamburg
- Re: [Cfrg] Progress on curve recommendations for … Andrey Jivsov
- Re: [Cfrg] Progress on curve recommendations for … Michael Hamburg
- Re: [Cfrg] Progress on curve recommendations for … Watson Ladd
- Re: [Cfrg] Progress on curve recommendations for … D. J. Bernstein
- Re: [Cfrg] Progress on curve recommendations for … D. J. Bernstein
- Re: [Cfrg] Progress on curve recommendations for … Andrey Jivsov
- Re: [Cfrg] Progress on curve recommendations for … Michael Hamburg