Add design document for LMS. by slontis · Pull Request #22357 · openssl/openssl

slontis · 2023-10-12T04:59:32Z

Checklist

documentation is added or updated
tests are added or updated

slontis · 2023-10-12T05:02:39Z

Put a hold on this to discuss within the OTC..
In particular the new API and what is supported/not supported need to be discussed.

doc/designs/lms.md

t8m · 2023-10-13T13:45:02Z

doc/designs/lms.md

+__owur int EVP_DigestVerifyHBSInit(EVP_MD_CTX *ctx, EVP_PKEY_CTX **pctx,
+                                   const char *mdname,
+                                   OSSL_LIB_CTX *libctx,
+                                   const char *props, EVP_PKEY *pkey,
+                                   const OSSL_PARAM params[],
+                                   const unsigned char *sig,
+                                   size_t siglen);   
+/* Alias: since the function signature is identical */
+#define EVP_DigestVerifyHBSUpdate(a,b,c) EVP_DigestVerifyUpdate(a,b,c)
+
+__owur int EVP_DigestVerifyHBSFinal(EVP_MD_CTX *ctx);


I like this proposal more, except for:

It should not be called with HBS in the name as this is generic call for any possible future signature schemes and not tightly coupled to hash based signatures.

Why do we need both pkey as input parameter and ppctx as output one? Would it be better to have only one of them. I'm unsure which one of them though.

How does it play with this proposal https://github.com/openssl/openssl/blob/master/doc/designs/fetching-composite-algorithms.md

I was trying to make the Init and FInal calls match... using a matching tag.. I dont care what the tag is.

It is the same API as the existing one with sig added to the end.

We would either need yet another function, or pass the signature in as an OSSL_PARAM.. We dont actually use EVP_SIGNATURE_fetch() normally currently, so this seems a bit early to be adding the EVP_SIGNATURE one.

In PKCS #11 we made the new API C_VerifySignature. Maybe EVP_SignatureVerifyInit?

We also said if you support the C_VerifySignature interface you need to support it for all the signing algorithms (basically they can just store the signature at init time and use the stored signature in Final). The form that takes the signature at init time is more general (for the signature implementers... all signatures can support this form), but less general for the application (applications that don't have the signature until the end can't use signature first without buffering).

Anyway I'm not familiar enough with normal openssl spellings, so you need to moderate my comments with openssl usage

I was trying to make the Init and FInal calls match... using a matching tag.. I dont care what the tag is.

Definitely needs a different name.

We would either need yet another function, or pass the signature in as an OSSL_PARAM.. We dont actually use EVP_SIGNATURE_fetch() normally currently, so this seems a bit early to be adding the EVP_SIGNATURE one.

I don't see why?

do_sigver_init() does this internally. Not much else needs the EVP_SIGNATURE_fetch()

Actually, the 3rd option (passing EVP_SIGNATURE) will become available with the effort mentioned... and it's now underway, so it wouldn't be a bad idea to collaborate around designing the API. If we're reusing do_sigver_init() (not sure why we'd have to), it can be modified to fit.

Err how/where can I comment on the composite algorithm design document?

You can start a discussion or raise an issue... or wait for the draft PR I'm currently preparing.

Do note that I'm currently exploring EVP_PKEY_sign() / EVP_PKEY_verify() and associated functions rather than EVP_DigestSign and EVP_DigestVerify function groups.

When I think of it, I think I'll start with a design document, and we can discuss that.

t8m · 2023-10-13T13:49:37Z

doc/designs/lms.md

+In order to support the new API calls there should be 2 additional dispatch
+functions..
+
+OSSL_CORE_MAKE_FUNC(int, signature_digest_verify_pbs_init,
+                    (void *ctx, const char *mdname, void *provkey,
+                     const OSSL_PARAM params[],
+                     const unsigned char *sig, size_t siglen))
+OSSL_CORE_MAKE_FUNC(int, signature_digest_verify_pbs_final,
+                    (void *ctx))


Note: It should be possible to implement this init_with_signature function in terms of the existing APIs for those algorithms that do not have this new provided function. We would just cache the signature and use it in the final call. That's another reason why the EVP function should not be named with HBS in the name as this can be a fully generic call supported even with older signature algorithms on older providers.

I would think returning not supported would be sufficient..

It's likely the new API is the new normal. All they NIST signature algorithms are defined needing the signature first. It provides better signature guarantees. Protocol people don't like it because protocols often put the signature at the end. My guess is protocols with end up doing single shot where they use the full algorithm to sign their preselected hashes.

Implementing the backwards compat approach seems desirable to me.

simo5 · 2023-10-13T18:09:11Z

May I ask for a requirement that if any signing operation is implemented that it can be disabled at built time, leaving only verification operations available?

LMS is something that should never been implemented in a generic software system, NIST and NSA as well recommend that LMS and XMSS signatures are implemented only in Hardware, and the reason is that duplicating state is catastrophic, and in software duplicating state is as simple as restarting a machine after a crash where updates didn't get to disk, or copying around files.

We do not want to give our users a knife that has cyanide laced razor blades for a handle.

slontis · 2023-10-15T23:07:12Z

May I ask for a requirement that if any signing operation is implemented that it can be disabled at built time, leaving only verification operations available?

LMS is something that should never been implemented in a generic software system, NIST and NSA as well recommend that LMS and XMSS signatures are implemented only in Hardware, and the reason is that duplicating state is catastrophic, and in software duplicating state is as simple as restarting a machine after a crash where updates didn't get to disk, or copying around files.

We do not want to give our users a knife that has cyanide laced razor blades for a handle.

There is no intention of implementing the sign or private key generation

levitte · 2023-10-16T07:22:31Z

doc/designs/lms.md

+Add a Init_ex function and leave the Final the same.
+
+i.e.
+EVP_DigestVerifyInit_ex3(..., const unsigned char *sig, size_t siglen);


@t8m mentioned _with_signature for the libcrypto<->provider interface. Could that be a good idea here as well, instead of yet another ex?

rjrelyea · 2023-10-16T15:20:30Z

doc/designs/lms.md

+- Support one shot operations:
+  Using existing EVP_DigestVerifyInit_ex + EVP_DigestVerify calls
+- Dont support streaming via existing interface:
+  EVP_DigestVerifyInit_ex + EVP_DigestVerifyUpdate + EVP_DigestVerifyFinal.


These are good choices.

rjrelyea · 2023-10-16T15:23:44Z

doc/designs/lms.md

+  sufficient for this use case. A separate LMS signature dispatch table could be
+  added if this is ever required.
+- CMS and X509 support - this may be added at a later date.
+- Implementing Extended Merkle signature scheme (XMSS) is a separate effort.


Yup. HSS with a single tree is basically LMS. No one uses bare LMS, so that's fine. Definitely good not so support signatures and key gen. When implementing XMSS, it's possible to use some common code, but LMS and XMSS is just different enough that it's probably best to have separate implementations (said by someone who has made the combined implementation as a testbed).

rjrelyea · 2023-10-16T15:26:49Z

doc/designs/lms.md

+
+Pass the signature after the init via an OSSL_PARAM.
+
+


We talked about both of theses type of schemes in PKCS #11: 1) adding just a new init function that takes the signature and 2) adding the signature to the mechanism parameter (the equivalent of OSSL_PARAM). Both of these generated the question of what do you return on Final if the signature is included; a) failure if it's not null, b) failure if it's not null and doesn't match, or c) undefined if the application includes the signature. In the end having a complete new set of C_VerifySignatureXXXX functions got rid of all those issues since the Final versions won't have a signature. We made the C_VerifySignatureUpdate a separate function, but your proposal to make it a #define for the normal update is actually good (so applications that need to support both don't have to keep track of which to call the correct update function.

slontis · 2023-10-16T22:10:57Z

Thanks for your input @rjrelyea

mattcaswell · 2023-11-02T13:34:44Z

doc/designs/lms.md

+                                   const char *props, EVP_PKEY *pkey,
+                                   const OSSL_PARAM params[],
+                                   const unsigned char *sig,
+                                   size_t siglen);   


Using EVP_MD_CTX as the primary ctx for EVP_DigestVerify* was a design mistake IMO. The output param of an EVP_PKEY_CTX * is just horrible. We had to hack around this mistake when we moved all this stuff to providers.

This could be an opportunity to do this properly and just make this pass in an EVP_PKEY_CTX.

That idea also ties in on this design: https://github.com/openssl/openssl/blob/master/doc/designs/fetching-composite-algorithms.md

It's actually a good idea, and aligns better with how other (non-PKEY) operations work.

mattcaswell · 2023-11-02T13:39:26Z

doc/designs/lms.md

+__owur int EVP_DigestVerifyHBSInit(EVP_MD_CTX *ctx, EVP_PKEY_CTX **pctx,
+                                   const char *mdname,
+                                   OSSL_LIB_CTX *libctx,
+                                   const char *props, EVP_PKEY *pkey,
+                                   const OSSL_PARAM params[],
+                                   const unsigned char *sig,
+                                   size_t siglen);   
+/* Alias: since the function signature is identical */
+#define EVP_DigestVerifyHBSUpdate(a,b,c) EVP_DigestVerifyUpdate(a,b,c)
+
+__owur int EVP_DigestVerifyHBSFinal(EVP_MD_CTX *ctx);


I was trying to make the Init and FInal calls match... using a matching tag.. I dont care what the tag is.

Definitely needs a different name.

We would either need yet another function, or pass the signature in as an OSSL_PARAM.. We dont actually use EVP_SIGNATURE_fetch() normally currently, so this seems a bit early to be adding the EVP_SIGNATURE one.

I don't see why?

mattcaswell · 2023-11-02T13:41:03Z

doc/designs/lms.md

+
+For the EVP_DigestVerifyFinal pass a NULL signature.
+The signature length must be zero in this case or an error will occur.
+If a signature is passed should it just ignore the value?


I prefer this proposal more that proposal 1. (Unless we go with my suggestion to use EVP_PKEY_CTX...in which case it really does need a new name).

I prefer this proposal more.

mattcaswell · 2023-11-02T13:43:01Z

doc/designs/lms.md

+                                   const unsigned char *sig,
+                                   size_t siglen);   
+/* Alias: since the function signature is identical */
+#define EVP_DigestVerifyHBSUpdate(a,b,c) EVP_DigestVerifyUpdate(a,b,c)


I know we've done this before - but I think this is very confusing and causes potential problems in the future if we ever want them to do different things.

mattcaswell · 2023-11-02T13:51:38Z

doc/designs/lms.md

+In order to support the new API calls there should be 2 additional dispatch
+functions..
+
+OSSL_CORE_MAKE_FUNC(int, signature_digest_verify_pbs_init,
+                    (void *ctx, const char *mdname, void *provkey,
+                     const OSSL_PARAM params[],
+                     const unsigned char *sig, size_t siglen))
+OSSL_CORE_MAKE_FUNC(int, signature_digest_verify_pbs_final,
+                    (void *ctx))


Implementing the backwards compat approach seems desirable to me.

mattcaswell · 2023-11-02T13:55:48Z

doc/designs/lms.md

+
+As well as using the test vectors supplied in [1] and [6], additional interop tests
+should be performed by generating data using other toolkits
+(such as Ciso or Bouncy Castle).


Do these implement the sign side?

Since the RFC originated from Cisco they needed to write a reference implementation. BC has the sign side. The Java SDK only implements the verify.. In my opinion it is asking for trouble implementing stateful signing (which is why it is supposed to be done in hardware only)

There is a reference implementation available: https://github.com/cisco/hash-sigs

tomato42 · 2023-11-21T18:35:26Z

I would go even further that what Simo said.

I consider not only presence of signature creation a problem, but signature verification too.

Safe use of any stateful hash based signature formats absolutely and unequivocally depends on the signature operation being performed in hardware. Doing it in a way that allows for disaster recovery, over 10, or 20+ years of use, is orders of magnitude harder still. That means that there will be very few originators of such signatures. Which means they will be used in very few places.

In case we have widely deployed implementations that can verify such signatures, there definitely will be people that don't know better and actually implement and use signature creation in software. So, just presence of signature verification is an incentive to do the wrong thing.

As such, I don't think openssl should ship with any code that can do LMS verification. It can have support for providers that support it (to support the hardware modules), but I think including verification code is a mistake. If there are specific users asking for it, it should be a separate provider module, not part of OpenSSL proper. Users should not be able to expect that LMS is supported out of the box.

See also: Nuclear Non-proliferation Treaty

slontis · 2023-11-21T18:45:42Z

I would go even further that what Simo said.

I consider not only presence of signature creation a problem, but signature verification too.

Safe use of any stateful hash based signature formats absolutely and unequivocally depends on the signature operation being performed in hardware. Doing it in a way that allows for disaster recovery, over 10, or 20+ years of use, is orders of magnitude harder still. That means that there will be very few originators of such signatures. Which means they will be used in very few places.

In case we have widely deployed implementations that can verify such signatures, there definitely will be people that don't know better and actually implement and use signature creation in software. So, just presence of signature verification is an incentive to do the wrong thing.

There is no state associated with the signature verification, so I dont agree. There are many things in crypto that you can do wrong if you dont know what you are doing.
@t-j-h Would you care to respond to why we should do HSS signature and key generation in OpenSSL.

tomato42 · 2023-11-21T19:20:09Z

My point is that there is a difference between "it's hard to do it correctly" and "there's literally at most double digit number of corporations in the world that will be able to do a production deployment correctly".

openssl-machine · 2024-07-09T00:08:22Z

This PR is in a state where it requires action by @openssl/otc but the last update was 61 days ago

openssl-machine · 2024-08-08T08:01:38Z

This PR is in a state where it requires action by @openssl/otc but the last update was 91 days ago

openssl-machine · 2024-09-08T00:08:29Z

This PR is in a state where it requires action by @openssl/otc but the last update was 122 days ago

levitte · 2024-09-09T09:53:05Z

Considering the recent additions to the EVP_PKEY_ sign and verify functionality, maybe this needs an update? Is the new interface ready enough so this can simply be a matter of writing provider code?

slontis · 2024-09-09T22:24:48Z

I am in the process of writing the code..

openssl-machine · 2024-10-10T00:08:47Z

This PR is in a state where it requires action by @openssl/committers but the last update was 30 days ago

hlandau · 2024-10-10T07:19:17Z

doc/designs/lms.md

+Hash Function Selection
+-----------------------
+
+- During the DigestVerifyInit()the passed in digest name is not required


hlandau · 2024-10-10T07:19:54Z

doc/designs/lms.md

+
+- Support one shot operations:
+  Using existing EVP_DigestVerifyInit_ex + EVP_DigestVerify calls
+- Dont support streaming via existing interface:


hlandau · 2024-10-10T07:20:23Z

doc/designs/lms.md

+
+For the EVP_DigestVerifyFinal pass a NULL signature.
+The signature length must be zero in this case or an error will occur.
+If a signature is passed should it just ignore the value?


I prefer this proposal more.

hlandau · 2024-10-10T07:29:28Z

doc/designs/lms.md

+
+As well as using the test vectors supplied in [1] and [6], additional interop tests
+should be performed by generating data using other toolkits
+(such as Ciso or Bouncy Castle).


s/Ciso/Cisco/

openssl-machine · 2024-11-10T00:08:35Z

This PR is in a state where it requires action by @openssl/committers but the last update was 30 days ago

openssl-machine · 2024-12-11T00:08:42Z

This PR is in a state where it requires action by @openssl/committers but the last update was 61 days ago

openssl-machine · 2025-01-11T00:08:57Z

This PR is in a state where it requires action by @openssl/committers but the last update was 92 days ago

openssl-machine · 2025-02-11T00:08:39Z

This PR is in a state where it requires action by @openssl/committers but the last update was 123 days ago

openssl-machine · 2025-03-14T00:08:50Z

This PR is in a state where it requires action by @openssl/committers but the last update was 154 days ago

openssl-machine · 2025-04-14T00:09:01Z

This PR is in a state where it requires action by @openssl/committers but the last update was 185 days ago

openssl-machine · 2025-05-15T00:09:15Z

This PR is in a state where it requires action by @openssl/committers but the last update was 216 days ago

openssl-machine · 2025-06-15T00:09:25Z

This PR is in a state where it requires action by @openssl/committers but the last update was 247 days ago

openssl-machine · 2025-07-16T00:09:21Z

This PR is in a state where it requires action by @openssl/committers but the last update was 278 days ago

openssl-machine · 2025-08-16T00:09:44Z

This PR is in a state where it requires action by @openssl/committers but the last update was 309 days ago

openssl-machine · 2025-09-16T00:09:26Z

This PR is in a state where it requires action by @openssl/committers but the last update was 340 days ago

openssl-machine · 2025-10-17T00:10:08Z

This PR is in a state where it requires action by @openssl/committers but the last update was 371 days ago

openssl-machine · 2025-11-17T00:10:17Z

This PR is in a state where it requires action by @openssl/committers but the last update was 402 days ago

openssl-machine · 2025-12-18T00:10:24Z

This PR is in a state where it requires action by @openssl/committers but the last update was 433 days ago

t8m · 2025-12-31T13:10:25Z

@slontis Could you please sync this with the actual implementation?

slontis · 2026-01-21T03:36:40Z

Closing this as it is not likely to be reviewed if I update it.

Add design document for LMS.

e971d5a

slontis added branch: master Applies to master branch approval: review pending This pull request needs review by a committer approval: otc review pending hold: discussion The community needs to establish a consensus how to move forward with the issue or PR labels Oct 12, 2023

fixup! Add design document for LMS.

919edea

levitte reviewed Oct 12, 2023

View reviewed changes

doc/designs/lms.md Show resolved Hide resolved

levitte reviewed Oct 12, 2023

View reviewed changes

doc/designs/lms.md Show resolved Hide resolved

tom-cosgrove-arm reviewed Oct 12, 2023

View reviewed changes

doc/designs/lms.md Outdated Show resolved Hide resolved

fixup! Add design document for LMS.

4f9901c

t8m added the triaged: design The issue/pr deals with a design document label Oct 13, 2023

t8m reviewed Oct 13, 2023

View reviewed changes

levitte reviewed Oct 16, 2023

View reviewed changes

rjrelyea reviewed Oct 16, 2023

View reviewed changes

t8m added tests: exempted The PR is exempt from requirements for testing and removed hold: discussion The community needs to establish a consensus how to move forward with the issue or PR labels Oct 17, 2023

t8m mentioned this pull request Oct 31, 2023

Init - Update - Final EdDSA signature verification #22567

Open

mattcaswell requested changes Nov 2, 2023

View reviewed changes

This was referenced Nov 7, 2023

Implement extended support to use composite algorithms directly in EVP_PKEY_{sign,verify} openssl/project#228

Closed

[design] Functions for explicitly fetched signature algorithms #22672

Closed

t8m removed the approval: otc review pending label Sep 9, 2024

slontis mentioned this pull request Sep 26, 2024

Request for Feature branch for HSS/LMS openssl/project#846

Closed

paulidale requested a review from a team October 10, 2024 03:00

paulidale approved these changes Oct 10, 2024

View reviewed changes

hlandau suggested changes Oct 10, 2024

View reviewed changes

t8m added waiting-for: contributor response This pull request is awaiting a response by the contributor and removed approval: review pending This pull request needs review by a committer labels Dec 31, 2025

slontis closed this Jan 21, 2026

Uh oh!

Conversation

slontis commented Oct 12, 2023

Checklist

Uh oh!

slontis commented Oct 12, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

slontis Nov 9, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

simo5 commented Oct 13, 2023

Uh oh!

slontis commented Oct 15, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

slontis commented Oct 16, 2023

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

tomato42 commented Nov 21, 2023

Uh oh!

slontis commented Oct 12, 2023 •

edited

Loading

slontis Nov 9, 2023 •

edited

Loading

slontis commented Oct 15, 2023 •

edited

Loading