Dan's implementation thoughts

danvangeest commented Jun 19, 2019

I implemented the current draft in a fork of mbed TLS (written in C). I also asked a colleague to implement a Java JCA provider to do composite certificate verification.

Things went mostly well, there were just two difficult points which I summarize below. The main take-away I think is that it's not just a "drop a new algorithm into the crypto library and associate identifiers with the algorithm" type of change.

Historically, most signature algorithms sign a message digest rather than the whole digest itself. The code we used is written to assume this. To get around this, one has to either:
    [Java] Buffer the data passed in through multiple update() calls for use in the final sign() call.
    [mbedTLS] Indicate that the Composite algorithm is special and pass the full message to the crypto API rather than pass a hash.
    This full message signing (or "Intrinsic" from the TLS 1.3 parlance) is becoming more common (EdDSA, HSS/LMS in CMS, possibly NIST PQ algorithms), so we should expect to see libraries have better support for this in the future.

When signing and verifying there is no good mechanism to associate the CompositeParams parameters from the signature algorithm identifier with the key. AFAIK there are only two other algorithms which have parameters set in the signature algorithm, RSA-PSS and ecdsa-with-Specified (which was a SEC1 thing, but not adopted by IETF). Where supported by mbedTLS and BouncyCastle, these algorithms are hard-coded as exceptions in the signature creation/verification code rather than processed through the generic APIs.

What follows is the elaborate explanation nobody wanted

mbedTLS has a generic public key API which is used by the X.509 creation code. I ended up extending this API to allow me to associate the signature parameters with a key prior to signing or verifying. An alternative to this would have been to modify the generic sign/verify APIs to take a parameters object which the algorithm implementation would understand. This is probably a better long-term solution but would have required significantly more changes.

JCA is in the same situation. You can register a new JCA Provider which implements a generic sign/verify API. There's a way to associate parameters, but BouncyCastle doesn't do this generically for all algorithm. There are two ways to address this:
    Skip BouncyCastle's Certificate.verify() call and verify the signature on the certificate manually after associating the parameters with the Signature object. This means that your new Provider can't just plug in and start handling OIDs automatically, the code which calls sign/verify needs to be updated (or BouncyCastle's certificate factory needs to be update to understand composite certs).
    Create a new X.509 certificate factory provider. This provider wraps the standard provider and returns composite-aware certificate objects which wrap the standard certificate objects. The composite-aware certificate can see when it's about to be verified with a composite private key, and do the parameter association before verifying the certificate. The advantage of this solution is that a relying party can verify a composite certificate without being aware of any composite details. The disadvantage is more effort on the provider implementation, and potential conflicts if multiple x.509 certificate factories are registered (issues with our factory creating certs which override the standard Java cert instead of a different registered factory's certs). A further disadvantage is that this solution only applies to verify composite certificates. It does not apply to generating composite certificates (one would still need to communicate the list of signature algorithms for signing the cert), or to creating/verifying composite signatures in protocols. The protocol implementation will need to associate the signature algorithms with the keys when signing and verifying.

opencrypto commented Jun 19, 2019 •

Just two comments on what you are writing here. The first one is about the signing algorithm. In PKIX, especially in certificates, the signing algorithm comprises both the scheme and the hashing algorithms - that is, it is wrong to separate the process of calculating the hash and then signing the data: the data should be passed to the signing engine, not the hash.

The second comment I have is about the issues you faced when implementing the idea - one of the things I have not seen you mention is the definition of the Composite-Public-Key and Composite-Private-Key. Are you implementing those concepts? If not, then I can see where you might have problems developing the provider - you need to have the full set of objects so you can use the normal / generic .verify() and .sign() functions).

In OpenSSL, I faced similar issues (and also because even Victor forgot how to use the functionalities to dynamically add a provider) - it is easier if you add a separate provider in the OpenSSL source code directly (which would be the next step to do, I think, in order to be able to leverage the composite-crypto in all applications without the need for special operations).

Thanks for sharing this considerations - they are really helpful and provide good insights into what to focus/look for when integrating with different crypto libraries (and could take us to provide some - maybe separate - implementation guidelines... ?)

I hope this quick comments make sense...

danvangeest commented Jun 19, 2019

Yes, I implemented Composite Public Key and Composite Private Key. The problem is associating each of the component private/public keys with the appropriate digest algorithm before signing/verifying. For normal signature algorithms this is already automatically supported because there's an OID defined per digest+signature algorithm combination (e.g. ecdsa-with-SHA256). For composite signature algorithms this is easily done if the CompositeParameters has already been associated with the composite key. But not many algorithms have needed so associate a parameters object with a key object in the past so the existing APIs don't usually allow for it and exceptions are hard coded instead. I think JCA does allow it, however most JCA users don't follow the correct steps to do so, since those steps weren't necessary for ECDSA/RSA.