Re: ssh-ed25519 implementations

[Ron Frederick <[e-mail]>]

Hi Mark,

On May 11, 2017, at 6:32 AM, Mark D. Baushke <[e-mail]> wrote:
> Hi Eric & Ron & Brian & Simon,
> 
> Given input from folks so far, I think it would be better if both
> Curve25519 and Curve448 continued to use the "mpint" format for K when
> generating a hash even though this is not what RFC7748 suggests.
> 
> Would it make sense to include the following text to the end of section
> 2.1 of https://tools.ietf.org/html/draft-ietf-curdle-ssh-curves-04 ?
> 
>    When performing the X25519 or X448 operations, the integer values
>    there will be encoded into byte strings by doing a fix-length
>    unsigned litle-endian conversion, per [RFC7748]. It is only later
>    when these byte strings are then passed to the ECDH code in SSH that
>    the bytes are re-interpreted as a fixed-length unsigned big-endian
>    integer value K, and then later that K value is encoded as a
>    variable-length signed "mpint" before being fed to the hash
>    algorithm used for key generation.
> 
> to help clarify the differences between RFC7748 and what is happening in
> SSH?
> 
> Much of this text is borrowed from what Ron Frederick has written to me,
> any remaining confusion is my fault.
> 
> I think that the above text should help clear up the confusion that Eric
> noted in this section of code.
> 
> If there are no problems with this text, I will release the -05 draft
> with it.


I just took a look at the updated draft. Here’s a copy of the text in section 2.1 and some inline suggestions:

2.1 <https://tools.ietf.org/html/draft-ietf-curdle-ssh-curves-05#section-2.1>.  Shared Secret Encoding

   The following step differs from [RFC5656 <https://tools.ietf.org/html/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 <https://tools.ietf.org/html/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."

   the 32 or 56 byte point obtained by scalar multiplication of the
   other side's public key and the local private key scalar.  The 32 or
   56 bytes of X are converted into K by interpreting the bytes as an
   unsigned fixed-length integer encoded in network byte order.  This
   conversion follows the normal "mpint" process as described in section <https://tools.ietf.org/html/rfc4251#section-5>
   5 of [RFC4251] <https://tools.ietf.org/html/rfc4251#section-5>.

[Ron] There are actually two conversions here, from the byte string X to the integer K, and then from K back to a byte string to be fed to the hash used for key generation. This text makes it sound like the conversion from X to K should follow the “mpint” conversion, but that’s not the case. The sentence about how to convert X into the integer K looks good, but I would drop the last sentence here and begin a new paragraph which discusses the second conversion from the integer K back to a byte string for insertion into the hash, such as:

The integer K is then fed along with other data to the key exchange method’s hash function to generate encryption keys. During this process, [RFC4253] specifies that K should be encoded as an “mpint” as described in section 5 of [RFC4251]. This conversion may result in a value which varies from the fixed-length byte string X as follows:

This new paragraph can replace the next paragraph below.

   To clarify a corner-case in this conversion, when X is encoded as an
   mpint K, in order to calculate the exchange hash, it may vary as
   follows:

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

   o  If the high bit of X is set, the mpint format requires a zero byte
      to be prepended.

   o  The length of the encoded K may not be the same as the original
      length of X due to trimming or prepending zero-bytes as needed for
      "mpint" format.

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

   Or, as pseudo code:

                 k := x;
                 while (k.length() > 0 && k[0] == 0) k = k[1:];
                 assert(k.length() > 0);
                 if 0 != (k[0] & 0x80) k = '\0' .. k;

                                 Figure 1

   When performing the X25519 or X448 operations, the integer values
   there will be encoded into byte strings by doing a fix-length
   unsigned litle-endian conversion, per [RFC7748 <https://tools.ietf.org/html/rfc7748>].  It is only later
   when these byte strings are then passed to the ECDH code in SSH that
   the bytes are re-interpreted as a fixed-length unsigned big-endian
   integer value K, and then later that K value is encoded as a
   variable-length signed "mpint" before being fed to the hash algorithm
   used for key generation.

[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. Also, “fix-length” here should be “fixed-length”. I think it is better to cover this point before diving into the details of how the “mpint” conversion is different from the original X byte string.
-- 
Ron Frederick
[e-mail]