[Cryptography] Kyber PQC Key Exchange

[Phillip Hallam-Baker]

On Mon, Aug 8, 2022 at 4:48 AM Kristian Gjøsteen <kristian.gjosteen at ntnu.no>
wrote:

> 31. jul. 2022 kl. 17:11 skrev Phillip Hallam-Baker <phill at hallambaker.com
> >:
> > I am trying to get some info on the mechanism underlying NIST's chosen
> key exchange, Kyber. So far the most accessible explanation is the Python
> implementation.
> >
> > If we are going to adopt a new approach to public key, some of us will
> want to understand it. And academic papers that spend the entire time
> referring to the differences with the previous papers are really no help at
> all.
> >
> > So does anyone have a pointer to a YouTube with a good description of
> the Lattice crypto approach? Just telling me something is a lattice is
> really telling me nothing at all. It might as well be a Hausdorffian
> Manifold with Lipschitz signature.
> >
> > At least some of the information I have received is inconsistent. I am
> told that I can't use Kyber as a drop in for ECDH because it is an
> interactive key exchange. The API seems to suggest otherwise. From a
> protocol design point of view, there is really no difference between a Key
> Agreement and a Key Encapsulation that can't be fixed with a bit of Key
> Wrap.
> >
> > The use case I have in mind is:
> >
> > 1) Alice exchanges public keys with Bob.
> > 2) Alice writes a Word document and encrypts to Bob's public key
> > 3) Alice puts enveloped Word document on thumb drive and mails it to Bob
> > 4) Bob gets the thumb drive and decrypts the document.
> >
> > From what was said at the CFRG meeting, I was expecting I might have to
> do an El Gamal like move and create an ephemeral key pair per document to
> encrypt. But that doesn't seem to be the case looking at the API.
> >
> > Then I find mention of 'malleability' which seems utterly odd to me
> since that is an integrity issue and not a confidentiality concern. And I
> can't find the word 'malleable' in the paper.
>
> Hi,
>
> Kyber is what cryptographers call a *key encapsulation mechanism* (KEM).
>
> There are two interesting stories here. The first is how Kyber is
> designed, and the second is how to use a KEM.
>
> *** The first story comes in two parts.
>
> The first part is how to design a public key encryption scheme (PKE) that
> has weak security (ind-cpa is the accepted technical term, essentially
> confidentiality against passive adversaries) based on a lattice problem
> (Module-LWE).
>
> The second is how to turn the PKE into a KEM that has strong security
> (ind-cca, confidentiality against active adversaries), which uses
> Fujisaki-Okamoto (FO). FO is a really nice trick that from the late 90s
> which went out of fashion in the dlog/factoring world because we have
> better tricks there, but has come back into fashion now, since the
> dlog/factoring tricks don’t work very well for most post-quantum schemes
> (for very interesting reasons).
>
> Both of these parts are well-described by the various Kyber papers, if you
> know the requisite background. If you don’t, I don’t really see how an
> implementation can help you. There are probably many good introductory
> videos for lattice cryptography out there, but unless your goal is a
> superficial explanation of the mechanics, you will probably need more.
> There are textbooks that will explain this stuff, if you care. Depending on
> your background and your goal, you will need anything from a few weeks to
> many years to get up to speed.
>
> «Malleable» is a concept that is important for the first story. The PKE
> that Kyber is constructed from is trivially malleable.
>
> Integrity and confidentiality is often tightly linked in applications, in
> the sense that many types of integrity failures lead to confidentiality
> failures. And vice versa.
>
> In practice, a system designer can often (sometimes?) compensate for
> malleability in a black box way, but it is usually easier for the
> cryptographer to deal with this. Which is what FO does.
>
> You usually cannot safely use the PKE scheme for anything sensible unless
> you are a high-powered cryptographer.
>
>
> *** The second story has multiple parts, but your use case suggests that
> you are interested in how to turn the KEM back into a PKE.
>
> (I am guessing that you actually know this stuff, but anyway…)
>
> At this point, it is worth reminding ourselves what the difference between
> a KEM and a PKE is. We all know what a PKE is. A KEM is a restricted sort
> of PKE that will only allow you to encrypt random messages (that’s the keys
> we encapsulate). In particular:
> * For a PKE, the encryption algorithm takes an encryption key and a
> message as input and outputs a ciphertext.
> * For a KEM, the encapsulation algorithm takes an encapsulation key as
> input and outputs a ciphertext and a message (key).
> The key generation and decryption/decapsulation algorithms work as you
> would expect.
>
> So how do we turn a KEM into a PKE? We use a construction called hybrid
> encryption, where we use the KEM to encapsulate a symmetric key and use a
> symmetric cryptosystem to encrypt the message. This is essentially simple.
> If you want multiple recipients, KEMs are slightly more complicated than
> PKEs. (It is probably possible to do a more efficient multi-recipient
> scheme based on Kyber, compared to Kyber used as a black box in the obvious
> fashion.)
>
> Another part of the second story is key exchange.
>
> If you have a KEM, you can do key exchange in a black box way. You can
> either use just the KEM or add signatures if you feel like it. This is easy
> and well-explained in textbooks.
>
> If you have a KEM, you can use it in TLS, but TLS is complex, so this is
> more complicated.
>
> Kyber is not in general a drop-in replacement for DH, but the words «in
> general» are doing a bit of work here.
>
> DH is best thought of as a key exchange scheme, but any such scheme
> trivially becomes a KEM. When you think of your DH as a KEM and only as a
> KEM, then Kyber is usually a drop-in replacement. At least if you don’t
> care about the length of your messages.
>
> If you use DH in a more complicated fashion, for instance for implicitly
> authenticated key exchange or in protocols like Signal, you often rely on
> the symmetry property of DH (both parties do exactly the same mathematical
> operations). Kyber does not have this property. Which means that it is not
> a drop-in replacement.
>
> --
> Kristian Gjøsteen
>

Thanks, this is a useful summary.

As far as protocol design goes, I do not need to understand what is in
the black box. However, I do need to be confident the people who
provided it are. And if they can't explain it to people outside the
number-theory world at a level higher than 'trust us', that is a
problem.

If we think we need to take PQM seriously, then we should take it
seriously and that means more than a 15 minute presentation on the
NIST competition results. An interim meeting with at least a couple of
hours to look into the proposed new apparatus would be the minimum in
my view.

The notion that we take a weak public key system and use particular
chosen constructions to make it robust is not new to us. That was
always the case with RSA which only provides a work factor of 80 bits
across 1024 bits of ciphertext. And as Rogaway pointed out. that is
not evenly distributed either. Hence the need for key wrapping
constructions.

We do need to be very particular about where the black box is drawn
however. What I thought I heard was that the new PQC crypto is a bit
fragile and needs to be considered with care.

I know that Data at Rest is an unfashionable area in data security,
not least because that is where 90% of the breaches that can be
addressed with cryptography occur (the remainder being Data in Use
breaches where cryptography doesn't provide a practical solution
except by turning it into a Data at Rest problem). But when I hear
about a new encryption primitive, that is what I want to hear about
first because that is what NIST-Kyber actually is, it is an encryption
primitive.

While it sounds like the inner mechanism would be sufficient for my
limited purposes, I would never consider using that any more than I
would consider using the inner compressor function of SHA-2 on its
own.


Trying to move too fast tends to slow things down in my experience.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://www.metzdowd.com/pipermail/cryptography/attachments/20220808/a320c171/attachment.htm>