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

Brian Smith <brian@briansmith.org> Tue, 29 December 2015 19:02 UTC

Return-Path: <brian@briansmith.org>
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 839C71A0856 for <tls@ietfa.amsl.com>; Tue, 29 Dec 2015 11:02:29 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.278
X-Spam-Level:
X-Spam-Status: No, score=-1.278 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, FM_FORGED_GMAIL=0.622, HTML_MESSAGE=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 to5xw0XsXyzt for <tls@ietfa.amsl.com>; Tue, 29 Dec 2015 11:02:26 -0800 (PST)
Received: from mail-oi0-x232.google.com (mail-oi0-x232.google.com [IPv6:2607:f8b0:4003:c06::232]) (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 7AF2A1A03A2 for <tls@ietf.org>; Tue, 29 Dec 2015 11:02:26 -0800 (PST)
Received: by mail-oi0-x232.google.com with SMTP id o124so191983721oia.1 for <tls@ietf.org>; Tue, 29 Dec 2015 11:02:26 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=briansmith-org.20150623.gappssmtp.com; s=20150623; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=v+I0zBdV0GtkkJhIp0Gg1nc2tAsAWTxadl9+gHia154=; b=LNqLmXTwRFsvQm8d8Cvv9x/zi8Wks4+atUb/TOWZRpZ/9J3+ul1qUR3vkDWnRv/vgr LPPQDc8+RTD1Docz8VPFZK3YhaEH5qySBfsLbtDQwgPv9GWx6RpKDdSKj3Cv2yD8sZwm UPVqPoK+q2tAqdtJMCMaDABu6bgXx4khVoVNHjdXrhIrJkKEvWz9ZwQqXbcfIxVWQOgP Cs6CL3am7ylIqGinTSCkPMi2q53wT5ziA4yFpMDMa7dq3abktSIiQyMd5/LFOFuB0oYr eqI/p+nv6y0zzGteJ2ZFflIm/AUgICrOmyM5uwvYHXqGFh99GhdWhz/YPMP+/5xZW4QW 9kow==
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:date :message-id:subject:from:to:cc:content-type; bh=v+I0zBdV0GtkkJhIp0Gg1nc2tAsAWTxadl9+gHia154=; b=Uw4JGuhYaxb80OkHSF0OUxfCv0SoKPzGM4p9YnhwKoFFArV7oAlONcBvi0kEGRnnz2 CLmTeJYdoxD46LpcTRgr0R6JlFLJZQAaASLrHsEw7f5YBYPHgK/o+v8AOZJhwsgAXJVa DkkCgAaSijXRoQfpFhD01X+HxRJybv8DKeV8lutbOmpcOaTgr5WxNpKh76wlgQSo8iOQ 8gESjLbui7BD4z99O8EJAIW4nim8Ob7oDWR/cJGkmjFQh1+kDvfWolM4bQyMxa5jsqcr lSTFxyRycWMzxCPgf+aBV66C0WVwX0OoJrOiJybeKshT+yFP5PRTMZQFEwXwI/9DhY17 mC0w==
X-Gm-Message-State: ALoCoQnN6JGPjN5sqzUY1USxAJQ4M/UL7nbSegi6A3zVivpqQxzDwaMhQEzPofHlJiuPM5ZW/SCSI6t22L7D/aVNwSFAQiYIOw==
MIME-Version: 1.0
X-Received: by 10.202.189.7 with SMTP id n7mr36962603oif.55.1451415745711; Tue, 29 Dec 2015 11:02:25 -0800 (PST)
Received: by 10.76.62.8 with HTTP; Tue, 29 Dec 2015 11:02:25 -0800 (PST)
In-Reply-To: <CAMfhd9XNDh8Cf42as7fdeA8sqpo-tkzr9udMgEWaqisc43aKjg@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> <CAMfhd9XNDh8Cf42as7fdeA8sqpo-tkzr9udMgEWaqisc43aKjg@mail.gmail.com>
Date: Tue, 29 Dec 2015 09:02:25 -1000
Message-ID: <CAFewVt5u1pBxt_i2nhWv1XhrvC7bD0rC+TdUenJ9cXhStrkY6g@mail.gmail.com>
From: Brian Smith <brian@briansmith.org>
To: Adam Langley <agl@imperialviolet.org>
Content-Type: multipart/alternative; boundary=001a113d7032f1e76f05280e0f4e
Archived-At: <http://mailarchive.ietf.org/arch/msg/tls/wy7TBPdQU5z4bDV5GgPv1yPhmUc>
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: Tue, 29 Dec 2015 19:02:29 -0000

Adam Langley <agl@imperialviolet.org> wrote:

> On Tue, Dec 22, 2015 at 3:15 PM, Brian Smith <brian@briansmith.org> wrote:
> > 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.


Does that matter, though? The CFRG document doesn't allow the sender to set
the high bit to 1, right? In particular, it says "All calculations are
performed in GF(p), i.e., they are performed modulo p." and "For X25519,
the unused, most-significant bit MUST be zero."

If the receiver can detect that the sender is non-conforming, then it
should be able to stop talking to it on that basis alone.


> 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.
>

I think there is value in it being a total function. But, I think there is
value in checking the conformance of the sender in the receiver. Note that
such a check can be layered on top of the X25519 primitive.

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

I do have a private implementation that does this check, not just for
X25519 but for basically all ECC calculations. I don't want to have to make
Curve25519 special in allowing non-canonical/non-reduced values when all
the rest of my code doesn't allow such cases, especially when the CFRG spec
already forbids implementations from sending the non-canonical/non-reduced
values.

>
> 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).
>

As long as senders conform to the spec, they will not notice what the
receiver does regarding this.

Cheers,
Brian
-- 
https://briansmith.org/