Subject: [Suit] SUIT Manifest MTI Algorithms

From: Russ Housley <[email-masked]>
Date: Wed, 10 Nov 2021 09:13:08 -0500

On Monday, there was a discussion of the mandatory-to-implement (MTI) algorithms, which concluded that HSS/LMS MUST be supported and ECDSA SHOULD be supported.

If you have concerns with this way forward, please respond to this message with your concerns by 26 November 2021.

For the SUIT WG Chairs,
 Russ

---

From: Rønningstad, Øyvind <[email-masked]>
Date: Wed, 10 Nov 2021 15:31:11 +0000

HSS/LMS is very interesting but quite unknown, what implementations exist currently?

Øyvind Rønningstad

-----Original Message-----
From: Suit <[email-masked]> On Behalf Of Russ Housley
Sent: Wednesday, November 10, 2021 15:13
To: suit <[email-masked]>
Subject: [Suit] SUIT Manifest MTI Algorithms

For the SUIT WG Chairs,
 Russ

_______________________________________________
Suit mailing list
[email-masked]
https://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.ietf.org%2Fmailman%2Flistinfo%2Fsuit&amp;data=04%7C01%7Coyvind.ronningstad%40nordicsemi.no%7Cd8db1737c9674affc06f08d9a4544578%7C28e5afa2bf6f419a8cf6b31c6e9e5e8d%7C0%7C0%7C637721504115319275%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C1000&amp;sdata=ZrO7RhyW1dwttxp1Q46uM9QpMrAUXOORiaaFfeXS7X8%3D&amp;reserved=0

---

From: Russ Housley <[email-masked]>
Date: Wed, 10 Nov 2021 11:19:25 -0500

It is in BouncyCastle.

I am also aware of these in GitHub:
  -  https://github.com/cisco/hash-sigs
  -  https://github.com/LoCCS/lms
  -  https://github.com/russhousley/pyhsslms

There are probably others.

Russ

> On Nov 10, 2021, at 10:31 AM, Rønningstad, Øyvind <Oyvind.Ronningstad=[email-masked]> wrote:
>

---

From: Ira McDonald <[email-masked]>
Date: Wed, 10 Nov 2021 12:26:00 -0500

Hi,

The US NIST SP800-208 Recommendation for Stateful Hash-Based Signature
Schemes (October 2020)
specifies HSS/LMS and references the RFC specs developed by the IRTF Crypto
Forum for these hash
algorithms:

https://csrc.nist.gov/publications/detail/sp/800-208/final

Among followers of IRTF Crypto Forum, there is high visibility of these
hash algorithms.  There has also
been take-up in ISO, ITU-T, and other SDO specs, because these are
Post-Quantum Safe algorithms.

Cheers,
- Ira

On Wed, Nov 10, 2021 at 11:19 AM Russ Housley <[email-masked]> wrote:

> > On Monday, there was a discussion of the mandatory-to-implement (MTI)
> algorithms, which concluded that HSS/LMS MUST be supported and ECDSA SHOULD
> be supported.
> >
> > If you have concerns with this way forward, please respond to this
> message with your concerns by 26 November 2021.
> >
> > For the SUIT WG Chairs,
> > Russ
>
> https://www.ietf.org/mailman/listinfo/suit
>

---

From: Emmanuel Baccelli <[email-masked]>
Date: Wed, 10 Nov 2021 18:53:26 +0100

Hi there,

One pain point is how small, microcontroller-based IoT devices may (or may
not) be able to meet this requirement.

We have recently conducted an experimental study on this topic, evaluating
SUIT on common microcontrollers (Cortex-M, ESP-32 and RISC-V)
In particular, we evaluate the cost of upgrading from ed25519 to HSS/LMS
with SUIT used to secure actual RIOT firmware updates:
see preprint at https://eprint.iacr.org/2021/781.pdf

In a nutshell: for small-sized software updates using SUIT with LMS, we
measured impact on network transfer costs (~45% more data over the wire)
and on memory footprint on-device (~35% more Flash memory required), but
only little impact on RAM or execution time, compared to using SUIT with
ed25519. If the baseline is something else  (i.e. not SUIT, or not
ed25519), the overhead might be more.

Note: we studied software-only, generic implementations. E.g., for LMS we
used Scott's implementation https://github.com/cisco/hash-sigs. If the
implementation is in HW or if the crypto is not part of the software that
needs to be updated, this overhead could be less.

What will be considered bearable overhead to upgrade to SUIT-compliant
security, on microcontroller-based IoT devices? That is a question.

Best,

--Emmanuel

---

From: Michael Richardson <[email-masked]>
Date: Wed, 10 Nov 2021 14:32:34 -0500

Emmanuel Baccelli <[email-masked]> wrote:
    > We have recently conducted an experimental study on this topic,
    > evaluating SUIT on common microcontrollers (Cortex-M, ESP-32 and
    > RISC-V) In particular, we evaluate the cost of upgrading from ed25519
    > to HSS/LMS with SUIT used to secure actual RIOT firmware updates: see
    > preprint at https://eprint.iacr.org/2021/781.pdf

Awesome!

    > measured impact on network transfer costs (~45% more data over the
    > wire) and on memory footprint on-device (~35% more Flash memory
    > required), but only little impact on RAM or execution time, compared to
    > using SUIT with ed25519. If the baseline is something else (i.e. not
    > SUIT, or not ed25519), the overhead might be more.

I looked into your paper trying to understand where this 35% more flash
memory required.  Is it table 6 and 7?   I think it's a 35% increase of
the verification code from ECDSA to HSS-LSS.  I don't think it's a 35%
increase in total flash required, right?

    > security, on microcontroller-based IoT devices? That is a question.

Your paper seems to suggest it's acceptable.

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

---

From: Russ Housley <[email-masked]>
Date: Wed, 10 Nov 2021 15:12:11 -0500

Emmanuel:

The signature verification for HSS/LMS should be much smaller and faster too.

I notices that you used the Cisco SHA-256 for HSS/LMS.  When I was using the Cisco code to ensure that pyhsslms.py was interoperable, I discovered that the SHA-256 in OpenSSL was a lot faster.  I wonder if the SHA-256 from mbedtls would give you different results.

Russ

> On Nov 10, 2021, at 2:32 PM, Michael Richardson <[email-masked]> wrote:
>

---

From: Emmanuel Baccelli <[email-masked]>
Date: Thu, 11 Nov 2021 09:40:14 +0100

Hi Michael,

    > [...] for small-sized software updates using SUIT with LMS, we

It's table 8 in https://eprint.iacr.org/2021/781.pdf
and it's a ~35% increase in total Flash, for the basic image we used RIOT
(simple application with network stack CoAP + SUIT).

> Your paper seems to suggest it's acceptable.

Our experimental study confirms quantum-resistant SUIT is doable in
practice,
and LMS signatures seems the best choice for that, at this point.
We did not conclude on the wide acceptability of using "large footprint"
crypto.

--Emmanuel

---

From: Emmanuel Baccelli <[email-masked]>
Date: Thu, 11 Nov 2021 12:22:08 +0100

Hi Russ

The signature verification for HSS/LMS should be much smaller and faster
> too.
I notices that you used the Cisco SHA-256 for HSS/LMS.  When I was using
> the Cisco code to ensure that pyhsslms.py was interoperable, I discovered
> that the SHA-256 in OpenSSL was a lot faster.  I wonder if the SHA-256 from
> mbedtls would give you different results.
>

Yes. Alternative implementations would be interesting to check too, indeed.
What our experiments on microcontrollers point to so far,
is that the pain point with LMS is more about memory footprint and
bytes-over-the-wire,
rather than on speed of crypto execution for signature verification.

--Emmanuel

---

From: Rønningstad, Øyvind <[email-masked]>
Date: Thu, 11 Nov 2021 12:13:46 +0000

Can you elaborate on the meaning of a MTI algorithm in this context? In practice, the manifest verification algorithm is decided at production-time because that's typically when the public keys are provisioned. The SUIT manifest processor is therefore compiled with support for exactly one algorithm, corresponding to the provisioned keys. If HSS/LMS is mandatory-to-implement, the root-of-trust public key must be an HSS/LMS key, so there is no need to even consider other algorithms at that point. This seems overly restrictive, or am I misunderstanding the meaning of MTI?

Would something like "mandatory to support" make more sense, where a SUIT implementation must have HSS/LMS as an option when compiling?

Øyvind

---

From: Michael Richardson <[email-masked]>
Date: Thu, 11 Nov 2021 07:38:06 -0500

<#secure method=pgpmime mode=sign>

    > (simple application with network stack CoAP + SUIT).

Ah, thank you.  I think that Internet advertising has taught my eyes to
ignore stuff outside the text body :-)

In that table:
   base: 52K
   with LMS/SHA3        + 34%

(so about 17K added)
I'm curious how much of that is just the SHA3 implementation.

I guess there wasn't a LMS/SHA2-256.

For many application, the base will be much bigger than 52K, so the impact of
17K may be less.  512K of flash is common.

Have you combined the LMS signature with your ICN based distribution?

    > We did not conclude on the wide acceptability of using "large footprint"

Understood.

Table 6 and 7 are also interesting.
LMS coming in at ~110ms, while ECDSA at 3x that, and EDDSA either being way
faster (41ms!) or much (20x) slower (C25519).  Does that include the time to
hash the firmware itself?   I don't think so.

That LMS might be *faster* than Pre-Quantum algorithms and therefore very
interesting for bootloaders that want to verify the image before starting it,
seemed like a major win to me.

I don't understand the two footnotes:
  1 Flash only contains the verification algorithms.
  2 Flash contains the verification algorithms and hard-coded keys.

Probably I don't understand Falcon, if there are no keys/trust-anchors required.

--
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 07:43:24 -0500

Rønningstad, Øyvind wrote:
   > Can you elaborate on the meaning of a MTI algorithm in this context? In
   > practice, the manifest verification algorithm is decided at
   > production-time because that's typically when the public keys are
   > provisioned. The SUIT manifest processor is therefore compiled with
   > support for exactly one algorithm, corresponding to the provisioned
   > keys. If HSS/LMS is mandatory-to-implement, the root-of-trust public key
   > must be an HSS/LMS key, so there is no need to even consider other
   > algorithms at that point. This seems overly restrictive, or am I
   > misunderstanding the meaning of MTI?

You aren't mis-understanding MTI.

What you are missing is that there are operational requirements where the factory
provisioned trust anchor will not be the used.
(But: that's probably the only situation that we see out there today)

In many industrial uses, particularly for safety related devices,
operators/owners of the devices will decide which firmware updates will be
applied, and when.   As such, the device will need to be configured to use a
different trust anchor.

This is all the discussion we had on the list and at the meeting about
interactions with third parties.

How such a thing will be managed, I don't know.

I'm gonna plug my draft-richardson-t2trg-idevid-considerations document here
as dealing with some of the issues around why all public key infrastructure
might not be the same, and how to discuss the differences.

--
]               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: Rønningstad, Øyvind <[email-masked]>
Date: Thu, 11 Nov 2021 13:01:05 +0000

I'm sorry, I still don't understand the implications for manifest processor implementations. Does MTI mean that whenever SUIT manifests are used, they must be signed by one or more keys, and one of those keys must be HSS/LMS key?

Øyvind

-----Original Message-----
From: Michael Richardson <[email-masked]> 
Sent: Thursday, November 11, 2021 13:43
To: Rønningstad, Øyvind <[email-masked]>; suit <[email-masked]>
Subject: Re: [Suit] SUIT Manifest MTI Algorithms

What you are missing is that there are operational requirements where the factory provisioned trust anchor will not be the used.
(But: that's probably the only situation that we see out there today)

In many industrial uses, particularly for safety related devices, operators/owners of the devices will decide which firmware updates will be
applied, and when.   As such, the device will need to be configured to use a
different trust anchor.

This is all the discussion we had on the list and at the meeting about interactions with third parties.

I'm gonna plug my draft-richardson-t2trg-idevid-considerations document here as dealing with some of the issues around why all public key infrastructure might not be the same, and how to discuss the differences.

---

From: Russ Housley <[email-masked]>
Date: Thu, 11 Nov 2021 08:28:34 -0500

I was thinking about this as MUST be able to verify an HSS/LMS signature, SHOULD be able to verify an ECDSA signature, and MAY be able to verify others.

Russ

> On Nov 11, 2021, at 8:01 AM, Rønningstad, Øyvind <Oyvind.Ronningstad=[email-masked]> wrote:
>

---

From: Koen Zandberg <[email-masked]>
Date: Thu, 11 Nov 2021 14:30:01 +0100

Hi,

On 11/11/2021 13:38, Michael Richardson wrote:
> <snip>
That depends a bit on the class of devices you're working on. On class 2 
devices this might fit comfortably, but for Class 0 and Class 1 type of 
devices the impact on required flash would be significant and might 
require an upgrade to a larger device to make it fit.
> hash the firmware itself?   I don't think so.
The measurements were done with a very minimal payload (a small 
sentence), so the payload-size dependent part of the verification time 
is relative small here.
> Probably I don't understand Falcon, if there are no keys/trust-anchors required.

We ran into trouble with the amount of memory present on the RISC-V 
board. (Only 128 kB of flash and 32 kB ram). Preferably the benchmark 
application generates a set of keys, sign a payload and then verify it 
with the signature.

For Falcon the signing algorithm stack requirement exceeded the 
available RAM on the device. In that case the public key and the 
signature for the payload was generated offline and included in the 
firmware.

The second footnote refers to the Dilithium case. The Dilithium library 
used didn't fit at all on the device, exceeding available stack in both 
the signing and verification case. Only the modified version using a 
precomputed expanded form of the public key stored in flash had low 
enough memory requirement to fit on the RISC-V device used. In the 
footnote "hard-coded" refers to that, the algorithm is flashed with a 
hard-coded public key and can't switch them. (So multiple trust-anchors 
is out of the question with this setup.)

Koen

---

From: Rønningstad, Øyvind <[email-masked]>
Date: Thu, 11 Nov 2021 13:46:53 +0000

How does that look if delegation chains are not supported? Do the RoT public keys have to be HSS/LMS keys?

Øyvind

-----Original Message-----
From: Russ Housley <[email-masked]> 
Sent: Thursday, November 11, 2021 14:29
To: Rønningstad, Øyvind <[email-masked]>
Cc: Michael Richardson <[email-masked]>; suit <[email-masked]>
Subject: Re: [Suit] SUIT Manifest MTI Algorithms

Russ

---

From: Russ Housley <[email-masked]>
Date: Thu, 11 Nov 2021 08:57:19 -0500

There is not an assumption that certification paths will be required.  For example, the public key could be baked into the clients that will be performing the verification.  Others may want to use certificates, but this is not saying anything about the certificate profile.

Russ

> On Nov 11, 2021, at 8:46 AM, Rønningstad, Øyvind <[email-masked]> wrote:
>

---

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

Koen Zandberg <[email-masked]> wrote:
    > For Falcon the signing algorithm stack requirement exceeded the available RAM
    > on the device. In that case the public key and the signature for the payload
    > was generated offline and included in the firmware.

But, isn't that the expected case?
We'd have verifier code only?  The signature would occur on developer's desk.

    > The second footnote refers to the Dilithium case. The Dilithium library used
    > didn't fit at all on the device, exceeding available stack in both the
    > signing and verification case. Only the modified version using a precomputed
    > expanded form of the public key stored in flash had low enough memory
    > requirement to fit on the RISC-V device used. In the footnote "hard-coded"
    > refers to that, the algorithm is flashed with a hard-coded public key and
    > can't switch them. (So multiple trust-anchors is out of the question with
    > this setup.)

Got it.
Manufacturers take note, ideally.

---

From: Michael Richardson <[email-masked]>
Date: Thu, 11 Nov 2021 10:13:00 -0500

Rønningstad, Øyvind wrote:
    > I'm sorry, I still don't understand the implications for manifest
    > processor implementations. Does MTI mean that whenever SUIT manifests
    > are used, they must be signed by one or more keys, and one of those
    > keys must be HSS/LMS key?

It means that devices MUST support HSS/LMS, because the third party MUST be
allowed to pick that algorithm.  But, it doesn't have to be used.

The device SHOULD support ECDSA, but if there are reasons not to include,
then don't.  A reason could be: code size, performance, obsoleted by PQ...

---

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

Russ Housley <[email-masked]> wrote:
    > There is not an assumption that certification paths will be required.
    > For example, the public key could be baked into the clients that will
    > be performing the verification.  Others may want to use certificates,
    > but this is not saying anything about the certificate profile.

draft-richardson-t2trg-idevid-considerations does have some ways to
describe such certificate profiles.

The goal isn't to proscribe a profile, but to be able to describe it.