cv25519 scalar byte order

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

cv25519 scalar byte order

Vincent Breitmoser
Hey folks,

I've been working recently on finally getting cv25519 to work in
OpenKeychain, and I did achieve an interoperable implementation in the
end. But there is a part that doesn't work as I expected from the spec,
maybe someone here has an explanation.

So, since we already had ECDH working for other curves, I had all the
KDF parts in place. I created an encrypted file in GnuPG and built a
unit test from that to work against. Switching out the curve operation
for X25519 didn't take long - but the test didn't work.

I got some intermediate crypto parameters from gnupg, and compared them
to my implementation. The difference in numbers happened around X25519
itself: I would give it the same numbers that GnuPG used as input for
the operation, but receive a different result and the aes-unwrap failed
afterwards.

The difference I found was that GnuPG apparently reverses the order of
bytes in the scalar before doing the X25519 operation. In its tests, it
uses the vectors from RFC 7748 as input for `test_cv(k, u)` function,
but the bytes of k are reversed before being handed to the actual
implementation:

https://github.com/gpg/libgcrypt/blob/master/tests/t-cv25519.c#L146

The input format for the X25519 parameters is defined in 4880-bis as
"0x40, followed by the custom format defined by the operation". I'm also
fairly sure I didn't similarly reverse the input scalar for EdDSA. So
this was quite the curveball for me (haha) while implementing this to
spec.

I spent some time looking at this, but couldn't find the part of the
spec that would require this reversing of bytes, and nobody I asked so
far could explain this behavior to me. Is GnuPG behaving weirdly? Or
what am I missing?

Cheers

 - V


_______________________________________________
Gnupg-devel mailing list
[hidden email]
http://lists.gnupg.org/mailman/listinfo/gnupg-devel
Reply | Threaded
Open this post in threaded view
|

Re: cv25519 scalar byte order

Werner Koch
On Sun, 11 Feb 2018 13:05, [hidden email] said:

> https://github.com/gpg/libgcrypt/blob/master/tests/t-cv25519.c#L146

Pretty please do not reference arbitrary clones of GnuPG software but us
the standard place git.gnupg.org (or maybe dev.gnupg.org).

It would also be useful to explain you question with a hex dump of the
parameters instead of just a verbal description.


Shalom-Salam,

   Werner

--
Die Gedanken sind frei.  Ausnahmen regelt ein Bundesgesetz.

_______________________________________________
Gnupg-devel mailing list
[hidden email]
http://lists.gnupg.org/mailman/listinfo/gnupg-devel

attachment0 (233 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: cv25519 scalar byte order

Vincent Breitmoser
Werner Koch([hidden email])@Tue, Feb 13, 2018 at 01:51:12PM +0100:
> It would also be useful to explain you question with a hex dump of the
> parameters instead of just a verbal description.

Sure.

X25519 Input:
k = 45afc2b924ad66c34dd0508f4aac568f8b8b3c154f7ae44104b794c7551dfd88
u = b94121e20db0369d7cbbd8d09372bae2d48d6e990b5f60895f326235e195e134

X25519 Output:
bouncycastle and tink = c3843a427995b2031e160409b6b1a29700e6e84ee274283bd754f8f9df212313
GnuPG = 005acc6baccaaf72041b10ca74c24e311804958dc87cda5a1e96073c0b922726

See attached secret key and secret message with those values. This fails
to decrypt for me if I use k for the X25519 input (before SP800-56A),
but succeeds with reverse(k).

While implementing to spec, this was unexpected for me, and it took me
quite a while to figure out what GnuPG was doing differently. I also
double-checked, for EdDSA the MPI value is not similarly reversed before
it is handed as a scalar to the algorithm.

 - V


_______________________________________________
Gnupg-devel mailing list
[hidden email]
http://lists.gnupg.org/mailman/listinfo/gnupg-devel

cv25519-encrypted.asc.gpg (222 bytes) Download Attachment
cv25519-key.sec.asc.gpg (642 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: cv25519 scalar byte order

NIIBE Yutaka
Vincent Breitmoser <[hidden email]> wrote:
> See attached secret key and secret message with those values. This fails
> to decrypt for me if I use k for the X25519 input (before SP800-56A),
> but succeeds with reverse(k).
>
> While implementing to spec, this was unexpected for me, and it took me
> quite a while to figure out what GnuPG was doing differently. I also
> double-checked, for EdDSA the MPI value is not similarly reversed before
> it is handed as a scalar to the algorithm.

Well, I admit that it's confusing, and it would be considered a kind of
problem in GnuPG implementation.  Let us consider how we can go forward.

FWIW, I debug with the following:

  $ gpg --debug=crypto -a -o /tmp/OUTPUT.asc -a -r <ECCKEY> -e SOMEFILE
  $ gpg --debug=crypto,ipc /tmp/OUTPUT.asc


I think that there are two things; input handling to
encryption/decryption functions and output handling from those
functions.  The latter is troublesome, I suppose.


(1) INPUT handling for ECDH

In the libgcrypt API of gcry_pk_encrypt, scalar input is defined as MPI
(big-endian order).

When GnuPG calls gcry_pk_encrypt, no conversion is done for scalar
input; The octet sequence is interpreted as standard MPI (big-endian).

# In the test code of X25519 (libgcrypt/tests/t-cv25519.c), the scalar
# input K is needed to be converted from little-endian (defined in
# X25519) to big-endian, thus, we have reverse_buffer.

While gcry_pk_decrypt supports scalar input with the prefix 0x40 for
little-endian public key, gcry_pk_encrypt doesn't support scalar input
with the prefix 0x40 (yet).

I think that this is just a little problem.  It is possible for
libgcrypt to support the prefix 0x40, so that t-cv25519.c can be
less confusion.


(2) OUTPUT handling for ECDH

Both of gcry_pk_encrypt and gcry_pk_decrypt output the scalar with the
prefix 0x40.  After the prefix, it's little-endian.

In GnuPG (pk_ecdh_encrypt_with_shared_point in gnupg/g10/ecdh.c),

    For shared secret, result comes with the prefix 0x40 from libgcrypt,
    then, the octet sequence after 0x40 is used as-is (with no
    conversion of endian) to the input to KDF function.

I think that we have interpretation problem here.

In the section 7. Key Derivation Function in RFC 6637, KDF is described
referring NIST-SP800-56A and RFC 6090.

For the prefix 0x40, I interpret it as "extracting X part from the
representation of Z", no change of byte-order.
--

_______________________________________________
Gnupg-devel mailing list
[hidden email]
http://lists.gnupg.org/mailman/listinfo/gnupg-devel
Reply | Threaded
Open this post in threaded view
|

Re: cv25519 scalar byte order

NIIBE Yutaka
Hello,

Here is an example packet of secret key as an output of GnuPG's
--list-packets.

==========================
# off=267 ctb=9c tag=7 hlen=2 plen=93
:secret sub key packet:
        version 4, algo 18, created 1518583322, expires 0
        pkey[0]: 0A2B060104019755010501 cv25519 (1.3.6.1.4.1.3029.1.5.1)
        pkey[1]: 40FD57ED7E6D3490F0BFB4995F281A53648842CDB84DEBA6726DF5BA1994968D23
        pkey[2]: 03010807
        skey[3]: 5669627AB7427CE223BD94101603978F3F4599AE1A007087A0B3DBBFB67D3278
        checksum: 0f5a
        keyid: 55C6A075A3C82F68
==========================

I wonder if we have difference in the interpretation of secret part
(skey[3]).

In GnuPG, this part is interpreted as standard MPI representation
(big-endian).

For better interoperability, we could support the prefix 0x40 for this
secret part, I suppose.
--

_______________________________________________
Gnupg-devel mailing list
[hidden email]
http://lists.gnupg.org/mailman/listinfo/gnupg-devel
Reply | Threaded
Open this post in threaded view
|

Re: cv25519 scalar byte order

Vincent Breitmoser
> I wonder if we have difference in the interpretation of secret part
> (skey[3]).
>
> In GnuPG, this part is interpreted as standard MPI representation
> (big-endian).

MPIs are specified as big-endian, but this doesn't really have meaning
if they aren't actually interpreted as numbers.  RFC7748 specifically
defines EdDSA and X25519 over octet-strings:

# Although the functions work internally with integers, the inputs and
# outputs are 32-byte strings (for X25519) or 56-byte strings (for X448)
# and this specification defines their encoding.

My expectation was that skey[3] would be passed to the functions as-is,
which was matched by GnuPG for EdDSA, but not X25519.

As for where to go from here, I don't know. Most importantly, we should
make sure the spec can be independently implemented in an interoperable
way. :)

 - V


_______________________________________________
Gnupg-devel mailing list
[hidden email]
http://lists.gnupg.org/mailman/listinfo/gnupg-devel
Reply | Threaded
Open this post in threaded view
|

Re: cv25519 scalar byte order

NIIBE Yutaka
Vincent Breitmoser <[hidden email]> wrote:
> MPIs are specified as big-endian, but this doesn't really have meaning
> if they aren't actually interpreted as numbers.  RFC7748 specifically
> defines EdDSA and X25519 over octet-strings:

That would be an interesting claim.

Please note that our adoption of ECDH using Curve25519 was done before
X25519.  In the context of RFC 6637, which defines 18 for ECDH public
key algorithm, it is a valid interpretation to handle the secret key
field in a way described in the section 9. Encoding of Public and
Private Keys.

It seems for me that you are implementing OpenPGP ECDH of Curve25519 on
top of X25519 function.  That's different path.  If so, I could
understand your claim, but... if it is the case, from my viewpoint, it's
more relevant to have new algorithm ID of twenty-something.

> My expectation was that skey[3] would be passed to the functions as-is,
> which was matched by GnuPG for EdDSA, but not X25519.

Since EdDSA has its own algorithm ID, the definition of the field is up
to EdDSA.

> As for where to go from here, I don't know. Most importantly, we should
> make sure the spec can be independently implemented in an interoperable
> way. :)

Perhaps, refering RFC7749 for Curve25519 is not good if it can result
such a confusion?  While I don't know how to improve the spec, but
it is needed to clarify.
--

_______________________________________________
Gnupg-devel mailing list
[hidden email]
http://lists.gnupg.org/mailman/listinfo/gnupg-devel
Reply | Threaded
Open this post in threaded view
|

Re: cv25519 scalar byte order

Vincent Breitmoser
Hey gniibe,

> Please note that our adoption of ECDH using Curve25519 was done before
> X25519.  In the context of RFC 6637, which defines 18 for ECDH public
> key algorithm, it is a valid interpretation to handle the secret key
> field in a way described in the section 9.

That actually explains a lot, haha!

I was following the reference to RFC7748 from rfc4880bis:
https://tools.ietf.org/html/draft-ietf-openpgp-rfc4880bis-04#section-13.1

And given that the public point is encoded with a 0x40 prefix, I assumed
that X25519 was used the same way as EdDSA as a type of ECDH. What else
would define the "custom point compression" format that is used here, if
not X25519?

> it's more relevant to have new algorithm ID of twenty-something.

That would be a lot simpler both in terms of specification and
implementation - just put byte arrays into a well-defined,
well-specified and widely used method. Compared to actually dealing with
points on curves and their different representations etc.

Alas, it's probably too late for that idea to be useful.

> Perhaps, refering RFC7749 for Curve25519 is not good if it can result
> such a confusion?  While I don't know how to improve the spec, but
> it is needed to clarify.

I'm not sure. If it's valid to "just X25519, then KDF" (and that worked
at least for me, modulo reversing the byte array) then I would
definitely point that out specifically in the spec, as it greatly
simplifies implementation. I had failed implementing cv25519 support
using bouncycastle's plain Curve25519 primitives before.

Thanks for your input so far, much appreciated!

 - V


_______________________________________________
Gnupg-devel mailing list
[hidden email]
http://lists.gnupg.org/mailman/listinfo/gnupg-devel
Reply | Threaded
Open this post in threaded view
|

Re: cv25519 scalar byte order

Werner Koch
In reply to this post by NIIBE Yutaka
On Wed, 14 Feb 2018 06:13, [hidden email] said:

> I wonder if we have difference in the interpretation of secret part
> (skey[3]).
>
> In GnuPG, this part is interpreted as standard MPI representation
> (big-endian).
>
> For better interoperability, we could support the prefix 0x40 for this
> secret part, I suppose.

That would be incorrect.  The prefix (e.g. 0x40) indicates a _point_
format and not the format of a scalar.  Thus skey[3] MAY not have this
prefix.


Shalom-Salam,

   Werner


--
#  Please read:  Daniel Ellsberg - The Doomsday Machine  #
Die Gedanken sind frei.  Ausnahmen regelt ein Bundesgesetz.

_______________________________________________
Gnupg-devel mailing list
[hidden email]
http://lists.gnupg.org/mailman/listinfo/gnupg-devel

attachment0 (233 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: cv25519 scalar byte order

Daniel Kahn Gillmor-7
On Mon 2018-02-19 15:23:10 +0100, Werner Koch wrote:

> On Wed, 14 Feb 2018 06:13, [hidden email] said:
>
>> I wonder if we have difference in the interpretation of secret part
>> (skey[3]).
>>
>> In GnuPG, this part is interpreted as standard MPI representation
>> (big-endian).
>>
>> For better interoperability, we could support the prefix 0x40 for this
>> secret part, I suppose.
>
> That would be incorrect.  The prefix (e.g. 0x40) indicates a _point_
> format and not the format of a scalar.  Thus skey[3] MAY not have this
> prefix.
what does this "MAY NOT" mean?  if this is an attempt at RFC 2119
language, i don't understand it.  Do you mean "MUST NOT" ?

What steps are needed to clarify the documentation here so that we can
have interoperable implementations?

          --dkg

_______________________________________________
Gnupg-devel mailing list
[hidden email]
http://lists.gnupg.org/mailman/listinfo/gnupg-devel

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

Re: cv25519 scalar byte order

Werner Koch
On Mon, 19 Feb 2018 17:24, [hidden email] said:

>> That would be incorrect.  The prefix (e.g. 0x40) indicates a _point_
>> format and not the format of a scalar.  Thus skey[3] MAY not have this
>> prefix.
>
> what does this "MAY NOT" mean?  if this is an attempt at RFC 2119
> language, i don't understand it.  Do you mean "MUST NOT" ?

I was thinking SHOULD NOT but indeed it MUST be MUST NOT.

> What steps are needed to clarify the documentation here so that we can
> have interoperable implementations?

I can't remember an open issue regaring this in the WG.  Should be
handled there anyway,


Salam-Shalom,

   Werner


--
#  Please read:  Daniel Ellsberg - The Doomsday Machine  #
Die Gedanken sind frei.  Ausnahmen regelt ein Bundesgesetz.

_______________________________________________
Gnupg-devel mailing list
[hidden email]
http://lists.gnupg.org/mailman/listinfo/gnupg-devel

attachment0 (233 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: cv25519 scalar byte order

Daniel Kahn Gillmor-7
Over in
https://lists.gnupg.org/pipermail/gnupg-devel/2018-February/033437.html,
a discussion was started about scalar byte order for OpenPGP curve 25519
keys:

On Mon 2018-04-09 18:53:53 +0200, Werner Koch wrote:

> On Mon, 19 Feb 2018 17:24, [hidden email] said:
> [ gniibe wrote: ]
>>> That would be incorrect.  The prefix (e.g. 0x40) indicates a _point_
>>> format and not the format of a scalar.  Thus skey[3] MAY not have this
>>> prefix.
>>
>> what does this "MAY NOT" mean?  if this is an attempt at RFC 2119
>> language, i don't understand it.  Do you mean "MUST NOT" ?
>
> I was thinking SHOULD NOT but indeed it MUST be MUST NOT.
>
>> What steps are needed to clarify the documentation here so that we can
>> have interoperable implementations?
>
> I can't remember an open issue regaring this in the WG.  Should be
> handled there anyway,

I'm moving this discussion to the WG :)

    --dkg

_______________________________________________
Gnupg-devel mailing list
[hidden email]
http://lists.gnupg.org/mailman/listinfo/gnupg-devel