Implement KEM en-/decoders

[Muzosh]

In #123, PKCS#8 encoders for Dilithium, Falcon and Sphincs+ were added. However, the initial message also links draft for Kyber. Why was it not included in the PR (I can't see any mention of Kyber in Files changed)?

In https://github.com/open-quantum-safe/oqs-provider/issues/84#issuecomment-1296125057, @baentsch mentions that KEM algorithms do not need to have encoder/decoder functions. What if I want to use openssl to generate Kyber1024 keypair? I didn't find a way to do it, even in raw form.

[baentsch]

The answer to the question is "Yes": Indeed there are no en-/decoders for Kyber (or any other PQ-KEM). The rationale was that we (thought we)'d need to persist key material only for PQ-signature algorithms (for X.509 etc)... Which openssl commands would/should benefit from persisting PQ-KEM key material (beyond key gen)?

[Muzosh]

Thanks for the reply.

Which openssl commands would/should benefit from persisting PQ-KEM key material (beyond key gen)?

Well, beyond keygen, I would say encapsulation and decapsulation, but I see that these functions do not really exist in vanilla openssl. Only way to "encapsulate" something is to encrypt it with rsautl and RSA public key.

[Muzosh]

Btw is there a way to do Kyber keygen, where openssl at least outputs keys in their raw form (what libOQS actually returns when keygen function executes)? I know I can use any programming language and run libOQS from there, but I guess it would be nice to have in openssl as it is system-wide command-line application.

[baentsch]

encapsulation and decapsulation, but I see that these functions do not really exist in vanilla openssl

Correct -- kind of: They of course do exist but don't have an external interface as they're (AFAIK only) used for TLS connection establishment (internally).

Btw is there a way to do Kyber keygen, where openssl at least outputs keys in their raw form

No: openssl can do this only if oqsprovider has suitable encoders. Those could probably be added without a lot of problems -- but without a use case this seems like a waste of effort. But for example if someone were interested to implement https://www.ietf.org/archive/id/draft-housley-lamps-cms-kemri-00.html in openssl I'd gladly immediately add it. If you have other/further use cases, please let us know.

[baentsch]

@Muzosh Considering the above, do you still see a need for exporting KEM keys? Which standard(s) would you like to see this following then? If so, would you want to re-name this issue to "Implement KEM en-/decoders" (listing the standards this should implement)?

[Muzosh]

@baentsch you mentioned CMS with KEM as an example. I'm actually working on a PQ version of something very similar: CDOC. In the reference implementation of CDOC2 (new version that I'm trying to make quantum-safe), they are currently using ECDH and RSA for creating Content Encryption Key for recipients. Therefore KEM encoders might come in handy to serialize Kyber and other PQ-KEM public keys in different key distribution systems.

I have other ways on how to generate and store Kyber keys myself for now, so there is no rush.

[baentsch]

Thanks for letting us know.

KEM encoders might come in handy to serialize Kyber and other PQ-KEM public keys

Agreed.

[Muzosh]

I have other ways on how to generate and store Kyber keys myself for now, so there is no rush.

Meaning that I can wait for more use cases from others in order for it to become more relevant and worth the effort.

[ralienpp]

@baentsch, my colleagues and I are working on implementing the KEM features of RFC4210bis in OpenSSL. We've made good progress and successfully tested everything with RSA-KEM, and we'd like to do it with post-quantum algorithms too. Our bottleneck is the lack of KEM encoders and decoders in the provider.

We'd like to test it with Kyber (because we already have an implementation in Java), but eventually we'll want to test it with all post-quantum KEMs.

If you are looking for a good use case - I think this is it. The work done so far is in this branch of OpenSSL, we'll merge it into the upstream project as soon as everyone is happy with it (CC @rajeev-0).

[baentsch]

@ralienpp This indeed sounds like a good use case. Two immediate questions: 1) Can you provide a list of openssl commands you'd want to use/possibly already test this (RSA-KEM) with? 2) Is there a list of OIDs for (PQ)KEMs we could use (if I get you right you already have Kyber implemented in Java, so probably already use some... Can you point to the code or another location please)?

[ralienpp]

To the best of my knowledge, no OIDs are defined yet. In our experiments we use a dummy value of 1,2,3,4,1945,1111,9999 for Kyber512, with the intention to replace it as soon as the world moves on.

The logic can be triggered via openssl's cmp command. Here's a recipe you can follow to invoke the KEM-related logic from the aforementioned openssl branch. The test environment requires a CMP server and a CMP client, both can be simulated with OpenSSL. A scenario can look like this:

$cd openssl/test/recipes/80-test_cmp_http_data/Mock
# Run the server with a KEM key in one terminal 
$openssl cmp -config server_withkem.cnf -verbosity 8 -port 1700

# in another terminal, run the client
$openssl cmp -server 127.0.0.1:1700 -config test_withserverkem.cnf -section "Mock commands" -no_proxy 127.0.0.1 -cmd ir -cert signer.crt -key signer.key -srvcert kem.crt -certout out.test.pem 

The configuration files, certificates and keys used by the mock are a part of the repository, so the example should work out of the box.

To tinker with a post-quantum KEM, you'll need a KEM certificate. At the moment I have no elegant of producing one (normally I'd do it with OpenSSL :-). I'm attaching a sample I concocted manually, by taking a classic cert, replacing the subject public key with the raw bytes of Kyber512 as returned by liboqs/python and wrapped in a BitString, changing the algorithm OID; then signing it it with an RSA key and updating the signature.

kem-cert-experiment.zip

[Muzosh]

Is there a list of OIDs for (PQ)KEMs we could use (if I get you right you already have Kyber implemented in Java, so probably already use some... Can you point to the code or another location please)?

I have found that BouncyCastle expanded on OQS's OIDs in their BCObjectIdentifiers.java. They use same OIDs for digital signatures as OQS, but they also created new ones for KEMs.

Process for finding this was really hard and frustrating, because documentation of PQ capabilities in BC is almost non-existent. But following their variables in this class, you can construct an KEM OID that they use for various PQ KEM algorithms.

For example, Kyber512, these are the relevant lines that occur through out the java file: ASN1ObjectIdentifier bc = new ASN1ObjectIdentifier("1.3.6.1.4.1.22554"); ASN1ObjectIdentifier bc_kem = bc.branch("5"); ASN1ObjectIdentifier pqc_kem_kyber = bc_kem.branch("6"); ASN1ObjectIdentifier kyber512 = pqc_kem_kyber.branch("1");

Resulting OID for Kyber512 in BouncyCastle library: 1.3.6.1.4.1.22554.5.6.1

[Muzosh]

Unrelated note:

BC also already internally and also externally (meaning the developer needs to know about this) works with RFC drafts for ASN1 structures (most of them mentioned here), so I guess that's the reason they to came up with some OIDs. I would argue, that for now using ASN1 drafts really complicates things for developers who want to try out PQ algorithms. The "raw bytes rule" (input and output raw bytes, internal structure of parameters is up to the authors and their algorithm implementations) is far more simpler to use and I appreciate libOQS following that.

@ralienpp I guess your implementation in Java is already done, but if you would like to switch to using BouncyCastle with PQ algorithms, check out my presentation from slide 20. There are some code examples I used in my implementation (results of trial&error and desperate web searching). Another possible source is oqs-bouncycastle repo, where the author possibly tried to make OQS and BC solutions interoperable, but there is no documentation either and files seem rather chaotic.

[baentsch]

To tinker with a post-quantum KEM, you'll need a KEM certificate. At the moment I have no elegant of producing one (normally I'd do it with OpenSSL :-)

Could you please provide openssl commands you'd use to do this? The only suitable command(s) I can think of are genpkey and req -new. The former works fine for the private key (also storing it with a suitably added encoder works OK), but the latter (intended to create and store the public key) doesn't quite work -- arguably because it (correctly) cannot use the (KEM!) algorithm to sign (the CSR).

So, beyond the CMP example above (beginning only when key & cert exists), can you please provide openssl commands you can use right now to create a classic crypto KEM certificate (without --internally-- triggering the use of a signature function for that algorithm)? Those would be the first commands I'd like to check correct function of the new KEM en/decoders with. If such openssl commands don't (yet) exist, I guess this use-case/issue will need to move "upstream".

[rajeev-0]

You could create the certificate without generating the CSR by using openssl x509 with -force_pubkey. e.g.

openssl x509 -new -subj "/CN=KEM_CERT" -CA <root.crt> -CAkey <root.key> -out <kem.crt> -force_pubkey <kem_pub.pem> -extensions SAN -extfile <(printf "[SAN]\nbasicConstraints=critical,CA:false\nkeyUsage=critical,keyEncipherment")

[baentsch]

You could create the certificate without generating the CSR by using openssl x509 with -force_pubkey. e.g.

openssl x509 -new -subj "/CN=KEM_CERT" -CA <root.crt> -CAkey <root.key> -out <kem.crt> -force_pubkey <kem_pub.pem> -extensions SAN -extfile <(printf "[SAN]\nbasicConstraints=critical,CA:false\nkeyUsage=critical,keyEncipherment")

Well, this command uses a public key in a file (the "-force_pubkey" argument), but how is (a representation of) the public key stored in such file in the first place? According to https://github.com/openssl/openssl/discussions/22121#discussioncomment-7041853 no such command exists.

In other words, this issue cannot be resolved before https://github.com/openssl/openssl/issues/22132 is resolved.