Re: [Cfrg] Fwd: Re: Safecurves draft

Manuel Pégourié-Gonnard <mpg@elzevir.fr> Thu, 09 January 2014 09:28 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 0BEBC1AE08D for <cfrg@ietfa.amsl.com>; Thu, 9 Jan 2014 01:28:02 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0.994
X-Spam-Level:
X-Spam-Status: No, score=0.994 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FH_RELAY_NODNS=1.451, HELO_EQ_FR=0.35, MIME_8BIT_HEADER=0.3, RDNS_NONE=0.793] autolearn=no
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 c4Da4ZePQnIa for <cfrg@ietfa.amsl.com>; Thu, 9 Jan 2014 01:28:00 -0800 (PST)
Received: from mordell.elzevir.fr (unknown [IPv6:2001:4b98:dc0:41:216:3eff:feeb:c406]) by ietfa.amsl.com (Postfix) with ESMTP id 9D8E71ADBD1 for <cfrg@irtf.org>; Thu, 9 Jan 2014 01:27:59 -0800 (PST)
Received: from thue.elzevir.fr (thue.elzevir.fr [88.165.216.11]) by mordell.elzevir.fr (Postfix) with ESMTPS id 3696B161DF for <cfrg@irtf.org>; Thu, 9 Jan 2014 10:27:49 +0100 (CET)
Received: from [192.168.0.124] (unknown [192.168.0.254]) by thue.elzevir.fr (Postfix) with ESMTPSA id 11F892988A for <cfrg@irtf.org>; Thu, 9 Jan 2014 10:27:47 +0100 (CET)
Message-ID: <52CE6B92.4030504@elzevir.fr>
Date: Thu, 09 Jan 2014 10:27:46 +0100
From: =?UTF-8?B?TWFudWVsIFDDqWdvdXJpw6ktR29ubmFyZA==?= <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
References: <52CE59C1.6020500@akr.io> <52CE59F4.8050205@akr.io>
In-Reply-To: <52CE59F4.8050205@akr.io>
X-Enigmail-Version: 1.6
OpenPGP: id=98EED379; url=https://elzevir.fr/gpg/mpg.asc
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
Subject: Re: [Cfrg] Fwd: Re: Safecurves draft
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, 09 Jan 2014 09:28:02 -0000

On 09/01/2014 09:12, Alyssa Rowan wrote:
> On 08/01/2014 23:50, Watson Ladd wrote:
> 
>> I don't want to rename curves because that induces consistency
>> issues.
> 
> Entirely accepted: I raised it merely as a question. People are
> already beginning to adopt these curves of their own volition, so
> changing the names of them could be confusing, yes.
> 
About names, I'd really like the names to reflect the type of the curve
(Montgomery or Edwards). This is already the case for other curve families, by
the way. So, Mxxx and Exxx seem great to me. I'd even go so far as to rename
Curve25519 as M255, but I'm sure there are good reasons to disagree on this point.

While at it, I also think the document should define the curves for each type in
distinct sections. Overall, the goal is that it should be easy for other
document to define the of just the Montgomery (or just the Edwards) curves for
use in a protocol, and refer to the appropriate section of this draft.

>> - no indication of security concerns and need or lack of checking
>> public key values
> 
> Important advantages. We should cover this, I think.
> 
While at it, we should also document the requirements for private keys, which
are different from the way they are usually chosen for short Weierstrass curves.

>> […several objections to the name ‘safe’, implying other curves
>> aren’t, raising the NIST curves…]
> 
> As the SafeCurves criteria clearly explains:
> [...]
> 
I think this kind of thing should go in the draft :)

> Compared to the curves we've got at the moment (most of which don't
> even have clearly-explained design criteria, and the ones that do are
> unfortunately inefficient), the choice of name seems entirely apt to me.
> 
I tend to disagree on this point. Don't take me wrong, I think these curves are
a useful tool in making security better, for all of the reasons mentioned above.
However, they're not some kind of magic security pill either, and IMO it would
be bad for security to give this impression. This goes both sides:
- people shouldn't think any implementation of the "safe" Montgomery/Edwards
curves is automatically flawless;
- people shouldn't think the NIST/Brainpool curves are so impossibly hard to
implement right that they don't even try.

Take the points list on the frontpage of the safecurves site, for instance
(numbered by me for convenience).

1. Your implementation produces incorrect results for some rare curve points.
2. Your implementation leaks secret data when the input isn't a curve point.
3. Your implementation leaks secret data through branch timing.
4. Your implementation leaks secret data through cache timing.

Point 3 and 4 are entirely a property of the implementation, not of the curve.
Point 2 can (and must) be addressed by telling everyone to validate points. I
mean, the idea of validating inputs shouldn't be new to anyone implementing
crypto! About point 1, it probably depends on the reference used, but Hankerson
& al's "Guide to ECC", which looks like a classic to me, gives formulas that are
correct in all cases (but have data-dependant branches). Besides, this problem
can be completely avoided by using a well-chosen multiplication algorithm,
ensuring that the special cases will never be hit.

Overall, of course it's nice that issues 1 and 2 are completely annihilated by
Montgomery and Edwards curves, and to be fair point 4 is a bit easier to address
with these curves too. But I wouldn't go as far as to say that they are
inherently safer than the Brainpool curves. They are easier to implement
correctly, have excellent performance, and reduce the conflicts between security
and efficiency/ease of implementation, which is great. But I'm still a bit
uncomfortable with calling them "safe" and implying all other curves aren't.

Manuel.

PS: besides, there's a practical advantage in being more specific than "safe":
when/if someone comes with other curves which have arguably nicer
security/implementation properties, a neutral and specific term will remain
appropriate, while "safe" will sound odd. (It's like calling things "modern".)