X25519 - why openssl shows server temp key as 253 bits?

classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

X25519 - why openssl shows server temp key as 253 bits?

M K Saravanan
Hi,

When using openssl with X25519, why it shows the server temp key as 253 bits?

Example:

---
No client certificate CA names sent
Peer signing digest: SHA256
Peer signature type: RSA
Server Temp Key: X25519, 253 bits
---

I thought Curve25519 is using 256 bit keys.

Why 253 instead of 256?

with regards,
Saravanan
--
openssl-users mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-users
Reply | Threaded
Open this post in threaded view
|

Re: X25519 - why openssl shows server temp key as 253 bits?

Kyle Hamilton
Probably because the definition of X25519 requires that bits 0, 1, and 2 of the first byte of the private key are set to 0 before being used, and OpenSSL counts the number of bits including the highest-order set bit.  (Really, there's an additional 2 bits that are also set to known values: bit 6 of the last byte is set, and bit 7 of the last byte is cleared.  In my view, this actually reduces the necessary brute-force search space from 256 bits to 251 bits. However, literally any 32-byte string can be used as a public key.  Apparently, djb views this as sufficient to call it a 256-bit strength function.)

For the specification, please see the subsection entitled "Responsibilities of the User" in section 3 of https://cr.yp.to/ecdh/curve25519-20060209.pdf .

-Kyle H





On Mon, Sep 3, 2018, 22:29 M K Saravanan <[hidden email]> wrote:
Hi,

When using openssl with X25519, why it shows the server temp key as 253 bits?

Example:

---
No client certificate CA names sent
Peer signing digest: SHA256
Peer signature type: RSA
Server Temp Key: X25519, 253 bits
---

I thought Curve25519 is using 256 bit keys.

Why 253 instead of 256?

with regards,
Saravanan
--
openssl-users mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-users

--
openssl-users mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-users
Reply | Threaded
Open this post in threaded view
|

Re: X25519 - why openssl shows server temp key as 253 bits?

Robert Moskowitz
And I seem to recall that one bit is for compact representation.  That is, is y positive or negative.  With p256, you have to transmit x and y or deal with the compact representation patent.

On 09/04/2018 08:00 AM, Kyle Hamilton wrote:
Probably because the definition of X25519 requires that bits 0, 1, and 2 of the first byte of the private key are set to 0 before being used, and OpenSSL counts the number of bits including the highest-order set bit.  (Really, there's an additional 2 bits that are also set to known values: bit 6 of the last byte is set, and bit 7 of the last byte is cleared.  In my view, this actually reduces the necessary brute-force search space from 256 bits to 251 bits. However, literally any 32-byte string can be used as a public key.  Apparently, djb views this as sufficient to call it a 256-bit strength function.)

For the specification, please see the subsection entitled "Responsibilities of the User" in section 3 of https://cr.yp.to/ecdh/curve25519-20060209.pdf .

-Kyle H





On Mon, Sep 3, 2018, 22:29 M K Saravanan <[hidden email]> wrote:
Hi,

When using openssl with X25519, why it shows the server temp key as 253 bits?

Example:

---
No client certificate CA names sent
Peer signing digest: SHA256
Peer signature type: RSA
Server Temp Key: X25519, 253 bits
---

I thought Curve25519 is using 256 bit keys.

Why 253 instead of 256?

with regards,
Saravanan
--
openssl-users mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-users




--
openssl-users mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-users
Reply | Threaded
Open this post in threaded view
|

Re: X25519 - why openssl shows server temp key as 253 bits?

Jakob Bohm-7
On 04/09/2018 15:43, Robert Moskowitz wrote:
> And I seem to recall that one bit is for compact representation. That
> is, is y positive or negative.  With p256, you have to transmit x and
> y or deal with the compact representation patent.
>
Not sure if this applies do X25519 and Ed255 which use different
techniques than the traditional curves.

Those two are also intended to avoid data-dependent if() statements
(because of side channel attacks), but remain vulnerable on CPUs
where division or multiplication instructions have data-dependent
time and/or power consumption (which is unfortunately most of the
common ones).

> On 09/04/2018 08:00 AM, Kyle Hamilton wrote:
>> Probably because the definition of X25519 requires that bits 0, 1,
>> and 2 of the first byte of the private key are set to 0 before being
>> used, and OpenSSL counts the number of bits including the
>> highest-order set bit. (Really, there's an additional 2 bits that are
>> also set to known values: bit 6 of the last byte is set, and bit 7 of
>> the last byte is cleared.  In my view, this actually reduces the
>> necessary brute-force search space from 256 bits to 251 bits.
>> However, literally any 32-byte string can be used as a public key. 
>> Apparently, djb views this as sufficient to call it a 256-bit
>> strength function.)
>>
>> For the specification, please see the subsection entitled
>> "Responsibilities of the User" in section 3 of
>> https://cr.yp.to/ecdh/curve25519-20060209.pdf .
>>
>> -Kyle H
>>
>>
>>
>>
>>
>> On Mon, Sep 3, 2018, 22:29 M K Saravanan <[hidden email]
>> <mailto:[hidden email]>> wrote:
>>
>>     Hi,
>>
>>     When using openssl with X25519, why it shows the server temp key
>>     as 253 bits?
>>
>>     Example:
>>
>>     ---
>>     No client certificate CA names sent
>>     Peer signing digest: SHA256
>>     Peer signature type: RSA
>>     Server Temp Key: X25519, 253 bits
>>     ---
>>
>>     I thought Curve25519 is using 256 bit keys.
>>
>>     Why 253 instead of 256?
>>
>>     with regards,
>>     Saravanan
>>

Enjoy

Jakob
--
Jakob Bohm, CIO, Partner, WiseMo A/S.  https://www.wisemo.com
Transformervej 29, 2860 Søborg, Denmark.  Direct +45 31 13 16 10
This public discussion message is non-binding and may contain errors.
WiseMo - Remote Service Management for PCs, Phones and Embedded

--
openssl-users mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-users
Reply | Threaded
Open this post in threaded view
|

Re: X25519 - why openssl shows server temp key as 253 bits?

Robert Moskowitz
My source is Dr. Lange at the IETF meeting in Toronto when the IETF
selected EC25519.

A curve point needs an x and a y.  But do you need the y for the
computation.  Do you only need its sign?  I don't know.  I am not a
mathematician.

I may have misunderstood her at the time.

On 09/04/2018 10:19 AM, Jakob Bohm wrote:

> On 04/09/2018 15:43, Robert Moskowitz wrote:
>> And I seem to recall that one bit is for compact representation. That
>> is, is y positive or negative. With p256, you have to transmit x and
>> y or deal with the compact representation patent.
>>
> Not sure if this applies do X25519 and Ed255 which use different
> techniques than the traditional curves.
>
> Those two are also intended to avoid data-dependent if() statements
> (because of side channel attacks), but remain vulnerable on CPUs
> where division or multiplication instructions have data-dependent
> time and/or power consumption (which is unfortunately most of the
> common ones).
>
>> On 09/04/2018 08:00 AM, Kyle Hamilton wrote:
>>> Probably because the definition of X25519 requires that bits 0, 1,
>>> and 2 of the first byte of the private key are set to 0 before being
>>> used, and OpenSSL counts the number of bits including the
>>> highest-order set bit. (Really, there's an additional 2 bits that
>>> are also set to known values: bit 6 of the last byte is set, and bit
>>> 7 of the last byte is cleared.  In my view, this actually reduces
>>> the necessary brute-force search space from 256 bits to 251 bits.
>>> However, literally any 32-byte string can be used as a public key. 
>>> Apparently, djb views this as sufficient to call it a 256-bit
>>> strength function.)
>>>
>>> For the specification, please see the subsection entitled
>>> "Responsibilities of the User" in section 3 of
>>> https://cr.yp.to/ecdh/curve25519-20060209.pdf .
>>>
>>> -Kyle H
>>>
>>>
>>>
>>>
>>>
>>> On Mon, Sep 3, 2018, 22:29 M K Saravanan <[hidden email]
>>> <mailto:[hidden email]>> wrote:
>>>
>>>     Hi,
>>>
>>>     When using openssl with X25519, why it shows the server temp key
>>>     as 253 bits?
>>>
>>>     Example:
>>>
>>>     ---
>>>     No client certificate CA names sent
>>>     Peer signing digest: SHA256
>>>     Peer signature type: RSA
>>>     Server Temp Key: X25519, 253 bits
>>>     ---
>>>
>>>     I thought Curve25519 is using 256 bit keys.
>>>
>>>     Why 253 instead of 256?
>>>
>>>     with regards,
>>>     Saravanan
>>>
>
> Enjoy
>
> Jakob

--
openssl-users mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-users
Reply | Threaded
Open this post in threaded view
|

Re: X25519 - why openssl shows server temp key as 253 bits?

Jakob Bohm-7
On 04/09/2018 16:24, Robert Moskowitz wrote:
> My source is Dr. Lange at the IETF meeting in Toronto when the IETF
> selected EC25519.
>
> A curve point needs an x and a y.  But do you need the y for the
> computation.  Do you only need its sign?  I don't know.  I am not a
> mathematician.
>
> I may have misunderstood her at the time.

Ok, she (if anyone) should know.

I expect the papers, sample code etc. by Bernstein, Lange et al to
provide all the details of this.

>
> On 09/04/2018 10:19 AM, Jakob Bohm wrote:
>> On 04/09/2018 15:43, Robert Moskowitz wrote:
>>> And I seem to recall that one bit is for compact representation. That
>>> is, is y positive or negative. With p256, you have to transmit x and
>>> y or deal with the compact representation patent.
>>>
>> Not sure if this applies do X25519 and Ed255 which use different
>> techniques than the traditional curves.
>>
>> Those two are also intended to avoid data-dependent if() statements
>> (because of side channel attacks), but remain vulnerable on CPUs
>> where division or multiplication instructions have data-dependent
>> time and/or power consumption (which is unfortunately most of the
>> common ones).
>>
>>> On 09/04/2018 08:00 AM, Kyle Hamilton wrote:
>>>> Probably because the definition of X25519 requires that bits 0, 1,
>>>> and 2 of the first byte of the private key are set to 0 before being
>>>> used, and OpenSSL counts the number of bits including the
>>>> highest-order set bit. (Really, there's an additional 2 bits that
>>>> are also set to known values: bit 6 of the last byte is set, and bit
>>>> 7 of the last byte is cleared.  In my view, this actually reduces
>>>> the necessary brute-force search space from 256 bits to 251 bits.
>>>> However, literally any 32-byte string can be used as a public key.
>>>> Apparently, djb views this as sufficient to call it a 256-bit
>>>> strength function.)
>>>>
>>>> For the specification, please see the subsection entitled
>>>> "Responsibilities of the User" in section 3 of
>>>> https://cr.yp.to/ecdh/curve25519-20060209.pdf .
>>>>
>>>> -Kyle H
>>>>
>>>>
>>>>
>>>>
>>>>
>>>> On Mon, Sep 3, 2018, 22:29 M K Saravanan <[hidden email]
>>>> <mailto:[hidden email]>> wrote:
>>>>
>>>>     Hi,
>>>>
>>>>     When using openssl with X25519, why it shows the server temp key
>>>>     as 253 bits?
>>>>
>>>>     Example:
>>>>
>>>>     ---
>>>>     No client certificate CA names sent
>>>>     Peer signing digest: SHA256
>>>>     Peer signature type: RSA
>>>>     Server Temp Key: X25519, 253 bits
>>>>     ---
>>>>
>>>>     I thought Curve25519 is using 256 bit keys.
>>>>
>>>>     Why 253 instead of 256?
>>>>
>>>>     with regards,
>>>>     Saravanan
>>>>




Enjoy

Jakob
--
Jakob Bohm, CIO, Partner, WiseMo A/S.  https://www.wisemo.com
Transformervej 29, 2860 Søborg, Denmark.  Direct +45 31 13 16 10
This public discussion message is non-binding and may contain errors.
WiseMo - Remote Service Management for PCs, Phones and Embedded
--
openssl-users mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-users
Reply | Threaded
Open this post in threaded view
|

Re: X25519 - why openssl shows server temp key as 253 bits?

Viktor Dukhovni
In reply to this post by Robert Moskowitz
With curve25519, the scalar multiplication function:

  (x, y) -> n * (x, y) = (x', y') -> x'

has the property that for valid points on the extended curve (degree
two extension of F(p) that gives a y for every x in F(p)), x' depends
only on x, and can be effectively computed from x alone, and this can
be done for all x in F(p) since all "x" values are either on the curve
or its "twist".  Therefore, the X25519 key agreement protocol only
uses the x-coordinate.

IIRC, Ed25519 signatures do require a y-coordinate sign, and so the
signature representation is not x-only.

> On Sep 4, 2018, at 10:24 AM, Robert Moskowitz <[hidden email]> wrote:
>
> My source is Dr. Lange at the IETF meeting in Toronto when the IETF selected EC25519.
>
> A curve point needs an x and a y.  But do you need the y for the computation.  Do you only need its sign?  I don't know.  I am not a mathematician.

--
        Viktor.

--
openssl-users mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-users
Reply | Threaded
Open this post in threaded view
|

Re: X25519 - why openssl shows server temp key as 253 bits?

Michael Richardson
In reply to this post by Robert Moskowitz

Robert Moskowitz <[hidden email]> wrote:
    > A curve point needs an x and a y.  But do you need the y for the
    > computation.  Do you only need its sign?  I don't know.  I am not a
    > mathematician.

My understanding is that you need x and y to do the computation.
(And I observe this in code)

However, since x and y have to be on the curve, if you know x, then
that constrained y to be one or two values... so you need to know the *sign*
of y, which is transmitted as a single bit. Then you can calculate y.
The fundamental reason behind this is because sqrt(4) = 2, and sqrt(4) = -2...

Since some bits of the x are required to be 0, it's possible to encode the
sign of Y into the encoded X bit-stream...

--
]               Never tell me the odds!                 | ipv6 mesh networks [
]   Michael Richardson, Sandelman Software Works        | network architect  [
]     [hidden email]  http://www.sandelman.ca/        |   ruby on rails    [


--
openssl-users mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-users

signature.asc (497 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: X25519 - why openssl shows server temp key as 253 bits?

Viktor Dukhovni
> On Sep 4, 2018, at 12:10 PM, Michael Richardson <[hidden email]> wrote:
>
> My understanding is that you need x and y to do the computation.
> (And I observe this in code)

The Y coordinate is not needed for X25519 and X448 Diffie-Helman key agreement,
these operate on the X (sometimes called "u") coordinate only.

The Ed25519 and Ed448 algorithms do use compressed-encodings with one bit
used to disambiguate the choice of square-root for one of the coordinates.
With Edwards form the choice of which to to compress is arbitrary, the
curve is invariant under exchange of x and y or change of either sign.

        https://tools.ietf.org/html/rfc8032#section-5.1.2
        https://tools.ietf.org/html/rfc8032#section-5.2.2

--
--
        Viktor.
--
openssl-users mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-users