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

Manuel Pégourié-Gonnard <mpg@elzevir.fr> Wed, 15 January 2014 21:36 UTC

Return-Path: <mpg@elzevir.fr>
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 B1FA11AE40C for <cfrg@ietfa.amsl.com>; Wed, 15 Jan 2014 13:36:52 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -3.788
X-Spam-Level:
X-Spam-Status: No, score=-3.788 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, GB_I_LETTER=-2, HELO_EQ_FR=0.35, MIME_8BIT_HEADER=0.3, 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 Mavvs0F9_GzB for <cfrg@ietfa.amsl.com>; Wed, 15 Jan 2014 13:36:50 -0800 (PST)
Received: from mordell.elzevir.fr (mordell.elzevir.fr [92.243.3.74]) by ietfa.amsl.com (Postfix) with ESMTP id 43BB31AE237 for <cfrg@irtf.org>; Wed, 15 Jan 2014 13:36:50 -0800 (PST)
Received: from thue.elzevir.fr (thue.elzevir.fr [88.165.216.11]) by mordell.elzevir.fr (Postfix) with ESMTPS id BEB86161BF for <cfrg@irtf.org>; Wed, 15 Jan 2014 22:36:37 +0100 (CET)
Received: from [192.168.0.124] (unknown [192.168.0.254]) by thue.elzevir.fr (Postfix) with ESMTPSA id C6F6D2986B for <cfrg@irtf.org>; Wed, 15 Jan 2014 22:36:35 +0100 (CET)
Message-ID: <52D6FF63.8060801@elzevir.fr>
Date: Wed, 15 Jan 2014 22:36:35 +0100
From: =?ISO-8859-1?Q?Manuel_P=E9gouri=E9-Gonnard?= <mpg@elzevir.fr>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Icedove/24.1.1
MIME-Version: 1.0
To: "'cfrg@irtf.org'" <cfrg@irtf.org>
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>
X-Enigmail-Version: 1.6
OpenPGP: id=98EED379; url=https://elzevir.fr/gpg/mpg.asc
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
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 21:36:52 -0000

Hi Dan,

On 15/01/2014 18:02, Dan Brown wrote:
> 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.

We can probably take this as an indication that the document should be
very clear on that point (like, clearer that the safecurves pages).

> 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.)
> 
I think we can agree that NUNS is a very desirable property, but that
almost by definition we can't produce a curve for which it holds with
absolute certainty: all we can do it try to maximise the probability,
under reasonable assumptions, that the curve has this property.

> 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.
> 
For what it's worth, my current understanding is that, for a
Brainpool-like construction to maximise the NUNS probability, the only
necessary assumption is that the PRF and the "NUMS" seed have no special
relationship with the potential attacks on curves, which certainly looks
like a very reasonable assumption to make. OTOH, for a Curve25519-like
"rigid" selection to provide NUNS (with high probability), a necessary
assumption is that the upcoming (or currently known only to a few)
attacks don't have a higher probability to apply on a curve with small
coefficients than on the set of all curves (resisting known attacks).

IIRC the discussions on the TLS list, Daniel Bernstein quite strongly
holds the opinion that this assumption is reasonable, and if I
understand your last email correctly, you're not claiming it's an
unreasonable assumption to make.

Obviously, a point in favour of the "PRF(NUMS seed)" construction is
that it's probably easier to believe in it without any particular
knowledge of the attacks on ECDLOG and the deeper properties that make them
work or not.

But my very humble opinion, mostly based on comments by people with more
knowledge than me on this topic, is that both assumptions are
reasonable enough to give us confidence in the security of the curves (both
Brainpool and "rigid" ones) against upcoming attacks.

Manuel.