Page MenuHome GnuPG

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

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.Tue, Jun 1, 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.