Subject: Re: [Secdispatch] Clarification Question for the Comment from Eric Rescorla (

From: Carrick Bartle <[email-masked]>
Date: Thu, 2 Jan 2020 10:45:21 -0800

> it's not useful to be prepared in that fashion
> unless the algorithm that you are deploying is the one that is
> eventually selected, because otherwise you just have to start over
> once the selection is made.

Just to be specific, do you mean, for instance, all the certificates with the PQ algorithm that wasn't chosen would have to be revoked?

> the primary rationale for doing composite key exchange now is to
> defend against retrospective attacks in case a quantum computer exists
> in the future. In this setting, it isn't critically important to have
> the PQ algorithm be the one we eventually land on, because each
> connection is separately negotiated and as long as the PQ algorithm
> has some security, you're getting benegit,.

In that case, would it make sense to take the next step with drafting an intended standard for composite key exchanges (that is PQ algorithm-agnostic)? If not, why not?

Carrick

> On Dec 25, 2019, at 5:57 PM, Eric Rescorla <[email-masked]> wrote:
> 
> On Mon, Dec 23, 2019 at 8:38 PM Carrick Bartle <[email-masked] <mailto:[email-masked]>> wrote:
> > How can it be true that it's too early to start developing a protocol
> > for composite keys and signatures for Web PKI when Cloudflare and
> > Google have already finished a round of experiments with composite key
> > exchanges? Maybe I'm reading too much into it, but the existence of
> > those experiments suggested to me that the need for composite/composite
> > implementations was imminent. (I understand that the draft in question
> > concerns signatures, not key exchanges, but apparently there isn't
> > even a draft for the latter yet.)
> 
> ISTM that these cases are pretty different, in a number of respects.
> 
> First, the primary rationale for doing composite key exchange now is to
> defend against retrospective attacks in case a quantum computer exists
> in the future. In this setting, it isn't critically important to have
> the PQ algorithm be the one we eventually land on, because each
> connection is separately negotiated and as long as the PQ algorithm
> has some security, you're getting benegit,.
> 
> The primary rationale for doing PQ authentication now (or for that
> matter composite authentication) is to be prepared for the day when QC
> exists and we are therefore unable to rely on classical
> algorithms. However, it's not useful to be prepared in that fashion
> unless the algorithm that you are deploying is the one that is
> eventually selected, because otherwise you just have to start over
> once the selection is made.
> 
> Moreover, in order to be truly prepared, what you need isn't
> principally relying party deployment, but rather authenticating party
> (in the case of the WebPKI, server-side) deployment. The reason for
> this is that in the world where a QC exists, you don't have protection
> until the relying party refuses to accept the classical credential
> [0], and at present, any client which does so will effectively be
> unable to communicate. And in order to make that happen, relying
> parties will have to require a post-quantum algorithm (most likely as
> a composite) and that's something I don't expect them to be willing to do
> until there's widespread agreement on what that algorithm should be.
> 
> 
> > If not now, when? After NIST crowns a winner? I don't see why it's
> > necessary to wait that long given that the proposed solutions are
> > algorithm-independent. And since the standardization process takes a
> > while, won't waiting until then mean that there won't be a standard
> > until after it's needed?
> 
> No, i don't think so.
> 
> For the reasons above, ISTM that real deployment will have to wait
> until we have a selected algorithm. One could, as you suggest, deploy
> some sort of multi-algorithm container, but IMO we will be far better
> off just deploying new composite algorithms as if the were single
> new algorithms, in the same way as we have done for key establishment.
> 
> For this reason, I think we ought to wait until there is a consensus
> PQ signature algorithm, at least for the WebPKI.
> 
> -Ekr
> 
> [0] This is why this kind of composite isn't helpful in the world
> where a secret QC exists not.
> 
> 
> _______________________________________________
> Secdispatch mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/secdispatch

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 2 Jan 2020 10:50:58 -0800

On Thu, Jan 2, 2020 at 10:45 AM Carrick Bartle <[email-masked]>
wrote:

> Just to be specific, do you mean, for instance, all the certificates with
> the PQ algorithm that wasn't chosen would have to be revoked?
>

Probably not.

At a high level, there are two possible designs:

1. A certificate which has a composite signature in place of the classical
signature and thus cannot be validated by old clients.
2. A certificate which has a PQ signature somehow attached in a way that it
leaves the classical signature valid (as in an extension).

In the former case, every server would need two certificates (one composite
and one classical) and use signature_algorithms to distinguish which one to
use. Once clients stopped liking the old PQ algorithm, then those composite
certificates would become irrelevant and just be unused. In the latter
case, the certificates would continue to be valid and the client could just
ignore the PQ part of the signature.

What "start over" means in this case is get to the point where there is a
critical mass of client and server deployment, a process which takes time.

> In that case, would it make sense to take the next step with drafting an
> intended standard for composite key exchanges (that is PQ
> algorithm-agnostic)? If not, why not?
>

I think not, at least for TLS. The consensus of implementors seems to be
that it's better to just cast composite algorithms as if they were new DH
groups, so there's not a huge amount of leverage in a generic mechanism.

-Ekr

Carrick
> On Mon, Dec 23, 2019 at 8:38 PM Carrick Bartle <[email-masked]>
> wrote:

---

From: Carrick Bartle <[email-masked]>
Date: Thu, 2 Jan 2020 11:19:49 -0800

> What "start over" means in this case is get to the point where there is a critical mass of client and server deployment, a process which takes time.

I see.

> I think not, at least for TLS. The consensus of implementors seems to be that it's better to just cast composite algorithms as if they were new DH groups, so there's not a huge amount of leverage in a generic mechanism.

My understanding is that the Cloudflare-Google implementation generated two separate shared secrets. Also this draft references several different "ad hoc" approaches in implementations: https://tools.ietf.org/html/draft-stebila-tls-hybrid-design-01 <https://tools.ietf.org/html/draft-stebila-tls-hybrid-design-01>.

Carrick

> On Jan 2, 2020, at 10:50 AM, Eric Rescorla <[email-masked]> wrote:
> 
> 
> 
> On Thu, Jan 2, 2020 at 10:45 AM Carrick Bartle <[email-masked] <mailto:[email-masked]>> wrote:
> 1. A certificate which has a composite signature in place of the classical signature and thus cannot be validated by old clients.
> 2. A certificate which has a PQ signature somehow attached in a way that it leaves the classical signature valid (as in an extension).
> 
> In the former case, every server would need two certificates (one composite and one classical) and use signature_algorithms to distinguish which one to use. Once clients stopped liking the old PQ algorithm, then those composite certificates would become irrelevant and just be unused. In the latter case, the certificates would continue to be valid and the client could just ignore the PQ part of the signature.
> 
> What "start over" means in this case is get to the point where there is a critical mass of client and server deployment, a process which takes time.
> 
> I think not, at least for TLS. The consensus of implementors seems to be that it's better to just cast composite algorithms as if they were new DH groups, so there's not a huge amount of leverage in a generic mechanism.
> 
> -Ekr
> 
> Carrick
> 
> 
> 
> 
>> On Dec 25, 2019, at 5:57 PM, Eric Rescorla <[email-masked] <mailto:[email-masked]>> wrote:
>> 
>> [email-masked] <mailto:[email-masked]>
>> https://www.ietf.org/mailman/listinfo/secdispatch <https://www.ietf.org/mailman/listinfo/secdispatch>

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 2 Jan 2020 12:11:24 -0800

On Thu, Jan 2, 2020 at 11:19 AM Carrick Bartle <[email-masked]>
wrote:

> My understanding is that the Cloudflare-Google implementation generated
> two separate shared secrets. Also this draft references several different
> "ad hoc" approaches in implementations:
> https://tools.ietf.org/html/draft-stebila-tls-hybrid-design-01.
>

Well, yes, but on the wire it's packaged as a single group and key share.

https://blog.cloudflare.com/the-tls-post-quantum-experiment/

-Ekr

> 2. A certificate which has a PQ signature somehow attached in a way that
> it leaves the classical signature valid (as in an extension).
>
> In the former case, every server would need two certificates (one
> composite and one classical) and use signature_algorithms to distinguish
> which one to use. Once clients stopped liking the old PQ algorithm, then
> those composite certificates would become irrelevant and just be unused. In
> the latter case, the certificates would continue to be valid and the client
> could just ignore the PQ part of the signature.
>

---

From: Douglas Stebila <[email-masked]>
Date: Thu, 2 Jan 2020 20:13:42 -0500

> I think not, at least for TLS. The consensus of implementors seems to be that it's better to just cast composite algorithms as if they were new DH groups, so there's not a huge amount of leverage i…

We'll soon be pushing a revision of https://tools.ietf.org/html/draft-stebila-tls-hybrid-design-01 that focuses on doing composite algorithms as new DH groups.

Douglas

---

From: Mike Ounsworth <[email-masked]>
Date: Wed, 8 Jan 2020 16:26:21 +0000

Ekr said:

In the former case, every server would need two certificates (one composite and one classical) and use signature_algorithms to distinguish which one to use.

I agree with your conclusion about composite breaking backwards compatibility.

That said, I caution us against thinking about this problem only in terms of a single use-case or protocol (TLS in this case).  I want to keep this discussion considering certificate use-cases that don’t have algorithm negotiation mechanisms, for example code-signing, S/MIME, PKI smart cards, file encryption, whatever uses certificates in a way that isn’t “online”.  I would love to see the IETF provide a solution that applies to certificates and signatures in general, rather than punting this problem to each protocol design team to solve independently.

This conclusion – that you’re only getting security value once a PQ exists, and any alg implementation we chose today will likely be obsolete by then -- is probably right for browsers, but what about IoT devices validating their firmware signature on boot? Or PKI smartcards?  Or legal contracts signed under eIDAS?  Today we are creating certificates and signed data objects that will outlive the advent of a QC.  I think that blurs closer to the “retrospective attack” scenario that you used for motivating composite key exchange.

While I’m aware that I’m using motivating examples from outside the IETF, I think we have an opportunity to define a standard that is generic for all (or at least most) certificate use-cases.  Let’s do the debate here about carrying multiple signatures and the semantics of validating it, rather than pushing it out to each protocol design team to debate independently.

---
Mike Ounsworth | Office: +1 (613) 270-2873

From: Secdispatch <[email-masked]> On Behalf Of Eric Rescorla
Sent: January 2, 2020 2:11 PM
To: Carrick Bartle <[email-masked]>
Cc: Dr. Pala <[email-masked]>; Salz, Rich <[email-masked]>; IETF SecDispatch <[email-masked]>; Stephen Farrell <[email-masked]>
Subject: [EXTERNAL]Re: [Secdispatch] Clarification Question for the Comment from Eric Rescorla (

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

On Thu, Jan 2, 2020 at 11:19 AM Carrick Bartle <[email-masked]<mailto:[email-masked]>> wrote:
What "start over" means in this case is get to the point where there is a critical mass of client and server deployment, a process which takes time.

I see.

My understanding is that the Cloudflare-Google implementation generated two separate shared secrets. Also this draft references several different "ad hoc" approaches in implementations: https://tools.ietf.org/html/draft-stebila-tls-hybrid-design-01.

-Ekr

Carrick

On Jan 2, 2020, at 10:50 AM, Eric Rescorla <[email-masked]<mailto:[email-masked]>> wrote:

On Thu, Jan 2, 2020 at 10:45 AM Carrick Bartle <[email-masked]<mailto:[email-masked]>> wrote:

Probably not.

-Ekr

Carrick

On Dec 25, 2019, at 5:57 PM, Eric Rescorla <[email-masked]<mailto:[email-masked]>> wrote:

No, i don't think so.

-Ekr

_______________________________________________
Secdispatch mailing list
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/secdispatch

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 8 Jan 2020 08:43:45 -0800

Mike,

The context of this thread is my comments at the mic that I didn't think
this made much sense for the WebPKI. I haven't fully thought through the
non-WebPKI cases.

With that said, if you are concerned about long-term signatures, I don't
really understand the point of a hybrid scheme, given that we don;'t really
have that high confidence in any PQ signature system other than hash
signatures, so why not *just* use hash signatures?

-Ekr

On Wed, Jan 8, 2020 at 8:26 AM Mike Ounsworth <
[email-masked]> wrote:

> which one to use.
> That said, I caution us against thinking about this problem only in terms
> of a single use-case or protocol (TLS in this case).  I want to keep this
> discussion considering certificate use-cases that don’t have algorithm
> negotiation mechanisms, for example code-signing, S/MIME, PKI smart cards,
> file encryption, whatever uses certificates in a way that isn’t “online”.
> I would love to see the IETF provide a solution that applies to
> certificates and signatures in general, rather than punting this problem to
> each protocol design team to solve independently.
>
>
>
>
>
> This conclusion – that you’re only getting security value once a PQ
> exists, and any alg implementation we chose today will likely be obsolete
> by then -- is probably right for browsers, but what about IoT devices
> validating their firmware signature on boot? Or PKI smartcards?  Or legal
> contracts signed under eIDAS?  Today we are creating certificates and
> signed data objects that will outlive the advent of a QC.  I think that
> blurs closer to the “retrospective attack” scenario that you used for
> motivating composite key exchange.
>
>
>
> While I’m aware that I’m using motivating examples from outside the IETF,
> I think we have an opportunity to define a standard that is generic for all
> (or at least most) certificate use-cases.  Let’s do the debate here about
> carrying multiple signatures and the semantics of validating it, rather
> than pushing it out to each protocol design team to debate independently.
>
>
>
>
>
> ---
>
> *Mike* Ounsworth *|* Office: +1 (613) 270-2873
>
>
>
> *From:* Secdispatch <[email-masked]> *On Behalf Of *Eric
> Rescorla
> *Sent:* January 2, 2020 2:11 PM
> *To:* Carrick Bartle <[email-masked]>
> *Cc:* Dr. Pala <[email-masked]>; Salz, Rich <[email-masked]>; IETF
> SecDispatch <[email-masked]>; Stephen Farrell <
> [email-masked]>
> *Subject:* [EXTERNAL]Re: [Secdispatch] Clarification Question for the
> Comment from Eric Rescorla (
>
>
>
> *WARNING:* This email originated outside of Entrust Datacard.
> *DO NOT CLICK* links or attachments unless you trust the sender and know
> the content is safe.
> ------------------------------
>
>
>
>
>

---

From: Mike Ounsworth <[email-masked]>
Date: Wed, 8 Jan 2020 17:10:11 +0000

Yeah, hash-based is probably a good fit for many use-cases.

My discussions with other parties around HBS have gotten stuck around two points:

Stateless vs stateful: Stateless: big&slow. Stateful: distributing keys across load-balancers or switch-over to a disaster-recovery site during a power-outage becomes tricky.  There are some Merkle tree-splitting techniques that alleviate this at the cost of needing to decide at keygen time how many copies of the private key you want.  Also, if your end-entity has the risk of abrupt power-offs, then you have the risks described in McGrew et al “State Management for Hash-Based Signatures”.  So you probably don’t want stateful end-entities.  Do you then want heterogenous PKI chains rooted in HBS with something else below?  There’s just a lot of unanswered questions.

Migration: Max Pala (co-author on the Composite Signatures draft) wants something where you have multiple signatures on an object, and the verifier checks as many as they have implementations of.  Yes, there’s a breaking change when you cut over to using the composite structure, but after that you can do staged migrations of client software and signing algorithms.  If widely adopted, this could even help the next time we need to do a SHA1 -> SHA2 type migration (i.e. a generic composite mechanism could have utility beyond the PQ migration).

---

From: Eric Rescorla <[email-masked]>
Sent: January 8, 2020 10:44 AM
To: Mike Ounsworth <[email-masked]>
Cc: Carrick Bartle <[email-masked]>; Dr. Pala <[email-masked]>; Salz, Rich <[email-masked]>; IETF SecDispatch <[email-masked]>; Stephen Farrell <[email-masked]>
Subject: Re: [EXTERNAL]Re: [Secdispatch] Clarification Question for the Comment from Eric Rescorla (

Mike,

The context of this thread is my comments at the mic that I didn't think this made much sense for the WebPKI. I haven't fully thought through the non-WebPKI cases.

With that said, if you are concerned about long-term signatures, I don't really understand the point of a hybrid scheme, given that we don;'t really have that high confidence in any PQ signature system other than hash signatures, so why not *just* use hash signatures?

-Ekr

On Wed, Jan 8, 2020 at 8:26 AM Mike Ounsworth <[email-masked]<mailto:[email-masked]>> wrote:
Ekr said:

---

From: Secdispatch <[email-masked]<mailto:[email-masked]>> On Behalf Of Eric Rescorla
Sent: January 2, 2020 2:11 PM
To: Carrick Bartle <[email-masked]<mailto:[email-masked]>>
Cc: Dr. Pala <[email-masked]<mailto:[email-masked]>>; Salz, Rich <[email-masked]<mailto:[email-masked]>>; IETF SecDispatch <[email-masked]<mailto:[email-masked]>>; Stephen Farrell <[email-masked]<mailto:[email-masked]>>
Subject: [EXTERNAL]Re: [Secdispatch] Clarification Question for the Comment from Eric Rescorla (

I see.

-Ekr

Carrick

Probably not.

-Ekr

Carrick

No, i don't think so.

-Ekr