Re: [TLS] Before we PQC... Re: PQC key exchange sizes

[Phillip Hallam-Baker <[e-mail]>]

On Fri, Aug 5, 2022 at 4:42 PM Blumenthal, Uri - 0553 - MITLL <
[e-mail]> wrote:

> In yesterday’s working group meeting we had a bit of a discussion of the
> impact of the sizes of post-quantum key exchange on TLS and related
> protocols like QUIC. As we neglected to put Kyber’s key sizes in our slide
> deck (unlike the signature schemes), I thought it would be a good idea to
> get the actual numbers of Kyber onto the mailing list.
>
> Before we dive into applying the NIST algorithms to TLS 1.3 let us first
> consider our security goals and recalibrate accordingly.
>
>
>
> That’s always a good idea.
>
>
>
> I have the luxury of having 0 users. So I can completely redesign my
> architecture if needs be. But the deeper I have got into Quantum Computer
> Cryptanalysis (QCC) PQC, the less that appears to be necessary.
>
>
>
> Respectfully disagree – though if all you got to protect is your
> TLS-secured purchases from Amazon.com, I’d concede the point.
>
>
>
> First off, let us level set. Nobody has built a QC capable of QCC and it
> is highly unlikely anyone will in the next decade.
>
>
>
> You cannot know that, and “professional opinions” vary widely.
>

The relevant qualification in this case is to have experience of
experimental physics. I spent eight years working in high energy physics. I
can spot a science project when I see one. The folk who wrote the MIT
Quantum Computing course are as skeptical about the scalability of the
super-cold quantum machines as I am. The trapped ion approach is certainly
a plausible threat but nobody has managed to make that work yet and the
current progress is in the optical systems and not the hyperfine transition
systems.



> So, what we are concerned about today is data we exchange today being
> cryptanalyzed in the future.
>
> We can argue about that if people want but can we at least agree that our
> #1 priority should be confidentiality.
>
>
>
> Yes and yes.
>
>
>
> So the first proposal I have is to separate our concerns into two separate
> parts with different timelines:
>
>
>
> #1 Confidentiality, we should aim to deliver a standards based proposal by
> 2025.
>
>
>
> If we (well, some of us) got the data *today* that mustn’t be disclosed a
> decade from now, then we do not have the luxury of waiting till 2025.
> Otherwise, see above.
>

I know people would like to have a solution much sooner but what people
want and what they can reasonably expect are frequently very different
things.

Let us not repeat the failure of the DPRIV working group which decided that
the problem was so very very urgent that they had to have a solution in 12
months time then used that arbitrary and idiotic constraint to exclude any
UDP transport scheme from consideration. As I predicted seven years ago,
the TLS based solution they adopted which depended on TLS quickstart was
never used because it was undeployable. We only got a deployable version of
DPRIV a few months ago when the DNS over QUIC scheme went to last call.

My point here is that it is a really bad idea to set schedules for
delivering standards according to what people assert is 'necessary'. in the
DPRIV case, trying to make the process work faster actually made it much
slower.

Given the amount of work required, the time taken to get people up to speed
with the new approach, 2025 seems like a fairly optimistic date to deliver
a spec even with it being a priority.

The other point to make in this respect is that yes, a heck of a lot of
data that is generated today will have serious consequences if disclosed as
a result of QCC. But that data is a really small fraction of the TLS
traffic today which is vastly more than any adversary could store. Also,
people who genuinely have such concerns need to be looking at Data at Rest
security as their primary security mechanism. So given the almost complete
lack of concern for Data at Rest security in the industry right now, I am
tending to see the PQC concerns as being less about security and more about
something else.



> #2 Fully QCC hardened spec before 2030.
>
>
>
> If by “fully…” you mean “including PQ digital signatures”, I’d probably
> agree.
>

Not just that. We have to go through and audit every part of the TLS/WebPKI
system to check and it is a very large and very complex system. It is bad
enough trying to get my head around all the possible issues with the Mesh
which is a system with one specification and no legacy. TLS/PKIX/ACME is
going to be a real bear.

I am now thinking in terms of 'Post Quantum Hardened" and "Post Quantum
Qualified". Hardening a system so it doesn't completely break under QCC is
a practical near term goal. Getting to a fully qualified system is going to
be a root-and-canal job.


Second observation is that all we have at this point is the output of the
> NIST competition and that is not a KEM. No sorry, NIST has not approved a
> primitive that we can pass a private key to and receive that key back
> wrapped under the specified public key. What NIST actually tested was a
> function to which we pass a public key and get back a shared secret
> generated by the function and a blob that decrypts to the key.
>
>
>
> The output of NIST PQC is *exactly* KEM. And it’s fully specified.
>
>
>
> NIST did not approve 'KYBER' at least it has not done so yet.
>
>
>
> NIST did – what it did *not* do is finalizing the specs, which requires
> public review. Some people conjecture that Kyber will not need many changes
> to become a “full” standard.
>

And other people are claiming that Kyber has limitations, that it does not
support non-interactive protocols, etc. etc. While I would be happy to see
some qualified cryptographers come out and say that those people are wrong
and misinformed etc., I am not seeing that pushback at this point.

My issue here is that opening the box voids the manufacturer's warranty and
at this point we do not have a description of what the inner box is or what
caveats might apply to using the inner mechanism.


TLS protocol includes derivation of “session” keys. Currently it employs
> asymmetric “pre-Quantum” crypto. That has to be replaced by PQ asymmetric
> crypto. That’s the most appropriate (and the only) point to deploy PQC in.
> I’ve no clue about Mesh, so exclude Mesh from my comment.
>
>
>
> The solution I am currently working with is to regard QCC at the same
> level as a single defection. So if Alice has established a separation of
> the decryption role between Bob and the Key Service, both have to defect
> (or be breached) for disclosure to occur. Until I get Threshold PQC, I am
> going to have to accept a situation in which the system remains secure
> against QCC but only if the key service does not defect.
>
>
>
> Skipping the above.
>
>
>
> Applying the same principles to TLS we actually have two key agreements in
> which we might employ PQC:
>
>
>
> 1) The primary key exchange
>
> 2) The forward secrecy / ephemeral / rekey
>
>
>
> Looking at most of the proposals they seem to be looking to drop the PQC
> scheme into the ephemeral rekeying. That is one way to do it but does the
> threat of QCC really justify the performance impact of doing that?
>
>
>
> First, I don’t see performance impact from that. PQC KEMs are pretty fast.
> The main cost is in exchanging much larger bit blobs. Second – if your
> today’s data will maintain its value into 2030+, then definitely yes;
> otherwise – who cares.
>
>
>
> PQC hardening the initial key exchange should suffice provided that we fix
> the forward secrecy exchange so that it includes the entropy from the
> primary. This would bring TLS in line with Noise and with best practice. It
> would be a change to the TLS key exchange but one that corrects an
> oversight in the original forward secrecy mechanism.
>
>
>
> If your rekey depends on the initial key values, and/or uses only Classic
> crypto – how can you provide Forward Secrecy?
>

The TLS nomenclature is confused here. To me a session key is what I apply
to data, i.e.

session = KDF (ephemeral-agreement)

My rekey uses the initial values plus the ephemeral exchange, ie

session = KDF (initial-exchange + ephemeral-agreement)

So the key I use to encrypt the data is secure if either the
initial-exchange is secure or the ephemeral-agreement is secure. I have not
proved that but any inability to produce such a proof should probably stand
as indicating a limitation in the current state of the art in formal proofs
of security than the protocol design.

What I propose using in a minimally PQC hardened exchange is:

session = KDF (initial-exchange + initial-PQC + ephemeral-agreement)

That is one option but not the only one. There are

0) Classic initial, no forward secrecy
1) Classic initial + PQC initial, no forward secrecy
2) Classic initial + PQC initial, classical forward secrecy
3) Classic initial, classical forward secrecy + PQC forward secrecy
4) Classic initial, PQC forward secrecy
5) Classic initial + PQC initial, PQC forward secrecy
6) Classic initial + PQC initial, classical forward secrecy + PQC forward
secrecy
etc.

Given that Google has spent the past five years telling people that
security signals absolutely don't work, they are going to face a billion
dollar anti-trust suit from certain CAs if they then try to provide a new
security signal to show off support for PQC crypto. So persuading sites to
deploy PQC support might be challenging.


The big difference between PQC initial and PQC forward secrecy is that if
the PQC agreement is going to take place as an initial key agreement, the
public key has to be attested by the TLS server certificate. It is this
move that makes '0RTT' possible. As I keep saying, 0RTT is not really a
thing, we just have clever ways to conceal parts of the protocol by moving
them into a different protocol. If we want Kyber to work as 0RTT, we have
to use the same techniques.

The term 'interactive' is used very differently in protocol design and
cryptography. DH and ECDH are mutual key exchanges. Alice and Bob both
receive a shared secret that both contribute to equally. Kyber is a
unilateral key exchange, Alice encrypts to Bob's public key without using
her key. If we want to have a mutually authenticated key exchange, Bob is
going to have to encrypt something to Alice's public key.