Subject: [Suit] using/building/standardizing HMS-LMS infrastructure

From: Michael Richardson <[email-masked]>
Date: Thu, 11 Nov 2021 08:19:14 -0500

It seems that the SUIT WG is becoming quite comfortable with making HSS-LMS
mandatory to implement.   I want to ask some questions about the
infrastructure that will be required to operate things.
This is very much what draft-richardson-t2trg-idevid-considerations deals with.

What I am trying to avoid with this email and maybe subsequent documents is
that we wind up in a situation where HSS-LMS is rejected by industry because
they don't know how to operate it, and our MTI winds up being meaningless.

My understanding is that when creating HSS-LMS signatures that the signer has
to perform a read/modify/write cycle on the private component.

Failure to perform the write operation means that keys will get reused, and
the signatures will not be valid.
I don't think that results in disclosing a private key, as would happen if a
nonce is reused in the GCM/CCM/etc. symmetric cipher use though!
My understanding is that reusing the key would result in a signature that
would be rejected by verifiers as being a duplicated, and thus ignored.

This is constrasted to the Pre-Quantum methods (RSA, DSA, ECDSA, EDDDSA),
where a private key can be loaded from a secure storage, used and then the
in-ram copy destroyed.

There are two risks that I think are important to identify:

1) an HSM that overwrites the new content with the old risks failing halfway
   through, possibly resulting in loss of key.
   Some kind of append-only aka log-based file system would deal with that.

2) off-site/business continuity copies of the key may need much higher
   interactions with the primary/active site in order to remain in sync.
   Existing systems could essentially transfer the secrets once and then be
   done.

When we numbered certificates with sequential serial numbers there was
some need to transfer the counter to the backup system.  But that was
a public piece of information, signed by the CA, so the secondary system
could update it's serial number just by examining a public document.
Now, we generate serial numbers randomly, so we don't need to do that
anymore.

I think that if the secondary site saw all of the signed objects that it
could determine which keys were already used, and could advance itself
without having to interact directly with the HSM at the primary site.

Are there already documents (at NIST?) that explain operation of HSS-LMS signer?
If there aren't, is this something that the IETF should do?

Note that whatever we do, we need to make sure that it scales to the
developer's desktop so that the developer is always exercising the update
mechanism when working. (Otherwise, they put backdoors in due to frustration)

--
Michael Richardson <[email-masked]>   . o O ( IPv6 IøT consulting )
           Sandelman Software Works Inc, Ottawa and Worldwide

---

From: Michael Richardson <[email-masked]>
Date: Thu, 11 Nov 2021 11:34:57 -0500

{I screwed up t2trg, put it at @ietf.org, which is wrong}

Mike Ounsworth <Mike.Ounsworth=[email-masked]> wrote:
    > This is also a concern that I share. (but admit that I'm not familiar with your draft)

    > TL;DR: we've been modelling state re-use as full key compromise. Would
    > love to get that double-checked. Failover and human error are my big
    > concerns.

re-use is full key compromise?  I find that surprising, so I'll go read more.

    > My (admittedly non-expert) understanding is that state reuse means
    > reuse of a one-time signature leaf key, which will allow signature
    > forgery of any bits where the two signed messages differ. If you sign
    > the identical message twice, no biggie; if you sign the bitwise inverse
    > message then you've essentially leaked the entire private key of that
    > leaf node. I don't know the HSS-LMS construction well enough to know if
    > leaf-node (aka state) reuse can even be detected by the verifier. This
    > is a question best answered by @ScottF.

Ah, I see.

    > I share your morbid fear over deployment concerns. Particularly I'm
    > worried about sub-points of your #2:

    > 2a) Multiple copies of your signing infrastructure running in
    > Active-Active mode (ex. multiple IoT manufacturing facilities). Maybe
    > the answer here is that in an LMS / XMSS world, each site needs a
    > dedicated key (aka intermediate CAs, I suppose).

I think that this could make sense.... assuming one uses a CA structure.
If we were using LSS-HMS for IDevIDs, then there would be more of an issue.
I think that a cross-network locking protocol (with human override) is
probably acceptable for firmware signing.   I think that each product line
ought to have it's own key, and I don't think that people sign firmware more
than once a day.... maybe the high-speed DevOps people, but there are other
issues there.

    > 2b) Disaster site failover; your active site gets hit with a tornado
    > and loses power. No worries, your fancy DNS starts re-routing traffic
    > to your DR site within milliseconds. No matter how quick, there is the
    > potential that an object was signed and published in the time between
    > the last HSM sync and the power failure.

Exactly.

    > 2c) Human error on operations like a backup restore, datacentre
    > migration, onboarding new HSM hardware, etc. Datacentre engineers are
    > not cryptographers. Write the SOP in sanguine ink if you want, but I
    > bet someone somewhere will bungle this. Given our assumption that state
    > reuse (if the signature is published) is key compromise, then even
    > running your automated sanity tests after restoring the backup, but
    > before syncing, it could be disastrous.

In particular, if your signing machine is a virtual machine and it's subject to
snapshots, then it's really really easy to take a hardware fault, restore to
snapshot and think it is all well.

    > The only "provable" solution that I've heard about seems to be making
    > your private key so large that you can afford to give each instance its
    > own subtree -- ex. using an ID-prefixed index, for example. It does
    > mean that at keygen time you need to know how many instances you'll
    > ever need.

There is a planning document here.  Is this an IETF job to write it?
ISO17000 series is, apparently, about the audit process for examining
infrastructure like this, but, I'm not really sure... because my eyes glazed
over trying to understand it.  I came across it while trying to find
specifications that proscribed root-key ceremonies for enterprises.

    > Though I suppose this does not address the human error point
    > if you forget to assign it a unique ID. Needless to say, despite many
    > conversations with people who try to convince me otherwise, I remain
    > skeptical about the deployability of stateful hash-based signatures.

I share your concern:  I think that if we can get some good examples out
there, then maybe we can overcome the issues.
Perhaps someone like RIPE, ngi.eu creating a poor-man's HSM.
(air-gapped RPI4 with webcam to read QRcode of thing to sign, eInk to provide
result?  the crypt.tech people have become quiet, but that might be pandemic)

Mike Ounsworth <Mike.Ounsworth=[email-masked]> wrote:
    > Another option which I think is not politically popular (see NSA
    > presentation at LAMPS 112 and following mail list discussion) is to
    > hybrid your LMS / XMSS key with Ed25519; while it does not solve the
    > state-reuse problem, it would buy you time to deal with the
    > consequences of mis-managing your state.

Even if we assume a hybrid key, we still have to manage the LMS part, right?

--
]               Never tell me the odds!                 | ipv6 mesh networks [
]   Michael Richardson, Sandelman Software Works        |    IoT architect   [
]     [email-masked]  http://www.sandelman.ca/        |   ruby on rails    [

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Thu, 11 Nov 2021 21:22:10 +0000

A few years ago, I looked at how bad state re-use would be; my conclusion while using that to generate a forgery would not be trivial, it is *far* easier than the security levels you obtain without it.

Notes:
- No, this was a rather informal study, and I didn't publish it anywhere
- I did note that the W=8 setting made things considerably easier on an attacker than the W=4 setting
- The actual effort required appeared to depend quite a bit on the actual two message signed (which, because they are nondetermanisticly hashed, could be modeled as random).  That means you might get lucky (and so finding a forgery might be a lot of work), or you might not unlucky
- I didn't try to get an estimate on the exact expected difficulty; from what I remember, at W=8 and with a bit of bad luck, it might be feasible for TLAs, and possibly even for someone who can rent a bunch of cloud computation - with a lot of bad luck, it might be down to what you can do on a laptop.

So, the bottom line is: don't do that.  While it might not be as bad as a full key compromise, it's safest to treat it as if it were.

BTW: Mike's outline about how the compromise would work is off - LMS (actually, LMS-OTS) converts the message into a base 2**w string (and appends an 'inverted checksum', also in base 2**w).  When we generate a signature, we effectively list each digit; the attacker can easily generate a new signature that increases any digit, however he cannot decrement them.  With a single signature, the attacker cannot sign a different hash (because if he increments a digit anywhere, some digit in the inverted checksum will decrement, and he can't do that).  However, if he has two signatures from the same one-time signature, he can mix and match digits from the two signatures.  For example, if the first signature has the first two digits as (3 7) and the second signature has the first two digits as (9 4), he can generate a signature with the first two digits (4 6); in this case, the inverted checksum doesn't save us, because (as long as no other digits change), he can use the digits from the inverted checksum from the second signature.

One difficulty the attacker would have with this attack is that he cannot actually specify which digits he can use; he has to hash various messages, and look for one that works with the digits from the two messages.  Evaluating how hard that would be is what's problematic with figuring out exactly how weak this case it.

-----Original Message-----
From: Mike Ounsworth <[email-masked]> 
Sent: Thursday, November 11, 2021 9:38 AM
To: Michael Richardson <[email-masked]>; suit <[email-masked]>; LAMPS WG <[email-masked]>; [email-masked]; Scott Fluhrer (sfluhrer) <[email-masked]>
Subject: RE: [EXTERNAL] [lamps] using/building/standardizing HMS-LMS infrastructure

Hi Michael,

TL;DR: we've been modelling state re-use as full key compromise. Would love to get that double-checked. Failover and human error are my big concerns.

My (admittedly non-expert) understanding is that state reuse means reuse of a one-time signature leaf key, which will allow signature forgery of any bits where the two signed messages differ. If you sign the identical message twice, no biggie; if you sign the bitwise inverse message then you've essentially leaked the entire private key of that leaf node. I don't know the HSS-LMS construction well enough to know if leaf-node (aka state) reuse can even be detected by the verifier. This is a question best answered by @ScottF.

I share your morbid fear over deployment concerns. Particularly I'm worried about sub-points of your #2:

2a) Multiple copies of your signing infrastructure running in Active-Active mode (ex. multiple IoT manufacturing facilities). Maybe the answer here is that in an LMS / XMSS world, each site needs a dedicated key (aka intermediate CAs, I suppose).

2b) Disaster site failover; your active site gets hit with a tornado and loses power. No worries, your fancy DNS starts re-routing traffic to your DR site within milliseconds. No matter how quick, there is the potential that an object was signed and published in the time between the last HSM sync and the power failure.

2c) Human error on operations like a backup restore, datacentre migration, onboarding new HSM hardware, etc. Datacentre engineers are not cryptographers. Write the SOP in sanguine ink if you want, but I bet someone somewhere will bungle this. Given our assumption that state reuse (if the signature is published) is key compromise, then even running your automated sanity tests after restoring the backup, but before syncing, it could be disastrous.

The only "provable" solution that I've heard about seems to be making your private key so large that you can afford to give each instance its own subtree -- ex. using an ID-prefixed index, for example. It does mean that at keygen time you need to know how many instances you'll ever need. Though I suppose this does not address the human error point if you forget to assign it a unique ID. Needless to say, despite many conversations with people who try to convince me otherwise, I remain skeptical about the deployability of stateful hash-based signatures.

---
Mike Ounsworth
Software Security Architect, Entrust

-----Original Message-----
From: Spasm <[email-masked]> On Behalf Of Michael Richardson
Sent: November 11, 2021 7:19 AM
To: suit <[email-masked]>; LAMPS WG <[email-masked]>; [email-masked]
Subject: [EXTERNAL] [lamps] using/building/standardizing HMS-LMS infrastructure

WARNING: This email originated outside of Entrust.
DO NOT CLICK links or attachments unless you trust the sender and know the content is safe.

______________________________________________________________________

What I am trying to avoid with this email and maybe subsequent documents is that we wind up in a situation where HSS-LMS is rejected by industry because they don't know how to operate it, and our MTI winds up being meaningless.

My understanding is that when creating HSS-LMS signatures that the signer has to perform a read/modify/write cycle on the private component.

Failure to perform the write operation means that keys will get reused, and the signatures will not be valid.
I don't think that results in disclosing a private key, as would happen if a nonce is reused in the GCM/CCM/etc. symmetric cipher use though!
My understanding is that reusing the key would result in a signature that would be rejected by verifiers as being a duplicated, and thus ignored.

This is constrasted to the Pre-Quantum methods (RSA, DSA, ECDSA, EDDDSA), where a private key can be loaded from a secure storage, used and then the in-ram copy destroyed.

When we numbered certificates with sequential serial numbers there was some need to transfer the counter to the backup system.  But that was a public piece of information, signed by the CA, so the secondary system could update it's serial number just by examining a public document.
Now, we generate serial numbers randomly, so we don't need to do that anymore.

I think that if the secondary site saw all of the signed objects that it could determine which keys were already used, and could advance itself without having to interact directly with the HSM at the primary site.

Note that whatever we do, we need to make sure that it scales to the developer's desktop so that the developer is always exercising the update mechanism when working. (Otherwise, they put backdoors in due to frustration)

Any email and files/attachments transmitted with it are confidential and are intended solely for the use of the individual or entity to whom they are addressed. If this message has been sent to you in error, you must not copy, distribute or disclose of the information it contains. Please notify Entrust immediately and delete the message from your system.

---

From: Ludovic Perret <[email-masked]>
Date: Tue, 16 Nov 2021 22:22:20 +0000

------ Message d'origine ------
De: "Michael Richardson" <[email-masked]>
À: "suit" <[email-masked]>; "LAMPS WG" <[email-masked]>; "[email-masked]" 
<[email-masked]>
Envoyé : 11/11/2021 14:19:14
Objet : [lamps] using/building/standardizing HMS-LMS infrastructure

>If there aren't, is this something that the IETF should do?

About that, there is a document from ETSI
ETSI TR 103 692
State management for stateful authentication mechanisms
https://www.etsi.org/deliver/etsi_tr/103600_103699/103692/01.01.01_60/tr_103692v010101p.pdf

and also the NIST SP SP 800-208 on stateful HBS 
(https://csrc.nist.gov/publications/detail/sp/800-208/final)

Still, not sure these address all your concerns.

Best Regards,

Ludovic Perret,

---

From: Michael Richardson <[email-masked]>
Date: Mon, 22 Nov 2021 16:51:15 -0500

Ludovic Perret <[email-masked]> wrote:
    >> Are there already documents (at NIST?) that explain operation of
    >> HSS-LMS signer?  If there aren't, is this something that the IETF
    >> should do?

    > About that, there is a document from ETSI ETSI TR 103 692 State
    > management for stateful authentication mechanisms

Section 6.2 goes into this a reasonable amount.
It seems that using deterministic signatures is useful.
Section 7 is also in the direction that I was thinking.

    > Still, not sure these address all your concerns.

Has better pictures if you are trying to understand the algorithms, but less
practical advice.

-- 
Michael Richardson <[email-masked]>, Sandelman Software Works
 -= IPv6 IoT consulting =-