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

David McGrew <> Thu, 16 January 2014 13:13 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id D19351AE21E for <>; Thu, 16 Jan 2014 05:13:34 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -10.039
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 ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id EhRedqwa2WsC for <>; Thu, 16 Jan 2014 05:13:33 -0800 (PST)
Received: from ( []) by (Postfix) with ESMTP id 6C5321AE1A4 for <>; Thu, 16 Jan 2014 05:13:33 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple;;; 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 ([]) by with ESMTP; 16 Jan 2014 13:13:21 +0000
Received: from [] ( []) by (8.14.5/8.14.5) with ESMTP id s0GDDK2c000660; Thu, 16 Jan 2014 13:13:20 GMT
Message-ID: <>
Date: Thu, 16 Jan 2014 08:13:21 -0500
From: David McGrew <>
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 <>
References: <> <> <> <> <> <> <>
In-Reply-To: <>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Cc: Dan Brown <>, "''" <>
Subject: Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid v Pseudorandom
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-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.


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