Re: [Cfrg] Curve manipulation, revisited

Benjamin Black <b@b3k.us> Mon, 29 December 2014 17:14 UTC

Return-Path: <b@b3k.us>
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 6AE221A884C for <cfrg@ietfa.amsl.com>; Mon, 29 Dec 2014 09:14:39 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.977
X-Spam-Level:
X-Spam-Status: No, score=-1.977 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FM_FORGED_GMAIL=0.622, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7] 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 a0ZtkSp2aKwt for <cfrg@ietfa.amsl.com>; Mon, 29 Dec 2014 09:14:37 -0800 (PST)
Received: from mail-wi0-f177.google.com (mail-wi0-f177.google.com [209.85.212.177]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id D2C7B1A87AD for <cfrg@irtf.org>; Mon, 29 Dec 2014 09:14:36 -0800 (PST)
Received: by mail-wi0-f177.google.com with SMTP id l15so22673583wiw.4 for <cfrg@irtf.org>; Mon, 29 Dec 2014 09:14:35 -0800 (PST)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc:content-type; bh=xe3mTknj01r0u1rF4jwE0keNSfrwxnN3KeFcc3cGZE4=; b=e0oacdjcJKAd6mTRIYFvJAyid2TKRYh6/kKYOfCg2fxQczhTN9bmDU+bM4iSXqLyKp uGq/V9jItrDV0jsSxZcuQ264q0Ew11pNAM34GA14kGOrzCcpVX80+mWjl9cCuhR7onAl l1NrKLrhVoCXmIUNsfI+F1rnBDVNFzxLNov++sinI81fOLlu0oxDMVwaobaEj0g1XfWF Ty0T5RT+WJYKufkfEMfj949Nr79zb4bn1l88QLx5VzfP9B2mVtxGfGbXzO0nV80CmaEx tgkChtNJhG6YnWwGZT2ArE2cUhFdfx1u95vAOAE6LQW680qjZpqZXS5xgd2nmOR8N9Qg LNQw==
X-Gm-Message-State: ALoCoQkBJzo81vMxEMk+Z0o9v12TxGXp4NskyT/xz+K0c4YwqtDRS/BANjN02Mt5zcjkcQz2YIHM
X-Received: by 10.180.75.42 with SMTP id z10mr98234600wiv.70.1419873275531; Mon, 29 Dec 2014 09:14:35 -0800 (PST)
MIME-Version: 1.0
Received: by 10.216.190.139 with HTTP; Mon, 29 Dec 2014 09:14:15 -0800 (PST)
In-Reply-To: <CAMfhd9XEqMwFzJ4sK4aHGbke6REZb26uaEEv9gbM5v_goDzwUA@mail.gmail.com>
References: <CAMfhd9W684XMmXn3ueDmwrsQ_ZdiFG+VqYLxkvs7qDwiJdpk6w@mail.gmail.com> <1725646678.805875.1419539885135.JavaMail.yahoo@jws100115.mail.ne1.yahoo.com> <CAMfhd9Ua5fFZk46Xx1AN2VgyJ=Yng6fnO8aN-_ZfzXQn0Xbxhg@mail.gmail.com> <CA+Vbu7zqFcu8d1053mZ_eEm0q=np6T3snSQ4rfY0k1-4hBVDsA@mail.gmail.com> <CAMfhd9XEqMwFzJ4sK4aHGbke6REZb26uaEEv9gbM5v_goDzwUA@mail.gmail.com>
From: Benjamin Black <b@b3k.us>
Date: Mon, 29 Dec 2014 09:14:15 -0800
Message-ID: <CA+Vbu7zO3OatbC+cXiV58hvJCuqiTYvnsSuyopDXum4qBX54fw@mail.gmail.com>
To: Adam Langley <agl@imperialviolet.org>
Content-Type: multipart/alternative; boundary="f46d0438957336e932050b5e02ab"
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/y6e34a5XG7vACSU0OTlinEDITKA
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] Curve manipulation, revisited
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: Mon, 29 Dec 2014 17:14:39 -0000

On Mon, Dec 29, 2014 at 5:31 AM, Adam Langley <agl@imperialviolet.org>
wrote:

> On Mon, Dec 29, 2014 at 7:57 AM, Benjamin Black <b@b3k.us> wrote:
> > It seems performance is the real priority here and you will happily
> discard
> > things you insist are necessary for security when they conflict with
> > performance. At the 128-bit security level the ladder can be faster. At
> the
> > 200-bit+ security levels the ladder is slower. Should we blame the
> > implementor who elects not to use a single-coordinate ladder? Should we
> > wonder why you would choose not to eliminate these security failures?
>
> Montgomery ladders allow for very simple, robust implementations of
> scalar-mult. Sometimes an implementation might want to trade off cache
> pressure for speed, but certainly not all will. If we accept that
> supporting Montgomery ladders is a requirement, then we can easily
> meet that by sending the Montgomery-x value in ECDH protocols because
> windowed methods can easily output this. Thus these are not in
> conflict.
>
>
After Yarov and Benger I don't know how robust anyone should assume ladders
are, though that might be beside the point. Had Dan been insisting that
ladders be _allowed_ then I would agree with you, as I have said the same
(in the line just before the part you quoted, even). What Dan said is that
single-coordinate ladders are _required_. They are not (or, to quote Dan
again, "False."). X-only on the wire has clear advantages and I support
that recommendation, but that does not force use of ladders.


> > This section of your paper raises another interesting point. It seems a
> > slight performance drop in exchange for consuming less SRAM can be a
> > desirable property to you. In Adam's Faster Curve25519 post
> > (https://www.imperialviolet.org/2013/05/10/fastercurve25519.html), he
> > achieves significant performance improvements at a cost of 24KB of cache
> for
> > tables.
>
> Keep in mind that this was mostly the result of me needing to explain
> windowed methods to someone. The practical benefit to ECDH systems is
> minimal since the base-point multiplication can be amortised. (Fast
> signatures, however, obviously can benefit, but there's no danger of
> an invalid-curve attack when multiplying by the base point.)
>
>
My point was that space/time trade-offs like that seem to be acceptable or
unacceptable to Dan depending on what is being argued.


> > I'm not sure what point you are trying to make here. The people who
> haven't
> > submitted curves should remain silent? That is antithetical to the IETF
> > process.
>
> I think Tanja is commenting on the fact that the IETF process is alien
> to most cryptographers. Cryptographers often run competitions (e.g.
> the AES and SHA-3 competitions) where teams submit candidates and a
> winner is decided. That's very different to the more "collaborative"
> method common at the IETF.
>
>
I'm experiencing a similar cultural impedance problem.


b