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

Brian Smith <brian@briansmith.org> Tue, 22 December 2015 21:36 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 403521A907D for <tls@ietfa.amsl.com>; Tue, 22 Dec 2015 13:36:36 -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 lamkTbHvNtRD for <tls@ietfa.amsl.com>; Tue, 22 Dec 2015 13:36:34 -0800 (PST)
Received: from mail-ob0-x231.google.com (mail-ob0-x231.google.com [IPv6:2607:f8b0:4003:c01::231]) (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 A92581A907C for <tls@ietf.org>; Tue, 22 Dec 2015 13:36:34 -0800 (PST)
Received: by mail-ob0-x231.google.com with SMTP id ba1so61586945obb.3 for <tls@ietf.org>; Tue, 22 Dec 2015 13:36:34 -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=gdTydPPAKlTEAn0ybt/hJ6/Jt3ENwYSqFM66rSVQZOY=; b=hpnZqdKL0h8kHuGE1GHhy7lu876jnWIzxDNJ4mGwzBnvTuwJREjtZ4/ecAtFKlinfv ZPdbQqjiXMDW6s7pqiiTGwcRuNDgDG0O8tba19Joxv9b2lqeOlBXQHhr/QCxaWj8dus8 xcrmjq2xtStEQDSJ84d1pEPoeCNKS1F0kUDPWr6c1tmtgLAmkqhk35V2zc/Dzvu4+CvC xGLi2Bcfvs0bQfBCxJ28V9jVrtS+upjkEAmVKd3FoNzE/XsX3T2MPkEN5S1diAZ8YaZA eMqz1DnC8tmq6Dozfg9c0VUpUX76WeBzlUZkwkeDRY5RK82rtg5joBSZhtd33SbM6lLE xoXw==
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=gdTydPPAKlTEAn0ybt/hJ6/Jt3ENwYSqFM66rSVQZOY=; b=j1GtSQPX7qRbKXTFYkbdmkUOhOh+H/t7EhQA/RHqKD2Bm/W/G2XzdbK/eRUOQlH3mR T6rGHvrK8gHFE8syP98LNSNLY0jM7rfH1h/jfNra26cV3GNyFmfoF8LBVVA0GckvsC/I pEXVka66Wm8QLChr+sNpTaUwT3dj4TfXx9/lHrGipvHAafs0ic4Mn+QBzS/wtChagsu6 z5oLFM+aKhPdyf+OFaO0ziNG6j0eKo12WjD+DMYezTAUHoJf02fh6TTOCEWSFXwlpBNp Ukap1P3BTDVpuytVuTkVrbhicnMKjabhHqS00uwLB3H2S7McjE8FXYqNXR0RYeEnAGeE JdtQ==
X-Gm-Message-State: ALoCoQlH8iuW1QKFe+xZkgK2H0GJVKW4QWhi1l7ImIju2UkVtlO1JevrmL/5vlMoPjsLVgE7wo9aC/F3KWNwjfCyiXmfTu9taA==
MIME-Version: 1.0
X-Received: by 10.60.98.33 with SMTP id ef1mr12699922oeb.62.1450820192994; Tue, 22 Dec 2015 13:36:32 -0800 (PST)
Received: by 10.76.62.8 with HTTP; Tue, 22 Dec 2015 13:36:32 -0800 (PST)
In-Reply-To: <CAMfhd9XDfwmoze+BdFVedhCGDQRNbL63ZT=KZc-7dEr0UMk4dA@mail.gmail.com>
References: <CAMfhd9XDfwmoze+BdFVedhCGDQRNbL63ZT=KZc-7dEr0UMk4dA@mail.gmail.com>
Date: Tue, 22 Dec 2015 11:36:32 -1000
Message-ID: <CAFewVt7A_hBXBNzqaU6cQaU5Ysk86xo+fn69zDOn0oHYPiJazg@mail.gmail.com>
From: Brian Smith <brian@briansmith.org>
To: Adam Langley <agl@imperialviolet.org>
Content-Type: multipart/alternative; boundary=089e0115edca3c9caf0527836642
Archived-At: <http://mailarchive.ietf.org/arch/msg/tls/OdYtUpymru5oUVDdcE5xTXZZvtI>
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, 22 Dec 2015 21:36:36 -0000

Adam Langley <agl@imperialviolet.org> wrote:

> Currently
> https://tools.ietf.org/html/draft-ietf-tls-curve25519-01#section-2.3
> says that implementations SHOULD reject inputs with the high-bit set.
> I think that should be dropped. The X25519 function is specified in
> terms of bytes in draft-irtf-cfrg-curves and I think the TLS spec
> should just use that draft.


First, maybe I'm overlooking something obvious, but I'm not seeing it: Why
are we concerned only with whether the high bit has been set, instead of
whether the public value has been reduced mod q (q == 2^255-19)? Aren't
there ~19 interesting values that don't have the high bit set but which are
also relevant to this issue?

The draft notes that if the sender calculated the result correctly, then
the result will never have the high bit set. So, then, we should have a
requirement on the sender that the sender MUST NOT send a representation of
its public value that has the high bit set? And, more generally, the sender
MUST NOT send a representation of its public value that isn't reduced mod
q. Would this be problematic to add this requirement?

If we added the above requirement on senders, then it would matter less
whether receivers reject values that aren't reduced mod q, as a conforming
implementation would never send them, right?

It seems like a good idea to reject non-reduced public values because:

1. By the argument in section 2.3, a conforming sender would never send
them, so if the sender did send one, it means there's a problem with the
sender of unknown severity, or an unknown attack on the wire. Either way,
it's safest to bail out early.

2. Rejecting non-reduced values allows us to compare keys (after
validation) by bytewise comparison and/or comparison of secure hashes of
the bytes. AFAICT, this seems to matter less for x25519 and ECDH in general
than it matters for signatures, but I bet that is just because I'm not
creative enough to discover why it might matter for ECDH. I did give an
example of why it can matter for signature public keys in [1]. It seems
better to me to be cautious on the topic.

[1] https://code.google.com/p/chromium/issues/detail?id=522228#c9

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