Re: ssh-ed25519 implementations

Ron Frederick <ronf@timeheart.net> Sat, 13 May 2017 05:32 UTC

Return-Path: <bounces-ietf-ssh-owner-secsh-tyoxbijeg7-archive=lists.ietf.org@NetBSD.org>
X-Original-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com
Delivered-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 80627129B77 for <ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com>; Fri, 12 May 2017 22:32:44 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -4.091
X-Spam-Level:
X-Spam-Status: No, score=-4.091 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, HEADER_FROM_DIFFERENT_DOMAINS=0.001, RCVD_IN_DNSWL_MED=-2.3, RP_MATCHES_RCVD=-0.001, SPF_PASS=-0.001, T_DKIM_INVALID=0.01] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=fail (1024-bit key) reason="fail (body has been altered)" header.d=timeheart.net
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 wscAcHUFVHVI for <ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com>; Fri, 12 May 2017 22:32:42 -0700 (PDT)
Received: from mail.netbsd.org (mail.NetBSD.org [IPv6:2001:470:a085:999::25]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 131BF129B34 for <secsh-tyoxbijeg7-archive@lists.ietf.org>; Fri, 12 May 2017 22:30:24 -0700 (PDT)
Received: by mail.netbsd.org (Postfix, from userid 605) id E694C84DF5; Sat, 13 May 2017 05:30:22 +0000 (UTC)
Delivered-To: ietf-ssh@netbsd.org
Received: by mail.netbsd.org (Postfix, from userid 1347) id 8C17884DCF; Sat, 13 May 2017 05:30:22 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1]) by mail.netbsd.org (Postfix) with ESMTP id 403DB84DCF for <ietf-ssh@netbsd.org>; Sat, 13 May 2017 05:24:15 +0000 (UTC)
X-Virus-Scanned: amavisd-new at netbsd.org
Authentication-Results: mail.netbsd.org (amavisd-new); dkim=pass (1024-bit key) header.d=timeheart.net
Received: from mail.netbsd.org ([127.0.0.1]) by localhost (mail.netbsd.org [127.0.0.1]) (amavisd-new, port 10025) with ESMTP id pwXFHDm7Pxra for <ietf-ssh@netbsd.org>; Sat, 13 May 2017 05:24:14 +0000 (UTC)
Received: from mail-pf0-x230.google.com (mail-pf0-x230.google.com [IPv6:2607:f8b0:400e:c00::230]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by mail.netbsd.org (Postfix) with ESMTPS id 3062584CD8 for <ietf-ssh@netbsd.org>; Sat, 13 May 2017 05:24:13 +0000 (UTC)
Received: by mail-pf0-x230.google.com with SMTP id m17so39103145pfg.3 for <ietf-ssh@netbsd.org>; Fri, 12 May 2017 22:24:13 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=timeheart.net; s=mail; h=mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=cKN9oSPunz8b3EgvhWMDmgSWwDGv9uUxTewKPMi0DGg=; b=Ht5C//D6babAF7UPo9OkVU8JxmO8pKofZ8oeLhkwisw8DwP/ycKg1+9HrmJ/0+eMVp p4lO3y17fcM/UkNn33QxqqAQfcCOKr3jF/muZU/9ToTy74BIXiA+I1lf+pqGIfde5Zuj IwbpLb+H1XZsf8g0o8UzuvGnpQ1sZFfIOwKN0=
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=cKN9oSPunz8b3EgvhWMDmgSWwDGv9uUxTewKPMi0DGg=; b=ODLnqGnUStDmJ1PUpZ+jijLPfiTlb6OYMsMSvFwCUoAvVERQzNNG4Ia1PEm1pQ+C2v No9Sg82ukMR4CeWegeXaEB74Y3OUIB06uxQMxmj+D9IG4pOGlR4DX6fxc9wX4WgAsd3j 8sJE15pmMdlpfLkGveiVI1Aql+G+Ip2MZ+/iZ1mIs1Yx92kN+pASt2o5Fl661uwFrV6r 7pBLYMOJTmwQz5c2gffDakAlLOmNeCRuyNynVFanl3qtKv0oUAmIm5La8iKeWN6aaSrn QKFGAlMu5IOOAUE9Dkd02eQDtD8a9ZUeqGcQo3cJ9028BiUqFRRL/eZ0Mj3pdmmrtp21 h0PQ==
X-Gm-Message-State: AODbwcCgJOZiS5AuK4z4czd/jPyoQdZbIjrpsy6htro9fkfs4LJfH/f3 GtYvQDiVec8kZQ==
X-Received: by 10.84.142.129 with SMTP id 1mr9474087plx.3.1494653052856; Fri, 12 May 2017 22:24:12 -0700 (PDT)
Received: from ?IPv6:2601:647:4282:2200:cfa:5497:d692:7eeb? ([2601:647:4282:2200:cfa:5497:d692:7eeb]) by smtp.gmail.com with ESMTPSA id y63sm8909487pfa.107.2017.05.12.22.24.11 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 12 May 2017 22:24:11 -0700 (PDT)
Content-Type: text/plain; charset=utf-8
Mime-Version: 1.0 (Mac OS X Mail 10.3 \(3273\))
Subject: Re: ssh-ed25519 implementations
From: Ron Frederick <ronf@timeheart.net>
In-Reply-To: <1139.1494566512@eng-mail01.juniper.net>
Date: Fri, 12 May 2017 22:24:09 -0700
Cc: Eric Rescorla <ekr@rtfm.com>, Brian Smith <brian@briansmith.org>, denis bider <denisbider.ietf@gmail.com>, Simon Tatham <anakin@pobox.com>, "ietf-ssh@NetBSD.org" <ietf-ssh@NetBSD.org>, "curdle@ietf.org" <curdle@ietf.org>
Content-Transfer-Encoding: quoted-printable
Message-Id: <336063E0-135F-4A75-94E4-71540669E21A@timeheart.net>
References: <76FD0F39-1F3D-4476-A3D8-D4C942C2EFD1@juniper.net> <CABcZeBNYUV=-azoZzZjnNtCEu3K0A-THHN2mt02V65oihbbrXw@mail.gmail.com> <36528.1494509552@eng-mail01.juniper.net> <6047C877-67DE-404F-8FBD-5B2C19D16EA6@timeheart.net> <1139.1494566512@eng-mail01.juniper.net>
To: "Mark D. Baushke" <mdb@juniper.net>
X-Mailer: Apple Mail (2.3273)
Sender: ietf-ssh-owner@NetBSD.org
List-Id: ietf-ssh.NetBSD.org
Precedence: list
List-Unsubscribe: <mailto:majordomo@NetBSD.org?subject=Unsubscribe%20ietf-ssh&body=unsubscribe%20ietf-ssh>

Hi Mark,

On May 11, 2017, at 10:21 PM, Mark D. Baushke <mdb@juniper.net> wrote:
> Ron Frederick <ronf@timeheart.net> writes:
>> 2.1 Shared Secret Encoding
>> 
>>   The following step differs from [RFC5656], which uses a different
>>   conversion.  This is not intended to modify that text generally, but
>>   only to be applicable to the scope of the mechanism described in this
>>   document.
>> 
>>   The shared secret, K, is defined in [RFC4253] as a multiple precision
>>   integer (mpint).  Curve25519/448 outputs a binary string X, which is
>> 
>> [Ron] RFC 4253 actually says that K is “encoded as an mpint”. I’d
>> suggest saying “The shared secret, K, is defined in [RFC4253] as an
>> integer."
> 
> Section 8 of RFC 5253 actually says "It computes K = e^y mod p" which
> means that K is a multiple precision integer.

Section 8 is specific to the original Diffie Hellman key exchange. The computation is different for ECDH (described in section 4 of RFC 5656), but that states "The SSH framework requires that the shared key be an integer.” and then goes on to describe how to do the conversion from an EC field element. For X25519, I think it makes sense to state something similar.


> As an aside, it really should end up be larger than a simple integer.
> Not stated, but the math works best if it is on the order of at least
> half the number of bits of q such that g^(xy) is greater than p which
> lets the mod operation do something useful.

I agree that in all of these cases the integer K is likely to be very large (much larger than something which would fit in a traditional integer value in a language like C). However, “mpint” here really is just an encoding. In Python, for example, K can be represented as a plain Python “int” type, since that natively supports arbitrarily large integers (limited only by available memory, I think). The “mpint” conversion here actually changes the type from an “int” to a byte array, which is needed to be able to feed the bytes to the hash function. Even in other languages where large integers are represented as some form of an array already, it’s important that the exact representation of this integer as a byte array is specified, so that all parties compute the hash in a consistent manner.


>>   o  Trim all leading zero-bytes of X.  If X is all zero-bytes, then
>>      the key exchange MUST fail.
>> 
>> [Ron] Are you sure this is necessary? 
> 
> Yes.
> 
>> I don’t see any mention of this restriction in RFC 4253. If the
>> integer value of K is 0, it can still be encoded as a valid mpInt.
> 
> It is not in RFC4253, it is in RFC4251 where it says:
> 
>   mpint
> 
>      Represents multiple precision integers in two's complement format,
>      stored as a string, 8 bits per byte, MSB first.  Negative numbers
>      have the value 1 as the most significant bit of the first byte of
>      the data partition.  If the most significant bit would be set for
>      a positive number, the number MUST be preceded by a zero byte.
>      Unnecessary leading bytes with the value 0 or 255 MUST NOT be
>      included.  The value zero MUST be stored as a string with zero
>      bytes of data.

That does not say that 0 is an invalid value. It simply says that when converting to an “mpint" byte array, 0 is represented by a zero-byte array.


> The check for X is all zero-bytes needs to be done per RFC7748:
> 
>   Both now share K = X25519(a, X25519(b, 9)) = X25519(b, X25519(a, 9))
>   as a shared secret.  Both MAY check, without leaking extra
>   information about the value of K, whether K is the all-zero value and
>   abort if so (see below).
>   ...elided...
>   The check for the all-zero value results from the fact that the
>   X25519 function produces that value if it operates on an input
>   corresponding to a point with small order, where the order divides
>   the cofactor of the curve (see Section 7).  The check may be
>   performed by ORing all the bytes together and checking whether the
>   result is zero, as this eliminates standard side-channels in software
>   implementations.

Ok.

I still have some doubts about whether this belongs in this specification, though, as it seems like the abort operation should be performed by the code implementing the X25519 multiplication. Before returning the byte array X, I would expect that code to check for an all-zeroes result and return an error, so the code handling this value in SSH would never even see the case where the converted value K ends up being 0.

As one data point, I checked the libsodium implementation, and it was changed back in November of 2015 (release 1.0.7) to perform this check and return an error if the result of the scalar multiplication ends up being all-zeroes. I don’t see a specific test vector which I can use to actually confirm that this works, though — does anyone happen to have one?


>> [Ron] Actually, after doing all of this, the mpint conversion also
>> requires the that resulting byte string be preceded by a 4-byte
>> big-endian length value. So, even if the X value has no bytes removed
>> or prepended, it will be 4 bytes longer than it was originally.
>> There’s no mention of this length here.
> 
> True, because the prepended length is not a part of the hash to the best
> of my recollection. Am I mistaken?

Yes - the fixed-size 4-byte length is always included as part of the bytes fed to the hash.


>> [Ron] With the changes I have proposed above, I’m not sure this last
>> paragraph is needed. Alternately, I’d think about working some of this
>> text into the two paragraphs above that discuss the conversion from X
>> to K and then from K to an mpint. 
> 
> I am also not sure, but I have left it in for now. Please see my 'diff'
> below for the changes to see if it looks better or worse to you.

This definitely looks better. It still needs additional text to cover the insertion of the fixed length bytes in front of the encoded “mpint” value, though.
-- 
Ron Frederick
ronf@timeheart.net