Subject: [Suit] Quantum resistance in firmware formats

From: Michael Richardson <[email-masked]>
Date: Fri, 10 Nov 2017 09:49:20 -0500

The proposed architectures that we have either assume a relatively capable
bootloader, or the ability to double buffer images.

One of the advantages of the double buffering is that the firmware update
code itself can easily be updated.
Updating a bootloader image may be significantly more risky, and so I imagine
that it might rarely or never occur in a device's lifetime.

So my question is: how much concern should we put into quantum resistant
signature algorithms?  Is it worth the risk of being on the bleeding edge
here with the hope of winning?  Should we perhaps plan on our manifests (and
images) being signed more than once by the same entity using different
algorithms?

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

---

From: Brendan Moran <[email-masked]>
Date: Fri, 10 Nov 2017 15:35:33 +0000

This is very interesting. I don’t think there’s a problem in terms of multiple signatures so far.

The way that I envision signature verification working is that the device must simply accrue sufficient permissions to install an update:
* Each signer has a set of permissions for each component/storageId
* Each component specifies which permissions are required to install to that component/storageId

The device proceeds, verifying the signatures that it can, aggregating the permissions of valid signatures. Once it has sufficient permissions to meet the permission requirements of the target component/storageId.

If that is the way that the suit client works on a device, then receiving multiple signatures should be reasonable.

To keep the boot loader simple, you can terminate the trust relationship with the update authority in the suit client. If that’s the case, then the boot loader can work with MAC instead. This does not provide for a full secure-boot story, but it does provide for updated cryptographic primitives.

Best Regards,
Brendan Moran

> On 10 Nov 2017, at 14:49, Michael Richardson <[email-masked]> wrote:
>
>
> _______________________________________________
> Suit mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/suit

IMPORTANT NOTICE: The contents of this email and any attachments are confidential and may also be privileged. If you are not the intended recipient, please notify the sender immediately and do not disclose the contents to any other person, use it for any purpose, or store or copy the information in any medium. Thank you.

---

From: Hannes Tschofenig <[email-masked]>
Date: Fri, 10 Nov 2017 16:02:06 +0000

Hi Michael,

Only a quick remark (since I am jetlagged).

When quantum resistance was mentioned in earlier discussions it referred to the use of different algorithms rather than signing multiple times (see Section 10 of RFC 8240).

I haven't looked at the quantum resistant crypto proposals, such as https://tools.ietf.org/html/draft-housley-cms-mts-hash-sig-07, and their performance implications myself. It would indeed be useful/interesting if someone could explore this space a bit more and collect some data. While large signature sizes have been reported those may not necessary matter as much since the firmware updates are less frequent and the firmware images are generally larger (and therefore the overhead from the signature itself may be relatively small).
In general, however, IoT device security will not look great if quantum computers become a reality since IoT devices are typically tailored for the given task. OEMs do not seem to over-dimension the CPU, and other aspects of the system (unless there are other reasons). These devices have limited space for storing keys in secure memory, and switching to other algorithms may not be easy either when hardware crypto is used.

Authorizing a firmware update by multiple parties is a requirement, as explained in https://mailarchive.ietf.org/arch/msg/suit/Hq8NjQJG-EEvHSWjIXMXhCgx1OA. It has surfaced also on the mailing list in discussions before. Hence, I think this functionality should be covered. Authorizing a firmware update by multiple parties will not necessarily imply signing it multiple times (as discussed in Section 3 of RFC 8240). It remains to be seen how often it will be used in low end IoT devices a lot.

Ciao
Hannes

-----Original Message-----
From: Suit [mailto:[email-masked]] On Behalf Of Michael Richardson
Sent: 10 November 2017 22:49
To: [email-masked]
Subject: [Suit] Quantum resistance in firmware formats

The proposed architectures that we have either assume a relatively capable bootloader, or the ability to double buffer images.

One of the advantages of the double buffering is that the firmware update code itself can easily be updated.
Updating a bootloader image may be significantly more risky, and so I imagine that it might rarely or never occur in a device's lifetime.

So my question is: how much concern should we put into quantum resistant signature algorithms?  Is it worth the risk of being on the bleeding edge here with the hope of winning?  Should we perhaps plan on our manifests (and
images) being signed more than once by the same entity using different algorithms?

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

---

From: Russ Housley <[email-masked]>
Date: Fri, 10 Nov 2017 11:37:28 -0500

Please take a look at draft-housley-cms-mts-hash-sig-07.  It show how hash-based signatures would be used with RFC 4108.

Russ

> On Nov 10, 2017, at 9:49 AM, Michael Richardson <[email-masked]> wrote:
> 
>

---

From: Michael Richardson <[email-masked]>
Date: Fri, 10 Nov 2017 12:52:39 -0500

> multiple signatures so far.

Agreed.

    > The way that I envision signature verification working is that the
    > device must simply accrue sufficient permissions to install an update:
    > * Each signer has a set of permissions for each component/storageId *
    > Each component specifies which permissions are required to install to
    > that component/storageId

Sure... but I was specifically thinking is that a manufacturer could
introduce the new Quantum-resistant signatures to the packages as soon as
such a standard (in the form of an OID or IANA allocation) became available.
I think that there is some concern that the quantum-resistant methods may
prove to be secure.  But, if one introduced them soon, and continued to rely
on E{C,d}DSA signatures as well, then there a double hedge against each one
being defeated.
(If both are defeated, then we are in short-term trouble if we have no third
method, but in any case, we have to get third method deployed)

    > To keep the boot loader simple, you can terminate the trust
    > relationship with the update authority in the suit client. If that’s
    > the case, then the boot loader can work with MAC instead. This does not
    > provide for a full secure-boot story, but it does provide for updated
    > cryptographic primitives.

I'm not sure I understand what you are saying here.
I think you are talking about secure boot (validating the image is good
before booting it), vs validating the image is good before storing it to flash?

---

From: Michael Richardson <[email-masked]>
Date: Fri, 10 Nov 2017 12:55:50 -0500

Hannes Tschofenig <[email-masked]> wrote:
    > I haven't looked at the quantum resistant crypto proposals, such as
    > https://tools.ietf.org/html/draft-housley-cms-mts-hash-sig-07, and
    > their performance implications myself. It would indeed be
    > useful/interesting if someone could explore this space a bit more and
    > collect some data. While large signature sizes have been reported those

Agreed.

...

    > Authorizing a firmware update by multiple parties is a requirement, as
    > explained in
    > https://mailarchive.ietf.org/arch/msg/suit/Hq8NjQJG-EEvHSWjIXMXhCgx1OA. It
    > has surfaced also on the mailing list in discussions before. Hence, I
    > think this functionality should be covered. Authorizing a firmware
    > update by multiple parties will not necessarily imply signing it
    > multiple times (as discussed in Section 3 of RFC 8240). It remains to
    > be seen how often it will be used in low end IoT devices a lot.

exactly: multiple signatures from different parties was already in scope.
I'm suggesting that multiple signatures from the same entity should be in
scope.  (Note this also covers some ways of doing key-rollover!)

---

From: Michael Richardson <[email-masked]>
Date: Fri, 10 Nov 2017 13:14:51 -0500

Russ Housley <[email-masked]> wrote:
    > Please take a look at draft-housley-cms-mts-hash-sig-07.  It show how
    > hash-based signatures would be used with RFC 4108.

Yes, I had no doubt that we had options we could include.

For a bootloader that won't get updated ever for the lifetime (20yr) of a
device, do you think that mts-hash SHOULD be a MTI?

(And if not, how would we transition to such a scheme?)

---

From: Brendan Moran <[email-masked]>
Date: Fri, 10 Nov 2017 18:53:28 +0000

> On 10 Nov 2017, at 17:52, Michael Richardson <[email-masked]> wrote:

> scope.  (Note this also covers some ways of doing key-rollover!)

I’m happy with this approach. I believe that the device will need to set the multiple-signatures policy. Otherwise, if one signature algorithm is broken, the forging party can simply designate that one signature is good enough.

> before booting it), vs validating the image is good before storing it to flash?

Yes, the point I am making is that you can handle boot loader verification by using MAC with a key that is shared only between the Suit client and the boot loader. Then, the boot loader trusts the Suit client to validate the update using up-to-date cryptographic primitives. In IoT devices that support a secure execution context, delegating this to the Suit client on behalf of the boot loader may be a more acceptable tradeoff, provided that the signature verification portion of the Suit client runs in the secure context.

In order to convince a boot loader to boot the wrong image, an attacker would require a privilege escalation on the IoT device (access to the Bootloader/Suit client PSK and write access to the firmware partition) in addition to delivery of improperly signed firmware. So far, AES and SHA-2 algorithms appear to be quantum-resistant, so this should be a reasonable approach.

The down-side of this approach is that we lose some defence in depth. If the boot loader can verify the author’s signature directly, then it can distrust the Suit client. This allows multiple independent verifications of the update before it is executed.

So, there is a tradeoff here. Either the bootloader becomes complex and must contain several modern asymmetric cryptographic primitives, or it becomes simple, but trusts the Suit client.

Best Regards,
Brendan

---

From: Carsten Bormann <[email-masked]>
Date: Sat, 11 Nov 2017 06:08:12 +0800

> before booting it), vs validating the image is good before storing it to flash?

I think Brendan is saying that a device that delegates most of its authorization functions to an authorization manager may be able to use its security association with that to check a simple MAC on a signed (here really: MACed) claim by the authorization manager.

Complexity arguments about the format are important.
But we also need to keep in mind that support in the format for more complex validation may not be needed in specific deployments.  As long as there is a way to express simple cases (such as the single-MAC based one above) in the format without undue complexity, there is no problem with supporting more complex validation as well for those deployments that need it and can support it.

Grüße, Carsten

---

From: Russ Housley <[email-masked]>
Date: Fri, 10 Nov 2017 17:48:14 -0500

> device, do you think that mts-hash SHOULD be a MTI?

If we do not deploy a quantum-resistant signature algorithm now, then we will not be able to trust the signature on the firmware that deploys the next generation of cryptographic algorithm after a large-scale quantum computer gets invented.  We need to deploy this protection now.  We will not get enough notice to roll it out later.  Look how long it too to transition away from SHA-1.

Russ

---

From: Madjid Nakhjiri <[email-masked]>
Date: Fri, 10 Nov 2017 22:55:25 +0000

Hi Russ, 

Has been a long time. Are there SOCs out there with quantum resistant
signature algorithm support?

Regards,
Madjid Nakhjiri, 
Sr. Director, ARTIK Security Architect

On 11/10/17, 2:48 PM, "Suit on behalf of Russ Housley"
<[email-masked] on behalf of [email-masked]> wrote:

>If we do not deploy a quantum-resistant signature algorithm now, then we
>will not be able to trust the signature on the firmware that deploys the
>next generation of cryptographic algorithm after a large-scale quantum
>computer gets invented.  We need to deploy this protection now.  We will
>not get enough notice to roll it out later.  Look how long it too to
>transition away from SHA-1.
>
>Russ
>

---

From: Emmanuel Baccelli <[email-masked]>
Date: Sat, 11 Nov 2017 12:47:03 +0100

On Fri, Nov 10, 2017 at 11:08 PM, Carsten Bormann <[email-masked]> wrote:

> [...] As long as there is a way to express simple cases (such as the
> single-MAC based one above) in the format without undue complexity, there
> is no problem with supporting more complex validation as well for those
> deployments that need it and can support it.
>
>
+1

We need to keep in mind the basic case of:

- single authority/signature,
- IoT devices with ~10 KiB RAM and ~100 KiB flash,
- single firmware,

which *cannot* be burdened with too much complexity while we try to cover
more elaborate use-cases.

Best,

Emmanuel

---

From: Carsten Bormann <[email-masked]>
Date: Sat, 11 Nov 2017 21:19:18 +0800

> signature algorithm support?

All of them do support verifying Merkle-tree signatures (as long as they can run programs).

draft-mcgrew-hash-sigs-07 is based on SHA-256, which you can either run in CPU code or may have hardware support for.  Since firmware upgrades don’t happen every second, the overhead for that should be negligible (and is dominated by computing the hash of the firmware itself, anyway).

Grüße, Carsten

---

From: Michael Richardson <[email-masked]>
Date: Sat, 11 Nov 2017 12:47:21 -0500

> signature algorithm support?

As Carsten said, we can run SHA256-based merkle-tree algorithms today.

There are some quantum resistant asymmetric methods which are being
development (NIST is having a competition I think), but my understanding that
none have the confidence we need, and there are IPR on some of them.

So, I think that I agree strongly with Russ.

Russ said:
    >> If we do not deploy a quantum-resistant signature algorithm now, then
    >> we will not be able to trust the signature on the firmware that
    >> deploys the next generation of cryptographic algorithm after a
    >> large-scale quantum computer gets invented.  We need to deploy this
    >> protection now.  We will not get enough notice to roll it out later.
    >> Look how long it too to transition away from SHA-1.

---

From: Michael Richardson <[email-masked]>
Date: Sat, 11 Nov 2017 12:58:09 -0500

Brendan Moran <[email-masked]> wrote:
    mcr> I'm not sure I understand what you are saying here.  I think you are
    mcr> talking about secure boot (validating the image is good before booting
    mcr> it), vs validating the image is good before storing it to flash?

    > Yes, the point I am making is that you can handle boot loader
    > verification by using MAC with a key that is shared only between the
    > Suit client and the boot loader. Then, the boot loader trusts the Suit
    > client to validate the update using up-to-date cryptographic

    > primitives. In IoT devices that support a secure execution context,
    > delegating this to the Suit client on behalf of the boot loader may be
    > a more acceptable tradeoff, provided that the signature verification
    > portion of the Suit client runs in the secure context.

i.e. the SUIT client has to have enough priveledge to update the MAC
     that the boot loader uses to validate the firmware.

In a double-buffer approach, the SUIT client would be in the main firmware.
You are saying, I think that the problem with this approach is that an
exploit again the SUIT client permits the attacker to write/update the MAC
that the boot loader uses, while an asymetric validation by the boot loader
requires no priveledged write.

I feel uncomfortable with the assumption that the SUIT manifest->boot loader
can be run in a trusted environment.  I think we are just trading one set of
potentially reviewable trusted code for another set of unreviewable trusted code.

{I keep typing "boat loader"...}

    > So, there is a tradeoff here. Either the bootloader becomes complex and
    > must contain several modern asymmetric cryptographic primitives, or it
    > becomes simple, but trusts the Suit client.

But, I think that we can consider this all an implementation detail, and that
really it does not affect whether or not we can support a Quantum resistant
signature.

--
]               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: Michael Richardson <[email-masked]>
Date: Sat, 11 Nov 2017 13:12:59 -0500

Emmanuel Baccelli <[email-masked]> wrote:
    > [...] As long as there is a way to express simple cases (such as
    > the single-MAC based one above) in the format without undue
    > complexity, there is no problem with supporting more complex
    > validation as well for those deployments that need it and can
    > support it.

    > which *cannot* be burdened with too much complexity while we try to
    > cover more elaborate use-cases.

So, by "single firmware" are you saying that boot-loader downloads and validates?
Do you think we need need to make transfer protocol accomodations for such a
boot-loader?   This might be LWIG rather than SUIT work.

---

From: Madjid Nakhjiri <[email-masked]>
Date: Wed, 15 Nov 2017 17:39:20 +0000

Hi Michael,

So SHA-256 is just the hash, but I was referring to the signature
algorithm (Lamport, Diffie,
Winternitz, and Merkle (LDWM)) that requires its own public/private key
pair. So I need to use LDWM private key to sign and public key to verify?
The questions are: 1) is LDWM quantum resistant? And more importantly 2)
and 3) here
2) Is there an HSM out there today that hosts a LDWM private key signing
storage and operation?
3) Do I have accelerate the LDWM public key verification or just run it in
SW? And in the latter case, which crypto libraries support LDWM?

If I am going to go to my implementer and ask to implement this, there is
little implementation guidance..

Regards,
Madjid Nakhjiri,

---

From: Madjid Nakhjiri <[email-masked]>
Date: Wed, 15 Nov 2017 17:43:23 +0000

Hi Carsten 

As I mentioned in my other email. Regarding, it is not just the
verification, it is also secure signing and HSM support.
Regarding verification, it won¹t just happen on the occasional firmware
update. If you need to build the entire stack based on this update, then
it will need to happen every time you boot up.

Regards,
Madjid Nakhjiri, 

On 11/11/17, 5:19 AM, "Carsten Bormann" <[email-masked]> wrote:

>draft-mcgrew-hash-sigs-07 is based on SHA-256, which you can either run
>in CPU code or may have hardware support for.  Since firmware upgrades
>don¹t happen every second, the overhead for that should be negligible
>(and is dominated by computing the hash of the firmware itself, anyway).
>
>Grüße, Carsten
>
>

---

From: "Dr. Pala" <[email-masked]>
Date: Thu, 16 Nov 2017 06:02:17 +0800

Hi Madjid,

On 11/16/17 1:43 AM, Madjid Nakhjiri wrote:
> [...]
Not necessarily. In particular, after the firmware is verified for 
installation, the device could use simpler mechanisms (e.g., HMAC w/ a 
device-specific secret - hopefully HW protected like we have in many 
chips today) to quickly validate that the image has not changed across 
boots (that is actually all is needed after the initial validation has 
occurred during "installation").

Cheers,
Max

-- 
Best Regards,
Massimiliano Pala, Ph.D.
OpenCA Labs Director
OpenCA Logo

---

From: Brendan Moran <[email-masked]>
Date: Thu, 16 Nov 2017 15:26:30 +0000

Hi Max,

> On 15 Nov 2017, at 22:02, Dr. Pala <[email-masked]> wrote:
>> [...]
> Not necessarily. In particular, after the firmware is verified for installation, the device could use simpler mechanisms (e.g., HMAC w/ a device-specific secret - hopefully HW protected like we have in many chips today) to quickly validate that the image has not changed across boots (that is actually all is needed after the initial validation has occurred during "installation”).

I’ve discussed this option a bit in the past. The challenge here is that there are two steps in the chain of trust. The boot loader trusts the verifier. The verifier trusts the update authority(s). Now, if the verifier is in the boot loader, this is a single trust relationship. However, if the verifier lives outside the boot loader, then things are more complex. The boot loader must trust the application. This suggests that the application will require some sort of secure processing environment and some form of attestation.

Best Regards,
Brendan

---

From: David Brown <[email-masked]>
Date: Thu, 16 Nov 2017 10:31:43 -0700

On Thu, Nov 16, 2017 at 03:26:30PM +0000, Brendan Moran wrote:
>I’ve discussed this option a bit in the past. The challenge here is
>that there are two steps in the chain of trust. The boot loader
>trusts the verifier. The verifier trusts the update authority(s).
>Now, if the verifier is in the boot loader, this is a single trust
>relationship. However, if the verifier lives outside the boot loader,
>then things are more complex. The boot loader must trust the
>application. This suggests that the application will require some
>sort of secure processing environment and some form of attestation.

If we have the situation where it is the trusted bootloader that is
doing the HMAC, it also has to have the capability to verify the
signature, which reduces the benefit of using the HMAC for
verification.

It can still be useful, though, if considered a performance
improvement.  For example, a small implementation of Ed25519 might
take several seconds to verify a signature.  If the bootloader could
verify the signature once, and then write an HMAC with a device key
only it has access to, subsequent boots could be much faster.

David

---

From: Michael Richardson <[email-masked]>
Date: Thu, 16 Nov 2017 12:45:00 -0500

Madjid Nakhjiri <[email-masked]> wrote:
    > algorithm (Lamport, Diffie, Winternitz, and Merkle (LDWM)) that
    > requires its own public/private key pair.

yes, but LDWM is repeated hashing in a particular way.
Yes, you are right, it still has a private key, which the generator of the
firmware needs to know.

    > key to sign and public key to verify?  The questions are: 1) is LDWM
    > quantum resistant?

That's my understanding.

    > And more importantly 2) and 3) here 2) Is there an
    > HSM out there today that hosts a LDWM private key signing storage and
    > operation?

I'm sure that one could be built.
I'll bet that https://cryptech.is/ could be adapted to keep the private key.

---

From: Michael Richardson <[email-masked]>
Date: Thu, 16 Nov 2017 17:12:27 -0500

Brendan Moran <[email-masked]> wrote:
    > that there are two steps in the chain of trust. The boot loader trusts
    > the verifier. The verifier trusts the update authority(s). Now, if the
    > verifier is in the boot loader, this is a single trust
    > application. This suggests that the application will require some sort
    > of secure processing environment and some form of attestation.

You describe the situation well.

As far as I can see, this has no affect on the shape of the bits on wire.
Do you agree that this is an implementation issue.  Not a trivial one, but
never-the-less, not "our" problem.

(And yes, it's possible to do it wrong and wind up having very long boot
times as a result)

It might matter as to how many firmware packages are sent, as perhaps one of
them needs to be signed in a teep-happy way either in-addition-to, or
instead-of, the other signature.

So in the end, the requirement for multiple signatures seems to capture this
situation?

---

From: Brendan Moran <[email-masked]>
Date: Tue, 28 Nov 2017 16:53:18 +0000

> On 16 Nov 2017, at 22:12, Michael Richardson <[email-masked]> wrote:
>
>

I agree. This has no bearing on the design of the manifest format. It may have some bearing on the architecture, but it’s an open question for system designers. They can choose the trade-off they want.

> (And yes, it's possible to do it wrong and wind up having very long boot

Definitely.

> So in the end, the requirement for multiple signatures seems to capture this

Agreed. Multi-sig is probably the right answer.

Best Regards,
Brendan