Re: [lamps] draft-gazdag-x509-hash-sigs-00

["Kousidis, Stavros" <[e-mail]>]

Hi Antonio,

it has been a while but let me add my thoughts to your proposal.

The problems are:


1)      You don't solve the distribution/backup problem while you are signing with a specific tree during your first X years.

2)      Your signature sizes grow over time with every subtree you add because of the additional OTS in the newly established multi-tree.

3)      You change the public key once you add a subtree.

Let me elaborate on point 3) as this is something you certainly don't want:

HSS encodes the number of levels in the public key (see §6.1 in RFC8554) so that you know how to verify a signature when you receive it (see §6.3 in RFC8554). Likewise XMSS/XMSS^MT encodes an identifier specifying the (multi-)tree (see §4.1.7 and §4.2.2 in RFC8391). This means that your trust anchor changes (e.g. X.509 certificate) and you have to distribute it again.

Best
Stavros

Von: Vaira, Antonio <[e-mail]>
Gesendet: Mittwoch, 1. Februar 2023 13:31
An: Kousidis, Stavros <[e-mail]>
Cc: LAMPS <[e-mail]>; [e-mail]; [e-mail]; Kampanakis, Panos <[e-mail]>
Betreff: RE: [lamps] draft-gazdag-x509-hash-sigs-00

Hi Stavros,

My interpretation is that the SEED should be indeed considered as "private keying material" therefore I am also concerned with the point b) you raised.

I would also add, even if we theoretically do not concern ourselves with the operational/cost overheads of having a lot of HSMs initialized and put in storage, can we realistically be sure that by the time we will need these HSMs they will all boot? The timeline I have in mind is 20+ years (realistic RootCA lifetime) and I am not sure if an HSM, even if stored in "perfect conditions", will still boot after 20 years.

For the reason above, I was thinking about an alternative approach that can be summarized with the following steps:
1. the tree #1 is generated, with a height that is proportional to the required number of signatures and its leaves can be used to perform digital signatures,
2. after X years, for example 5 years, the last leaf of tree #1 is used to sign a new subtree, tree #2, that corresponds to OTS private keys that are initialized in a new HSM,
3. repeat step 2 after every X years, initializing each time new OTS private keys in a new HSM.

After 3 iterations the HBS state would look like the following:

           root
          -
         / \
        /   \
       /     \
      /       \
     /         \
    /           \
   /             \
  -----------------
  |    |          |
  |    |          |
sig1 sig2  ...   -
                 / \
                /   \
               /     \
              /       \
             /         \
            /           \
           /             \
          -----------------
          |    |          |
          |    |          |
         sig1 sig2  ...   -
                         / \
                        /   \
                       /     \
                      /       \
                     /         \
                    /           \
                   /             \
                  -----------------
                  |    |    |    |
                  |    |   |    |
                 sig1 sig2  ...  ...

The first 2 trees can be considered as no longer usable, even if there are still unused leaves, because their corresponding OTS private keys are in HSMs which may no longer be available. The OTS keys associated to the tree corresponds are generated and stored on a "fresh" HSM.

Without considering redundancy requirements (also not considered in the steps above for sake of simplicity), with this approach it would be possible to use one HSM at the time and replace it after X years with a new one (avoiding to initialize HSMs and securely store them) and it would not be needed to redistribute the root to all the relying parties. But the signature would increase of a fixed number of bytes (i.e., the signature performed over the root of the new subtree using the last OTS private key of the parent tree) every X years.

What do you think?

Thanks
Antonio

-----Original Message-----
From: Kousidis, Stavros <[e-mail]<mailto:[e-mail]>>
Sent: Wednesday, 1 February 2023 08:54
To: Vaira, Antonio (T CST SEA-DE) <[e-mail]<mailto:[e-mail]>>
Cc: LAMPS <[e-mail]<mailto:[e-mail]>>; [e-mail]<mailto:[e-mail]>; [e-mail]<mailto:[e-mail]>; Kampanakis, Panos <[e-mail]<mailto:[e-mail]>>
Subject: AW: [lamps] draft-gazdag-x509-hash-sigs-00

Dear Antonio,

I feel that we will have to take up a discussion on practical issues that CAs face when using stateful HBS in our draft. This already came up in comments that Panos sent, see here: https://eur01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fmailarchive.ietf.org%2Farch%2Fmsg%2Fspasm%2FhUe6bBqGoJhyu5vObbYJMbtCEDw%2F&data=05%7C01%7Cantonio.vaira%40siemens.com%7Cd988d9a6eb5d4ac79f4808db042989a7%7C38ae3bcd95794fd4addab42e1495d55a%7C1%7C0%7C638108348674728031%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&sdata=%2BjO3%2Bi0NfdqHmSaEJ9BCbpE3Hv8xwsaoVfnkuWfwfVg%3D&reserved=0

The §7 of NIST SP 800-208 elaborates on distributed multi-trees instantiated via cryptographic modules. It is stated there that

"due to the risks associated with copying OTS keys, this recommendation prohibits exporting private keying material (Section 8)."

I do ask myself if the "private keying material" described here includes the secret value "SEED" that can be used to pseudorandomly generate an LMS or XMSS private key (see Appendix A in RFC8554 or analoguously §3.1.7 in RFC8391).

On the one hand I would say yes, but:

a) As I read NIST SP 800-208 the requirements described in §7 and §8 are primarily concerned with the OTS private keys (that is when the counter comes into play along with the SEED).
b) I cannot imagine how one can practically address the "do not export private keying material" requirement if the SEED is included here. This would imply your interpretation that at key generation time one would have to put a lot of sleeping HSMs on the shelf. As a concrete example, imagine aiming for 2^20 signatures and instantiating HSS with two levels, height 10 on the top level and height 20 on the bottom level. The top level covering the distribution/redundancy aspect. That would mean that your shelf is packed with 2^10 HSMs holding the bottom level LMS instances. You could aim for height 5 on the top level tree, but still 2^5 HSMs are not practical in my personal opinion.

@All: May I ask, how the above mentioned requirement about exporting private keying material has to be interpreted?

However, I (personally) still think that stateful HBS should be available as an option in our ecosystems.

Best
Stavros

-----Ursprüngliche Nachricht-----
Von: Vaira, Antonio <[e-mail]<mailto:[e-mail]>>
Gesendet: Dienstag, 31. Januar 2023 13:33
An: Kousidis, Stavros <[e-mail]<mailto:[e-mail]>>; Kampanakis, Panos <[e-mail]<mailto:[e-mail]>>
Cc: LAMPS <[e-mail]<mailto:[e-mail]>>; [e-mail]<mailto:[e-mail]>
Betreff: RE: [lamps] draft-gazdag-x509-hash-sigs-00

Dear Stavros, Dear Panos,

I hope I am not intruding this conversation, I would like to add a couple of personal considerations:

- I believe that we will also need to have "stateful HBS ICAs", to at least sign "stateful HBS code-signing certificates". This would allow a relying party to validate the code-signing certificates, and its associated certificate chain, by verifying only one type of digital signatures, which in this case would be a stateful HBS scheme. This type of ICAs may be handled as RootCA, so probably there is not much to add to the security considerations.
- my understanding of stateful HBS schemes is that the state of the private key can be uniquely identified by the authentication path that is part of the signature. Could we think to derive a unique value, out of this authentication path and embed it into a certificate field? Maybe such certificate can be further published, for example on CT, to allow public scrutiny of the CA operations?
- on a more generic note, the recent publication of CNSA 2.0, despite applying only to NSS, may trigger other regulatory bodies, which may be transversal to the scope of NSS, to adopt similar guidelines. Therefore I think we might have to deal with stateful HBS sooner than later.

- @Stavros: it would be very interesting to know more about how you plan to handle the requirements from §7 of NIST SP 800-208.
    > in my understanding, to fulfil the requirements set forth in this section one would that initializing several hypertrees on different HSMs. One or more HSMs may be used immediately and the remaining should be securely stored for later use (as disaster recovery mechanism for example). I think this approach might prove to be quite cumbersome, at least over a long period of time (which is intended use of stateful HBS).
    > do you see additional approaches that would allow to comply with the requirements from §7 of NIST SP 800-208?


Many thanks
Antonio Vaira

-----Original Message-----
From: Spasm <[e-mail]<mailto:[e-mail]>> On Behalf Of Kousidis, Stavros
Sent: Monday, 23 January 2023 09:33
To: Kampanakis, Panos <kpanos=[e-mail]<mailto:kpanos=[e-mail]>>
Cc: LAMPS <[e-mail]<mailto:[e-mail]>>; [e-mail]<mailto:[e-mail]>
Subject: Re: [lamps] draft-gazdag-x509-hash-sigs-00

Dear Pano,

thank you for your comments and suggestions, and sorry for the late reply.

The typical use case we have in mind are root and (potentially also subordinate) CAs which are using an HSM for cert signing that ensures the secure handling of the state. When discussing this in the security considerations we would also stress on NISTs proposal to use "Distributed Multi-Tree Hash-Based Signatures" (see NIST SP 800-208 §7) as a design to further ensure that states are handled appropriately.

We have tracked the other use cases you mentioned as an issue in in our repository. I think Stefan Gazdag has some experience here and we will discuss how to incorporate your suggestions in the security considerations.

Best
Stavros

-----Ursprüngliche Nachricht-----
Von: Kampanakis, Panos <kpanos=[e-mail]<mailto:kpanos=[e-mail]>>
Gesendet: Donnerstag, 29. Dezember 2022 18:23
An: Kousidis, Stavros <[e-mail]<mailto:[e-mail]>>
Cc: LAMPS <[e-mail]<mailto:[e-mail]>>; [e-mail]<mailto:[e-mail]>
Betreff: RE: [lamps] draft-gazdag-x509-hash-sigs-00

One more comment regarding draft-gazdag-x509-hash-sigs.

Stateful HBS had come up previously for X.509 and some participants voiced serious concerns https://eur01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fmailarchive.ietf.org%2Farch%2Fmsg%2Fspasm%2FDKPDfaQZxF5_De9BYuoWsRKp4gM%2F&data=05%7C01%7Cantonio.vaira%40siemens.com%7Cd988d9a6eb5d4ac79f4808db042989a7%7C38ae3bcd95794fd4addab42e1495d55a%7C1%7C0%7C638108348674728031%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&sdata=Wedj6fJ8p564lYwaDHXQAjbEYjT8oX5jl1A8eNop9So%3D&reserved=0 A summary of the counter-arguments could be that CAs have messed up before, how can we rest assured they will not reuse state.

I think your argument for Stateful HBS in this draft is only for root CAs which sign a few ICAs and then go to sleep and rarely wake up. Maybe another use is for code-signing EKU certs where the signer controls its signing process and the verifiers trust it.  The draft also mentions subordinate CA certificates. I don't think these are good use-cases for stateful HBS. I would suggest for the draft to clearly stress the potentially use-cases for Stateful HBS. Also I suggest for the security considerations section to stress the importance and how you envision these use-cases will be able to address the state concern. For example a Root CA uses an HSM and signs very few ICA certs and then goes offline. Another example is a code-signer keeps track of all its signatures and can go back and attest the state was not reused periodically and its verifiers usually trust the signer. Another one could be the state look ahead where you retrieve x states and change your pointer before you even start signing anything.



-----Original Message-----
From: Spasm <[e-mail]<mailto:[e-mail]>> On Behalf Of Kousidis, Stavros
Sent: Saturday, December 24, 2022 12:11 AM
To: Russ Housley <[e-mail]<mailto:[e-mail]>>
Cc: LAMPS <[e-mail]<mailto:[e-mail]>>; [e-mail]<mailto:[e-mail]>
Subject: RE: [EXTERNAL][lamps] draft-gazdag-x509-hash-sigs-00

CAUTION: This email originated from outside of the organization. Do not click links or open attachments unless you can confirm the sender and know the content is safe.



Dear Russ,

thank you for the information.

In the next version we will adopt the "OCTET STRING" definition of RFC 8708 for HSS and apply this also to XMSS/XMSS^MT. The same applies to SPHINCS+ where we will adopt the definition of "draft-ietf-lamps-cms-sphincs-plus-01".

Best
Stavros

-----Ursprüngliche Nachricht-----
Von: Russ Housley <[e-mail]<mailto:[e-mail]>>
Gesendet: Freitag, 23. Dezember 2022 18:12
An: [e-mail]<mailto:[e-mail]>
Cc: LAMPS <[e-mail]<mailto:[e-mail]>>
Betreff: [lamps] draft-gazdag-x509-hash-sigs-00

Dear I-D Authors:

RFC 8708 has this definition:

     HSS-LMS-HashSig-PublicKey ::= OCTET STRING

This will carry the bytes as defined in RFC 8554.

draft-gazdag-x509-hash-sigs-00 says:

    HSS-HashSig-PublicKey ::= SEQUENCE {
       levels     OCTET STRING, -- number of levels L
       tree       OCTET STRING, -- typecode of top-level LMS tree
       ots        OCTET STRING, -- typecode of top-level LM-OTS
       identifier OCTET STRING, -- identifier I of top-level LMS key pair
       root       OCTET STRING  -- root T[1] of top-level tree
    }

This will produce a different byte string than RFC 8554.  I think this is a problem.  There should only be one way to encode the HSS/LMS public key.

Russ

_______________________________________________
Spasm mailing list
[e-mail]<mailto:[e-mail]>
https://eur01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.ietf.org%2Fmailman%2Flistinfo%2Fspasm&data=05%7C01%7Cantonio.vaira%40siemens.com%7Cd988d9a6eb5d4ac79f4808db042989a7%7C38ae3bcd95794fd4addab42e1495d55a%7C1%7C0%7C638108348674728031%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&sdata=wFkKzzwn5JFkvymGcyOrOix99O8otkKQ5pdOmuGwh5M%3D&reserved=0

_______________________________________________
Spasm mailing list
[e-mail]<mailto:[e-mail]>
https://eur01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.ietf.org%2Fmailman%2Flistinfo%2Fspasm&data=05%7C01%7Cantonio.vaira%40siemens.com%7Cd988d9a6eb5d4ac79f4808db042989a7%7C38ae3bcd95794fd4addab42e1495d55a%7C1%7C0%7C638108348674728031%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&sdata=wFkKzzwn5JFkvymGcyOrOix99O8otkKQ5pdOmuGwh5M%3D&reserved=0