Re: [TLS] Using Brainpool curves in TLS

Nico Williams <nico@cryptonector.com> Wed, 16 October 2013 16:29 UTC

Return-Path: <nico@cryptonector.com>
X-Original-To: tls@ietfa.amsl.com
Delivered-To: tls@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 856FC11E8313 for <tls@ietfa.amsl.com>; Wed, 16 Oct 2013 09:29:31 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.981
X-Spam-Level:
X-Spam-Status: No, score=-1.981 tagged_above=-999 required=5 tests=[AWL=-0.004, BAYES_00=-2.599, FM_FORGED_GMAIL=0.622]
Received: from mail.ietf.org ([12.22.58.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id YQWI9O-5C8kg for <tls@ietfa.amsl.com>; Wed, 16 Oct 2013 09:29:27 -0700 (PDT)
Received: from homiemail-a16.g.dreamhost.com (caiajhbdccac.dreamhost.com [208.97.132.202]) by ietfa.amsl.com (Postfix) with ESMTP id D436511E8304 for <tls@ietf.org>; Wed, 16 Oct 2013 09:29:26 -0700 (PDT)
Received: from homiemail-a16.g.dreamhost.com (localhost [127.0.0.1]) by homiemail-a16.g.dreamhost.com (Postfix) with ESMTP id 4DF61508072 for <tls@ietf.org>; Wed, 16 Oct 2013 09:29:26 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=cryptonector.com; h= mime-version:in-reply-to:references:date:message-id:subject:from :to:cc:content-type; s=cryptonector.com; bh=gM0ta3DkWJ67gqm4dhA6 B1KAeUQ=; b=eh4rR4OXiCBy8xTEET/hakLKfRUZ6HTf+MlH1qdrcubNHgDVu8nQ AZ1G1ziqgAWvQDN/l8baOaG9qP27L850KQenWzcmJc/MWMNygfvqG1ZRe0Ecw4a3 nwuXHAIJJSdggVVeWxmMuc3uCvNrfNPUmjTKOdnvjd/QRu3LuF/dZ1Q=
Received: from mail-ie0-f180.google.com (mail-ie0-f180.google.com [209.85.223.180]) (using TLSv1 with cipher RC4-SHA (128/128 bits)) (No client certificate requested) (Authenticated sender: nico@cryptonector.com) by homiemail-a16.g.dreamhost.com (Postfix) with ESMTPSA id 26950508084 for <tls@ietf.org>; Wed, 16 Oct 2013 09:29:26 -0700 (PDT)
Received: by mail-ie0-f180.google.com with SMTP id e14so1763987iej.11 for <tls@ietf.org>; Wed, 16 Oct 2013 09:29:25 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=WmrdsK+j1JSmYakR6zA45R+oKvvaCgG5Rk4L+irzodw=; b=JhlfzL4JCzMsAQWOy7IJI1+qNfw2dzlqx2CI/6/mIQOVmuwnMjng1k8tJVi1laMi6J dusCICTEXdT0+8FL15lYdPMHR5zuwxdyk1hZUnpXcKOcXSn0KK04tBnRSQhDHjPndAjF JFbiKT5PWnPptauz+SEQ4+PnrnAFtKTJbii7xjk5GpMy9lJyPENjaKLrQb32YKdmNNvj QoGSNt9yc+4fKvnMYN4heHdHAutaOgjkkv6mWb297Ptv3QLYYk+l2Wrzj31i+Ac+G+LH dE1fGPLbKyC8tQu3iqoy8376SGzM4qogCt3/WUEpg8Ls1RGCBqBjO36bnPkSsc/Oh2r9 XB0g==
MIME-Version: 1.0
X-Received: by 10.42.82.196 with SMTP id e4mr1607107icl.58.1381940965242; Wed, 16 Oct 2013 09:29:25 -0700 (PDT)
Received: by 10.64.128.225 with HTTP; Wed, 16 Oct 2013 09:29:25 -0700 (PDT)
In-Reply-To: <525EB695.9070607@secunet.com>
References: <525C11B5.2050604@secunet.com> <525CEFA4.2030903@funwithsoftware.org> <01b901cec9a0$004e12b0$00ea3810$@offspark.com> <CACsn0ckOnrQTOLdUo9gT8hbTx4cEqX9CP6=BRFYtpV1CpT7HXQ@mail.gmail.com> <525E3E6B.1020604@secunet.com> <CA+cU71=ws7Uh6OuJhMdU521Uvm1zj=agb3HPNZudpX1R6v7mXA@mail.gmail.com> <525EAC5D.7080105@secunet.com> <CACsn0cmWpj1ax+S+wTVvVU09SC_z50X=yfhDDgaq1M0AQD2jOw@mail.gmail.com> <525EB695.9070607@secunet.com>
Date: Wed, 16 Oct 2013 11:29:25 -0500
Message-ID: <CAK3OfOhhxPPFTE9He+vf3BsJL4qiRgty6T9TgO2QXz7n=kbpnA@mail.gmail.com>
From: Nico Williams <nico@cryptonector.com>
To: Johannes Merkle <johannes.merkle@secunet.com>
Content-Type: text/plain; charset="UTF-8"
Cc: Patrick Pelletier <code@funwithsoftware.org>, "tls@ietf.org" <tls@ietf.org>
Subject: Re: [TLS] Using Brainpool curves in TLS
X-BeenThere: tls@ietf.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: "This is the mailing list for the Transport Layer Security working group of the IETF." <tls.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/tls>, <mailto:tls-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/tls>
List-Post: <mailto:tls@ietf.org>
List-Help: <mailto:tls-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/tls>, <mailto:tls-request@ietf.org?subject=subscribe>
X-List-Received-Date: Wed, 16 Oct 2013 16:29:31 -0000

On Wed, Oct 16, 2013 at 10:53 AM, Johannes Merkle
<johannes.merkle@secunet.com> wrote:
>> Curve25519 picks the smallest value of A that meets the parameters.
> Why the smallest, not the largest negative? Why using little /big endian (don't know which was used) instead of the
> other? Why choosing exactly these conditions (you phrase it "parameters").

Endianness has no impact on the mathematics involved.

Smallest because there is such a thing (as opposed to largest, which
is unbound).  It could have been smallest absolute value, allowing one
more degree of freedom.  Perhaps there's a class of attacks that works
with positive As and not with negative As (or vice-versa)?  But that
seems unlikely.

> Don't get me wrong. I admit that the construction of Curve25519 is extremely rigid, and even more rigid than that of the
> Brainpool curves. I only point to the fact that there is no perfect rigidity.

Agreed.  I like DJB's curve constructions because as much as possible
is explained verifiably.

>> is deterministic. Brainpool is close enough that I would say "quite
>> rigid" as opposed to "deterministic construction". Basically, the
>
> I think we can agree on that statement.

Agreed.

But the SafeCurves site doesn't focus only on construction rigidity,
and it doesn't discount Brainpool on account of rigidity in its
construction.  SafeCurves also covers other issues.  SafeCurves
declares Brainpool curves not safe according to the following
criteria:

 - feasibility of efficient constant-time implementation
   http://safecurves.cr.yp.to/ladder.html

 - twist security
   http://safecurves.cr.yp.to/twist.html

   IIUC this means that when using non-twist secure curves one has to
validate that peers' public keys are on the curve being used, which in
turn would require exchanging not just public keys but also Schnorr
signatures (and, of course, verifying those signatures before using
peers' public keys for any other purpose).

 - completeness
   http://safecurves.cr.yp.to/complete.html

   This is an argument that's purely about implementation complexity
and performance.  I'm not sure how concerned to be about this -- less
than about the previous two concerns above, no doubt.

 - indistinguishability of public key values from random
   http://safecurves.cr.yp.to/ind.html

   No EC curve has this.  But for some curves one can construct a
mapping between any point and some small set of non-points all of
which can then be mapped right back into the original.  And such a
mappings can be made constant-time in the case of the three given safe
curves.  But no such mappings are known for the other curves
(including Brainpool).

   This is primarily a problem for protocols aiming for privacy
protection and for some ZKPPs (e.g., EKE) (but not for, say, J-PAKE,
which, incidentally, uses Schnorr signatures to verify public key
validity).

Nico
--