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

David McGrew <mcgrew@cisco.com> Thu, 16 January 2014 13:13 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 D19351AE21E for <cfrg@ietfa.amsl.com>; Thu, 16 Jan 2014 05:13:34 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -10.039
X-Spam-Level:
X-Spam-Status: No, score=-10.039 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, 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 EhRedqwa2WsC for <cfrg@ietfa.amsl.com>; Thu, 16 Jan 2014 05:13:33 -0800 (PST)
Received: from alln-iport-8.cisco.com (alln-iport-8.cisco.com [173.37.142.95]) by ietfa.amsl.com (Postfix) with ESMTP id 6C5321AE1A4 for <cfrg@irtf.org>; Thu, 16 Jan 2014 05:13:33 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cisco.com; i=@cisco.com; l=2060; q=dns/txt; s=iport; t=1389878001; x=1391087601; h=message-id:date:from:mime-version:to:cc:subject: references:in-reply-to:content-transfer-encoding; bh=rMifeDIMS8eGj/Y4o9KVTaxsybWUEyMgrYF1rUEi8g0=; b=bSgTcXbBCw7MLIrG+vPmuJNeOiA9zSS40vrBdJljZtL2kuJ7zaUGOL8R ikLhPuLh7OtD0ElZZ8sew2csT9Soje8otsIM2H9/XE3wcjnIWjdEu1OP1 eqXhGq9C7UKVbl8czt9/e3MM66c3Yeijrzvdnk0EI7xZPeLEzr1o/PsmB 0=;
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: Ai8FAJ7Z11KtJXG//2dsb2JhbABZgwu5EYMIgQ8WdIIlAQEBAwEnEUABEAsYCRYPCQMCAQIBRQYNAQcCh3gIxB0Xjn8HhDgBA4lHjlqGRotRg0se
X-IronPort-AV: E=Sophos;i="4.95,667,1384300800"; d="scan'208";a="13315471"
Received: from rcdn-core2-4.cisco.com ([173.37.113.191]) by alln-iport-8.cisco.com with ESMTP; 16 Jan 2014 13:13:21 +0000
Received: from [10.0.2.15] (rtp-mcgrew-8914.cisco.com [10.117.10.229]) by rcdn-core2-4.cisco.com (8.14.5/8.14.5) with ESMTP id s0GDDK2c000660; Thu, 16 Jan 2014 13:13:20 GMT
Message-ID: <52D7DAF1.4070506@cisco.com>
Date: Thu, 16 Jan 2014 08:13:21 -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: Johannes Merkle <johannes.merkle@secunet.com>
References: <20140113230750.6111382.6841.8590@certicom.com> <52D48450.3070701@akr.io> <810C31990B57ED40B2062BA10D43FBF5C1F190@XMB116CNC.rim.net> <52D59C35.10807@cisco.com> <810C31990B57ED40B2062BA10D43FBF5C2217A@XMB116CNC.rim.net> <52D72201.6030803@cisco.com> <52D7BB8B.90007@secunet.com>
In-Reply-To: <52D7BB8B.90007@secunet.com>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Cc: Dan Brown <dbrown@certicom.com>, "'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 13:13:35 -0000

Hi Johannes,

On 01/16/2014 05:59 AM, Johannes Merkle wrote:
> David McGrew schrieb am 16.01.2014 01:04:
>> 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.)
>>
> My understanding of Dan's reasoning is different. I think, the "unknown" in "probability of being vulnerable to an
> unknown attack" relates to the entity generating the curve, i.e. NUTS captures the objective of generating curves in a
> way that minimizes the "probability" that the curve may be or become vulnerably to attacks unknown by the party
> generating the curve.
>
> Of course, "probability" refers more to a "feeling in the guts" than to a (Bayesian) probability.
>
>
>> 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?
>>
> In retrospective this approach would be less convincing because some might still speculate that seed definition had been
> specified at a later point of time, in spite of all evidence records.

Yes, I agree.

David

>
> And still, DJB could argue that the freedom in choices made for the derivation of the parameters, e.g. SHA-512, leaves
> some questions unanswered, and he would probably label these curves (on the safecurve page) as being only "somewhat rigid".
>
> regards,
> Johannes
>
> .
>