Re: [Cfrg] Requirements for curve candidate evaluation update

Benjamin Black <b@b3k.us> Wed, 13 August 2014 23:23 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 5A1C71A046D for <cfrg@ietfa.amsl.com>; Wed, 13 Aug 2014 16:23:37 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.577
X-Spam-Level:
X-Spam-Status: No, score=-0.577 tagged_above=-999 required=5 tests=[BAYES_05=-0.5, 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 QDLR6E7i2mAP for <cfrg@ietfa.amsl.com>; Wed, 13 Aug 2014 16:23:25 -0700 (PDT)
Received: from mail-wi0-f170.google.com (mail-wi0-f170.google.com [209.85.212.170]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 03A281A0432 for <cfrg@ietf.org>; Wed, 13 Aug 2014 16:22:37 -0700 (PDT)
Received: by mail-wi0-f170.google.com with SMTP id f8so9061515wiw.1 for <cfrg@ietf.org>; Wed, 13 Aug 2014 16:22:36 -0700 (PDT)
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=npwm4M+VoN7LJjbjQuQxwDSD6iZ1xr88JGCMRM+/+bY=; b=dhl331dskyiljdusNedRF7Akh+23KDFoCX9BwYPypdakwnodOkFfzUN4R1Yl20j4Ry fb6WTUjCcH93eL5U9kx5Au3NGysATwqYIiUZJgTekCo41rRqQSH+x8ulYAoDDf9F9++S jD5JDxc98mEaK1ah0qKdXqNzpnr55ge9Uz2lqvhrP7IJgvGfcyx3uUX0czi47R/Xr4Zj 5SQS9qn3tBFU08AJ1Lz5/aGtlDYa16vQpUMYgW4uZnbctdq9QimEYGNLxu4beaVBieBg +V8GRrB77gg7cVINGX597HZvOXyDROrAN9TgeT3EU9dVSIj9X7e++3xYBOw3jgB6Jd4a WG6A==
X-Gm-Message-State: ALoCoQlRb8Z9/82/iAFeG7SeEisYSStstLkYTCJH2FknmvcUDBbwNk/fixA9P6UfiRoyDNMSj+6w
X-Received: by 10.194.179.73 with SMTP id de9mr7177409wjc.87.1407972156610; Wed, 13 Aug 2014 16:22:36 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.216.44.138 with HTTP; Wed, 13 Aug 2014 16:22:16 -0700 (PDT)
In-Reply-To: <2A0EFB9C05D0164E98F19BB0AF3708C7185A0C8CEB@USMBX1.msg.corp.akamai.com>
References: <CA+Vbu7wuAcmtAKJYEgAaSBTf6sj8pRfYpJhz2qV_ER=33mrk8Q@mail.gmail.com> <2A0EFB9C05D0164E98F19BB0AF3708C7185A0C8CEB@USMBX1.msg.corp.akamai.com>
From: Benjamin Black <b@b3k.us>
Date: Wed, 13 Aug 2014 16:22:16 -0700
Message-ID: <CA+Vbu7zfbx-OqU=ggXgutDb+GNwvS3QpkTwzU1c+2Lcv=3Gawg@mail.gmail.com>
To: "Salz, Rich" <rsalz@akamai.com>
Content-Type: multipart/alternative; boundary=089e013c63a63fb5d305008b10e7
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/r6LX4dYeDwJZfJ0PNcvqrax_IH0
Cc: "cfrg@ietf.org" <cfrg@ietf.org>
Subject: Re: [Cfrg] Requirements for curve candidate evaluation update
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, 13 Aug 2014 23:23:37 -0000

On Tue, Aug 12, 2014 at 3:05 PM, Salz, Rich <rsalz@akamai.com> wrote:
>
> I have asked before, perhaps you missed it.
>
>
>
> I take exception to your claims that “single curve model” and “no change
to wire formats” are facts on the ground.  Can you justify that?
>
>
>
> --
>
> Principal Security Engineer
>
> Akamai Technologies, Cambridge MA
>
> IM: rsalz@jabber.me Twitter: RichSalz

Rich,

The facts on the ground, as described in my post, are that people
implementing these systems may not be professional cryptographers, and even
if they are, they make mistakes, so requiring implementation of two
different models or transforms between models is a significant burden. If
an implementer wishes to use a different model internally, they can do so.
The difference is not requiring everyone do so.

As illustrated in the NaCl and TweetNaCl libraries having multiple required
models makes implementation more challenging, even for some of the best
cryptographers in the world. From
http://tweetnacl.cr.yp.to/tweetnacl-20131229.pdf :

"However, NaCl’s performance comes at a price. A single NaCl function
usually consists of several different implementations, often including
multiple assembly-language implementations optimized for different CPUs.
NaCl’s compilation system is correspondingly complicated. Auditing the NaCl
source is a time-consuming job. For example, four implementations of the
ed25519 signature system have been publicly available and waiting for
integration into NaCl since 2011, but in total they consist of 5521 lines
of C code and 16184 lines of qhasm code. Partial audits have revealed a bug
in this software (r1 += 0 + carry should be r2 += 0 + carry in
amd64-64-24k) that would not be caught by random tests; this illustrates
the importance of audits."

"In principle we could use the same scalar-multiplication code for both
Curve25519 and Ed25519. This would require conversion of points on M to
points on E and back. If we used the x-coordinate-based differential
addition ladder of Curve25519 also for Ed25519, we would additionally need
code to recover the y-coordinate as described by Okeya and Sakurai in [20].
Conversion code is not substantially shorter than the code required for the
Curve25519 Montgomery ladder, so we decided to not use the same code for
scalar multiplication in Curve25519 and Ed25519."

That requiring multiple models makes implementation more difficult and
implies more code is both intuitively obvious and supported by available
evidence. Again, implementers are allowed, even encouraged, to write
whatever optimizations they like. Requiring them to implement specific
optimizations for small performance gains at a cost of more, and more
difficult, code would be unusual in any IETF proposal, but is especially
out of place when the proposal is for core cryptography primitives.

You, like many of us, have had up close and personal experience with bugs
in crypto code. You know that even the best make mistakes. Requiring a
single model for everything significantly reduces opportunities for
mistakes and the small performance gain of multiple models does not justify
requiring the additional exposure.


b