Subject: Re: [Secdispatch] Problem statement for post-quantum multi-algorithm PKI

From: "Dr. Pala" <[email-masked]>
Date: Thu, 12 Sep 2019 08:38:52 -0600

Hi SecDispatch, Mike,

Our industry (Cable) is working on this problem already - some of our 
members have started investigating few things in the post-quantum field 
and in particular how to protect our PKIs in this uncertain environment.

With few billions certificates issued across the industry, we heavily 
rely on certificates for device authentication and, therefore, we need 
to work on a solution today.

For us, the use of Composite Crypto is quite an interesting path to 
pursue because it provides an easy way to protect today our PKIs against 
the factorization threat (not only certificates, but all the data 
structures for PKIX) thus allowing to verify the authentication with 
Post-Quantum algorithms when we will need to make the switch (deferred 
Algorithm Agility).

We intend to support this idea and actively deploy it for our PKIs and 
eventually expand the adoption of this approach in other environments we 
are engaged in (e.g., medical devices, cellular networks, WiFi Alliance 
and WBA, etc.)

Looking forward to find a good home for this project within the IETF - a 
simple but powerful tool for our "PKI toolboxes"

Cheers,
Max

> Hi SecDispatch,
>
> This got bounced here from LAMPS because the scope is potentially more than a "limited" pkix change, and because this needs multi-WG visibility to decide on a category of solution.
>
>
>
> Background / history
> --------------------
>
> The Post-Quantum community (for example, surrounding the NIST PQC competition), is pushing for "hybridized" crypto that combines RSA/ECC with new primitives in order to hedge our bets against both quantum adversaries, and also algorithmic / mathematical breaks of the new primitives.
>
>
> A year and a half ago, a draft was put to LAMPS for putting PQ public key and signatures into X.509v3 extensions. This draft has been allowed to expire, but is being pursued at the ITU.
> https://datatracker.ietf.org/doc/draft-truskovsky-lamps-pq-hybrid-x509/
>
>
> Earlier this year, a new draft was put to LAMPS for defining "composite" public key and signature algorithms that, essentially, concatenate multiple crypto algorithms into a single key or signature octet string. This draft stalled in LAMPS over whether it is the correct overall approach.
> https://datatracker.ietf.org/doc/draft-ounsworth-pq-composite-sigs/
>
>
> Now I'm taking a step back and submitting a draft that acts as a semi-formal problem statement, and an overview of the three main categories of solutions.
> https://datatracker.ietf.org/doc/draft-pq-pkix-problem-statement/
>
>
>
>
> My Opinion
> ----------
>
> Personally, I'm fairly agnostic to the chosen solution, but feel that we need some kind of standard(s) around the post-quantum transition for certificates and PKI. Personally, I feel that Composite is mature enough as an idea to standardize as a tool in our toolbox for contexts where it makes sense, even if a different mechanism is preferred for TLS and IPSEC/IKE.
>
>
>
>
> Requested action from SECDISPATCH
> ---------------------------------
>
> 1. Feedback on the problem statement draft.https://datatracker.ietf.org/doc/draft-pq-pkix-problem-statement/
>
> 2. Discussion of how to progress this.
>
>
>
>
> PS I'm a new IETF'er, please be gentle :P
>
> Thanks,
> - - -
> Mike Ounsworth | Software Security Architect
> Entrust Datacard

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

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Thu, 12 Sep 2019 19:08:49 +0000

I agree that this is an important problem to solve.

One might think we have plenty of time, given that Real Quantum Computers are, more than likely, more than 10 years away, and even once you have one, you cannot use your Quantum Computer to break the authentication of recorded conversations.

On the other hand, authentication also brings in additional issues; instead of having a two party system (where as long as both the client and the server support a postquantum algorithm, they can negotiate it), we now have an (at least) three party system, the client, the server, and the CA.  this additional party makes the upgrade path more complicated.  So, while we have more time, we may need it.

I don’t think it’s too early to start thinking about the issues..

From: Secdispatch <[email-masked]> On Behalf Of Dr. Pala
Sent: Thursday, September 12, 2019 10:39 AM
To: [email-masked]
Subject: Re: [Secdispatch] Problem statement for post-quantum multi-algorithm PKI

Hi SecDispatch, Mike,

Our industry (Cable) is working on this problem already - some of our members have started investigating few things in the post-quantum field and in particular how to protect our PKIs in this uncertain environment.

With few billions certificates issued across the industry, we heavily rely on certificates for device authentication and, therefore, we need to work on a solution today.

For us, the use of Composite Crypto is quite an interesting path to pursue because it provides an easy way to protect today our PKIs against the factorization threat (not only certificates, but all the data structures for PKIX) thus allowing to verify the authentication with Post-Quantum algorithms when we will need to make the switch (deferred Algorithm Agility).

We intend to support this idea and actively deploy it for our PKIs and eventually expand the adoption of this approach in other environments we are engaged in (e.g., medical devices, cellular networks, WiFi Alliance and WBA, etc.)

Looking forward to find a good home for this project within the IETF - a simple but powerful tool for our "PKI toolboxes"

Cheers,
Max

Hi SecDispatch,

Background / history

--------------------

My Opinion

----------

1. Feedback on the problem statement draft. https://datatracker.ietf.org/doc/draft-pq-pkix-problem-statement/

Thanks,

- - -

Entrust Datacard

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

---

From: Stephen Farrell <[email-masked]>
Date: Thu, 12 Sep 2019 20:28:15 +0100

Hiya,

> I agree that this is an important problem to solve.

Depending, on the "this," I agree or disagree:-)

Discussion of how to get what PKI offers in a world where
current asymmetric algorithms might be weak and where
quantum-resistant, but new, algorithms are emerging, is
an excellent topic to start to consider.

I also think it seems a bit mad to consider x.509 as the
main thing to consider so I'm not at all keen on seeing
this problem space as being one where all we need is yet
another sticking plaster for x.509. That said, I do get
that people invested in x.509-based PKI may reasonably
prefer less-change to more-change, I just think we may
be sad if we miss another opportunity to move on leaving
behind some of this 1980's baggage.

Cheers,
S.

> 
> One might think we have plenty of time, given that Real Quantum
> Computers are, more than likely, more than 10 years away, and even
> once you have one, you cannot use your Quantum Computer to break the
> authentication of recorded conversations.
> 
> On the other hand, authentication also brings in additional issues;
> instead of having a two party system (where as long as both the
> client and the server support a postquantum algorithm, they can
> negotiate it), we now have an (at least) three party system, the
> client, the server, and the CA.  this additional party makes the
> upgrade path more complicated.  So, while we have more time, we may
> need it.
> 
> From: Secdispatch <[email-masked]> On Behalf Of Dr.
> Pala Sent: Thursday, September 12, 2019 10:39 AM To:
> [email-masked] Subject: Re: [Secdispatch] Problem statement for
> post-quantum multi-algorithm PKI
> 
> 
> Hi SecDispatch, Mike,
> 
> members have started investigating few things in the post-quantum
> field and in particular how to protect our PKIs in this uncertain
> environment.
> 
> rely on certificates for device authentication and, therefore, we
> need to work on a solution today.
> 
> pursue because it provides an easy way to protect today our PKIs
> against the factorization threat (not only certificates, but all the
> data structures for PKIX) thus allowing to verify the authentication
> with Post-Quantum algorithms when we will need to make the switch
> (deferred Algorithm Agility).
> 
> We intend to support this idea and actively deploy it for our PKIs
> and eventually expand the adoption of this approach in other
> environments we are engaged in (e.g., medical devices, cellular
> networks, WiFi Alliance and WBA, etc.)
> 
> Looking forward to find a good home for this project within the IETF
> - a simple but powerful tool for our "PKI toolboxes"
> 
> Cheers, Max
> 
> 
> 
> Hi SecDispatch,
> 
> 
> 
> This got bounced here from LAMPS because the scope is potentially
> more than a "limited" pkix change, and because this needs multi-WG
> visibility to decide on a category of solution.
> 
> 
> 
> 
> 
> 
> 
> Background / history
> 
> --------------------
> 
> 
> 
> The Post-Quantum community (for example, surrounding the NIST PQC
> competition), is pushing for "hybridized" crypto that combines
> RSA/ECC with new primitives in order to hedge our bets against both
> quantum adversaries, and also algorithmic / mathematical breaks of
> the new primitives.
> 
> 
> 
> 
> 
> A year and a half ago, a draft was put to LAMPS for putting PQ public
> key and signatures into X.509v3 extensions. This draft has been
> allowed to expire, but is being pursued at the ITU.
> 
> Earlier this year, a new draft was put to LAMPS for defining
> "composite" public key and signature algorithms that, essentially,
> concatenate multiple crypto algorithms into a single key or signature
> octet string. This draft stalled in LAMPS over whether it is the
> correct overall approach.
> 
> Now I'm taking a step back and submitting a draft that acts as a
> semi-formal problem statement, and an overview of the three main
> categories of solutions.
> 
> Personally, I'm fairly agnostic to the chosen solution, but feel that
> we need some kind of standard(s) around the post-quantum transition
> for certificates and PKI. Personally, I feel that Composite is mature
> enough as an idea to standardize as a tool in our toolbox for
> contexts where it makes sense, even if a different mechanism is
> preferred for TLS and IPSEC/IKE.
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 1. Feedback on the problem statement draft.
> -- Best Regards, Massimiliano Pala, Ph.D. OpenCA Labs Director 
> [OpenCA Logo]
> 
> 
> _______________________________________________ Secdispatch mailing
> list [email-masked] 
> https://www.ietf.org/mailman/listinfo/secdispatch
>

---

From: Mike Ounsworth <[email-masked]>
Date: Thu, 12 Sep 2019 19:47:08 +0000

Hi Stephen,

That's an exciting solution space that's orthogonal to the ones that I wrote up in my Problem Statement draft. Do you have some concretes on what such a "replace X.509" proposal might look like?

I suggest that even with full support for such a proposal, it would still make sense to standardize a "less change to the 1980s baggage" so that existing systems have something they can do in the short term. Speaking as a PKI vendor, this is starting to be an uncomfortably hot issue with our customers who are deploying 20 year lifetime devices and want post-quantum protection on them like now with like no code changes.

So exactly as you say "people invested in x.509-based PKI may reasonably prefer less-change to more-change" :P

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

-----Original Message-----
From: Secdispatch <[email-masked]> On Behalf Of Stephen Farrell
Sent: Thursday, September 12, 2019 2:28 PM
To: Scott Fluhrer (sfluhrer) <[email-masked]>; Dr. Pala <[email-masked]>; [email-masked]
Subject: [EXTERNAL]Re: [Secdispatch] Problem statement for post-quantum multi-algorithm PKI

Hiya,

Discussion of how to get what PKI offers in a world where current asymmetric algorithms might be weak and where quantum-resistant, but new, algorithms are emerging, is an excellent topic to start to consider.

I also think it seems a bit mad to consider x.509 as the main thing to consider so I'm not at all keen on seeing this problem space as being one where all we need is yet another sticking plaster for x.509. That said, I do get that people invested in x.509-based PKI may reasonably prefer less-change to more-change, I just think we may be sad if we miss another opportunity to move on leaving behind some of this 1980's baggage.

Cheers,
S.

> instead of having a two party system (where as long as both the client 
> and the server support a postquantum algorithm, they can negotiate 
> it), we now have an (at least) three party system, the client, the 
> server, and the CA.  this additional party makes the upgrade path more 
> complicated.  So, while we have more time, we may need it.
> 
> eventually expand the adoption of this approach in other environments 
> we are engaged in (e.g., medical devices, cellular networks, WiFi 
> Alliance and WBA, etc.)
> 
> This got bounced here from LAMPS because the scope is potentially more 
> than a "limited" pkix change, and because this needs multi-WG 
> competition), is pushing for "hybridized" crypto that combines RSA/ECC 
> with new primitives in order to hedge our bets against both quantum 
> adversaries, and also algorithmic / mathematical breaks of the new 
> primitives.
> 
> 
> 
> 
> 
> enough as an idea to standardize as a tool in our toolbox for contexts 
> where it makes sense, even if a different mechanism is preferred for 
> TLS and IPSEC/IKE.
> 
> 
> 
> 
> 
> 
> 
> 
> 
> -- Best Regards, Massimiliano Pala, Ph.D. OpenCA Labs Director [OpenCA 
> Logo]
> 
>

---

From: Stephen Farrell <[email-masked]>
Date: Thu, 12 Sep 2019 21:05:07 +0100

Hiya,

On 12/09/2019 20:47, Mike Ounsworth wrote:
> Hi Stephen,
> 
> That's an exciting solution space that's orthogonal to the ones that
> I wrote up in my Problem Statement draft. Do you have some concretes
> on what such a "replace X.509" proposal might look like?

I don't. In an IETF context/discussion though, I might start
from looking at how acme accounts are handled or how assertions
are being handled using e.g. cose. I think the encoding of the
assertions is easy enough. Figuring out what assertions to
encode is where the work'd be. For example, is the offline CA
model even worth bothering with? Maybe encouraging multiple
independent assertions is better than trying to encapsulate
all the verifier needs into one blob? Etc. One thing that'd
be a MUST in my little head would be making anything like
notAfter be optional. But no, I don't have a worked-out
proposal and nor do I know if others would like to work
on that.

> I suggest that even with full support for such a proposal, it would
> still make sense to standardize a "less change to the 1980s baggage"
> so that existing systems have something they can do in the short
> term. 

What short-term problem is there? (That needs solving.)

And what'd stop this sticking plaster from blocking any
other mechanisms get deployed as has happened to date
with x.509? Doing sufficiently better than x.509 to
displace x.509 in a classical context has turned out to
be too hard, despite a couple of attempts. It's not that
x.509 is ultra-terrible (it's only mediocre-terrible:-)
but once something is in place then a new thing has to
be sufficiently better to displace that. So there's a
real opportunity cost to the path you're suggesting I
reckon.

> Speaking as a PKI vendor, this is starting to be an
> uncomfortably hot issue with our customers who are deploying 20 year
> lifetime devices and want post-quantum protection on them like now
> with like no code changes.

New algorithms => new code. Transition from 1 key => >1 key
means new code. I don't see how "no new code" is relevant
here. And I can see ways in which minimising the amount of
new code might lead to a higher liklihood of vulnerabilities.

> So exactly as you say "people invested in x.509-based PKI may
> reasonably prefer less-change to more-change" :P

Sure. I don't think there's anything wrong with you proposing
what you're proposing. I just think that doing that would be
heading about 180 degrees in the wrong direction:-)

Cheers,
S.

> 
> - - - Mike Ounsworth | Office: +1 (613) 270-2873
> 
> -----Original Message----- From: Secdispatch
> <[email-masked]> On Behalf Of Stephen Farrell Sent:
> Thursday, September 12, 2019 2:28 PM To: Scott Fluhrer (sfluhrer)
> <[email-masked]>; Dr. Pala <[email-masked]>;
> [email-masked] Subject: [EXTERNAL]Re: [Secdispatch] Problem
> statement for post-quantum multi-algorithm PKI
> 
> 
> Hiya,
> 
> Discussion of how to get what PKI offers in a world where current
> asymmetric algorithms might be weak and where quantum-resistant, but
> new, algorithms are emerging, is an excellent topic to start to
> consider.
> 
> I also think it seems a bit mad to consider x.509 as the main thing
> to consider so I'm not at all keen on seeing this problem space as
> being one where all we need is yet another sticking plaster for
> x.509. That said, I do get that people invested in x.509-based PKI
> may reasonably prefer less-change to more-change, I just think we may
> be sad if we miss another opportunity to move on leaving behind some
> of this 1980's baggage.
> 
> Cheers, S.
> 
>> 
>>  once you have one, you cannot use your Quantum Computer to break
>> the authentication of recorded conversations.
>> 
>> [email-masked] Subject: Re: [Secdispatch] Problem statement
>> for post-quantum multi-algorithm PKI
>> 
>> 
>> Hi SecDispatch, Mike,
>> 
>> Our industry (Cable) is working on this problem already - some of
>> our members have started investigating few things in the
>> post-quantum field and in particular how to protect our PKIs in
>> this uncertain environment.
>> 
>> With few billions certificates issued across the industry, we
>> heavily rely on certificates for device authentication and,
>> therefore, we need to work on a solution today.
>> 
>> against the factorization threat (not only certificates, but all
>> the data structures for PKIX) thus allowing to verify the
>> authentication with Post-Quantum algorithms when we will need to
>> make the switch (deferred Algorithm Agility).
>> 
>> Looking forward to find a good home for this project within the
>> IETF - a simple but powerful tool for our "PKI toolboxes"
>> 
>> Cheers, Max
>> 
>> 
>> 
>> Hi SecDispatch,
>> 
>> 
>> 
>> A year and a half ago, a draft was put to LAMPS for putting PQ
>> public key and signatures into X.509v3 extensions. This draft has
>> been allowed to expire, but is being pursued at the ITU.
>> 
>> https://datatracker.ietf.org/doc/draft-truskovsky-lamps-pq-hybrid-x509
>>
>> 
/
>>  concatenate multiple crypto algorithms into a single key or
>> signature octet string. This draft stalled in LAMPS over whether it
>> is the correct overall approach.
>> 
>> Personally, I'm fairly agnostic to the chosen solution, but feel
>> that we need some kind of standard(s) around the post-quantum
>> transition for certificates and PKI. Personally, I feel that
>> Composite is mature enough as an idea to standardize as a tool in
>> our toolbox for contexts where it makes sense, even if a different
>> mechanism is preferred for TLS and IPSEC/IKE.
>> 
>> 
>> 
>> 
>> 
>> 
>> 
>> 
>>

---

From: Daniel Van Geest <[email-masked]>
Date: Thu, 12 Sep 2019 20:14:57 +0000

Hi,

On 2019-09-12, 3:48 PM, "Secdispatch on behalf of Mike Ounsworth" <[email-masked]<mailto:[email-masked]> on behalf of [email-masked]<mailto:[email-masked]>> wrote:

Hi Stephen,

+1.  We’ve heard from organizations interested in tools like these but from a “we still haven’t finished the ECDSA migration yet” perspective.  Inertia may not be the best reason to pursue an idea, but I think there is demand for a solution within X.509.

Not that we shouldn’t also take this opportunity to do things right for those able to adapt more rapidly, so that they can drop the 1980s baggage (and not saddle themselves with new 2020s baggage as well :-) ).  It is an either/or proposition?  If it’s “both”, is there desire to actually work on both, or will one inevitably end up consuming all the interest/resources?

Daniel

- - -

-----Original Message-----
From: Secdispatch <[email-masked]<mailto:[email-masked]>> On Behalf Of Stephen Farrell
Sent: Thursday, September 12, 2019 2:28 PM
To: Scott Fluhrer (sfluhrer) <[email-masked]<mailto:[email-masked]>>; Dr. Pala <[email-masked]<mailto:[email-masked]>>; [email-masked]<mailto:[email-masked]>
Subject: [EXTERNAL]Re: [Secdispatch] Problem statement for post-quantum multi-algorithm PKI

Hiya,

Cheers,
S.

From: Secdispatch <[email-masked]<mailto:[email-masked]>> On Behalf Of Dr.
[email-masked]<mailto:[email-masked]> Subject: Re: [Secdispatch] Problem statement for

list [email-masked]<mailto:[email-masked]>
_______________________________________________
Secdispatch mailing list
[email-masked]<mailto:[email-masked]>

---

From: "Panos Kampanakis (pkampana)" <[email-masked]>
Date: Fri, 13 Sep 2019 01:40:47 +0000

> I also think it seems a bit mad to consider x.509 as the main thing to consider so I'm not at all keen on seeing this problem space as being one where all we need is yet another sticking plaster fo…

X.509-based PKI may reasonably prefer less-change to more-change. That would be almost all usecases. I am not sure I can realistically envision a PQ world that does authentication completely differently than how the world has been doing it for decades. 

Based on detailed experiments (and a paper to be published soon) I am convinced that two of the PQ signature candidates in the NIST PQ competition could be viable for the way PKIX works today. And based on reports I have seen from Google, Cloudflare, AWS and Microsoft and based on the NIST KEM algorithm candidates characteristics there are key exchange options that could play ok in almost all usecases of secure tunnels today. 

Before we boil the ocean although it has been boiled already, we need to be sure it needs boiling. I am not convinced it does. 

Panos

-----Original Message-----
From: Secdispatch <[email-masked]> On Behalf Of Mike Ounsworth
Sent: Thursday, September 12, 2019 3:47 PM
To: Stephen Farrell <[email-masked]>; Scott Fluhrer (sfluhrer) <[email-masked]>; Dr. Pala <[email-masked]>; [email-masked]
Subject: Re: [Secdispatch] [EXTERNAL]Re: Problem statement for post-quantum multi-algorithm PKI

Hi Stephen,

- - -

-----Original Message-----
From: Secdispatch <[email-masked]> On Behalf Of Stephen Farrell
Sent: Thursday, September 12, 2019 2:28 PM
To: Scott Fluhrer (sfluhrer) <[email-masked]>; Dr. Pala <[email-masked]>; [email-masked]
Subject: [EXTERNAL]Re: [Secdispatch] Problem statement for post-quantum multi-algorithm PKI

Hiya,

Cheers,
S.

[email-masked]

---

From: Michael Richardson <[email-masked]>
Date: Sat, 14 Sep 2019 04:19:33 +0200

> Computers are, more than likely, more than 10 years away, and even once
    > you have one, you cannot use your Quantum Computer to break the

No, we really don't have plenty of time.
Some suggest that it is actually already rather *late*

Long-lived devices (such as automobiles) are being designed today, for
production in mid-2020s, and many will be on the road until 2040.

-- 
]               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: Stephen Farrell <[email-masked]>
Date: Sat, 14 Sep 2019 03:28:00 +0100

Hiya,

> production in mid-2020s, and many will be on the road until 2040.

Count me unconvinced.

Either those devices will have s/w update or they're screwed
already even without requiring the putative existence of a
quantum computer. And we are discussing authentication
here, mostly of origins I guess, and not confidentiality,
so post-facto attacks don't count afaics.

I'd appreciate if someone could explain the specifics of
the pressing issue here that requires us to not wait for
e.g., the outcome of the NIST competition.

Cheers,
S.

---

From: "Salz, Rich" <[email-masked]>
Date: Sat, 14 Sep 2019 02:33:52 +0000

>    Count me unconvinced.
  
Me too.

Someone should dig up and post the video link to Kenny Paterson's talk.  Key take-away:  wait for NIST, it's always "two years away."

---

From: Michael Richardson <[email-masked]>
Date: Sat, 14 Sep 2019 04:53:37 +0200

Stephen Farrell <[email-masked]> wrote:
    >> > One might think we have plenty of time, given that Real Quantum >
    >> once > you have one, you cannot use your Quantum Computer to break the
    >> No, we really don't have plenty of time.  Some suggest that it is
    >> actually already rather *late*
    >> 

    > Either those devices will have s/w update or they're screwed already

If QM mechanisms take a lot more ram or a lot more bandwidth, then
software updates aren't going to help them.
My understanding is that safety critical systems in cars are authenticating
to each other over the internal buses (CAN, etc.) already.

    > even without requiring the putative existence of a quantum
    > computer. And we are discussing authentication here, mostly of origins
    > I guess, and not confidentiality, so post-facto attacks don't count
    > afaics.

    > I'd appreciate if someone could explain the specifics of the pressing
    > issue here that requires us to not wait for e.g., the outcome of the
    > NIST competition.

I'm not saying that we can't wait to finalize things.
I'm saying that we shouldn't wait for it to be finalized to start.

Can we support multiple signatures inside a certificate? I don't think so.
So what can we do?

---

From: Mohit Sethi M <[email-masked]>
Date: Sun, 15 Sep 2019 12:43:01 +0000

Indeed. I found Kenny's talk on this topic from IETF 99 very 
informative. Here is the link:

https://youtu.be/abmd1n5WUvc?t=1445

--Mohit

---

From: Ira McDonald <[email-masked]>
Date: Sun, 15 Sep 2019 10:29:34 -0400

Hi,

Thanks for the link to Kenny's talk.

Stephen - The hard problem for automotive vehicles is that, even if
Quantum Computing never comes to pass, algorithms and various
implementations go on having new weaknesses found over time.
But decent performance requires hardware assist, in many cases.
But automotive ECUs are very unlikely to start have large FPGAs
added soon.  Replacing 100s of expensive ECUs in fielded vehicles
to allow practical algorithm agility is not going to happen.  This issue
that Michael Richardson mentioned is at the top of the list for the
automotive cybersecurity community.

Cheers,
- Ira

Ira McDonald (Musician / Software Architect)
Co-Chair - TCG Trusted Mobility Solutions WG
Co-Chair - TCG Metadata Access Protocol SG
Chair - Linux Foundation Open Printing WG
Secretary - IEEE-ISTO Printer Working Group
Co-Chair - IEEE-ISTO PWG Internet Printing Protocol WG
IETF Designated Expert - IPP & Printer MIB
Blue Roof Music / High North Inc
http://sites.google.com/site/blueroofmusic
http://sites.google.com/site/highnorthinc
mailto: [email-masked]
PO Box 221  Grand Marais, MI 49839  906-494-2434

On Sun, Sep 15, 2019 at 8:43 AM Mohit Sethi M <mohit.m.sethi=
[email-masked]> wrote:

> > Someone should dig up and post the video link to Kenny Paterson's talk.
> Key take-away:  wait for NIST, it's always "two years away."
> >
> >
> >

---

From: Mike Ounsworth <[email-masked]>
Date: Mon, 16 Sep 2019 16:05:22 +0000

> I'd appreciate if someone could explain the specifics of the pressing issue here that requires us to not wait for e.g., the outcome of the NIST competition.

My Goal: multi-vendor interop on PQ certificates. I'm coming from the perspective of a CA; it can take years to distribute a root cert to all the places it needs to be before you can really start using it. Plus, people want to playing with these things ASAP to understand the scope of infrastructure changes required. There's the time pressure.

I think you're right that to really deploy any meaningful 20 year root using, for example the small lattice schemes, we'll need to wait for the NIST PQC algs to stop having so much churn. 

That said, laying the groundwork for the "hybrid" property in certificates that the NIST PQC community is calling for will require much debate and a few RFCs. This work is necessary and independent of the choice of algorithm from the NIST PQC competition, so why should we wait until 2023 to _start_ thinking about it? Why not do it in parallel, be able to offer alpha test versions of PKI products before the conclusion of the NIST PQC, and be ready to drop-in the NIST winners the day they're ready?

- - -

-----Original Message-----
From: Secdispatch <[email-masked]> On Behalf Of Michael Richardson
Sent: Friday, September 13, 2019 9:54 PM
To: Stephen Farrell <[email-masked]>
Cc: [email-masked]
Subject: [EXTERNAL]Re: [Secdispatch] Problem statement for post-quantum multi-algorithm PKI

    > Either those devices will have s/w update or they're screwed already

If QM mechanisms take a lot more ram or a lot more bandwidth, then software updates aren't going to help them.
My understanding is that safety critical systems in cars are authenticating to each other over the internal buses (CAN, etc.) already.

---

From: Daniel Van Geest <[email-masked]>
Date: Mon, 16 Sep 2019 18:06:47 +0000

Michael,

On 2019-09-13, 10:54 PM, "Secdispatch on behalf of Michael Richardson" <[email-masked]<mailto:[email-masked]> on behalf of [email-masked]<mailto:[email-masked]>> wrote:

Why not?  Mike’s problem statement draft has two potential technical solutions doing just that, each with advantages and disadvantages.  Or is there more of a logistical or other issue?  Knowing why you think we can’t support multiple signatures inside a certificate could help refine the problem statement.

Thanks,
Daniel Van Geest

---

From: Stephen Farrell <[email-masked]>
Date: Mon, 16 Sep 2019 21:58:47 +0100

Hiya,

Replying to various folks at once...

> automotive cybersecurity community.

I don't understand how devices that are not going to be updated
can support algorithm agility. Perhaps you mean that you want to
deploy those devices soon and not update for a couple of decades
or something? If so, that sound like a bad plan to me, and one
that'd be better to not cater to really. (RFC8240 has lots of
discussion of that.)

On 16/09/2019 17:05, Mike Ounsworth wrote:
> My Goal: multi-vendor interop on PQ certificates.

That seems to beg the question again as to why x.509 is needed
at all as part of a PQ solution.

> I'm coming from the
> perspective of a CA; it can take years to distribute a root cert to
> all the places it needs to be before you can really start using it.
> Plus, people want to playing with these things ASAP to understand the
> scope of infrastructure changes required. There's the time pressure.
>
> I think you're right that to really deploy any meaningful 20 year
> root using, for example the small lattice schemes, we'll need to wait
> for the NIST PQC algs to stop having so much churn.
>
> That said, laying the groundwork for the "hybrid" property in
> certificates that the NIST PQC community is calling for will require
> much debate and a few RFCs. This work is necessary and independent of
> the choice of algorithm from the NIST PQC competition, so why should
> we wait until 2023 to _start_ thinking about it? Why not do it in
> parallel, be able to offer alpha test versions of PKI products before
> the conclusion of the NIST PQC, and be ready to drop-in the NIST
> winners the day they're ready?

One reason to not do it in parallel is that we don't know how the
winning algorithm parameters will look. I can easily imagine NIST
modifying how those are encoded and/or introducing new variations,
after basic algorithms have been picked, leading to things having
to be re-done.

(Sorry if the quoting is messed up below, if so, it was messed up
in my MUA before I started is my excuse:-)
On 16/09/2019 19:06, Daniel Van Geest wrote:
> Why not?  Mike’s problem statement draft has two potential technical
> solutions doing just that, each with advantages and disadvantages.
> Or is there more of a logistical or other issue?  Knowing why you
> think we can’t support multiple signatures inside a certificate could
> help refine the problem statement.

Again, that assumes that x.509 is a sensible part of a solution.
We should first question that. (Mike's draft [1] doesn't.)

Secondly, even if x.509 additions were useful somehow for backwards
compatibility (which I find hard to believe TBH) then dealing with
>1 certificate is likely far easier than messing about inside certs
and thereby breaking all the lovely/horrible x.509 code out there.
So Mike's section 2.1 [1] is way easier than the 2.[2|3] approaches,
despite it being the one with no specific drafts.

Again, all that said, I do understand why it may be attractive
for those who produce certificates to argue for putting the PQ
magic beans inside x.509. There are costs elsewhere implied in
doing that, so it ought not be a starting-out assumption.

I don't consider the question as to why a PQ x.509 is needed
nor why now has been satisfactorily answered so far.

Cheers,
S.

[1] https://tools.ietf.org/html/draft-pq-pkix-problem-statement

---

From: "Panos Kampanakis (pkampana)" <[email-masked]>
Date: Mon, 16 Sep 2019 21:35:46 +0000

> That seems to beg the question again as to why x.509 is needed at all as part of a PQ solution. 

Because there is nothing else as widely adopted. You haven't articulated what would replace X.509 and how the world would migrate away from such a ubiquitous standard. 
Composite classic+PQ X.509 may not be the way to go, but replacing X.509 altogether with something new is not a realistic goal imo. 

-----Original Message-----
From: Secdispatch <[email-masked]> On Behalf Of Stephen Farrell
Sent: Monday, September 16, 2019 4:59 PM
To: [email-masked]
Subject: Re: [Secdispatch] Problem statement for post-quantum multi-algorithm PKI

Hiya,

On 15/09/2019 15:29, Ira McDonald wrote:
> But automotive ECUs are very unlikely to start have large FPGAs added 
> soon.  Replacing 100s of expensive ECUs in fielded vehicles to allow 
> practical algorithm agility is not going to happen.  This issue that 
> Michael Richardson mentioned is at the top of the list for the 

I don't understand how devices that are not going to be updated can support algorithm agility. Perhaps you mean that you want to deploy those devices soon and not update for a couple of decades or something? If so, that sound like a bad plan to me, and one that'd be better to not cater to really. (RFC8240 has lots of discussion of that.)

> My Goal: multi-vendor interop on PQ certificates.

That seems to beg the question again as to why x.509 is needed at all as part of a PQ solution.

> I think you're right that to really deploy any meaningful 20 year root 
> using, for example the small lattice schemes, we'll need to wait for 
> the NIST PQC algs to stop having so much churn.
>

One reason to not do it in parallel is that we don't know how the winning algorithm parameters will look. I can easily imagine NIST modifying how those are encoded and/or introducing new variations, after basic algorithms have been picked, leading to things having to be re-done.

Secondly, even if x.509 additions were useful somehow for backwards compatibility (which I find hard to believe TBH) then dealing with
and thereby breaking all the lovely/horrible x.509 code out there.
So Mike's section 2.1 [1] is way easier than the 2.[2|3] approaches, despite it being the one with no specific drafts.

Again, all that said, I do understand why it may be attractive for those who produce certificates to argue for putting the PQ magic beans inside x.509. There are costs elsewhere implied in doing that, so it ought not be a starting-out assumption.

I don't consider the question as to why a PQ x.509 is needed nor why now has been satisfactorily answered so far.

Cheers,
S.

---

From: Mike Ounsworth <[email-masked]>
Date: Mon, 16 Sep 2019 21:37:43 +0000

Hi Stephen,

I feel like we're arguing in circles here and not making any progress.

Re: figuring out "hybrid signature authentication" in parallel with NIST; 
You seem to be implying that we can't work on defining message structures to hold multiple keys and signatures until we know the exact encodings of the NIST winners. I'm not sure I follow the reason why.

Currently, something like, for example, CMS (RFC 5652)  is abstracted away from the encodings of a given algorithm; an algorithm can choose any method it wishes to turn its public key and signature into an octet string; how it does it is an internal detail of the algorithm and has no bearing on the CMS spec. This is abstraction between protocol and crypto is a core part of crypto agility. Surely we can start thinking about how to properly combine multiple signatures before we know exactly what those signatures will be.

Re: "Why X.509?"
You seem to be expecting me to justify why X.509 is worth keeping.
I'm expecting you to propose an alternative and justify why it's better.
We're at a stalemate. 

Since X.509 is the accepted standard, I think the ball's in your court here to justify why it should be binned.

- - -

-----Original Message-----
From: Secdispatch <[email-masked]> On Behalf Of Stephen Farrell
Sent: Monday, September 16, 2019 3:59 PM
To: [email-masked]
Subject: [EXTERNAL]Re: [Secdispatch] Problem statement for post-quantum multi-algorithm PKI

Hiya,

Cheers,
S.

---

From: Stephen Farrell <[email-masked]>
Date: Mon, 16 Sep 2019 22:42:17 +0100

Hiya,

On 16/09/2019 22:35, Panos Kampanakis (pkampana) wrote:
> Because there is nothing else as widely adopted. 

There is nothing "adopted" for PQ PKI, neither widely nor
as a niche.

> You haven't
> articulated what would replace X.509 

Yep, I said that before. It's worth a leisurely discussion
as to what might be done.

> and how the world would migrate
> away from such a ubiquitous standard. 

I didn't say we ought migrate away from x.509, for classic
algorithm uses. Just as acme account handling doesn't use
x.509, something that may be needed for a PQ PKI does not
have to use x.509.

Cheers,
S.

> Composite classic+PQ X.509 may
> not be the way to go, but replacing X.509 altogether with something
> new is not a realistic goal imo.
> 
> 
> 
> 
> Monday, September 16, 2019 4:59 PM To: [email-masked] Subject:
> Re: [Secdispatch] Problem statement for post-quantum multi-algorithm
> PKI
> 
> 
> Hiya,
> 
>> implementations go on having new weaknesses found over time. But
>> decent performance requires hardware assist, in many cases. But
>> automotive ECUs are very unlikely to start have large FPGAs added 
>> soon.  Replacing 100s of expensive ECUs in fielded vehicles to
>> allow practical algorithm agility is not going to happen.  This
>> issue that Michael Richardson mentioned is at the top of the list
>> for the automotive cybersecurity community.
> 
> I don't understand how devices that are not going to be updated can
> support algorithm agility. Perhaps you mean that you want to deploy
> those devices soon and not update for a couple of decades or
> something? If so, that sound like a bad plan to me, and one that'd be
> better to not cater to really. (RFC8240 has lots of discussion of
> that.)
> 
> 
>> I'm coming from the perspective of a CA; it can take years to
>> distribute a root cert to all the places it needs to be before you
>> can really start using it. Plus, people want to playing with these
>> things ASAP to understand the scope of infrastructure changes
>> required. There's the time pressure.
>> 
>> root using, for example the small lattice schemes, we'll need to
>> wait for the NIST PQC algs to stop having so much churn.
>> 
>> certificates that the NIST PQC community is calling for will
>> require much debate and a few RFCs. This work is necessary and
>> independent of the choice of algorithm from the NIST PQC
>> competition, so why should we wait until 2023 to _start_ thinking
>> about it? Why not do it in parallel, be able to offer alpha test
>> versions of PKI products before the conclusion of the NIST PQC, and
>> be ready to drop-in the NIST winners the day they're ready?
> 
> after basic algorithms have been picked, leading to things having to
> be re-done.
> 
> (Sorry if the quoting is messed up below, if so, it was messed up in
> my MUA before I started is my excuse:-) On 16/09/2019 19:06, Daniel
> Van Geest wrote:
>> Why not?  Mike’s problem statement draft has two potential
>> technical solutions doing just that, each with advantages and
>> disadvantages. Or is there more of a logistical or other issue?
>> Knowing why you think we can’t support multiple signatures inside a
>> certificate could help refine the problem statement.
> 
> Again, that assumes that x.509 is a sensible part of a solution. We
> should first question that. (Mike's draft [1] doesn't.)
> 
> and thereby breaking all the lovely/horrible x.509 code out there. So
> Mike's section 2.1 [1] is way easier than the 2.[2|3] approaches,
> Again, all that said, I do understand why it may be attractive for
> those who produce certificates to argue for putting the PQ magic
> beans inside x.509. There are costs elsewhere implied in doing that,
> so it ought not be a starting-out assumption.
> 
> I don't consider the question as to why a PQ x.509 is needed nor why
> now has been satisfactorily answered so far.
> 
> Cheers, S.
>

---

From: Ira McDonald <[email-masked]>
Date: Mon, 16 Sep 2019 17:47:57 -0400

Hi Stephen,

The autos *are* going to have regular OTA firmware updates
to some of their ECUs (they already do so, in many cases).

The unsolved problem is to change to a whole new family of
crypto algorithms in those updates, because there couldn't
be any crypto hardware acceleration.  Autos already have
application layer add-ons for internal vehicle network security
in many cases.  If those crypto algorithms (NOT standardized
in SAE or by regulations) have to change, then the only cure
is blanket replacement in a dealer service bay of all of the
ECUs.  Because the "son of AES" (for example) won't be
feasible because of message timing constraints in those autos
without hardware acceleration.  These are typically constrained
ECUs without the available horsepower to just use the software
versions of entirely new crypto algorithms.

I hope that was more clear.  The problem is real and urgent,
given the current digital ECU counts in autos (from 100 to 259
ECUs).

I don't defend this situation at all, but the auto OEMs and the
hands-off regulators have long since abandoned mechanical
control units.

Cheers,
- Ira

---

From: "Salz, Rich" <[email-masked]>
Date: Mon, 16 Sep 2019 21:53:23 +0000

So why are multiple algorithms needed if the target platform (cars) cannot update to handle them?

---

From: Stephen Farrell <[email-masked]>
Date: Mon, 16 Sep 2019 22:56:46 +0100

Hiya,

> I feel like we're arguing in circles here and not making any

I don't think we're arguing in circles. (When one of us says
that again, you may have a case:-)

> Re: figuring out "hybrid signature authentication" in parallel with
> NIST; You seem to be implying that we can't work on defining message
> structures to hold multiple keys and signatures until we know the
> exact encodings of the NIST winners. I'm not sure I follow the reason
> why.

"can't work" is not what I said. I argued it'd be unwise. My
experience of the output of NIST competitions is that it seems
often followed by a year or so of confusion as to how to
represent algorithm parameters and as to how many variants of
algorithms are defined. I also recall the NULL AlgorithmIdentifier
parameters fun with x.509 going on for years. I bet if you went
to stackexchange you'd find quite recent questions resulting
from that decades old lack of clarity in defining such things.

> 
> Currently, something like, for example, CMS (RFC 5652)  is abstracted
> away from the encodings of a given algorithm; an algorithm can choose
> any method it wishes to turn its public key and signature into an
> octet string; how it does it is an internal detail of the algorithm
> and has no bearing on the CMS spec. This is abstraction between
> protocol and crypto is a core part of crypto agility. Surely we can
> start thinking about how to properly combine multiple signatures
> before we know exactly what those signatures will be.

Sure, chatting about that last is fine and I'm happy to engage.
Starting from an assumption that that mixing is done inside x.509
is begging the question though.

> Re: "Why X.509?" You seem to be expecting me to justify why X.509 is
> worth keeping. I'm expecting you to propose an alternative and
> justify why it's better. We're at a stalemate.

No. We're keeping x.509 (sadly:-). Yes, I'm asking for reasons
why it is necessary to modify x.509 for a PQ PKI. If you don't
have any argument to that effect that's fine, you're then arguing
that this design is easier for you. That's a sane argument for
what could be considered a not-sane outcome:-)

> Since X.509 is the accepted standard, I think the ball's in your
> court here to justify why it should be binned.

Multiple algs/keys per cert requires everyone who uses
x.509 now to change. That is not warranted by wishes for
a PQ PKI at this point, and perhaps never.

That and it's an ~30 year old not very good technology,
so yeah, maybe I'm just fed up with it having first written
code for x.509 in about 1992;-)

Cheers,
S.

> Monday, September 16, 2019 3:59 PM To: [email-masked] Subject:
> [EXTERNAL]Re: [Secdispatch] Problem statement for post-quantum
> multi-algorithm PKI
> 
> 
> Hiya,
>

---

From: Ira McDonald <[email-masked]>
Date: Mon, 16 Sep 2019 17:59:21 -0400

Hi Rich,

The autos *do* already support numerous algorithms (including
nation-specific mandatory ones).  They do update their crypto
(for bug-fixes and for new algorithms).  But when new algorithms
are from an entirely different family and need hardware acceleration
to achieve hard timing constraints *within* vehicle internal networks,
there is no practical solution.  Auto OEMs and parts suppliers are
not going to dramatically increase the cost of their ECUs in order
to add FPGAs or something else to allow field upgrades of their
hardware acceleration.

I perceive that this list doesn't care about this issue.  Beware your
lovely "connected cars" in future years.  I'll give up doing a poor
job of explaining the problem on this list.

Cheers,
- Ira

---

From: "Salz, Rich" <[email-masked]>
Date: Mon, 16 Sep 2019 22:09:00 +0000

So you want something defined now so that hardware acceleration can be developed, when we don’t know what algorithms we’ll actually need post-quantum? That’s a bit snarky, but does it capture what you are saying?

                /r$, jack of all trades master of none

---

From: Ira McDonald <[email-masked]>
Date: Mon, 16 Sep 2019 19:15:54 -0400

Hi Rich,

We're still talking past each other.  I'm aware that we can't
pre-load hardware acceleration for new algorithms yet to
be defined.  But the lack of that hardware acceleration is
going to be a practical deterrent to crypto agility in these
long-lived automotive ECUs in future years.

Cheers,
- Ira

On Mon, Sep 16, 2019 at 6:09 PM Salz, Rich <[email-masked]> wrote:

> So you want something defined now so that hardware acceleration can be
> developed, when we don’t know what algorithms we’ll actually need
> post-quantum? That’s a bit snarky, but does it capture what you are saying?
>
>
>

---

From: Mike Ounsworth <[email-masked]>
Date: Tue, 17 Sep 2019 14:51:17 +0000

Hi Stephen,

I want to point out that while this discussion and existing came from LAMPS, and therefore are X.509 / PKIX in nature, the "Composite" proposal in my Problem Statement draft is lower level than X.509 and could be applied to any protocol that uses octet strings for public keys and signatures.

I've posted a new version with minor tweaks to make that more clear.

- - -

-----Original Message-----
From: Stephen Farrell <[email-masked]> 
Sent: Monday, September 16, 2019 4:57 PM
To: Mike Ounsworth <[email-masked]>; [email-masked]
Subject: Re: [EXTERNAL]Re: [Secdispatch] Problem statement for post-quantum multi-algorithm PKI

Hiya,

> I feel like we're arguing in circles here and not making any progress.

I don't think we're arguing in circles. (When one of us says that again, you may have a case:-)

> exact encodings of the NIST winners. I'm not sure I follow the reason 

"can't work" is not what I said. I argued it'd be unwise. My experience of the output of NIST competitions is that it seems often followed by a year or so of confusion as to how to represent algorithm parameters and as to how many variants of algorithms are defined. I also recall the NULL AlgorithmIdentifier parameters fun with x.509 going on for years. I bet if you went to stackexchange you'd find quite recent questions resulting from that decades old lack of clarity in defining such things.

Sure, chatting about that last is fine and I'm happy to engage.
Starting from an assumption that that mixing is done inside x.509 is begging the question though.

> worth keeping. I'm expecting you to propose an alternative and justify 
> why it's better. We're at a stalemate.

No. We're keeping x.509 (sadly:-). Yes, I'm asking for reasons why it is necessary to modify x.509 for a PQ PKI. If you don't have any argument to that effect that's fine, you're then arguing that this design is easier for you. That's a sane argument for what could be considered a not-sane outcome:-)

Multiple algs/keys per cert requires everyone who uses
x.509 now to change. That is not warranted by wishes for a PQ PKI at this point, and perhaps never.

That and it's an ~30 year old not very good technology, so yeah, maybe I'm just fed up with it having first written code for x.509 in about 1992;-)

Cheers,
S.

>> solutions doing just that, each with advantages and disadvantages. Or 
>> is there more of a logistical or other issue?
> those who produce certificates to argue for putting the PQ magic beans 
> inside x.509. There are costs elsewhere implied in doing that, so it 
> ought not be a starting-out assumption.
>

---

From: Stephen Farrell <[email-masked]>
Date: Tue, 17 Sep 2019 16:07:17 +0100

Hiya,

On 17/09/2019 15:51, Mike Ounsworth wrote:
> Hi Stephen,
> 
> I want to point out that while this discussion and existing came from
> LAMPS, and therefore are X.509 / PKIX in nature, the "Composite"
> proposal in my Problem Statement draft is lower level than X.509 and
> could be applied to any protocol that uses octet strings for public
> keys and signatures.
> 
> 

Fair enough. We can chat about it all at IETF106 :-)

Cheers,
S.

PS: Just while I think of it - ISTM hard to v. hard
to cater for stateful signatures in any of this, e.g.
using RFC8391 or RFC8554. Not asking for an answer
from you now, but it's another factor to consider.
That may argue against embedding any of this in
x.509 - notAfter could be meaningless to dangerous
for such algs. It may also be another argument to
wait and see what the NIST competition produces but
again we can talk about it at IETF106.

> -----Original Message----- From: Stephen Farrell
> <[email-masked]> Sent: Monday, September 16, 2019 4:57 PM 
> To: Mike Ounsworth <[email-masked]>;
> [email-masked] Subject: Re: [EXTERNAL]Re: [Secdispatch] Problem
>>  NIST; You seem to be implying that we can't work on defining
>> message structures to hold multiple keys and signatures until we
>> know the exact encodings of the NIST winners. I'm not sure I follow
>> the reason why.
> 
> experience of the output of NIST competitions is that it seems often
> followed by a year or so of confusion as to how to represent
> algorithm parameters and as to how many variants of algorithms are
> defined. I also recall the NULL AlgorithmIdentifier parameters fun
> with x.509 going on for years. I bet if you went to stackexchange
> you'd find quite recent questions resulting from that decades old
> lack of clarity in defining such things.
> 
>> 
>> Currently, something like, for example, CMS (RFC 5652)  is
>> abstracted away from the encodings of a given algorithm; an
>> algorithm can choose any method it wishes to turn its public key
>> and signature into an octet string; how it does it is an internal
>> detail of the algorithm and has no bearing on the CMS spec. This is
>> abstraction between protocol and crypto is a core part of crypto
>> agility. Surely we can start thinking about how to properly combine
>> multiple signatures before we know exactly what those signatures
>> will be.
> 
>> Re: "Why X.509?" You seem to be expecting me to justify why X.509
>> is worth keeping. I'm expecting you to propose an alternative and
> No. We're keeping x.509 (sadly:-). Yes, I'm asking for reasons why it
> is necessary to modify x.509 for a PQ PKI. If you don't have any
> argument to that effect that's fine, you're then arguing that this
> design is easier for you. That's a sane argument for what could be
> considered a not-sane outcome:-)
> 
> Multiple algs/keys per cert requires everyone who uses x.509 now to
> change. That is not warranted by wishes for a PQ PKI at this point,
> and perhaps never.
> 
> That and it's an ~30 year old not very good technology, so yeah,
> maybe I'm just fed up with it having first written code for x.509 in
> about 1992;-)
> 
> Cheers, S.
> 
>> 
>> 
>> Monday, September 16, 2019 3:59 PM To: [email-masked]
>>> Stephen - The hard problem for automotive vehicles is that, even
>>> if Quantum Computing never comes to pass, algorithms and various
>>>  automotive ECUs are very unlikely to start have large FPGAs
>>> to allow practical algorithm agility is not going to happen.
>>> This issue that Michael Richardson mentioned is at the top of the
>>> list for the automotive cybersecurity community.
>> 
>>  support algorithm agility. Perhaps you mean that you want to
>> deploy those devices soon and not update for a couple of decades or
>>  something? If so, that sound like a bad plan to me, and one that'd
>> be better to not cater to really. (RFC8240 has lots of discussion
>> of that.)
>> 
>> 
>>> distribute a root cert to all the places it needs to be before
>>> you can really start using it. Plus, people want to playing with
>>> these things ASAP to understand the scope of infrastructure
>>> changes required. There's the time pressure.
>>> 
>>> versions of PKI products before the conclusion of the NIST PQC,
>>> and be ready to drop-in the NIST winners the day they're ready?
>> 
>> in my MUA before I started is my excuse:-) On 16/09/2019 19:06,
>> Daniel Van Geest wrote:
>>> Knowing why you think we can’t support multiple signatures inside
>>> a certificate could help refine the problem statement.
>> 
>> So Mike's section 2.1 [1] is way easier than the 2.[2|3]
>> approaches, despite it being the one with no specific drafts.
>> 
>> beans inside x.509. There are costs elsewhere implied in doing
>> that, so it ought not be a starting-out assumption.
>> 
>> I don't consider the question as to why a PQ x.509 is needed nor
>> why now has been satisfactorily answered so far.
>> 
>> Cheers, S.
>>

---

From: Michael Richardson <[email-masked]>
Date: Tue, 17 Sep 2019 13:21:18 -0400

The argument is about the timing.
Whether we need to panic now or not.  Some suggest "we have time"

My comment was that automobiles are being designed around ECUs today that will
be built in 2025, which will be on the road until 2040.  So, no, we don't
have the luxury of a lot of time.

I'm personally unaware of a profile of X.509 certificates that permits a
CA to sign multiple public keys with multiple algorithms.  RFC5280 says:

   Certificate  ::=  SEQUENCE  {
        tbsCertificate       TBSCertificate,
        signatureAlgorithm   AlgorithmIdentifier,
        signatureValue       BIT STRING  }

I don't see a SET here, just a sequence.

We (the IETF) can't solve the problem of ECUs having multiple hardware
assists ourselves.  If I were working in that area, I'd already be looking
through all the NIST submissions from last fall and figuring out what I need
to accelerate them, and what operations are in common, and figuring out if I
can accelerate the common operations, can I win regardless of which one is picked?
Or at least, be closer to market to pick one or three variations.

Rotiling RFC5280 so that we can support multiple signature algorithms on
certificates means that we can get new CAs and related things deployed.
I'm with Stephen in asking if the DER encoding is worth keeping at this
point.

Encode ASN.1 in CBOR (CBOR encoding rules for ASN.1) if we think the ASN.1 is
worth keeping, switch to CDDL if not.  We probably need to keep the semantics.

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

---

From: Ira McDonald <[email-masked]>
Date: Tue, 17 Sep 2019 13:55:45 -0400

Hi Michael,

There's already work-in-progress in IETF WGs on CBOR wrapping
and/or encoding of X.509 certificates, including:

https://datatracker.ietf.org/doc/draft-ietf-cose-x509/

https://datatracker.ietf.org/doc/draft-raza-ace-cbor-certificates/

Cheers,
- Ira

---

From: Michael Richardson <[email-masked]>
Date: Tue, 17 Sep 2019 14:19:25 -0400

> https://datatracker.ietf.org/doc/draft-pq-pkix-problem-statement/

Thank you. I understand much better the three possibilities now.

As I understand it:
1) new algorithm numbers, "RSA+PQ1", "ECDSA+PQ2", etc.  works with old code
   because old-algorithms are negotiated.  Requires negotiation.

2) multiple certificate chains: seems to work well with web servers, but
   in my experience fails with everything else.  The "weak" chain fails
   and then what?

3) new certificates; the v3-extension hack is just that, a hack to do
   multiple certificate chains in a single object.   I assume that the PQx
   signature would cover the legacy public key value as well?

I prefer (3), btw.  (1) hadn't occured to me, as I don't think it works
well with objects at rest, such as firmware updates.

---

From: Stephen Farrell <[email-masked]>
Date: Tue, 17 Sep 2019 19:44:48 +0100

Hiya,

Just to be clear that is not my position.

> worth keeping, switch to CDDL if not.  We probably need to keep the semantics.

Seems like the semantics has to change with stateful signature schemes
with wall-clock time expiry is no longer appropriate for public keys.

Seems like the semantics has to change if N of M signatures must verify
compared to 1 of 1, esp if some alg may become "dubious" for say a
number of years before we find out that a break exists for that alg.
(The dubious alg may be due to a QC attack on a classic alg, or, and
maybe more likely, a classical attack on a new nad supposedly QC
resistant alg.)

Seems like existing x.509 libraries do not need to change, and nor
should they. We'd be breaking them horribly if we tried to retrofit
multiple algs/keys/sigs into x.509. Instead handle new things outside
x.509, so as to avoid introducing significant vulnerabilities into
what's now a more or less working system.

And I dispute the urgency for authentication. Long-lived devices that
cannot be updated in 20 years will be hugely vulnerable to things that
are nothing to do with quantum computers. It isn't worthwhile trying
to "fix" that now when it's too early to know what might or might not
be a good plan for dealing with authentication in a world that has a
working quantum computer - better to ensure those devices can be updated
and then do the best one can as needs arise. The probability of a
recall due to a vuln in a non-updatable device seems far higher than
anything else here.

Instead of all those bad plans - we should start to discuss what may
be needed for authentication in 20+ years time, part of which would be
quantum resistant algs. Another part may be an equivalent to CT which
turned out to be needed due to certificate mis-issuance, so the
discussion I'd be interested in wouldn't only be about quantum
computers. (But would overlap with that.)

Cheers,
S.

---

From: Mike Ounsworth <[email-masked]>
Date: Tue, 17 Sep 2019 19:04:06 +0000

Hi Michael,

Yup, Those are the general ideas, with one small correction; for 1) what we've proposed in draft-ounsworth-pq-composite-sigs is a SubjectPublicKeyInfo that has the algorithmID "Composite", and then the octet string for its public key data is an encoded SEQUENCE of SubjectPublicKeyInfos for RSA, PQ1, etc, -- basically the SPKI contains a list of SPKIs. Same trick for signatureAlgorithm and signatureValue.

This subtle difference avoids the explosion of pairwise OIDs "RSA+PQ1", "ECDSA+PQ2", etc. Also, this allows a legacy client to continue processing if it doesn't understand the OID for PQ2, but its local policy says that ECDSA alone is still ok for now, so there's a crypto agility win.

- - -

-----Original Message-----
From: Michael Richardson <[email-masked]> 
Sent: Tuesday, September 17, 2019 1:19 PM
To: Mike Ounsworth <[email-masked]>; [email-masked]
Subject: Re: [Secdispatch] [EXTERNAL]Re: Problem statement for post-quantum multi-algorithm PKI

As I understand it:

I prefer (3), btw.  (1) hadn't occured to me, as I don't think it works well with objects at rest, such as firmware updates.

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

---

From: Mike Ounsworth <[email-masked]>
Date: Tue, 17 Sep 2019 20:30:51 +0000

Hi Stephen,

I think we're making progress towards common understanding! Hurray!

> should they. We'd be breaking them horribly if we tried to 
> retrofit multiple algs/keys/sigs into x.509. Instead handle new 
> things outside x.509, so as to avoid introducing significant 
> vulnerabilities into what's now a more or less working system.

It sounds like what you're proposing will end up lining up with the still-yet-to-be-defined solution of "just use multiple cert chains", which requires no change to X.509 itself, and which I described in my Problem Statement draft as

2.2.1.  Multiple Certificate Chains

   If you want multiple public keys on multiple cryptographic
   algorithms, then get multiple certificates from multiple PKIs.  The
   protocol has control of negotiating which algorithms get used, how to
   encapsulate the large PQ data, etc.  In many ways, this is the most
   obvious solution.

Also, what I present as "2.1.  "Composite" concatenated keys and signatures" does not retrofit X.509 at all, except for defining new algorithmIDs, which is unavoidable.

And what I present as "2.2.2.  "Hybrid" v3 extensions" (and has an almost accepted ITU-T spec) only retrofits X.509 insofar as it adds a new v3 extension, which since X.509v3 was made to be extended, hardly seems like a retrofit. Also, by design, certs with these extensions can happily be parsed by non-upgraded X.509 libraries.

TL;DR: "We'd be breaking them horribly" seems like an unfair characterization of the proposals before us.

- - -

-----Original Message-----
From: Secdispatch <[email-masked]> On Behalf Of Stephen Farrell
Sent: Tuesday, September 17, 2019 1:45 PM
To: Michael Richardson <[email-masked]>; [email-masked]
Subject: [EXTERNAL]Re: [Secdispatch] Problem statement for post-quantum multi-algorithm PKI

Hiya,

On 17/09/2019 18:21, Michael Richardson wrote:
> 
> Encode ASN.1 in CBOR (CBOR encoding rules for ASN.1) if we think the 
> ASN.1 is worth keeping, switch to CDDL if not.  We probably need to keep the semantics.

Seems like the semantics has to change with stateful signature schemes with wall-clock time expiry is no longer appropriate for public keys.

Seems like the semantics has to change if N of M signatures must verify compared to 1 of 1, esp if some alg may become "dubious" for say a number of years before we find out that a break exists for that alg.
(The dubious alg may be due to a QC attack on a classic alg, or, and maybe more likely, a classical attack on a new nad supposedly QC resistant alg.)

Seems like existing x.509 libraries do not need to change, and nor should they. We'd be breaking them horribly if we tried to retrofit multiple algs/keys/sigs into x.509. Instead handle new things outside x.509, so as to avoid introducing significant vulnerabilities into what's now a more or less working system.

And I dispute the urgency for authentication. Long-lived devices that cannot be updated in 20 years will be hugely vulnerable to things that are nothing to do with quantum computers. It isn't worthwhile trying to "fix" that now when it's too early to know what might or might not be a good plan for dealing with authentication in a world that has a working quantum computer - better to ensure those devices can be updated and then do the best one can as needs arise. The probability of a recall due to a vuln in a non-updatable device seems far higher than anything else here.

Instead of all those bad plans - we should start to discuss what may be needed for authentication in 20+ years time, part of which would be quantum resistant algs. Another part may be an equivalent to CT which turned out to be needed due to certificate mis-issuance, so the discussion I'd be interested in wouldn't only be about quantum computers. (But would overlap with that.)

Cheers,
S.

---

From: Stephen Farrell <[email-masked]>
Date: Tue, 17 Sep 2019 22:16:55 +0100

Hiya,

On 17/09/2019 21:30, Mike Ounsworth wrote:
> 
> It sounds like what you're proposing will end up lining up with the
> still-yet-to-be-defined solution of "just use multiple cert chains",

Nope, sorry for being unclear. I'm coming around to arguing to
not bother with using x.509 at all any weird new PQ stuff, (like
stateful sigs or where values are big enough to cause protocol
problems in places x.509 is currently used), and to definitely
not embed multiple key/alg stuff inside x.509. Existing x.509
libraries could then continue to be used really unmodified (so
no change to what's often pretty flakey cert validation logic,
only crypto APIs) with current algs or where some PQ alg reall
fits the current model well enough. In addition, I'd argue to
wait 'till NIST are done to start in any detailed way. Hope
that's clearer.

Cheers,
S.

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 18 Sep 2019 08:08:55 -0400

+1

It looks fairly certain that PQ algorithms will either be a drop in
replacement requiring no changes or require so much change that PKIX is
pretty much irrelevant. We are not going to be using a Kohnfelder
architecture to support a PKI based on stateful signatures.

The two technologies we are going to need to revisit are Needham-Schroeder
(e.g. Kerberos) and Haber-Stornetta (e.g. Blockchain)

We do have some experience with BlockChain type technologies. Certificate
Transparency for one. But I don't feel like trying to build on top of that
so I wrote a separate BlockChain type technology for the Mathematical Mesh
which is basically Merkle Tree in JSON using JOSE as the crypto base. It
also builds in some of the same ideas from SAML.

The latest draft is here:

http://mathmesh.com/Documents/draft-hallambaker-mesh-dare.html

This is not designed as a PQ infrastructure but it does have some (much?)
of the infrastructure that you would want for building blocks for PQ.