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

Johannes Merkle <johannes.merkle@secunet.com> Thu, 16 January 2014 11:00 UTC

Return-Path: <Johannes.Merkle@secunet.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 9617D1AE2A7 for <cfrg@ietfa.amsl.com>; Thu, 16 Jan 2014 03:00:02 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -3.138
X-Spam-Level:
X-Spam-Status: No, score=-3.138 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_LOW=-0.7, RP_MATCHES_RCVD=-0.538] 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 KfYcdnAQqfo3 for <cfrg@ietfa.amsl.com>; Thu, 16 Jan 2014 03:00:00 -0800 (PST)
Received: from a.mx.secunet.com (a.mx.secunet.com [195.81.216.161]) by ietfa.amsl.com (Postfix) with ESMTP id 497581AE07C for <cfrg@irtf.org>; Thu, 16 Jan 2014 02:59:59 -0800 (PST)
Received: from localhost (alg1 [127.0.0.1]) by a.mx.secunet.com (Postfix) with ESMTP id BC96D1A0087; Thu, 16 Jan 2014 11:59:45 +0100 (CET)
X-Virus-Scanned: by secunet
Received: from a.mx.secunet.com ([127.0.0.1]) by localhost (a.mx.secunet.com [127.0.0.1]) (amavisd-new, port 10024) with LMTP id aInzTIvH9uty; Thu, 16 Jan 2014 11:59:44 +0100 (CET)
Received: from mail-gw-int (unknown [10.53.40.207]) by a.mx.secunet.com (Postfix) with ESMTP id 00BBB1A0076; Thu, 16 Jan 2014 11:59:24 +0100 (CET)
Received: from [10.53.40.200] (port=58332 helo=mail-srv1.secumail.de) by mail-gw-int with esmtp (Exim 4.80 #2 (Debian)) id 1W3kbJ-0007kM-Qu; Thu, 16 Jan 2014 11:55:05 +0100
Received: from [10.208.1.57] ([10.208.1.57]) by mail-srv1.secumail.de with Microsoft SMTPSVC(6.0.3790.4675); Thu, 16 Jan 2014 11:59:24 +0100
Message-ID: <52D7BB8B.90007@secunet.com>
Date: Thu, 16 Jan 2014 11:59:23 +0100
From: Johannes Merkle <johannes.merkle@secunet.com>
User-Agent: Mozilla/5.0 (Windows NT 6.1; rv:24.0) Gecko/20100101 Thunderbird/24.2.0
MIME-Version: 1.0
To: David McGrew <mcgrew@cisco.com>, 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> <52D72201.6030803@cisco.com>
In-Reply-To: <52D72201.6030803@cisco.com>
X-Enigmail-Version: 1.6
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
X-OriginalArrivalTime: 16 Jan 2014 10:59:24.0096 (UTC) FILETIME=[042EF400:01CF12AA]
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 11:00:02 -0000

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.

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