Re: ssh-ed25519 implementations

[Ron Frederick <[e-mail]>]

Hi Mark,

On May 13, 2017, at 7:51 AM, Mark D. Baushke <[e-mail]> wrote:
> I have made some adjustments. Here is a unified diff of the relevant
> changes to the .txt form of the draft. If the pseudo-code looks bad,
> let me know if I should just remove it or not.

I would lean toward removing the pseudo-code, and just letting RFC 4251 and the examples provided in section 5 there speak for themselves. If you do that, you probably don’t even need to describe the details of how to encode the length. All I was really looking for here is a mention that the length is present after the conversion, since you had so much detail about the conversion of the integer itself. However, if you just reference this encoding mechanism you may be fine without it. You could replace the second and third paragraphs below with:

The integer K is then encoded as an mpint using the process described in section 5 of [RFC451] and the resulting bytes are fed as described in [RFC4253] to the key exchange method’s hash function to generate encryption keys.


> --- draft-ietf-curdle-ssh-curves-05.txt	2017-05-11 11:58:23.000000000 -0700
> +++ draft-ietf-curdle-ssh-curves-06.txt	2017-05-13 07:46:54.000000000 -0700
> @@ -140,47 +140,64 @@
>    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
> -   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
> -   5 of [RFC4251].
> +   The shared secret, K, is defined in [RFC4253] and [RFC5656] as an
> +   integer encoded as a multiple precision integer (mpint).
> +   Curve25519/448 outputs a binary string X, which is 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 octets as an unsigned fixed-
> +   length integer encoded in network byte order.
> +
> +   The fixed-length integer is then minimized into the minimum number of
> +   octets to represent a positve mpint.  This conversion follows the
> +   normal "mpint" process as described in section 5 of [RFC4251] which
> +   requires that unnecessary leading bytes with the value 0 MUST NOT be
> +   included.  The length of the integer is then prepended with a 4 octet
> +   big-endian integer which is the length in octets of the minimized K.
> +
> +   The mpint K is then fed along with other data to the key exchange
> +   method's hash function to generate encryption keys.
> 
>    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.
> -
> -   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.
> 
> -   Or, as pseudo code:
> +   o  Trim all leading zero-bytes of X, as required in section 5 of
> +      [RFC4251].  If X is all zero-bytes, then the key exchange MUST
> +      fail as required in section 6 of [RFC7748].
> +
> +   o  Given X is a positive, if the MSB of X is set, then the "mpint"
> +      format requires a zero-byte to be prepended.
> +
> +   o  The length of the "mpint" form of K may not be the same as the
> +      original length of X due to trimming or prepending zero-byte
> +      values as needed for "mpint" format. prepend K with the big-endian
> +      number of octets for the length of K.
> +
> +   Or, as pseudo code (without dealing with side-channel issues):
> 
>                  k := x;
> -                 while (k.length() > 0 && k[0] == 0) k = k[1:];
> +                 while (k.length() > 0 && k[0] == 0) k := k[1:];
>                  assert(k.length() > 0);
> -                 if 0 != (k[0] & 0x80) k = '\0' .. k;
> +                 if 0 != (k[0] & 0x80) k := '\0' .. k;
> +                 l[0] := k.lengh() >> 24;
> +                 l[1] := (k.lengh() >> 16) & 0xff;
> +                 l[2] := (k.lengh() >> 8) & 0xff;
> +                 l[3] := k.lengh() & 0xff;
> +                 k := l .. 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
> +   there will be encoded into byte strings by doing a fixed-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

-- 
Ron Frederick
[e-mail]