Re: [Lake] Static-DH-based Protocols for LAKE

[Karthikeyan Bhargavan <[e-mail]>]

Hi Goran

> https://ericssonresearch.github.io/EDHOC/OPTLS-type-authentication/draft-selander-ace-cose-ecdhe.html#rfc.appendix.B <https://ericssonresearch.github.io/EDHOC/OPTLS-type-authentication/draft-selander-ace-cose-ecdhe.html#rfc.appendix.B>

Thanks for the GitHub link, I was not aware of this version.

> The protocol specified in Appendix B in the github is very similar to what you spell out in the mail below and with the same favorable message overhead as you listed in the table below. There are also the differences which we would like to understand in detail, but haven't had time to look at yet. Obviously, the ability to prove strong security properties should be guiding the detailed design. Also, it should be noted that the protocol in Appendix B is not optimized.

Indeed, it will be good to thrash through the options here. 
As I noted, there are many variants that will do the job, as long as we can agree what the constraints are.

> In our understanding of the requirements, we are targeting an AKE with three modes: PSK-only, RPK and certificate based. For PSK-only we do not require static DH-keys (which you do not either in your PSK LAKE instance below). For the certificate based mode we are requested to support signature-based public keys, since that is what is standardized and available in e.g. the X.509 based ecosystem. This does not exclude the use of certificates with static DH-keys, but for wide applicability we can't restrict to that certificate use case. The static DH mode corresponds in our view to an intermediate mode of the protocol between PSK-only and signature based. This is what we intended with the protocol setup as described in the github version, but this is still open for discussion and in particular in the details. 

One possibility for the certificate-based mode is to use a delegated credential. 
That is, use an X.509 certificate as usual, and use the leaf key to sign the DH key.
This adds the bit-cost of one signature, but since such credentials can be cached, this need not be not be a recurring cost.

In fact, the TLS 1.3 semi-static DH draft (https://tools.ietf.org/html/draft-rescorla-tls-semistatic-dh-01 <https://tools.ietf.org/html/draft-rescorla-tls-semistatic-dh-01>) also proposes a DH-based key exchange (a different variant),
and it relies on delegated credentials (https://tools.ietf.org/html/draft-ietf-tls-subcerts-04 <https://tools.ietf.org/html/draft-ietf-tls-subcerts-04>).

> It is interesting to note the trade-off your highlight between ID-PSK privacy and server authentication in the second message. The preferences of the community on this point still needs to be understood.

Yes, this will be good to understand. I find it a bit strange that we are working so hard to protect the privacy public key identities but that we do not try to protect PSK identifiers.

Best,
Karthik

> 
> Looking forward to an interesting discussion!
> 
> Göran
> 
> 
> On 2019-10-23, 13:13, "Lake on behalf of Karthikeyan Bhargavan" <[e-mail] on behalf of [e-mail]> wrote:
> 
>    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)
> 
> 
> 
>