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

Dan Brown <dbrown@certicom.com> Wed, 15 January 2014 17:02 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 2D44E1AE017 for <cfrg@ietfa.amsl.com>; Wed, 15 Jan 2014 09:02:36 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -3.899
X-Spam-Level:
X-Spam-Status: No, score=-3.899 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, GB_I_LETTER=-2, HTML_MESSAGE=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 XLPxIUrAhYcB for <cfrg@ietfa.amsl.com>; Wed, 15 Jan 2014 09:02:31 -0800 (PST)
Received: from smtp-p02.blackberry.com (smtp-p02.blackberry.com [208.65.78.89]) by ietfa.amsl.com (Postfix) with ESMTP id F1D0A1AE132 for <cfrg@irtf.org>; Wed, 15 Jan 2014 09:02:24 -0800 (PST)
Received: from xct107cnc.rim.net ([10.65.161.207]) by mhs215cnc.rim.net with ESMTP/TLS/AES128-SHA; 15 Jan 2014 12:02:05 -0500
Received: from XMB116CNC.rim.net ([fe80::45d:f4fe:6277:5d1b]) by XCT107CNC.rim.net ([fe80::b815:71ef:9f8f:e07c%16]) with mapi id 14.03.0158.001; Wed, 15 Jan 2014 12:02:04 -0500
From: Dan Brown <dbrown@certicom.com>
To: "'mcgrew@cisco.com'" <mcgrew@cisco.com>
Thread-Topic: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid v Pseudorandom
Thread-Index: Ac8QtEhLa4qQ887tT6aHk4eH+te9FQANPUQAABWJmQAAFCuIgAAcC7wQ
Date: Wed, 15 Jan 2014 17:02:03 +0000
Message-ID: <810C31990B57ED40B2062BA10D43FBF5C2217A@XMB116CNC.rim.net>
References: <20140113230750.6111382.6841.8590@certicom.com> <52D48450.3070701@akr.io> <810C31990B57ED40B2062BA10D43FBF5C1F190@XMB116CNC.rim.net> <52D59C35.10807@cisco.com>
In-Reply-To: <52D59C35.10807@cisco.com>
Accept-Language: en-CA, en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
x-originating-ip: [10.65.160.250]
Content-Type: multipart/alternative; boundary="_000_810C31990B57ED40B2062BA10D43FBF5C2217AXMB116CNCrimnet_"
MIME-Version: 1.0
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: Wed, 15 Jan 2014 17:02:36 -0000

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.

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.

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 (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.