Re: ssh-ed25519 implementations

[Ron Frederick <[e-mail]>]

Hi Mark,

On May 11, 2017, at 10:21 PM, Mark D. Baushke <[e-mail]> wrote:
> Ron Frederick <[e-mail]> 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
[e-mail]