Page MenuHome GnuPG

Failure to import Curve25519 ECDH secret subkey to the GnupG.
Open, NormalPublic

Description

It looks pretty similar to the issue https://dev.gnupg.org/T5114 :

GnuPG successfully imports attached secret primary key, but fails to import a Cure25519 subkey, asking for password 3 times (while it is stored in cleartext).
If secret key is encrypted, then it shows this message:

gpg: key 0865619E8F83FDC0/CF64DDBAD20995D3: error sending to agent: Bad secret key
gpg: error reading 'rnp-25519-secret.pgp': Bad secret key
gpg: import from 'rnp-25519-secret.pgp' failed: Bad secret key

Things I checked as well:

  • public key part works - encrypt in GnuPG -> decrypt in RNP succeeds.
  • generate the same keypair in GnuPG->import to RNP succeds (and works for decryption) as well.
  • generate the same keypair in GnuPG-re-import back also works.

As Curve25519 secret key is just 32-byte string, and I tried generation multiple times, I cannot see what can go wrong.

Details

Version
2.2.27

Event Timeline

werner triaged this task as High priority.Jun 1 2021, 3:46 PM
werner added projects: gnupg (gpg22), OpenPGP.

fwiw, gpg-agent complains that the keys don't match:

2021-06-01 19:03:48 gpg-agent[3575794] DBG: ecc_testkey inf: Montgomery/Standard
2021-06-01 19:03:48 gpg-agent[3575794] DBG: ecc_testkey nam: Curve25519
2021-06-01 19:03:48 gpg-agent[3575794] DBG: ecc_testkey   p:+7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed
2021-06-01 19:03:48 gpg-agent[3575794] DBG: ecc_testkey   a:+01db41
2021-06-01 19:03:48 gpg-agent[3575794] DBG: ecc_testkey   b:+01
2021-06-01 19:03:48 gpg-agent[3575794] DBG: ecc_testkey g.X:+09
2021-06-01 19:03:48 gpg-agent[3575794] DBG: ecc_testkey g.Y:+20ae19a1b8a086b4e01edd2c7748d14c923d4d7e6d7c61b229e9c5a27eced3d9
2021-06-01 19:03:48 gpg-agent[3575794] DBG: ecc_testkey g.Z:+01
2021-06-01 19:03:48 gpg-agent[3575794] DBG: ecc_testkey   n:+1000000000000000000000000000000014def9dea2f79cd65812631a5cf5d3ed
2021-06-01 19:03:48 gpg-agent[3575794] DBG: ecc_testkey   h:+08
2021-06-01 19:03:48 gpg-agent[3575794] DBG: ecc_testkey   q: [264 bit]
2021-06-01 19:03:48 gpg-agent[3575794] DBG:                  40d459dceb5501ea4a643472376b0b001f0dfeeca7df75da6bdd362938840559 \
2021-06-01 19:03:48 gpg-agent[3575794] DBG:                  30
2021-06-01 19:03:48 gpg-agent[3575794] DBG: ecc_testkey   d:+abe10530d48be80c31479cf0568f0bb46df20c834a5e918e7ea2629da63bf5c7
2021-06-01 19:03:48 gpg-agent[3575794] DBG: Bad check: There is NO correspondence between 'd' and 'Q'!
2021-06-01 19:03:48 gpg-agent[3575794] DBG: ecc_testkey   => Bad secret key

looks to me like you've got the byte ordering of the Curve25519 secret subkey reversed from the way that GnuPG expects it.

This is a bit funny because the byte ordering of the Ed25519 secret primary key is *not* reversed from the way that GnuPG expects it.

investigating the subkey in python:

from cryptography.hazmat.primitives.serialization import Encoding, Format
from cryptography.hazmat.primitives.asymmetric import x25519
from codecs import encode, decode
sec=b'abe10530d48be80c31479cf0568f0bb46df20c834a5e918e7ea2629da63bf5c7'
raw=decode(sec, 'hex')
## this is the byte ordering of the secret value as it appears in the transferred file
encode(x25519.X25519PrivateKey.from_private_bytes(raw).public_key().public_bytes(Encoding.Raw, PublicFormat.Raw), 'hex')
## yields b'9616ff96e28f9b4f3ae1d9623045d8fb6d9d880876b148ab10260fd2e7145606'
encode(x25519.X25519PrivateKey.from_private_bytes(bytes(reversed(raw))).public_key().public_bytes(Encoding.Raw, PublicFormat.Raw), 'hex')
## yields b'd459dceb5501ea4a643472376b0b001f0dfeeca7df75da6bdd36293884055930'
## this latter value matches `q`

The problem here appears to be that the "MPI" of the curve25519 secret key is not actually a standard-issue big-endian OpenPGP MPI -- it's an opaque bytestring expected to be passed to the underlying "native" implementation of x25519, in the same way that the secret key is handled for Ed25519.

This is not very well-described in the draft specification, i'm afraid. I'll try to follow up on openpgp@ietf.org with some clarifying text.

Thanks for investigations! Indeed, we do change byte order when storing/loading private key, as MPI should be big-endian, while curve25519 private key is little endian.
Do I correctly understand that we should store it in the MPI as it is (like with Ed25519)? It would be nice to clarify that in the RFC draft.
Another thing is that in my test even if byte order is not reversed in the secret key (including the attached test key), GnuPG still asks for password, reporting "error sending to agent: Bad passphrase".

From the commit https://dev.gnupg.org/rGba321b60bc3bfc29dfc6fa325dcabad4fac29f9c it seems that the same change should be applied for the Curve25519 case.

Investigated it more, and it looks problem is not in incorrect endianness. Exporting x25519 secret subkey from the GnuPG showed up that we still need to change byte order.
After some experiments I ended up with the following self-explaining code piece, which makes RNP-generated keys to work with GnuPG for import:

repeat:
    if (botan_privkey_create(&pr_key, "Curve25519", "", rng_handle(rng))) {
        goto end;
    }
    /* botan returns key in little-endian, while mpi is big-endian */
    if (botan_privkey_x25519_get_privkey(pr_key, keyle.data())) {
        goto end;
    }
    if ((keyle[31] != 0x45) || (keyle[0] != 0x40)) {
        botan_privkey_destroy(pr_key);
        goto repeat;
    }
    if (botan_privkey_export_pubkey(&pu_key, pr_key)) {
        goto end;
    }

Values 0x45 and 0x40 were picked from the key, generated by GnuPG.
Such key works with import/export and encryption/decryption.
So I'm assuming that source of the issue in some bit combinations handling.
Also attaching 'Good' key generated with RNP.

We invented the 0x40 compression flag to declare that as native curve point format. With the introduction of 448 things got more complicated due to the new IETF statdards for this curev. This is the reason for @gniibe's proposal for a Simple Octet String (SOS) as a new data type in OpenPGP.

@werner isn't it used just for the public key? The secret x25519 key, exported by GnuPG, looks as following (in the way it is stored in file):

45 93 03 2a 23 4c 00 81 84 60 67 b8 45 54 61 34 bb a5 37 4a cb d9 18 24 77 90 17 bb 4e a2 fb 40

Right. However, the SOS thing should then also be used for secret keys. (FWIW, I wrote my last comment while you were writing yours).

I think rGba321b60bc3bfc29dfc6fa325dcabad4fac29f9c has nothing to do with interoperable formats -- how things are stored in ~/.gnupg/private-keys-v1.d is unrelated to the interoperable transferable secret key format specified in 4880 or its revisions.

@dkg I mentioned it just because it was added as (part of the?) solution for Ed25519 issue, i.e. it is not something related to parsing of interoperable format but some further processing when secret key part is sent to the gpg-agent in some intermediate format.

I've mentioned this interop issue (and tried to propose clarifying language for the revised standard) in the IETF OpenPGP WG mailing list.

"Curve25519" in libgcrypt was implemented before the standardization of X25519. There are two problems here: endianess and tweaking-bits.

In libgcrypt, tweaking-bits is responsibility of caller.

So, If gpg-agent needs to accept bare big-endian secret (before twaking bits), we need something like this:

Better to have in-line:

diff --git a/agent/cvt-openpgp.c b/agent/cvt-openpgp.c
index 53c88154b..b1d43227a 100644
--- a/agent/cvt-openpgp.c
+++ b/agent/cvt-openpgp.c
@@ -159,7 +159,21 @@ convert_secret_key (gcry_sexp_t *r_key, int pubkey_algo, gcry_mpi_t *skey,
                EdDSA flag.  */
             format = "(private-key(ecc(curve %s)(flags eddsa)(q%m)(d%m)))";
           else if (!strcmp (curve, "Curve25519"))
-            format = "(private-key(ecc(curve %s)(flags djb-tweak)(q%m)(d%m)))";
+            {
+              unsigned int nbits;
+              unsigned char *buffer = gcry_mpi_get_opaque (skey[1], &nbits);
+              unsigned char d[32];
+
+              if (nbits != 256)
+                return gpg_error (GPG_ERR_BAD_SECKEY);
+
+              memcpy (d, buffer, 32);
+              d[0] = (d[0] & 0x7f) | 0x40;
+              d[31] &= 0xf8;
+              gcry_mpi_release (skey[1]);
+              skey[1] = gcry_mpi_set_opaque_copy (NULL, d, 256);
+              format = "(private-key(ecc(curve %s)(flags djb-tweak)(q%m)(d%m)))";
+            }
           else
             format = "(private-key(ecc(curve %s)(q%m)(d%m)))";

For an implementation of Curve25519 routine, it is needed to tweak those bits.

  • Clear the least-significant-bits (three bits), because the cofactor of the curve is 8.
  • Clear the most-significant-bit in 2^256-bit, because the order of the curve is smaller than 2^255.
  • Set the most-significant-bit in 2^255-bit, so that computation time can be more constant-time.

The issue here is which sides (caller or callee) do this. In libgcrypt for Curve25519, it is caller's responsibility.

gniibe: Can you explain why an import shall modify the secret key? Form my understanding it is an invalid secret key and thus it can't be used. An import operation is different than the key generation.

JFYI: Original curve25519-donna (as well as Botan library, and OpenSSL) tweaks bits inside of the exponentiation function, so secret keys with or without tweaked bits would be equivalent and produce the same public key.

Do we want to encourage multiple cleartext wire-format representations of the same secret key?

Do you think the standard should include guidance about generating (and interpreting) secret keys so that other implementations don't run into the same problem?

@werner
My patch is for the case if it's better to accept such a key of OpenPGP.
I don't know if it's better or not (yet). The purpose of this patch is to show the point where OpenPGP secret part translates into libgcrypt secret key, concretely.

Implementing Curve25519 at that time (before X25519), there were two ways : tweaking bits by caller or by callee.
For libgcrypt which implements curves with its own ECC functions, it was natural to put tweaking-bit handling to caller. In libgcrypt, well-known curves are defined inside, and it's caller to specify how it is used; For example, at that time, we had ECDSA with Ed25519.

(For X448, it's done in the way X448 is defined, in libgcrypt. Tweaking bits is done by callee. So, no problem.)

@dkg
The above is my explanation about what's going on with GnuPG and libgcrypt. For OpenPGP, I think that wire-format for ECC should be defined clearly.
For now, for Curve25519, secret-part is in big-endian with tweaked bits, that's the way GnuPG handles. It's not in native X25519 format.
Clear definition would be new curve with OID of X25519, which use native X25519 format.

@dkg
If we support native X25519 format, multiple representations will be possible (there are 32 ways, at least) for a single secret key, because it's the feature of X25519.

werner lowered the priority of this task from High to Normal.Jun 25 2021, 9:15 AM
werner edited projects, added OpenPGP, gnupg, Support; removed gnupg (gpg22), Bug Report.

We should not support a different OID or representation of 22519 which will only lead to incompatibilities and trouble existing users. 25519 is in too widespread use than to allow for any changes.

Do I correctly understand that issue will be resolved on GnuPG side by tweaking key bits before private-key import/and/or/operations?

@gniibe sorry for pinging, but this issue gets attention as TB users (with RNP OpenPGP backend) cannot import to GnuPG EdDSA secret key which was generated by RNP since it doesn't tweak bits when storing or exporting a secret key.
Should we update RNP to tweak those bits during storage to be more compatible (given that those bits doesn't make any difference)?

@onickolay No sorry needed. It was me, who cannot answer promptly.

I tend to do "accept generously when receive" but "do conservative what you send", as an implementer.

But, I also understand both sides ideas: (1) native format should be well supported, (2) multiple representations are considered bad.

Werner was against change of GnuPG side. And I stuck.

I hope, clarification/agreement from OpenPGP specification, if possible.

Right, as long as there is only one format in widespread use (based on a long existing 4880bis draft) only this format should go over the wire.
Thus, it is a matter how the key is exported. In cryptography you should never have several options - one clearly defined format is what you want. We have had enough trouble with PGP5 peculiarities but in that case their implementation had more users and thus GnuPG had to work around it. Not good, but there was no standard at all at this time.

Please be kind to the TB users and update RNP.

Thanks for the replies, this makes things clear. We'll update RNP to correctly set/unset those bits while saving a generated secret key and a way to fix up previously generated keys.

Thanks. I meanwhile pushed a fix to 2.3 so that a warning is shown if the low bits are set.

Thanks, Werner.
During further work on this got another issue:

Attempt to import to GnuPG x25519 subkey with non-tweaked bits, which is not encrypted, shows failure in interactive mode.
Further key listing shows that secret subkey is offline.

However, with --batch GnuPG reports successful import, and gpg --list-secret-keys shows that secret subkey is available.

Sample key is attached.

Yes, for migration from GnuPG 2.0 reasons, a batch import delays the key checking (i.e. converting from OpenPGP to GnuPG internal format) to the first use. Thus you don't see an error immediately. But if you encrypt something , you won't be able to decrypt it again:

gpg: using subkey 950EE0CD34613DBA instead of primary key 3176FC1486AA2528
gpg: encrypted with cv25519 key, ID 950EE0CD34613DBA, created 2021-09-20
      "eddsa-25519-non-tweaked"
gpg: public key decryption failed: Bad secret key

Well, while importing you get the warning:

gpg: warning: lower 3 bits of the secret key are not cleared
gpg: key 3176FC1486AA2528/950EE0CD34613DBA: secret key imported

Maybe I should turn that into an error.

Thanks for clarification, indeed attempt to decrypt data returns an error afterwards.