[Lake] Static-DH-based Protocols for LAKE

[Karthikeyan Bhargavan <[e-mail]>]

Hello All,

In my team, we have been formally analyzing various key exchange protocols, including some that use static Diffie-Hellman keys for authentication.
Some of these protocols would be particularly suited to LAKE, and I note that Appendix B of EDHOC draft 14 already hints at this.
I wouldn’t be surprised if this has already been discussed before, so do let me know if I am repeating things everyone knows.

For concreteness, I am sketching two protocols below and comparing them with EDHOC.
If there is interest in the working group, we could write up a more detailed, more general document describing the protocols and their formal analysis.

Static DH+PSK LAKE
==================
I propose the following composite protocol that uses both static DH and PSK (where the PSK can be set to Zero if unavailable).
We could easily remove PSKs from this protocol, but I left it in to show how the two authentication mechanism can be composed to obtain extra security.
In particular, the PSK could include some external key material (e.g. a key generated from a PQ-KEM ), and the use of PSK can protect against some bad-randomness vulnerabilities.

For those familiar with the Noise protocol framework, this protocol corresponds to XXpsk3, except that I am using EDHOC notation here to more clearly link the protocol to LAKE:

I -> R: TYPE, SUITES_U, G_X, C_U, UAD_1  
R->I:   C_U, G_Y, C_V, AEAD(K_2a; ID_CRED_V), AEAD(K_2b; UAD_2)
I->R: C_V, AEAD(K_3a; ID_CRED_U, ID_PSK), AEAD(K_3b; PAD_3)

Many of the elements here are the same as EDHOC:
- G_X = g^x: the initiator’s ephemeral public key
- G_Y = g^y: the responder’s ephemeral public key

Some things are different:
- ID_CRED_V is used to retrieve g^v, the responder's static Diffie-Hellman key
- ID_CRED_U is used to retrieve g^u, the initiator's static Diffie-Hellman key
- ID_PSK is used to retrieve a PSK (potentially a string of zeroes)
- K_2a is derived as KDF(g^xy, TH_2a)
- K_2b is derived as KDF(K_2a, g^xv, TH_2b)
- K_3a is derived as KDF(K_2b, g^uy, TH_3a)
- K_3b is derived as KDF(K_3a, PSK, TH_3b)

The transcripts are computed as usual:
- TH_2a includes the first message and all elements of the second message up to C_V
- TH_2b includes the first message and all elements of the second message up to the first AEAD
- TH_3a includes the first two messages and all elements of the third message up to C_V
- TH_3b includes the first two messages and all elements of the third message up to the first AEAD

Security guarantees: Assuming standard assumptions on full strength cryptographic primitives
- UAD_1 is insecure: no authenticity or confidentiality
- UAD_2 is authenticated by R and can only be read by the client who knows x.
- PAD_3 is secure: it can be read and written only by I and R.
- All messages from PAD_3 onwards have forward secrecy and KCI resistance

Message Sizes: Using the same overhead numbers as in the EDHOC draft
- 1st message: 38 bytes
- 2nd message: 58 bytes
- 3rd message: 34 bytes

Note:
- These calculations assume 8-byte AEAD tags.
  With full 16-byte tags, the sizes would be: 38, 74, 42
- This protocol combines the security of PSK and Asymmetric authentication at little cost.
   Removing PSKs would change only the third message, bringing sizes to: 38,58,32
 
PSK LAKE
=========

For completeness, here is the protocol using only PSKs and no static DH.
In Noise notation, this corresponds to the NNpsk3 pattern.

I -> R: TYPE, SUITES_U, G_X, C_U, UAD_1  
R->I:   C_U, G_Y, C_V, AEAD(K_2a;  UAD_2)
I->R: C_V, AEAD(K_3a; ID_PSK), AEAD(K_3b; PAD_3)

Keys:
- K_2a is derived as KDF(g^xy,TH_2a)
- K_3a is derived as KDF(K_2a, TH_3a)
- K_3b is derived as KDF(K_3a, TH_3b)

Message sizes: assuming full-sized AEAD tags and the same overheads as EDHOC
- 1st message: 38 bytes
- 2nd message: 45 bytes
- 3rd message: 13 bytes

Note:
- This protocol has the same structure as the more general protocol, except that it does not use static DH keys
- An important difference between this proposal and the EDHOC PSK case, is that here, we seek to provide privacy for ID_PSK by putting it in the third message.
- We could modify both protocols to send ID_PSK in the first message.
  This has a privacy cost, but the benefit that we can obtain server authentication already at the second message.


MANY OTHER VARIANTS
======================

I have sketched the above variants only to give rough examples of what we think are lightweight protocols for which we can prove strong security properties.
Many other variations are possible and may be worth considering. 

I am looking forward to your comments, especially if I am misunderstanding some requirements.

Best regards,
Karthik
(Inria Prosecco)