Subject: Re: [CFRG] NSA vs. hybrid

From: Mike Ounsworth <[email-masked]>
Date: Sat, 4 Dec 2021 20:32:56 +0000

Responding to a few different branches of this thread:

> "Scott Fluhrer (sfluhrer)" <[email-masked]> Sat, 13 November 2021 18:50 UTC
> One complication that certificates have over KEMs (in the context of TLS) is that there are more parties involved.

In addition to what Scott mentioned, there is also multiple layers of standards bodies involved. A bit of a squinty view:

1. CFRG will make cryptographic recommendations.
2. LAMPS will implement these recommendations for PKI and S/MIME.
3. CA/Browser Forum will make these new algs and cert types legal for publicly-trusted CAs.
4. Root keygen ceremonies need to happen under the newly-minted CA/B rules.
5. New root certs need to get included in browser trust stores.

Only then can we start actually using them. These are sequential steps that could take 1 - 2 years each. By my reckoning, if we start now, we have a 5 - 10 year road until we can actually use this on the web. I haven't even considered FIPS or HSM development lead times here...

> "Blumenthal, Uri - 0553 - MITLL" <[email-masked]> Thu, 02 December 2021 16:45 UTC
> Here are the possibilities and their relation to the usefulness of the Hybrid approach.
>1.  CRQC arrived, Classic hold against classic attacks,  PQ algorithms hold - Hybrid is useless.
>2. CRQC arrived, Classic hold against classic attacks, PQ algorithms fail - Hybrid is useless.
>3. CRQC arrived, Classic broken against classic attacks,  PQ algorithms hold - Hybrid is useless.
>4. CRQC arrived, Classic hold against classic attacks,  PQ algorithms broken - Hybrid useless.
>5. CRQC doesn't arrive, Classic hold against classic attacks,  PQ algorithms hold - Hybrid is useless.
>6. CRQC doesn't arrive, Classic hold against classic attacks,  PQ algorithms broken - Hybrid helps.
>7. CRQC doesn't arrive, Classic broken against classic attacks,  PQ algorithms hold - Hybrid is useless.
>8. CRQC doesn't arrive, Classic broken against classic attacks,  PQ algorithms broken - Hybrid is useless.
>You can see from the above that Hybrid would be of benefit in only one case out of eight, one I personally consider among the least probable.

IMO the one thing we *do know* is that PQ crypto libs will have implementation bugs, which means we *will* have to contend with case 6, at least transitively. Which, given your language, gives us a 100% chance that hybrid helps :)

> "Blumenthal, Uri - 0553 - MITLL" <[email-masked]> Thu, 02 December 2021 21:22 UTC
> I'm asking why the current Classic algorithms have not been paired using the same approach - as they have been around from 10 to 25 years longer than, e.g.,  NTRU.

Let's say this reasoning is correct; let's say that in retrospect we should have layered new ECC implementations with RSA for some transition period, isn't that more reason to develop hybrid mechanisms now so that they are available the next time we need to transition from an old battle-tested thing to a newer thing?

---
Mike Ounsworth
Software Security Architect, Entrust

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: Phillip Hallam-Baker <[email-masked]>
Date: Mon, 6 Dec 2021 01:27:53 -0500

You are missing one of the biggest steps which is availability of FIPS 140
validated HSMs without which nothing is going to be happening.

Nor is it automatic that the WebPKI will adopt PQC just because of
something CFRG does.

X448 and Ed448 have been out for years. Does anyone know of HSMs for
either of them?

Don't forget that HSMs use crypto to secure keys internally and so they
need multiple layers of validation. People are going to have to work on
timing attacks from scratch again.

The other point to consider is that the WebPKI only needs signatures and
there are other, simpler ways to achieve PQC hardening. We could heavily
modify Certificate Transparency for instance.

On Sat, Dec 4, 2021 at 3:33 PM Mike Ounsworth <Mike.Ounsworth=
[email-masked]> wrote:

> > One complication that certificates have over KEMs (in the context of
> TLS) is that there are more parties involved.
>
> In addition to what Scott mentioned, there is also multiple layers of
> standards bodies involved. A bit of a squinty view:
>
> Only then can we start actually using them. These are sequential steps
> that could take 1 - 2 years each. By my reckoning, if we start now, we have
> a 5 - 10 year road until we can actually use this on the web. I haven't
> even considered FIPS or HSM development lead times here...
>
>
>
>
> >You can see from the above that Hybrid would be of benefit in only one
> case out of eight, one I personally consider among the least probable.
>
>
> IMO the one thing we *do know* is that PQ crypto libs will have
> implementation bugs, which means we *will* have to contend with case 6, at
> least transitively. Which, given your language, gives us a 100% chance that
> hybrid helps :)
>
>
>
> > I'm asking why the current Classic algorithms have not been paired using
> the same approach - as they have been around from 10 to 25 years longer
> than, e.g.,  NTRU.
>
> Let's say this reasoning is correct; let's say that in retrospect we
> should have layered new ECC implementations with RSA for some transition
> period, isn't that more reason to develop hybrid mechanisms now so that
> they are available the next time we need to transition from an old
> battle-tested thing to a newer thing?
>
> ---
> Mike Ounsworth
> 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.
>
> _______________________________________________
> CFRG mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Mon, 6 Dec 2021 14:21:03 +0000

> The other point to consider is that the WebPKI only needs signatures and there are other,

> simpler ways to achieve PQC hardening. 

I’m not sure I follow. 

In my understanding, PQ hardening (especially for signatures) requires using PQ algorithms – what other ways are there?

> We could heavily modify Certificate Transparency for instance.

How would that help…?

 

On Sat, Dec 4, 2021 at 3:33 PM Mike Ounsworth <Mike.Ounsworth=[email-masked]> wrote:

---
Mike Ounsworth

---

From: Natanael <[email-masked]>
Date: Mon, 6 Dec 2021 18:09:04 +0100

Den mån 6 dec. 2021 15:21Blumenthal, Uri - 0553 - MITLL <[email-masked]>
skrev:

> there are other,
> In my understanding, PQ hardening (especially for signatures) requires
> using PQ algorithms – what other ways are there?
>
>
>

This is straying away from the main topic, but there is "quantum annoyance"
as a step in between quantum resistant or quantum weak.

In other words, systems where every session has to be broken individually
even if you have a quantum computer, rather than just breaking one key once
and then reading all sessions.

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Mon, 6 Dec 2021 17:42:18 +0000

>>> there are other, simpler ways to achieve PQC hardening. 
>>

Ah, "quantum annoyance". I did not think it's applicable to signatures.

> In other words, systems where every session has to be broken
> individually even if you have a quantum computer, rather than
> just breaking one key once and then reading all sessions. 

Yes. But as I said, while I have my personal opinion about this defense mechanism, it may work for key exchange, but IMHO not for signatures, unless in some point up the chain a "true" PQ signature is used - and even then, people with sensitive information to protect and worry about, cannot rely on this kind of "annoyance" defense.