Montgomery and (Edwards) Key Generation, Use, and Interoperability about opensc HOT 14 OPEN

This is problematic from the beginning of the edwards/montgomery keys in pkcs11 3.0. When I was putting together the basic support for this in opensc for nitrokey/openpgp, i tried to get some comments from the pkcs11 committee, but as far as I remember, there was no great consensus. In the end, I ended up implementing parsing for both ways.

I agree that when generating keys, we should try to go with the most standard and compatible way.

On the side note, I also noticed that the pkcs11-tool prints the EC_PARAMS as an OID regardless of the content, resulting in some weird results (did not manage to write the patch yet).

from opensc.

On the side note, I also noticed that the pkcs11-tool prints the EC_PARAMS as an OID regardless of the content, resulting in some weird results (did not manage to write the patch yet).

Most likely because https://github.com/OpenSC/OpenSC/blob/master/src/tools/pkcs11-tool.c#L5794 is reading
0x06 0x03 0x2b 0x65 0x70 because OpenSSL was involved. https://lapo.it/asn1js/ lists this as: "edwards25519"

In some of my tests I changed this in pkcs11-tool.c Note the 130b is changed to 130a

-       {"edwards25519","1.3.6.1.4.1159.15.1", "130c656477617264733235353139", 255, CKM_EC_EDWARDS_KEY_PAIR_GEN},
-       {"curve25519", "1.3.6.1.4.3029.1.5.1", "130b63757276653235353139", 255, CKM_EC_MONTGOMERY_KEY_PAIR_GEN},
+       {"edwards25519","1.3.6.1.4.1159.15.1", "130c656477617264733235353139", 255, CKM_EC_EDWARDS_KEY_PAIR_GEN}, /* send by curve name */
+       {"curve25519", "1.3.6.1.4.3029.1.5.1", "130a63757276653235353139", 255, CKM_EC_MONTGOMERY_KEY_PAIR_GEN}, /* send by curve name */
+       {"Ed25519", "1.3.101.112", "06032b6570", 255, CKM_EC_EDWARDS_KEY_PAIR_GEN}, /* RFC 4810 send by OID */
+       {"X25519", "1.3.101.110", "06032b656e", 255, CKM_EC_MONTGOMERY_KEY_PAIR_GEN}, /* RFC 4810 send by OID */

Maybe these tables need an extra field to indicate "favored" way to list or store OID or printable string in ecparams.

While looking at adding Montgomery keys and all the eddsa code added, it became obvious, much of it could be eliminated because CKA_ECPARMS and CKA_EC_POINT are common across all EC, Edwards and Montgomery keys.
And I am using pkcs15.h.diff.txt
I can get into generating a X25519 (RFC 8410 terms) but fail because key already exists and card-openpgp.c does not support key delete.

Also have modified sc_pkcs15_fix_ec_parameters to map a ecparams "printablestring" to the OID version. But have not gotten to trying to map these back into OIDs used withing OpenPGP and written to Yubikey and GUNK applets.

Not sure how far to go with all of this, as OpenPGP cards have a lot of other info stored which would not be easy to pass into pkcs11.

from opensc.

Some additional comments about curves 25519, RFCs and PKCS11:

RFC7748 and RFC8032 are "Request for Proposal" from: "Internet Research Task Force (IRTF)"
and also say:

This document is not an Internet Standards Track specification; it is
published for informational purposes.

This document is a product of the Internet Research Task Force
(IRTF). The IRTF publishes the results of Internet-related research
and development activities. These results might not be suitable for
deployment. This RFC represents the consensus of the Crypto Forum
Research Group of the Internet Research Task Force (IRTF). Documents
approved for publication by the IRSG are not a candidate for any
level of Internet Standard; see Section 2 of RFC 7841.

Where as RFC8410 is from the "Internet Engineering Task Force (IETF)" and says:

This is an Internet Standards Track document.

This document is a product of the Internet Engineering Task Force
(IETF). It represents the consensus of the IETF community. It has
received public review and has been approved for publication by the
Internet Engineering Steering Group (IESG). Further information on
Internet Standards is available in Section 2 of RFC 7841.

RFC8410 title: "Algorithm Identifiers for Ed25519, Ed448, X25519, and X448 for Use in the Internet X.509 Public Key Infrastructure" It is the only one that defines OIDs and provides a recommendation for curve names to be used for these OIDs how to used then in ASN.1 for public, private and certificates. These OIDs are used by OpenSSL.

So basically RFC7748 or RFC8032 are obsolete and OpenSC will never add a driver that does not support RFC8410 for 25519 curves.

So having support for the pkcs11 3.0 "ecparams" "PrintableString" in pkcs11-tool.c and can help pass in unknow curve or experimental names to any pkcs11 module.

Currently the OpenSC pkcs11 module and libopensc appear to only support 25519 curves in card-openpgp.c. And it appears GnuPG, Yubico and GNUK defined their own OIDs and the tokens use the same algorithms as defined in RFC8410. So we should prefer to use the RFC8410 names and OIDs but for backwards compatibility support the old names and OIDs.

Modified Proposed Resolution

pkcs11-tool.c define the RFC8410 curves including the 448 curves and any names know to be in use with OpenPGP and map to the RFC8410 OIDs.

If newer card drivers are added and the algorithms match RFC8410 we would only accept the RFC8410 OIDs
The card-openpgp.c (or any newer driver) would then map RFC4810 OIDs to any OIDs which are written to the cards.

from opensc.

Additional info on 25519 curves:

• RFC8410 Aug 2018 principal author Simon Josefsson was the primary author of experimental RFC 8032 Jan 2017

• https://www.iana.org/assignments/enterprise-numbers/enterprise-numbers lists OID 1.3.6.1.4.1.3029
  and private entry 3029 is registered to: Digital Data Security, Peter Gutmann, pgut001&cs.auckland.ac.nz
  https://en.wikipedia.org/wiki/Peter_Gutmann_(computer_scientist)

• https://oidref.com/1.3.6.1.4.1.11591 says 11591 is registered to Free Software Foundation, Gnu's Not Unix (GNU) Project

• https://github.com/gpg/gnupg/blob/master/common/openpgp-oid.c#L328 shows the RFC 8410 OIDS may be used in v5 keys.

from opensc.

Hi @dengert,

Can you elaborate on your plan to submit some of these changes in master so we build on them? At least this one: dengert@1b0d7c9#diff-fcf954433b996121efbb3028d15e969537c35c7fd4bcd8b2a31bba29c4af18f7R160

I noticed 3 typos in the Ed488 line, the first being the 488 -> 448 (name + size), and the OID should end in 70 -> 71

I did try the Ed ones with my own SoftHSM and they work correctly (I don't have the latest master OID print fix though).

My plan would be to add ed25519 + ed448 object create support and then EDDSA support to pkcs11-tool.

# pkcs11-tool --module=/system/lib/dll/pkcs11-qkeystore.so --keypairgen --key-type EC:Ed448 --usage-sign --label ed448key --id 2
Using slot 0 with a present token (0x0)
Key pair generated:
Private Key Object; EC_EDWARDS
  label:      ed448key
  ID:         02
  Usage:      sign
  Access:     sensitive, always sensitive, never extractable, local
Public Key Object; EC_EDWARDS  EC_POINT 255 bits
  EC_POINT:   acd282b9b23dcf9264cbdb096e41a9df197606504d920a3f8fa0e46bc91abd2b05cf713778ade1ae42c1c3754d9ce0ba5c225e279daf655400
  EC_PARAMS:  06032b6571 (OID 1.3.101.113)
  label:      ed448key
  ID:         02
  Usage:      verify
  Access:     local

from opensc.

Thanks for the fix, I have pushed two commits to X25519-improvements-2 that can be squashed at a later time.

Most of the other changes are in pkcs15 and pkac11 routines in libopensc and the OpenSc module. These include treating EDDSA and XEDDSA ecparams the same, so most of the code is already there.

I have been testing with Yubikey and GUNK both in openpgp. They have a further problem that part of the OID is written to the cards, and these cards are using the old OIDs, so there needs to be a mapping from the new OIDS to the old OIDs used on the cards and may change with newer OpenPGP cards as well. . Found today that this could be in done in card-openpgp.c which would not effect your SoftHSM.

Only RFC 8410 defines official OIDs, so these should be the ones we use, but support the old names.

My intent was to get the OpenPGP code working, then submit as a PR.

The main difference between the X25519-improvements and X25519-improvements-2 was to cleanup and reorganize the code with more commits that make more sense.

I hope to get the changes in next week.

from opensc.

@Jakuje @dlegaultbbry I am looking at https://github.com/OpenSC/OpenSC/blob/master/src/tools/pkcs11-tool.c#L149-L150
and we already know the 1159 should be 11591. and one of the printable string has an error.

But it also looks like the two OIDs and the printable strings should be switched so the lines look like:

{"edwards25519", "1.3.6.1.4.3029.1.5.1", "130a63757276653235353139", 255, CKM_EC_EDWARDS_KEY_PAIR_GEN},
{"curve25519", "1.3.6.1.4.11591.15.1", "130c656477617264733235353139", 255, CKM_EC_MONTGOMERY_KEY_PAIR_GEN},

See comment on how this was assigned: https://oid-rep.orange-labs.fr/get/1.3.6.1.4.1.3029.1.5.1 and note it is for Ed25519
and https://lapo.it/asn1js/ says: "OBJECT IDENTIFIER 1.3.6.1.4.1.11591.15.1 curve25519 (GNU encryption algorithm)"

from opensc.

Further evidence shows the OpenSC OIDs were correct and the comment from https://lapo.it/asn1js/ "OBJECT IDENTIFIER 1.3.6.1.4.1.11591.15.1 curve25519 (GNU encryption algorithm)" is misleading.

gpg-card
  factory-reset
  generate --algo=rsa2048 OPENPGP.3
  generate --algo=ed25519 OPENPGP.1
  generate --algo=cv25519 OPENPGP.2
quit

From OpenPGP specs version 3.4.1 says in blob 6E "Application Related Data"

• blob C1 "Algorithm attributes signature 1 Byte Algorithm ID, according to RFC 4880/6637 further bytes depending on algorithm (e. g. length)"
  modulus and length exponent).
• blob C2 "Algorithm attributes decryption"
• blob C3 "Algorithm attributes authentication"

From an opensc-debug.log The blog 6E can seen in the Incoming APDU (328 bytes)

• C1 0B 16 2B 06 01 04 01 DA 47 0F 01 00 from 1.3.6.1.4.1.11591.15.1 generate --algo=ed25519 OPENPGP.1
• C2 0C 12 2B 06 01 04 01 97 55 01 05 01 00 from 1.3.6.1.4.1.3029.1.5.1 generate --algo=cv25519 OPENPGP.2
• C3 06 01 08 00 00 11 00 from RSA2048 generate --algo=rsa2048 OPENPGP.3
• DA 06 01 08 00 00 11 00 reserved for Yubio Algorithm attributes Attestation key (but should be in blob 7E)

Note the 3rd byte is the Algorithm: SC_OPENPGP_KEYALGO_EDDSA=16, SC_OPENPGP_KEYALGO_ECDH=12 and SC_OPENPGP_KEYALGO_RSA=01

RFC 4880 from 31 August 2020 also confirms the above.

from opensc.

I agree that there seems to be wide confusion and misinformation from those early defined OID values.

https://oidref.com/1.3.6.1.4.1.11591.15.1 = ed25519
https://oidref.com/1.3.6.1.4.1.3029.1.5.1 = curve25519 (spelled as curvey25519!)

I think what is already there is fine minus the OID typo to be fixed. Then adding the extra ones you've already planned would provide enough support.

from opensc.

@dlegaultbbry I have pushed additional commits to https://github.com/dengert/OpenSC/tree/X25519-improvements-2
Can you have a look at these.

from opensc.

I'm not familiar with PKCS#15, but why do you refer to the keys as EDDSA and XEDDSA instead of [Ed|X][25519|448] in dengert@e31e306

In dengert@62df4cb the comments at lines 450 and 458 need a refresh since it's now 25519 + 448 which are defined.

Rest looks ok to me.

from opensc.

I will look at these. The common code in OpenSC, including pkcs11-tool, is designed to work with the [Ed|X][25519|448] curves using the RFC 8410 names or OIDs and the older names and OIDs. PKCS11 3.0 treats the older OIDs differently and passed a printable string rather then the OIDs. The new OpenSC will convert to the newer names and accept the older names. The only card-openpgp.c. is the only the supports any of these curves and it only supports the 25519 size curves with older names and are used by the cards. OpenPGP as of 3.4.1 had not defined any of these [Ed|X][25519|448] but Yubico and GNUK added the 2 older OIDs. card-openpgp.c will accept some and convert to/from the curve OIDs needed by the card.

The existing OpenSC code used these from opensc.h and I have not changed them.

#define SC_ALGORITHM_EDDSA		4
#define SC_ALGORITHM_XEDDSA		5
#define SC_PKCS15_TYPE_PRKEY_EDDSA		0x105
#define SC_PKCS15_TYPE_PRKEY_XEDDSA		0x106
#define SC_PKCS15_TYPE_PUBKEY_EDDSA		0x205
#define SC_PKCS15_TYPE_PUBKEY_XEDDSA		0x206

The above names apply to both 25519 and 448 size keys. Internally OpenSC uses OIDs that imply the size. In pkcs15-pubkey.c the ec_curve_infos[] entries include printable names, OIDs, and sizes. sc_pkcs15_fix_ec_parameters is used to fill in missing values to any struct sc_ec_parameters known (to OpenSC) EC or RFC 8410 curves.

RFC 8410 8 Human-Readable Algorithm Names names might be a better choice when the curve is not known. But Using ECDH could also be used for ordinary EC curves when uses for DH.

I have Nitrokey Start (GUNK) , Yubikey 5 NFC cards and can use software software PGP as well as OpenSSL 3.x

The RFC 8410 curves define ASN.1 for pubkeys, and ordinary EC public use uncompressed 04||x||y but not RFC 8410 keys.

There still needs to be a lot of testing of these mods, as I was not expecting anyone else at this time to wanting these changes.

from opensc.

Some updates on better support for Montgomery curves, the "X..." ones, in https://datatracker.ietf.org/doc/html/rfc8410 which also relates to #3118 #3000 #3090

OpenSSL only supports RFC 8410, but with some tests I have been able to use OpenSSL with Yubikey and NitroStart tokens with OpenPGP 3.4 applets. But it does not always work. I think I know why, but it needs further testing.

https://datatracker.ietf.org/doc/html/rfc8410#page-4 says:
"Both [RFC7748] and [RFC8032] define the public key value as being a
byte string. It should be noted that the public key is computed
differently for each of these documents; thus, the same private key
will not produce the same public key."

https://www.rfc-editor.org/errata_search.php?rfc=7748 says:
"Notes:

The Montgomery form of the curve is generally used with a ladder, where the v coordinate is unused and unspecified. Thus I picked the smaller of the two possible values for v.

However, the curve is birationally equivalent to edwards25519, where both coordinates of the base point are used and are already in widespread use. Sadly, picking the smaller of the values for v ends up mapping to the negative of the base point on edwards25519.

This change replaces v with -v so that it matches up."

I have seen OpenSSL and OpenSC derive work, but also fail. I have attributed code changes to the failures but the failures may indeed be the choice of the: "smaller of the two possible values for v" some times working and other times not. The choice is done on the token and since it a choice between which "v" is smaller it could be a 50-50 chance of using the correct "v".

If I am correct, one way to verify that OpenSSL using RFC8410 vs the Tokens using RFC 7748 can work is to do something like:

openssl genpkey  -algorithm X25519 -outform der -out openssl.pkey.der

# with a NitroStart token: 
pkcs15-init --verify --auth-id 3 --delete-objects privkey,pubkey --id 2 --generate-key X25519
#read pubkey
pkcs15-tool --read-public-key 2 --output NitroStart.pubkey.02.pem
#convert to der
openssl pkey -pubin -pubout -outform der -out NitroStart.pubkey.02.der -in NitroStart.pubkey.02.pem

# OpenSSL derive a generic key using the peer's (token) public key:
openssl pkeyutl -derive -keyform der -inkey openssl.pkey.der -peerform der -peerkey NitroStart.pubkey.02.der > openssl-NitroStart.derived.bin

# Nitro token derive gneric key using peer's (openssl) public:
pkcs11-tool -l --slot 1 --derive -m ECDH1-COFACTOR-DERIVE --id -2 -i  openssl.pkey.der -O NitroStart-openssl.derived.bin 
#Then compare the derived keys:
diff openssl-NitroStart.derived.bin  NitroStart-openssl.derived.bin

I plain on trying the above in a script for a few times to see the choice of a key will work 50% of the time.

If that is the case, OpenSC code during key generation could try a few times to generate a key that would work with OpenSSL.

If that is not the case it might be that the older OpenPGP tokens using the experimental RFCs will never work with OpenSSL, and much of the effort in #3090 is not usable.

There are many variables in all of this

• No other OpenSC supported cards/tokens use RFC8401.
• The tokens I have are older and it is not clear if newer tokens are any better or have addressed the Errata.
• Some OpenSC is using OpenSSL to create ASN1 for these curves, so the OIDs end up looking like RFC 8410 curves.
• OpenPGP has hinted that version 3.5 would use RFC 8410 but last version of OpenPGP, 3.4.1, was in 2020, 4 years ago.
• I believe the OpenSC code to generate the XEDDSA curves has never worked before and may never be used.
• Loading keys generated by OpenSSL to a token that does not address the Errata may not work and may need even more code to see if they work.

from opensc.

Well it turns out my test script was using the OpenSSL private key rather then the public key as the peer pubkey.

Here is revised script that works:
test.chances.of.key.working.sh.txt

So things are looking much better.

from opensc.