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

[Mike Ounsworth <[e-mail]>]

Uri said:
> In fact, the KEM (crypto_kem_enc(), to be specific) tells the caller what the shared secret will be. This reduces the need for the “post-processing” of the shared secret with KDF to actually generate symmetric keys for the subsequent traffic protection

This is actually a point of contention. I know that the NIST round 3 KEM candidates all finish with a round of SHAKE, and so have this property, but I have not seen any global definition of KEM that requires this property. For example, RFC 5990 which takes RSA-KEM and turns it into a Key Transport specifically does that “post-processing” (RFC 5990 p. 13):

   3. Derive a key-encrypting key KEK of length kekLen bytes from the
      (shared secret) byte string Z using the underlying key derivation function:

         KEK = KDF (Z, kekLen)



So, unless I'm missing something, if you're designing a crypto protocol where choice of algs is left to runtime config, then I think you still need to run the shared secret through a KDF to be sure. (I would love to be wrong about this ...)

---
Mike Ounsworth

From: CFRG <[e-mail]> On Behalf Of Blumenthal, Uri - 0553 - MITLL
Sent: August 4, 2022 4:49 PM
To: Phillip Hallam-Baker <[e-mail]>; Jeff Burdges <[e-mail]>
Cc: IRTF CFRG <[e-mail]>; Bas Westerbaan <bas=[e-mail]>
Subject: [EXTERNAL] Re: [CFRG] Kyber 'interactive key agreement'?

WARNING: This email originated outside of Entrust.
DO NOT CLICK links or attachments unless you trust the sender and know the content is safe.
________________________________________
I’m not sure I fully understand this discussion, but let me jump in. ;-)

IMHO, for the “protocol engineers” there’s nothing to understand about the NIST PQC algorithms, except that

a. These algorithms are all Key Encapsulation Mechanisms, and not Key Agreement mechanisms like, e.g., (EC)DH(E). In that sense, logically they are quite similar to the old now-deprecated RSA key encapsulation, where the client would generate a random symmetric key, encrypt it with the server’s RSA public key, and send this “encapsulated” symmetric key to the server. Thus, you cannot use them directly as a replacement for DH, period. You can create a Key Agreement protocol that uses NIST PQC KEMs as building blocks.
b. Luckily, PQC algorithms do some processing – NIST API does not even allow the caller to pass in the symmetric key to wrap/encapsulate. In fact, the KEM (crypto_kem_enc(), to be specific) tells the caller what the shared secret will be. This reduces the need for the “post-processing” of the shared secret with KDF to actually generate symmetric keys for the subsequent traffic protection, though all the protocols I’m aware of, including mine, do apply KDF to the KEM output.

You wrote that one can use Kyber as a drop-in replacement for ECDH. IMHO, it’s not quite correct, because in DH both sides contribute to the algorithm output, and here the control is on the “wrapper” side…
--
V/R,
Uri

There are two ways to design a system. One is to make it so simple there are obviously no deficiencies.
The other is to make it so complex there are no obvious deficiencies.
                                                                                                                                     -  C. A. R. Hoare


From: CFRG <mailto:[e-mail]> on behalf of Phillip Hallam-Baker <mailto:[e-mail]>
Date: Thursday, August 4, 2022 at 16:18
To: Jeff Burdges <mailto:[e-mail]>
Cc: CFRG <mailto:[e-mail]>, Bas Westerbaan <mailto:bas=[e-mail]>
Subject: Re: [CFRG] Kyber 'interactive key agreement'?



On Thu, Aug 4, 2022 at 2:47 PM Jeff Burdges <mailto:[e-mail]> wrote:


On Aug 4 2022, at 6:38 pm, Phillip Hallam-Baker <mailto:[e-mail]> wrote:
> 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.

Yes.

You'll want to understand the Fujisaki-Okamoto Transform (FO)
https://blog.cryptographyengineering.com/2018/07/

In essence, Alice's key would be vulnerable if she completed a key
exchange with a maliciously constructed public key, so instead Bob
reveals his secret key in an encrypted payload inside the first protocol
move.  Alice simply aborts if she cannot recompute the public key Bob provided.

NIST appear to have chosen the parameters for this competition with extreme subtlety. People who are finding problems here appear to be looking inside the black boxes NIST drew. They drew those boxes for a reason


The description of the parameters seems to be misleading some:

int crypto_kem_enc(unsigned char *ct,
                   unsigned char *ss,
                   const unsigned char *pk)

int crypto_kem_dec(unsigned char *ss,
                   const unsigned char *ct,
                   const unsigned char *sk)

Where:

sk is a sequence of bytes describing a private key
pk is a sequence of bytes describing a private key
ss is a sequence of bytes being the shared secret
ct is a sequence of bytes being the ciphertext

But in DH terms, ct is not a ciphertext, it is a key agreement blob and ss is the key agreement output.

If we write the signatures as:

Wrap (byte[] public, out byte[] recipientData, out byte[] sharedSecret)
UnWrap (byte[] private, byte[] recipientData, out byte[] sharedSecret)

We can see that Alice can't mistakenly reveal data by encrypting to Mallet's maliciously formed public key because Alice does not use her private key in the Wrap operation.

I know I can drop Kyber into my key exchange schemes for the Mesh because I can write the exact same signatures for ECDH.


RSA has serious issues as a result of the algorithm providing plaintext recovery and the fact that the security provided is not constant across all the bits.

As you say, for Noise, this is a drop in replacement. ss, is never used for any purpose other than to feed a KDF.

I am neither surprised nor particularly concerned about Signal's Axolotl ratchet. The notion that we should make use of all the available shared entropy when rekeying is a good principle. The Signal approach to this seems to be overly inflexible.


Any email and files/attachments transmitted with it are confidential and are intended solely for the use of the individual or entity to whom they are addressed. If this message has been sent to you in error, you must not copy, distribute or disclose of the information it contains. Please notify Entrust immediately and delete the message from your system.