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

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

On Sat, Aug 6, 2022 at 1:11 AM Benjamin Kaduk <[e-mail]> wrote:

> Hi Scott,
>
> mutt+links can't cope with your text/html using [p class="MsoNormal"
> style="margin-left:.5in"] for quoting (and the text/plain multipart
> alternative is completely busted), so I have to trim PHB's original in most
> instances.
>
> On Sat, Aug 06, 2022 at 03:18:31AM +0000, Scott Fluhrer (sfluhrer) wrote:
> >
> > > I have the luxury of having 0 users. So I can completely redesign my
> architecture if needs be.
> >
> > I would disagree; after all, we do have existing TLS 1.3
> implementations.  I believe it is important to avoid unnecessary changes,
> for two reasons:
>
> PHB's use of the first-person singular implies he's talking about the
> mathematical mesh, not TLS at all.
>

Exactly, once you have an installed base, every change is difficult. Unless
of course you have a closed system like Signal where everyone uses software
from the same source which also provides the service.

The other big difference is that TLS is critical infrastructure and I am
frankly rather offended by the idea that winning a prize at the NIST cipher
of the year show is all the cryptographers have to do to get us to deploy.
That is not how we go about things, or at least it shouldn't be.

We are designing a security specification here. One that has global impact.
I want to see this done properly. The cryptographers don't always get it
right. If we had paid a little more attention in the specification of HKDF,
we might have spotted an issue I discovered the hard way.

If we are going to add any value in this process we have to have enough
people willing to ask enough hard questions that we can be confident we
have an understanding of the problem in IETF. Right now, it looks like most
people are afraid to ask the obvious questions for fear of looking foolish.

I can explain RSA or DH to people with very little mathematical knowledge
beyond algebra. I literally have a degree in nuclear physics. If the people
presenting themselves as experts in this space are unable to explain the
issues with clarity, not only do I not understand the issues, I am unable
to determine if they understand them either.

Like my college tutor used to say, "There are two ways of constructing a
software design: One way is to make it so simple that there are obviously
no deficiencies, and the other way is to make it so complicated that there
are no obvious deficiencies. The first method is far more difficult."



> > I’m trying to figure out what you’re saying; at least one of us is
> confused.  NIST asked for a Key Exchange Mechanism (KEM), and Kyber meets
> that definition (which is essentially what you describe; both sides gets a
> shared secret).  That is the functionality that TLS needs, and is the
> functionality that NIST (and others) evaluated.  Yes, there are internal
> functions within Kyber; no one is suggesting those be used directly.  And,
> yes, NIST might tweak the precise definition of Kyber before it is formally
> approved; any such tweak would be minor (and there might not be any at
> all); if they do make such a change, it should not be difficult to modify
> any draft we put out to account for that change.
>
> I thought KEM expanded to "Key Encapsulation Mechanism" (viz RFC 9180).
> Indeed, my understanding is that PHB's specific point is that it is *not*
> an exchange, and rather that the sender picks a key and the recipient just
> gets that key without contributing do it.
> (Well, I think there is maybe also some bit in PHB's note that's quibbling
> about how the sender doesn't actually pick the key, and rather the local
> output of the KEM is the encapsulated blob plus the shared key, with the
> shared key not being an input to the KEM ... but I haven't read NIST's
> report yet and can't confirm or reject that assertion.)  I am reading PHB
> as saying that the "internal function" within Kyber that is an "actual KEM"
> is one that takes the shared key as input and produces the encapsulated
> blob as output (again, cannot confirm or reject).
>

It is a bit more than a quibble.

If we are going to make TLS post quantum, we have to allow for the
possibility that we have to change the PQC crypto. There are still laptops
and weekends after all. And if we depend on the replacement algorithm
providing for key recovery, we are going to have to add in additional key
wrap to make things work.


> It was my understanding that TLS 1.3 didn’t do rekeys
> (ChangeCipherSuite).  Instead, the key agreement is done only at connection
> establishment time, and could be broken into:
>

TLS doesn't call them rekeys because it considers each new session to be a
separate protocol exchange. But if you consider all the interactions as
being part of a single protocol, resumption is actually rekeying. That is
why 0-RTT is 'possible', we are not doing 0-RTT, we just called the setup
part of something else.



> >   *   Full negotiation (the client not having any context)
> >   *   Resumption (0-RTT or 1-RTT) negotiation (where the client has some
> secret data from a previous full negotiation)
> > Because those are both fresh negotiations, I don’t see any alternative
> to using a postquantum key exchange for both.
>

Are you proposing pure Kyber or a hybrid though?

Do we really trust the output of the competition enough to make it a single
point of failure in the most widely used cryptographic protocol? That would
seem to be an astonishing decision and one that I for one would be unable
to support.

Until we have PQC certificates, the initial exchange is going to be
classical. Including the output of the initial exchange in the ephemeral
exchange makes the system a hybrid exchange that is secure against QCC and
a breach of the PQC algorithm.