Supporting EdDSA - The Details

About EdDSA

EdDSA is a fairly new signature algorithm, at least if we compare to the classic algorithms we use, where RSA was introduced in 1977 and ECDSA entering wide use in the early 2000's. In contrast EdDSA was published in 2011. EdDSA is meant to be simple, elegant, and well defined, so it is hard to make security catastrophic mistakes upon use, something that is rather easy to do with the classic algorithms. EdDSA, with regards to digital signatures, consist of two distinct variants, Ed25519 and Ed448, with different key lengths. The usage of EdDSA, as relevant for us, has been standardized in RFC8032, RFC8410 and RFC8419.

EdDSA in EJBCA

Albeit not very widely used, we have been asked on occasions for support of EdDSA in EJBCA, commonly in IoT related use cases. Due to these requests we added software support for Ed25519 and Ed448 in EJBCA 7.4.0 in June 2020. As EJBCA is used in high security PKIs, Hardware Security Modules are typically used, and we have recently tested support for EdDSA in HSMs. 

This post describes the details of what is involved in supporting this new signature algorithm, in software and in hardware. The final result can be seen in the EJBCA documentation.

A note of caution: implementing cryptography is not for everyone, and we could not have done it without the help of our friends from Bouncy Castle, who helped us with the hard core details, and even gave us an introductory training session on the specific topic of EdDSA. Bouncy Castle support contracts are available though Crypto Workshop.

Software Support

The first step when supporting a new algorithm for PKI usage, in Java, is to get all the ASN.1 and Java crypto stuff in place. Without that, there is no going forward. This includes at least, but not exclusively the following parts:

• ASN.1 Object identifiers
• Public and Private key classes
• Reading and writing (encoding and decoding) said public and private keys
• SubjectPublicKeyInfo ASN.1 structures for properly encoding public keys in certificates and CSRs
• Signatures themselves, on at least certificates, CRLs, CSRs, OCSP responses and CMS messages
• Conversion between names (for example Ed25519) and OIDs (1.3.101.112)

A specific trick worth mentioning, that we stumbled upon, is that there are two versions of encoding/decoding format of EdDSA. A version 1 and a version 2, where different software implementation, for example OpenSSL, produces the v1 format, while others produce the (newer) v2 format. Needless to say, we needed to handle both.

For EJBCA, we are lucky to use the Bouncy Castle crypto APIs, which are commonly among the first to implement anything new. As Bouncy Castle had support for all the relevant RFCs EJBCA could start adding the application layer support right away. There were a few additions needed on the way, mostly related to various corner cases or handling encoding/decoding of keys and PKCS#12 files from different sources, that needed minor additional features in Bouncy Castle. As always, they were fast to add the needed tricks in the crypto API.

Usability

Apart from the core crypto pieces, EJBCA also implement a bunch of usability features making it easy(!) for users to use PKI with various algorithms. With EdDSA being so simple, both the keys and signature algorithm is referred to Ed25519 and Ed448, it still needed some extra code to fit into the overall structure. For the classic algorithms there are countless combinations, for example an RSA 2048 bit key can be used with all RSA signature algorithms:

• SHA256WithRSA
• SHA384WithRSA
• SHA512WithRSA
• SHA256WithRSAandMGF1
• ...

Just to name a few. And the same goes for ECDSA, but with even more combinations are there are numerous different EC curves to choose from. All in all there are hundreds of combinations that can be used in EJBCA, and we try to make it easier by or example limiting the available signature algorithms based on the selected key type. So albeit EdDSA having limited number of combinations, some if's and but's in the code is still needed for it to fit in the overall usability framework.

Another trick we play is that a suitable key encryption algorithm is selected, for Key Recovery, based on the signature algorithm used, typically this means selecting an RSA based algorithm, and we have a method for this, where EdDSA had to be added as well.

Adding HSM Support

We, and most of the world, use HSMs through the standard PKCS#11 API. In the until recently latest version of PKCS#11, version 2.40, there was no standardized support for EdDSA. As there was still a requirement from some users for EdDSA, the inevitable result was that some HSM vendors supported EdDSA using what is called Vendor Defined Mechanisms. This is of course a nightmare for product implementors, as specific support has be be built for HSMs from different vendors. PKCS#11 version 3 however, which was released only this year, introduced standardized support for EdDSA.

Now HSM vendors have moved to use the standardized way of supporting EdDSA, which means it's a good time for us to look at supporting HSMs for this algorithm.

Having recently introduced the P11-NG Crypto Token in EJBCA Enterprise, we have low level control of PKCS#11, as used by EJBCA, which was needed in order to support this new feature, P11v3 feature in a P11v2.40 library. In addition, SoftHSMv2 has support for EdDSA, making it easy to develop without access to a real hardware security module.

The last trickery showed up when generating keys and reading them from the HSM. According to the PKCS#11v3 specification the EdDSA public key is generated using the mechanism CKM_EC_EDWARDS_KEY_PAIR_GEN with the same parameters as a normal ECDSA key, which means that a CKA_EC_PARAMS is used in the public key template, with the OID of the curve as parameter, in this case the OID of Ed25519. The public key is then stored as a CKA_EC_POINT. The CKA_EC_POINT is normally used to store EC curve points, but in the case of Ed the point it's not quite the same. This required an if statement and some special handling in the case of EdDSA keys.

In the case of ECDSA:

final java.security.spec.EllipticCurve ellipticCurve = EC5Util.convertCurve(bcspec.getCurve(), bcspec.getSeed());
final java.security.spec.ECPoint ecPoint = ECPointUtil.decodePoint(ellipticCurve,
        ASN1OctetString.getInstance(ckaQ.getValue()).getOctets());
final org.bouncycastle.math.ec.ECPoint ecp = EC5Util.convertPoint(bcspec.getCurve(), ecPoint);
final ECPublicKeySpec pubKeySpec = new ECPublicKeySpec(ecp, bcspec);
final KeyFactory keyfact = KeyFactory.getInstance("ECDSA", BouncyCastleProvider.PROVIDER_NAME);
return keyfact.generatePublic(pubKeySpec);

 and in the case of EdDSA:

X509EncodedKeySpec edSpec = createEdDSAPublicKeySpec(ckaQ.getValue());
final KeyFactory keyfact = KeyFactory.getInstance(oid.getId(), BouncyCastleProvider.PROVIDER_NAME);
return keyfact.generatePublic(edSpec);

As usual, a big thanks to the team at Bouncy Castle for help.

Summary

With all the above details in place, we now have the functionality we need in EJBCA:

• Generating Ed25519 and Ed448 key pairs (in software and in HSMs)
• Retrieve public keys
• Test a key pair
• Sign and verify
• Certificate
• CRL
• OCSP response
• CSRs (PKCS#10 and CRMF)
  
• CMS message
• Read and write
• PEM files
• PKCS#12 files
• Presenting EdDSA in Web UIs in a user friendly way 

Cheers,

Tomas Gustavsson
CTO 

EJBCA Enterprise PKI and EJBCA Appliance developed by PrimeKey.

PrimeKey® and EJBCA® are trademarks of PrimeKey Solutions AB, in the EU, the United States, Japan and certain other countries.