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

[Sofía Celi <[e-mail]>]

Dear all,

>         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.

That is correct. At the moment, there does not seem to exist such a 
machine (a powerful "noise-free" quantum computer). There is a great 
paper from 2018 from John Preskill:
https://arxiv.org/abs/1801.00862 highlighting some of the challenges 
faced nowasays from quantum computers. Yesterday, I indeed sat with a 
bunch of quantum computing researchers and the best timeline we could 
give was 25-35 years. Let's see.

>     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.

I agree on these points. It is vital that we are careful with the 
migration and we don't repeat the same errors we did in the past. The 
point you raise of UDP is indeed something to be taking extra 
considerarion of. So far we had had some few experiments on how actually 
PQC works over real data but those experiments are not a full view of 
the Internet as we use it in many applications nowadays. Perhaps this 
time of waiting for the NIST standard should be devoted to testing those 
cases: on connections with unrealiable bandwidth, protocols over UPD, 
stateless servers, devices with different configurations, and more. I 
highlighted some of these cases on a presentation I gave yesterday: 
https://claucece.github.io/slides/Summer_School_PQC_TLS.pdf

> 
>     #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.

Completely agree. This is also the case for DNSSEC, for example. We 
don't have a proper mapping of those operational issues. We have started 
research on the matter so if you are interested in contributing, let us 
know.

> 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.

There is a notion of being 'quantum annoyant' to a quantum computer: 
perhaps that might be an starting point for other schemes that do no 
have a post-quantum counterpart as of right now. For others, a hybrid 
approach should definitly be taken such that classical cryptography 
still protects data.

>     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.

Inherently, KEMs do not support non-interactive protocols. A KEM is not 
a (EC)DH key exchange: we don't have an scheme that targets all the 
properties that (EC)DH KEX give us (there is CSIDH, which security is 
heavily debated in the community but it is not broken by the recent 
torsion "glue and split" attack). A thing we have also being working on 
is this: a proper explanation of what a KEM gives you and where its 
limits are when compared to (EC)DH KEX. I'll try sharing that over the 
next weeks.

>     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.

Not sure if I follow, so apologies in that. We already have a hybrid 
mechanism to add to the key exchange phase of TLS: 
https://datatracker.ietf.org/doc/draft-ietf-tls-hybrid-design/ The KDF 
functions used during the Key Schedule are not targeted by a quantum 
computer so if the initial master key is quantum-safe, so are the 
subsequent ones for the KDFs.

> 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.

That is correct. Such is the way KEMs work. We don't have that 
counterpart in post-quantum that we can attest to a high level of 
security. This is not so evidently needed in TLS but it is on Signal, 
OTR, and other protocols. I recently sent an email to the pqc mailing 
list around the matter: 
https://mailarchive.ietf.org/arch/msg/pqc/mW1r-57_OX7kAMGPef3noC4ZF_E/

Thank you,


-- 
Sofía Celi
@claucece
Cryptographic research and implementation at many places, specially Brave.
Chair of hprc at IRTF and anti-fraud at W3C.
Reach me out at: [e-mail]
Website: https://sofiaceli.com/
3D0B D6E9 4D51 FBC2 CEF7  F004 C835 5EB9 42BF A1D6