Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Closed
pdb0102 opened this issue Aug 6, 2024 · 12 comments
Labels
bug Something isn't working

Comments

@pdb0102
Copy link

pdb0102 commented Aug 6, 2024

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:
Screenshot 2024-08-05 at 22 10 00 Screenshot 2024-08-05 at 22 10 11 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 Build a module instead of a shared library. #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
@pdb0102 pdb0102 added the bug Something isn't working label Aug 6, 2024
@pdb0102 pdb0102 changed the title The privateKey encoding for pure ml-dsa differs from the privateKey encoding for composite ml-dsa-xxxx The privateKey encoding for pure ml-dsa differs from the privateKey encoding for the ml-dsa part in composite ml-dsa-xxxx Aug 6, 2024
@baentsch
Copy link
Member

baentsch commented Aug 6, 2024

Tagging @feventura fyi

@pdb0102
Copy link
Author

pdb0102 commented Aug 6, 2024

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
Copy link
Member

baentsch commented Aug 6, 2024

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
Copy link
Contributor

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
Copy link
Author

pdb0102 commented Aug 7, 2024

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
Copy link
Member

baentsch commented Aug 7, 2024

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
Copy link
Author

pdb0102 commented Aug 7, 2024

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:
Screenshot 2024-08-07 at 00 21 41

Screenshot 2024-08-07 at 00 24 36

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:
Screenshot 2024-08-07 at 00 29 26

Hope this helps/is what you were looking for.

@baentsch
Copy link
Member

baentsch commented Aug 7, 2024

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
Copy link

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
Copy link
Author

pdb0102 commented Aug 14, 2024

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.

Screenshot 2024-08-13 at 19 07 30

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.

@baentsch
Copy link
Member

baentsch commented Jan 6, 2025

@feventura OK in your mind to close this? @pdb0102, did you get a chance to validate your problems are gone with #549 landed so we can close for good?

@pdb0102
Copy link
Author

pdb0102 commented Jan 6, 2025

I'm fine with this being closed, but I haven't had a chance to validate the changes. Once the IETF switched to storing seeds instead of generated keys and supporting pre-hash signing, and the upstream libs didn't support that yet, I figured I'd wait until things settle a bit and everyone in the chain has caught up. (I'm using oqsprovider to as interop test with my own code that creates and consumes PKIX data)
I'll be updating my code to latest IETF drafts and testing interop again in the next couple of weeks, if I run into an issue, I'll just open a new item.

@baentsch baentsch closed this as completed Jan 7, 2025
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working
Projects
None yet
Development

No branches or pull requests

4 participants