Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid v Pseudorandom

David McGrew <mcgrew@cisco.com> Thu, 16 January 2014 00:04 UTC

Return-Path: <mcgrew@cisco.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 875E01AE425 for <cfrg@ietfa.amsl.com>; Wed, 15 Jan 2014 16:04:39 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -17.038
X-Spam-Level:
X-Spam-Status: No, score=-17.038 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, GB_I_LETTER=-2, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_HI=-5, RP_MATCHES_RCVD=-0.538, SPF_PASS=-0.001, USER_IN_DEF_DKIM_WL=-7.5] 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 uB6QQgXauOR1 for <cfrg@ietfa.amsl.com>; Wed, 15 Jan 2014 16:04:35 -0800 (PST)
Received: from rcdn-iport-2.cisco.com (rcdn-iport-2.cisco.com [173.37.86.73]) by ietfa.amsl.com (Postfix) with ESMTP id 440B11AE452 for <cfrg@irtf.org>; Wed, 15 Jan 2014 16:04:35 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cisco.com; i=@cisco.com; l=25462; q=dns/txt; s=iport; t=1389830663; x=1391040263; h=message-id:date:from:mime-version:to:cc:subject: references:in-reply-to; bh=j7sfajCmj52OOer4z5FkOCtchZR1eYsz1+3ry1heQRs=; b=a9Wq5vZJwl2r+MtWly85z94vfUgTJvT1Q9d1lQswtcGatQLmMGBOoST0 k6l4waj+WIXfXj6SBWzucgboIM6poZihc983tQVKz4Ksl5cnnqLpU8wFU Xqy1EosyS641VuPAjKBO53c1rQ2c5cj4YMjj046X+elc1jEGS4nfTUNqi c=;
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: Ag4FAAwh11KtJXG9/2dsb2JhbABZgkdEiWmyMYEQFnSCJQEBAQMBJwZBCgEFCwsOAwQBAQEJFgEHBwkDAgECATQJCAYNAQUCAod4CMM0F44dEQFLBQYBhDcBA4lHjlmGRYtQg0segTU
X-IronPort-AV: E=Sophos; i="4.95,665,1384300800"; d="scan'208,217"; a="297566796"
Received: from rcdn-core2-2.cisco.com ([173.37.113.189]) by rcdn-iport-2.cisco.com with ESMTP; 16 Jan 2014 00:04:19 +0000
Received: from [10.0.2.15] (rtp-mcgrew-8914.cisco.com [10.117.10.229]) by rcdn-core2-2.cisco.com (8.14.5/8.14.5) with ESMTP id s0G04H1o007402; Thu, 16 Jan 2014 00:04:18 GMT
Message-ID: <52D72201.6030803@cisco.com>
Date: Wed, 15 Jan 2014 19:04:17 -0500
From: David McGrew <mcgrew@cisco.com>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:17.0) Gecko/20130922 Icedove/17.0.9
MIME-Version: 1.0
To: Dan Brown <dbrown@certicom.com>
References: <20140113230750.6111382.6841.8590@certicom.com> <52D48450.3070701@akr.io> <810C31990B57ED40B2062BA10D43FBF5C1F190@XMB116CNC.rim.net> <52D59C35.10807@cisco.com> <810C31990B57ED40B2062BA10D43FBF5C2217A@XMB116CNC.rim.net>
In-Reply-To: <810C31990B57ED40B2062BA10D43FBF5C2217A@XMB116CNC.rim.net>
Content-Type: multipart/alternative; boundary="------------030507060602000201010007"
Cc: "'cfrg@irtf.org'" <cfrg@irtf.org>
Subject: Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid v Pseudorandom
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: Thu, 16 Jan 2014 00:04:39 -0000

Hi Dan,

On 01/15/2014 12:02 PM, Dan Brown wrote:
>
> Hi David,
>
> Good point about the "nothing up my sleeve" (NUMS) property. That's 
> what I meant when I earlier wrote the paragraph "Yes, rigidity helps 
> more to prevent malicious generation of the curve.  I am not 
> disagreeing with the safecurves site on that point. ".
>
> I re-read the safecurves rigidity page today. The safecurves rigidity 
> page does not use the NUMS term, but, in its strictest, to-the-letter 
> interpretation, I think it coincides with the meaning of NUMS.  I.e. 
> rigid == NUMS.
>
> I did ask earlier in this thread if I was misinterpreting the rigidity 
> page. Specifically, I was trying to ask if it was claiming something 
> stronger than NUMS.  Apparently I was indeed misinterpreting, at least 
> in to-the-letter sense, because I was construing the page to say 
> something more than NUMS.  Furthermore, in previous discussion with 
> Bernstein on the TLS mailing list, I had thought Bernstein was making 
> stronger claims than just NUMS, which may have reinforced my 
> misinterpretation above.  In retrospect, the TLS email exchange may 
> also have been mutual misunderstanding.
>
> David, your email and others are consistent with my rambling prose 
> being ineffective to explain my main point to a wider audience, so 
> I'll now try out some more emphatic language.
>

Sure.  I think that I did follow most of your previous post, but I was 
not sure that I could add more illumination on the subject, so I 
refrained from commenting.

> Consider a "nothing up their sleeves" (NUTS) property.  What it means: 
> if X has the NUTS property, then X is not affected by some attack that 
> "they" might know. Just to be clear, NUTS is an orthogonal property to 
> NUMS (i.e. they vs me).  For a potential example, perhaps P256 has the 
> NUTS property but not the NUMS property.  Also, achieving the NUMS and 
> NUTS properties are tasks, for which various tools can be used, and 
> arguments present as to whether, or to what extent, they are achieved.
>

I am sorry, I am not sure that I follow you.  My own thinking has been 
that NUMS would apply to the process used to generate the curve, rather 
than a curve itself.   I can see that some processes might generate 
trustworthy curves no matter who runs the process (which seems to be the 
NUTS case) and other processes might generate curves that I trust only 
if I run the process (which seems to be the NUMS case).

> Next, consider a "nothing up nobody's sleeve" (NUNS) property. [Please 
> forgive the double negative used to make this mnemonic acronym.  Think 
> additive negation, instead of standard English grammar's 
> multiplicative negation.  Think additive notation for ECC, as an 
> additional mnemonic.] It seems to me that NUMS+NUTS==NUNS.
>
> It seems to me that NUNS is not only formally stronger than NUMS, but 
> is also preferable to just NUMS only, because we usually define 
> algorithm security independently who the attacker is (not to be 
> confused with the capabilities they have, where we might make 
> distinctions.)
>
> If I understand Watson and Alyssa correctly (although I am not too 
> confident of my understanding), they think NUTS is irrelevant and 
> unachievable, respectively.
>
> If I understand Dan Bernstein's emails from the TLS list correctly, he 
> thinks NUTS is much less important than NUMS, because of the 
> quantities involved (and I agree), but nevertheless, that there are 
> arguments that the safe curves provide the NUTS property, namely the 
> all known attacks are independent of coefficient size (and I agree).  
> So, it is reasonable to argue the NUTS property to the safe curves 
> (and I agree).
>
> My primary point in this thread was meant to be that PRF(NUMS) => NUNS
>

I think the advocates of "rigid" curves mean to highlight the fact that 
the rigid process can generate only a small number of curves. In 
contrast, when we are presented by a verifiably pseudorandom curve that 
was generated with an input seed of unknown provenance, it might be the 
case that many seeds were tested and rejected until one was found that 
generated a curve on which the DL problem could be solved more easily.   
(Your model of "each curve has some probability of being vulnerable to 
an unknown attack" I think captures the concern, though one could 
generalize to a situation in which the expected running time of the DLP 
varied with the parameters.)

Now, it would be possible to make a "rigid" process out of a 
pseudorandom process by using a seed value that nobody can control (say, 
the sha512 hash of SP500 prices on a given future date). Perhaps this is 
what you mean by PRF(NUMS) -> NUNS?

regards,

David

> (summarizing the Brainpool curve selection process), without relying 
> about the assumption on attacks being independent of coefficient size, 
> so that random curve selection, as in Brainpool, provides better NUNS 
> than the curve selection process outlined in the safe curves site.  
>  Unfortunately, I did use Brainpool in the subject, which may have 
> undermined my own point, opening the door to speed comparisons, field 
> size issues, etc.
>
> I was really expecting, to no avail, somebody to finally concede this 
> point, but contend that the improvement was just very slight, because 
> of the reasonableness of the coefficient-size-independence 
> assumption.  Oh well.
>
> My secondary point was that some people may be confusing NUMS and 
> NUNS. Well, that's an ad hominem point, so my confidence is very low 
> there. Also, it is clearly nearly impossible to argue, since a 
> person's thoughts can change quickly.  I'm pretty Watson and Alyssa 
> disagree on this secondary point.
>
> Best regards,
>
> Dan
>
> *From:*David McGrew [mailto:mcgrew@cisco.com]
> *Sent:* Tuesday, January 14, 2014 3:21 PM
> *To:* Dan Brown
> *Cc:* 'akr@akr.io'; 'cfrg@irtf.org'
> *Subject:* Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid v Pseudorandom
>
> Hi Dan,
>
> thanks for sharing your thoughts.  It seems to me that the arguments 
> in favor of rigid curves comes down to the "nothing up my sleeve" 
> argument: if there are no free parameters to be chosen when 
> constructing an elliptic curve group, then there is no need to trust 
> the person doing the construction.
>
> ---------------------------------------------------------------------
> 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.