Re: [TLS] draft-ietf-tls-curve25519-01 and the X25519 significant bit.

Adam Langley <agl@imperialviolet.org> Mon, 28 December 2015 15:39 UTC

Return-Path: <alangley@gmail.com>
X-Original-To: tls@ietfa.amsl.com
Delivered-To: tls@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 3B2F81A016C for <tls@ietfa.amsl.com>; Mon, 28 Dec 2015 07:39:08 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 1.422
X-Spam-Level: *
X-Spam-Status: No, score=1.422 tagged_above=-999 required=5 tests=[BAYES_50=0.8, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, FM_FORGED_GMAIL=0.622, FREEMAIL_FROM=0.001, SPF_PASS=-0.001] 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 24uh2W0hFcks for <tls@ietfa.amsl.com>; Mon, 28 Dec 2015 07:39:07 -0800 (PST)
Received: from mail-qg0-x235.google.com (mail-qg0-x235.google.com [IPv6:2607:f8b0:400d:c04::235]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id BC06A1A016A for <tls@ietf.org>; Mon, 28 Dec 2015 07:39:06 -0800 (PST)
Received: by mail-qg0-x235.google.com with SMTP id 6so70643187qgy.1 for <tls@ietf.org>; Mon, 28 Dec 2015 07:39:06 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:sender:in-reply-to:references:date:message-id:subject :from:to:cc:content-type; bh=DVN7VeKB0/5if1+Dmqi6K7CkB/CQECceXrvSy0rlyYY=; b=FF1i2rwVbOtk6ZQ76wckxCcbjKdK7DcDqvBxT8dW3JuM2rLju4TdNjrMMrGE+gWL68 XpinVgyMlnpXUB1CnEkXfIXmJnGkcXRoZ7hydaY41ebkbEBwGzj2zAgus7uq4RjqlxhC m0kkvytat7T76ljSDqnu/nEw4qhyxjfKyEv3W/aYUxBjpqfzVr27847nJhhER/XEbBiY QvwmjcGpw4fRq4JVz3tUPljvETZJivjrMDbekk0Nl454enKCt17SdHCYO2Aijz5c2aSb I+mO1DkkTfxz+8uTCL1CWFzvWd86eNQyeaL8Y5AHbJqYn/1u+3oyhq8gDQO8XJzgKPFR yUug==
MIME-Version: 1.0
X-Received: by 10.140.106.37 with SMTP id d34mr72923783qgf.77.1451317145923; Mon, 28 Dec 2015 07:39:05 -0800 (PST)
Sender: alangley@gmail.com
Received: by 10.140.93.12 with HTTP; Mon, 28 Dec 2015 07:39:05 -0800 (PST)
In-Reply-To: <CAFewVt6kn7tVvV51+gm1tuCnitLnLSNTJsOqxNYRLi7zDhag6Q@mail.gmail.com>
References: <CAMfhd9XDfwmoze+BdFVedhCGDQRNbL63ZT=KZc-7dEr0UMk4dA@mail.gmail.com> <CAFewVt7A_hBXBNzqaU6cQaU5Ysk86xo+fn69zDOn0oHYPiJazg@mail.gmail.com> <CAMfhd9WxSubu2dy9=RO94NSemzaRfr0TRoYGD7DS9L-9XdK=QA@mail.gmail.com> <CAFewVt6kn7tVvV51+gm1tuCnitLnLSNTJsOqxNYRLi7zDhag6Q@mail.gmail.com>
Date: Mon, 28 Dec 2015 07:39:05 -0800
X-Google-Sender-Auth: BKB9D6z0unClHHJxm_4K-r16AWI
Message-ID: <CAMfhd9XNDh8Cf42as7fdeA8sqpo-tkzr9udMgEWaqisc43aKjg@mail.gmail.com>
From: Adam Langley <agl@imperialviolet.org>
To: Brian Smith <brian@briansmith.org>
Content-Type: text/plain; charset=UTF-8
Archived-At: <http://mailarchive.ietf.org/arch/msg/tls/oBFegNyRpLmEZNOtw2dFIHiJLYw>
Cc: Simon Josefsson <simon@josefsson.org>, "tls@ietf.org" <tls@ietf.org>
Subject: Re: [TLS] draft-ietf-tls-curve25519-01 and the X25519 significant bit.
X-BeenThere: tls@ietf.org
X-Mailman-Version: 2.1.15
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: <https://mailarchive.ietf.org/arch/browse/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: Mon, 28 Dec 2015 15:39:08 -0000

On Tue, Dec 22, 2015 at 3:15 PM, Brian Smith <brian@briansmith.org> wrote:
> I agree with all of that in principle. In fact, I think that most of section
> 2.3 should be removed in deference to the CFRG document, and only
> TLS-specific concerns should be given.
>
> I still think there is value in requiring senders to send their public value
> in the "normalized" form and for allowing (if not requiring) receivers to
> reject, at least, public values >= q, for the reasons I gave in my previous
> email. Ideally that would happen in the CFRG document. But, what is the
> status of the CFRG document? I've heard that it's past the point where
> changes will be accepted.

The CFRG document is in AUTH48 right now so, indeed, it's probably too
late for that sort of change.

To give some background about why the CFRG document ended up the way it did:

The curve25519 paper only mentions the extra bit to say: "Note that
Curve25519 is not surjective: in particular, its final output bit is
always 0 and need not be transmitted." [1]. It didn't specify whether
it should be ignored or not and implementations started to differ on
that point. Also, in order to keep the code simple, it didn't check
for values >= 2^255-19. Both because that could be more code in the
primitive itself, and because it would mean that the function would
change from being total to partial.

Some years ago, there was a small effort to align the different
implementations around the same behaviour and ignoring the bit was
chosen. I think that decision probably arose from changing the fewest
things and also the thought that people might want to use the extra
bit as a sign bit in the future.

No implementations rejected values >= 2^255-19 from what I recall.

Since the CFRG has standardised Curve25519, in practice the existing
implementations will seed the implementation ecosystem. Changing
something really subtle like the extra bit behaviour, or rejecting
oversized values, without a clear need, doesn't seem to me to be
worthwhile (or, perhaps, even achievable for a spec).

So at this point I'd like to nail down the existing behaviour with
tests, try to make it uniform across most implementations, and try to
avoid other specs interpreting the byte strings.

[1] http://cr.yp.to/ecdh/curve25519-20060209.pdf


Cheers

AGL

-- 
Adam Langley agl@imperialviolet.org https://www.imperialviolet.org