Subject: [Lake] Forward Security with PSK-Only LAKE

From: Karthik Bhargavan <[email-masked]>
Date: Fri, 17 Jan 2020 11:31:36 +0100

At the virtual interim call, Ekr mentioned how TLS resumption provides a form of forward secrecy (without the need for Diffie-Hellman).
I was not sure whether others on the call understood what he was referring to, so I thought it would be useful for me to write it out in some detail.

High-level Summary:
You don’t need DH for forward secrecy.
If A and B share a PSK and are willing to maintain some state in the form of a session counter, we can build a PSK-based LAKE that does not require DH, but does provide forward secrecy.
The key idea is that after each AKE, A and B derive a new PSK and throw away the old PSK.

———

At the beginning of a session: 
A and B have a PSK K, associated with id I, and a session counter C
(Initially, C is 0, but as we will see in the following protocol, at the end of each AKE, the counter increases by 1.)

A -> B: m1 = N_A, I, C, other_params
B -> A: m2 = N_B, other_params

K_m = HKDF(K, “mac_key”, m1 | m2)
K_e1 = HKDF(K, “ae_key A -> B”, m1 | m2)
K_e2 = HKDF(K, “ae_key B -> A”, m1 | m2)

A -> B: m3 = MAC(K_m, m1 | m2)
A -> B: AEAD(K_e1, msg0, …)
B -> A: AEAD(K_e2, msg1,…)

A and B set C <- C + 1, K <- HKDF(K, I, C+1)
A and B throw away the old PSK K.

--------

The above protocol can be generalized in several ways.
First, A and B need not have exactly the same counter C, instead they could negotiate the MAX of their two counters and derive the PSK corresponding to that counter.
Second, A and B may share both a long-term PSK K0 and an ephemeral PSK K and mix them both together in the protocol above. 
This provides a clean separation between the PSK used for authentication and the PSK used for forward secrecy.
Third, we may use the protocol above as a “fast resumption” mechanism but fall back to full PSK-ECDHE whenever we want.

To conclude, I wonder if we should explicitly consider a mechanism like the above as a requirement for LAKE.
It appears to meet the security goals we have set for PSK-LAKE and it is a good example of what can be achieved without an expensive DH operation.
(Incidentally, the message sizes of the protocol above are very tiny.)

-Karthik

---

From: Karthik Bhargavan <[email-masked]>
Date: Fri, 17 Jan 2020 11:58:45 +0100

It looks like I over-simplified the protocol.
Some clarifications and corrections below.

---
A -> B: m1 = N_A, I, C, other_params
B -> A: m2 = N_B, other_params, MAC(K_mB, m1 | m2)
A -> B: MAC(K_mA, m1 | m2)
A -> B: AEAD(K_eA, msg0,…)
B -> A: AEAD(K_eB, msg1,…)
——

At the end of a session:

Note:
- N_A and N_B are nonces generated by A and B, respectively.
- K_mA = HKDF(K, “mac_key A”, m1 | m2)
- K_mB = HKDF(K, “mac_key B”, m1 | m2)
- K_eA = HKDF(K, “ae_key A”, m1 | m2)
- K_eB = HKDF(K, “ae_key B”, m1 | m2)

> -- 
> Lake mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/lake

---

From: Eric Rescorla <[email-masked]>
Date: Fri, 17 Jan 2020 16:37:18 -0800

Thanks Karthik.

Just to sharpen this point: you *do* need a new DH exchange to get PCS, but
not to get PFS.

-Ekr

On Fri, Jan 17, 2020 at 2:58 AM Karthik Bhargavan <
[email-masked]> wrote:

> > First, A and B need not have exactly the same counter C, instead they
> could negotiate the MAX of their two counters and derive the PSK
> corresponding to that counter.
> > Second, A and B may share both a long-term PSK K0 and an ephemeral PSK K
> and mix them both together in the protocol above.
> > Third, we may use the protocol above as a “fast resumption” mechanism
> but fall back to full PSK-ECDHE whenever we want.
> >
> > It appears to meet the security goals we have set for PSK-LAKE and it is
> a good example of what can be achieved without an expensive DH operation.

---

From: Benjamin Beurdouche <[email-masked]>
Date: Sat, 18 Jan 2020 07:58:26 +0100

Yeah, btw, I think it is a minimal requirement to have FS but let’s not call LAKE a secure protocol if it is not gonna provide both FS and PCS for long term sessions...
B.

> On Jan 18, 2020, at 1:38 AM, Eric Rescorla <[email-masked]> wrote:
> 
> 
> Thanks Karthik.
> 
> Just to sharpen this point: you *do* need a new DH exchange to get PCS, but not to get PFS.
> 
> -Ekr
> 
> 
>> On Fri, Jan 17, 2020 at 2:58 AM Karthik Bhargavan <[email-masked]> wrote:
>> > It appears to meet the security goals we have set for PSK-LAKE and it is a good example of what can be achieved without an expensive DH operation..

---

From: Karthik Bhargavan <[email-masked]>
Date: Sat, 18 Jan 2020 11:51:18 +0100

Hi Ekr,

Indeed, the PSK-only protocol I described does not provide post-compromise security (PCS).
But as far as I understand, PCS is not a requirement for LAKE, just as it is not a requirement for TLS 1.3.
(Benjamin, I don’t think you meant to suggest that we cannot call TLS 1.3 a secure protocol?)

Introducing PCS as a requirement would require a larger discussion and more justification.
In any case, we are not yet in the stage of discussing specific protocol designs.
My main motivation was to clarify that we could reuse ideas from TLS resumption to provide a forward secure LAKE without requiring DH.

Best,
Karthik

> On 18 Jan 2020, at 07:58, Benjamin Beurdouche <[email-masked]> wrote:
> 
>> On Fri, Jan 17, 2020 at 2:58 AM Karthik Bhargavan <[email-masked] <mailto:[email-masked]>> wrote:
>> > [email-masked] <mailto:[email-masked]>
>> > https://www.ietf.org/mailman/listinfo/lake <https://www.ietf.org/mailman/listinfo/lake>
>> 
>> -- 
>> Lake mailing list
>> [email-masked] <mailto:[email-masked]>
>> https://www.ietf.org/mailman/listinfo/lake <https://www.ietf.org/mailman/listinfo/lake>
>> -- 
>> Lake mailing list
>> [email-masked]

---

From: Benjamin Beurdouche <[email-masked]>
Date: Sat, 18 Jan 2020 12:22:02 +0100

> On Jan 18, 2020, at 11:51 AM, Karthik Bhargavan <[email-masked]> wrote:
> 
> Hi Ekr,
> 

Ah : ) I guess it all depends on what you build on top of the AKE of course...
But anyhow, TLS is short-lived and even in the case of longer sessions using session tickets,
both peers can decide to start a fresh session by starting a fresh 1RTT handshake, correct ?

The argument of using PSK in contrast of DH to provide FS leads to the thinking that those are equivalent,
which obviously both you and Ekr point out not to be the case regarding PCS and compromise in general.

So, if you tell me that LAKE will provide a mechanism <insert name> (e.g.FS) that enables us to recover secrecy from a
passive compromise while most of the time using the PSK rotation for FS, I am willing to say it is ok.
Otherwise, if there is no hope to introduce freshness via <insert mechanism> (e.g.FS) and that a compromised session will always
remain compromised, I’ll maintain that we cannot claim this to be a secure AKE for protocols we’ll build on top...

For some reason, I see the claim “DH is too costly” has having the dangerous implication
“let’s do long term sessions with PSKs” and I think this is quite dangerous but I might be completely wrong here… : )

B.

---

From: Benjamin Beurdouche <[email-masked]>
Date: Sat, 18 Jan 2020 12:26:58 +0100

> remain compromised, I’ll maintain that we cannot claim this to be a secure AKE for protocols we’ll build on top…

(e.g. FS) -> (e.g. DH) obviously...

---

From: Karthik Bhargavan <[email-masked]>
Date: Sat, 18 Jan 2020 14:22:08 +0100

Yes, I take the point that we should be careful about security guarantees.

Further expanding on Ekr’s comment, one can see that there is room for various AKE modes with different levels of guarantees.
So far, we have mainly been thinking about PSK-ECDHE and SIG-ECDHE modes, since forward security was a core property.
I think  we should also consider a PSK-FS mode that achieves forward security via key derivation.

In practice, we may want devices to e.g.  bootstrap a PSK using SIG-ECDHE and then use PSK-FS for some period of time.
After some period of time, we may want to throw away the PSK and do another SIG-ECDHE from scratch.

-Karthik

> On 18 Jan 2020, at 12:26, Benjamin Beurdouche <[email-masked]> wrote:
> 
>

---

From: John Mattsson <[email-masked]>
Date: Wed, 22 Jan 2020 10:15:44 +0000

Hi Karthik,

This is a very good discussion to have. Agree that a lightweight FS mode without ECDHE is a good thing to have if it is significantly more lightweight than PSK-ECDHE and does not introduce synchronization problems.

Your suggestions for PSK-FS mode got me thinking if the AKE is the right layer to do this lightweight FS. Could it not be done more efficient on the OSCORE layer? E.g.

A                                              B
                    XXX-ECDHE
<---------------------------------------------->

A and B derive OSCORE session key K_eA1 and K_eB1 for OSCORE

A use K_eA1 for sequence number 0-(n-1)

A -> B: AEAD(K_eA1, msg_0,…)
A -> B: AEAD(K_eA1, msg_1,…)

A use K_eA2 = H(k_eA1) for sequence number n-(2n-1) and erases k_eA1 from memory

A -> B: AEAD(K_eA2, msg_n,…)
A -> B: AEAD(K_eA2, msg_n+1,…)

A use K_eA3 = H(k_eA2) for sequence number 2n-(3n-1) and erases k_eA2 from memory

A -> B: AEAD(K_eA3, msg_2n,…)
A -> B: AEAD(K_eA3, msg_2n+1,…)

etc....

Note that OSCORE already have a stateless PSK-FS mode defined in Appendix B.

>In practice, we may want devices to e.g.  bootstrap a PSK using SIG-ECDHE and then use
>PSK-FS for some period of time. After some period of time, we may want to throw away the
>PSK and do another SIG-ECDHE from scratch.

We may want to do that. We may also want to bootstrap a PSK using SIG-ECDHE and then use PSK-ECDHE for some period of time. These have different security properties. To discuss these topics further, I think we should discuss reasonable assumptions of what an attacker has access to in a constrained IoT environment and what kind of practical attacks we want to protect against.
- When an attacker gains physical access to a constrained IoT device, can he/she extract all the information or is long-term keys more protected than session keys?
- Does the attacker have access to all the traffic information? Many contrained IoT environments will be local.
- Is the attacker passive or active?

Cheers,
John

-----Original Message-----
From: Lake <[email-masked]> on behalf of Karthik Bhargavan <[email-masked]>
Date: Saturday, 18 January 2020 at 14:22
To: Benjamin Beurdouche <[email-masked]>
Cc: Eric Rescorla <[email-masked]>, "[email-masked]" <[email-masked]>
Subject: Re: [Lake] Forward Security with PSK-Only LAKE

    
    
    -Karthik