The privateKey encoding for pure ml-dsa differs from the privateKey encoding for the ml-dsa part in composite ml-dsa-xxxx

[pdb0102]

Describe the bug The privateKey encoding for pure ml-dsa differs from the privateKey encoding for composite ml-dsa-xxxx

To Reproduce Steps to reproduce the behavior:

1. Generate a ml-dsa key: openssl genpkey -algorithm mldsa87_p384 -out mldsa_p384.pem
2. Generate a ml-dsa-p384 key: openssl genpkey -algorithm mldsa87 -out mldsa.pem
3. Analyze the ASN.1 of both key files:
4. The privateKey Octet String node for pure ML is an Octet String that contains an Octet String, with the latter node having the key data
5. For the composite key, the first CompositeSignaturePrivateKey PrivateKey Octet String does not contain another Octet String, but the key data is directly stored as Data on the Octet String node.
6. draft-ietf-lamps-dilithium-certificates is vague (and mentions it's still under discussion) on how the private key is encoded ("A ML-DSA private key is encoded as MLDSAPrivateKey in the privateKey field as an OCTET STRING." - this could imply the key is the actual data of the Octet String node, or that the key is an Octet String under privateKey.

Expected behavior I would expect that, despite the ambiguity, the key is encoded the same way in both cases, either as a single octet string with raw key data, or a "constructed" octet string with another octet string and raw key data attached to that one. As it stands, it makes it hard to parse with the same method when parsing a composite key vs. pure key

Screenshots If applicable, add screenshots to help explain your problem.

Environment (please complete the following information):

• OS 5.4.0-187-generic #207-Ubuntu SMP Mon Jun 10 08:16:10 UTC 2024 x86_64 x86_64 x86_64 GNU/Linux
• OpenSSL version OpenSSL 3.3.1 4 Jun 2024 (Library: OpenSSL 3.3.1 4 Jun 2024)
• oqsprovider version [e.g. 0.4.0] oqsprovider name: OpenSSL OQS Provider version: 0.6.2-dev status: active

[baentsch]

Tagging @feventura fyi

[pdb0102]

Based on the sample private key I found here: https://github.com/lamps-wg/draft-composite-sigs/blob/main/examples/MLDSA44-ECDSA-P256-SHA256.pvt I'd assume that the composite code is emitting the intended ASN.1 and the pure ML-DSA privateKey double octet string is "wrong"?

[baentsch]

Thanks very much for the thorough analysis and clear problem description, @pdb0102 ! As you have this tooling at hand, may I ask (just for confirmation/my own peace of mind) whether you can confirm that hybrid keys (both for KEM and sig algs) are formatted as you expect them?

[feventura]

Thanks for the comment @pdb0102 , as you said the private key encode description on the MLDSA draft is vague. In the composite WG we already discussed about this topic and we think it should not contain the extra octet string layer.

[pdb0102]

Thanks very much for the thorough analysis and clear problem description, @pdb0102 ! As you have this tooling at hand, may I ask (just for confirmation/my own peace of mind) whether you can confirm that hybrid keys (both for KEM and sig algs) are formatted as you expect them?

@baentsch I verified the following algorithms all issue a single octet string with the key: mldsa44_pss2048, mldsa44_rsa2048, mldsa44_ed25519, mldsa44_p256, mldsa44_bp256, mldsa65_pss3072, mldsa65_rsa3072, mldsa65_p256, mldsa65_bp256, mldsa65_ed25519, mldsa87_p384, mldsa87_bp384, mldsa87_ed448

When trying to create a KEM key pair, OpenSSL gave me the finger:

openssl genpkey -algorithm p521_mlkem1024
Error writing key(s)
80D43839237F0000:error:1D800065:ENCODER routines:OSSL_ENCODER_to_bio:reason(101):crypto/encode_decode/encoder_lib.c:55:No encoders were found. For standard encoders you need at least one of the default or base providers available. Did you forget to load them?
80D43839237F0000:error:04800073:PEM routines:do_pk8pkey:error converting private key:crypto/pem/pem_pk8.c:133:

This could be due to my configuration/compilation options/openssl.cfg, or due to my own ignorance doing something wrong, though. I've been focused on DSA and haven't played with KEM before. I did verify that openssl list -kem-algorithms does report all the OQS provided KEM algorithms.

[baentsch]

Thanks for thoroughly checking all composite sigs. I'd be primarily interested in how the hybrid sigs (classic alg name before PQ alg name) do as per

There are two types of combinations: The Hybrids are listed above with a prefix denoting a classic algorithm, e.g., for elliptic curve: "p256_". The Composite are listed above with a suffix denoting a classic algorithm, e.g., for elliptic curve: "_p256".

If you'd also want to check KEM encoding, then this first needs to be enabled when building oqsprovider as we don't see persisting KEMs as a standard use case.

[pdb0102]

LOL. Lesen ist schwer :) Sorry about that. The hybrid sigs have the same issue as the pure sigs - Octet String containing Octet String that has the key:

Question - is the hybrid format or how to generate/sign/verify documented anywhere? composite has a draft describing it, but I haven't found anything on hybrid.

I did a quick rebuild with OQS_KEM_ENCODERS enabled, here's the ASN.1, showing that it's also Octet String containing an Octet String:

Hope this helps/is what you were looking for.

[baentsch]

Question - is the hybrid format or how to generate/sign/verify documented anywhere? composite has a draft describing it, but I haven't found anything on hybrid.

I don't think so: As far as I know it's simply a concatenation of classic and PQ data that has its origins in a proof-of-concept implementation in the original OQS-OpenSSL111 fork that got moved to the oqsprovider in a way ensuring interoperability with the original code -- but no one ever bothered to do a spec for this, right @dstebila @christianpaquin ?

[christianpaquin]

but no one ever bothered to do a spec for this, right @dstebila @christianpaquin ?

Not a formal spec, AFAIK. It used to be documented on the 1.0.2/1.1.1 project wiki, but the latest description can be found in this paper.

[pdb0102]

I've found a related problem, not sure if it should be a new issue or is related my original report.

An EdDsa25519 key's private key is represented as OctetString inside OctetString (see https://www.rfc-editor.org/rfc/rfc8410#page-7) :

> PrivateKey ::= OCTET STRING
>    For the keys defined in this document, the private key is always an
>    opaque byte sequence.  The ASN.1 type CurvePrivateKey is defined in
>    this document to hold the byte sequence.  Thus, when encoding a
>    OneAsymmetricKey object, the private key is wrapped in a
>    CurvePrivateKey object and wrapped by the OCTET STRING of the
>    "privateKey" field.
>  CurvePrivateKey ::= OCTET STRING

However, when the private key is part of a composite key, it is missing the CurvePrivateKey part, and the private key bytes are the data of the PrivateKey node. See the following screenshot that shows the end of the dump of a composite PQ key (visible is the end of the PQ key, and the full Ed key. The second half shows the dump of a regular Ed key PKCS#8 structure) Notice the missing second octet string in the first dump.

This seems to be a bug in the composite code, since the ML spec ("Each element is a OneAsymmetricKey` [RFC5958] object for a component private key.") says the OneAsymmetricKey syntax is to be used.