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

[Göran Selander <[e-mail]>]

Hi Karthik,

Thanks for your kind mail and for sharing your expertise in this area. Exactly as you propose, for the RPK-based mode there seems to be a good match in using static DH keys for authentication. As you noted, this is what is outline in Appendix B in -14 of EDHOC and is further elaborated in the github version, which will appear in -15:
https://ericssonresearch.github.io/EDHOC/OPTLS-type-authentication/draft-selander-ace-cose-ecdhe.html#rfc.appendix.B

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.

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. 

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.

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)