Re: [CFRG] Kyber 'interactive key agreement'?

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

Having discussed this in other forums, it appears to me that the
fundamental problem here is that we need more than a ten minute
introduction to PQC algorithms before the protocol development community
can fully get to grips with what is going on.

What I thought I was hearing was an introduction to the Kyber algorithm. It
now appears that what I was actually hearing was an introduction to
applying Kyber to certain types of TLS like key exchanges. Hence the
disconnect since at this point my only PQC concerns are for Data at Rest.
That is not going to stop me adding PQC algorithms to my chat clients but I
am doing that because I can, not because I really need to.


My primary PQC concern today is that people are creating a lot of Word,
Excel, Powerpoint etc. documents whose contents are likely to still be
sensitive in 10-30 years time.

My secondary concern is for chat clients using Signal type key exchanges.


What I am seeing is a LOT of incomplete, handwavy statements that suggest
there is a problem using Kyber in legacy protocols without giving concrete
examples. And when I look at the code, those issues disappear.

TLS is at this point probably the most used key exchange scheme in the
world. We have spent over a quarter century securifying it and optimizing
it all the time working within the context of RSA and DH type schemes. So
it is really not at all surprising if such a closely optimized system with
such a vast amount of legacy baggage isn't a clean fit.

'Zero round trip' is not really a thing in existing protocols either. What
appears to be a zero-round trip protocol is in fact an interactive protocol
in which the initial stages have been craftily hidden in a different
infrastructure. That is even the case in S/MIME and OpenPGP. Alice does not
simply send a message to Bob, she first interacts with a PKI to get Bob's
public key. That type of legermain is exactly what cryptographic protocol
architecture is all about. The only thing Kyber changes is that data
objects end up being too big for a single ethernet packet because the IEEE
is lame and won't give us the 64K frames we need.


When it comes to timing, I remain convinced that nobody is going to have a
Quantum Cryptanalysis Capable (QCC) machine for at least a decade. But I
also agree with Russ Housely that we absolutely have to start work now and
with some urgency if we are going to deliver a PQC internet in time.

Splitting this discussion into 15 minute presentations across a series of
IETF/IRTF working groups is not going to work. We need to have some forum
that is focused on applying PQC algorithms in the abstract before we go to
deployment.

The correct approach to applying PQC in TLS may very well turn out to be to
create a completely new TLS key agreement. If that does turn out to be the
case, we will get there a lot quicker if that option is on the table at the
start rather than spending four or five years trying to make it work before
anyone is allowed to suggest a clean start.



On Tue, Aug 2, 2022 at 3:51 PM Thom Wiggers <[e-mail]> wrote:

> Hi Philip,
>
> The most common situations I've found where KEMs don't work as a drop-in
> for DH are when you want to do some authentication scheme.
>
> For example, consider the OPTLS/draft-tls-semistatic proposals. In OPTLS,
> the client sends over a g^x as usual, but the server takes that public key
> and directly combines it with its long-term DH secret s to compute g^{xs}
> (which OPTLS uses to compute a MAC). That's precisely the DH operation that
> KEMs don't give you. To do OPTLS with KEMs, you need an extra round-trip:
> the client needs to first receive the long-term KEM secret before it can
> send back an encapsulation.[1] KEMTLS/draft-celi-wiggers-tls-authkem uses
> some tricks to do basically that, but avoid the round-trip.
>
> Ephemeral KEM key exchange in TLS (1.3) doesn't have this problem, because
> authentication is done via signature. Plain old signatures are generally
> non-interactive (putting all of the additional PQ signatures baggage aside).
>
> DH is amazingly symmetric in its operations, and it seems to be turning
> out that this property was a big gift.
>
> In some discussions with Trevor Perrin about Noise protocols it seemed
> that there are two obvious ways out of this mess (at least for Noise
> protocols): an extra round-trip, or adding signatures. Of course, adding
> either to a protocol that did not have them is kind of a bummer.
>
> Cheers,
>
> Thom
>
> [1]: This was first discussed, as far as we're aware of, in the master's
> thesis of Wouter Kuhnen (OPTLS revisited, section 6.2)
> http://www.ru.nl/publish/pages/769526/thesis-final.pdf
>
> Op di 2 aug. 2022 om 19:58 schreef Bas Westerbaan <bas=
> [e-mail]>:
>
>> This might not look like it is a drop in replacement for ECDH,
>>>
>>
>> It is not. But for TLS it is sufficient: client generates a keypair and
>> sends pk. Server encapsulates for that pk and returns the created
>> ciphertext.
>>
>>
>>> [These routines call indcpa_enc, indcpa_dec which have rather different
>>> signatures. But the external interface is drop-in as far as I can see.]
>>>
>>
>> Don't use those.
>>
>>
>>> I did a search on 'malleability' in the Kyber paper and found nothing.
>>> So perhaps a clarification of the terms.
>>>
>>
>> The term you want to search for is IND-CCA2.
>>
>> Best,
>>
>>  Bas
>> _______________________________________________
>> CFRG mailing list
>> [e-mail]
>> https://www.irtf.org/mailman/listinfo/cfrg
>>
>