Re: ssh-ed25519 implementations

["Mark D. Baushke" <[e-mail]>]

Hi Ron,

Ron Frederick <[e-mail]> writes:

> Hi Mark,
> 
> On May 11, 2017, at 6:32 AM, Mark D. Baushke <[e-mail]> wrote:
> 
> I just took a look at the updated draft. Here’s a copy of the text in
> section 2.1 and some inline suggestions:

I am always interested in making the text better.

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

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.

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

True, that is confusing and should be fixed.

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

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.

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.

I suppose that could be done first in linear time by oring all of the
bytes without leaking side channel information...

        k := x
        zbcheck := 0
	for byte in k: zbcheck |= k[byte];
        assert(zbcheck > 0);
        while (k.length() > 0 &amp;&amp; k[0] == 0) k := k[1:];
        if 0 != (k[0] &amp; 0x80) k := '\0' .. k;    

which is kind of ugly...

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

True, because the prepended length is not a part of the hash to the best
of my recollection. Am I mistaken?

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

Hmmm... should the above use := for assignments everywhere like this?

              k := x;
              while (k.length() > 0 &amp;&amp; k[0] == 0) k := k[1:];
              assert(k.length() > 0);
              if 0 != (k[0] &amp; 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. 

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.

> Also, “fix-length” here should be “fixed-length”.

Sure, I can make that change.

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

Hmmm.... here is how I have updated the text:

--- draft-ietf-curdle-ssh-curves-05.xml	2017-05-11 11:58:15.000000000 -0700
+++ draft-ietf-curdle-ssh-curves-06.xml	2017-05-11 22:18:37.000000000 -0700
@@ -169,8 +169,15 @@
           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.
+        </t>
+
+        <t>
+          The integer K is then fed along with other data to the key
+          exchange method's hash function to generate encryption keys.
           This conversion follows the normal "mpint" process as
-          described in section 5 of <xref target="RFC4251"/>.
+          described in section 5 of <xref target="RFC4251"/> which
+          requires that unnecessary leading bytes with the value 0
+          MUST NOT be included.
         </t>
 
         <t>
@@ -181,32 +188,36 @@
           <list style="symbols">
 
             <t>
-              Trim all leading zero-bytes of X. If X is all
-              zero-bytes, then the key exchange MUST fail.
+              Trim all leading zero-bytes of X, as required in section
+              5 of <xref target="RFC4251"/>. If X is all
+              zero-bytes, then the key exchange MUST fail as required
+              in section 6 of <xref target="RFC7748"/>.
             </t>
 
             <t>
-              If the high bit of X is set, the mpint format requires a
-              zero byte to be prepended.
+              Given X is a positive, if the MSB of X is set, then
+              the "mpint" format requires a zero-byte to be prepended.
             </t>
 
             <t>
-              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.
+              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.
             </t>
 
           </list>
 
           <figure anchor="pseudo.code">
             <preamble>
-              Or, as pseudo code:
+              Or, as pseudo code (without dealing with side-channel
+              issues):
             </preamble>
             <artwork>
               k := x;
-              while (k.length() > 0 &amp;&amp; k[0] == 0) k = k[1:];
+              while (k.length() > 0 &amp;&amp; k[0] == 0) k := k[1:];
               assert(k.length() > 0);
-              if 0 != (k[0] &amp; 0x80) k = '\0' .. k;
+              if 0 != (k[0] &amp; 0x80) k := '\0' .. k;
             </artwork>
           </figure>
         </t>
@@ -214,7 +225,7 @@
         <t>
           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 <xref
+          fixed-length unsigned litle-endian conversion, per <xref
           target="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