[noise] Extra key derivation - use cases, mechanisms

[Alexey Ermishkin]

I have some thoughts about renegotiation which is lazy, lock-free and  app-level transparent.

Inside every encrypted transport message we add a first type byte which can have following values:

"Data" - just an ordinary data packet, nothing to do
"Renegotiation start" - XX/IK/whatever message, depending on what we agreed during the initial handshake. 
"Renegotiation continue" - Sign of processing the previous token + next token message
"Renegotiation done" - Sign of completing the handshake. All following data packets will be encrypted with the new key

Every packet has encrypted data. In case we want to "force" renegotiation, data can be 0 bytes. If we perform a renegotiation, transport packet may contain BOTH handshake message and some "app data" encapsulated inside one data packet.

Suppose we have some data flow between client and server. At some random point client decides to do renegotiation using XX pattern. It has already done handshake and uses key K1 for encrypting transport data. Server uses K2 for encrypting data to client.

When Client wants to send some data to Server it "asks" how much plaintext data will fit into each packet. And when client decides to renegotiate, it gives plaintext a little less packet room, depending on the token message size.

Client->Server : 
len || Enc(K1, "Renegotiation start" || len || first XX message || app data)
It also continues to send data as usual until renegotiation is not completed:

len || Enc(K1, "Data" || app data)
...
len || Enc(K1, "Data" || app data)

Server continues to answer the usual way:
Server->Client:
Len || Enc(K2, "Data" || app data)
...

At some other random point in time, server receives the first renegotiation message and processes it. It then sends to client:
Server->Client:
len || Enc(K2, "Renegotiation Continue" || len || second XX message || app data)
and as usual
...
Len || Enc(K2, "Data" || app data)

At some third random point in time client receives server's answer, containing second XX message, processes it calculating K3 / K4 and sends back the following packet:
Client-> Server
len || Enc(K1, "Renegotiation done" || len || third XX message || app data)
Throws away K1

All following Client->Server packets will be
len || Enc(K3, "Data" app data)

HOWEVER

Until client receives "Renegotiation done" from server, it continues to decrypt server packets using K2

...

At some 4th random point in time Server receives "Renegotiation done" from client, calculates K3/K4,
throws away K1, switching to K3 for decryption messages from client

It also sends
Server->Client:

len || Enc(K2, "Renegotiation done" || len (0) || 0 bytes message || app data)

Throws away K2

and all following messages:

Len || Enc(K4, "Data" || app data)

Client receives "Renegotiation done" from server, throws away old K2, and switches to using K4 for decrypting.

Thus we achieve transparent renegotiation without app level knowing that it happened at all. 
Moreover, we can use advantage of knowing previous static keys / trust and use patterns like KK or even NN


-----Original Message-----
From: Noise [mailto:noise-bounces at moderncrypto.org] On Behalf Of Trevor Perrin
Sent: Saturday, February 25, 2017 11:17 PM
To: noise <noise at moderncrypto.org>
Subject: Re: [noise] Extra key derivation - use cases, mechanisms

Mulling over "rekey" and "extra key derivation" some more:

I'm thinking "rekey" is a good use case for additional key derivation, thus worth supporting in the spec, but other use cases are better handled by applications.

Discussion below, contrasting with TLS at several points.  TLS is the most elaborate example of extra key derivation (e.g. the "resumption", "traffic", and "exporter" secrets in TLS 1.3).  So it's worth looking closely and seeing what that accomplishes.


Use cases:

(1) REKEY:  Deriving a new key k = F(k), where F is a one-way function, has obvious value for forward secrecy.  For maximum flexibility, it should be up to the application if and when to rekey.
However, the mechanism should be very efficient so it could be used frequently (e.g. after every transport message).

TLS 1.3 has focused on less-frequent rekey to limit the data under each cipher key, rather than high-frequency rekey for forward-secrecy.
They've found it acceptable to store an additional "traffic secret"
for rekeying, to send an encrypted message to trigger each update, and to perform 3 HMACs per update.  I think we'd prefer something more efficient.


(2) RESUMPTION:  We might want a key (or keys) from an earlier session to be used as a PSK for a later session.  This could be handled by having the application transmit the PSK, instead of deriving the PSK from other keys:

(a) Security-wise, transmitting the PSK makes it easier for a single session to associate different PSKs with different identifiers or tickets.  This would enable the PSKs to be deleted individually after they are used, for forward secrecy.  By comparison, in TLS 1.3 the server can send multiple new tickets in one session, but all tickets are bound to the session's single resumption PSK.

(b) Security-wise, a transmitted PSK would be protected by the current encryption key, so would get forward-secrecy benefit from rekeying.
This is harder to achieve if resumption PSKs are derived.

For example, in TLS 1.3 the resumption PSK is automatically derived in
the handshake, and is not updated by rekey.   Suppose the server gives
the client a resumption PSK which is used right away for a parallel session.  The client can't delete the resumption PSK without losing the ability to get and use additional session tickets from the initial session, so the forward-secrecy benefit of rekey doesn't apply to the parallel session.

(c) Efficiency-wise, deriving the PSK would seem to save transmission of 32 bytes.  However, if the PSK is transmitted to the client then the server can choose its value.  Thus, instead of storing the PSK inside the session ticket, the server could derive the PSK from a server-side stored key plus the (username, timestamp, and other unique identifiers in the session ticket).  With this, the message-size difference might be small - maybe just several bytes if an extra identifier is needed.


(3) RENEGOTIATION:  We might want to renegotiate a session by performing a new handshake "inside" an existing session, which was supported in TLS prior to 1.3.  The new session would need to bind the old session, e.g. by including the old session's "h" as the new session's prologue.  If this was done, then the new handshake would only be accepted if performed inside the session identified by "h".
This would convince each party that the other party knows the old session's keys, so there would be no need to also use a PSK from the old session.


(4) CHANNEL BINDING: TLS uses an "exporter" mechanism to derive a channel binding value, but Noise just uses the handshake hash "h" for channel binding.  This is simpler, particularly because "h" is defined at all points during the Noise handshake.  By contrast, the TLS "exporter secret" and "early exporter" secrets are only calculated at specific points, so deriving a channel binding from them might not bind more-recently transmitted data.


(5) USING HANDSHAKE INSIDE OTHER PROTOCOLS:  The TLS exporter mechanism is used in EAP-TLS, where the TLS handshake is embedded in some other protocol (EAP), but after the handshake the TLS traffic keys are discarded and some other key is exported.

Alternatively, the traffic key could have been used, instead of discarded.  Similarly, if a Noise handshake is being used as part of some other protocol, the two keys output from Split could simply be repurposed.  Different prologues and/or payloads would prevent cross-protocol attacks in case of key-reuse.


(6) MISC:  Are there other uses for something like "TLS Exporters"?

In general, a premise of Noise (or TLS) is that two parties can communicate over a secure channel.  If cases arise where they need to share small secret keys, they can just transmit them  (point 2, above).  I'm not seeing much gained by special-casing this as "key export" instead of "data transmission".

That said, we've reserved the MAXINT nonce for key derivation.  So we should continue to reserve the ability to do some sort of export / extra key derivation using this, for general future-proofing.

============

In the next draft, I'll try to add a rekey() method on CipherState that just encrypts 32 bytes of zeros using the MAXINT nonce and then sets k to the first 32 bytes of output.  Using this method would be up to the application.

I'll also allow cipher functions to override this with a more specific rekey (e.g. for AESGCMSIV we could do something more efficient instead of going through the entire encryption process).

And I'll mention that this doesn't preclude using the MAXINT nonce from deriving additional secrets (e.g. encrypting 64 bytes of zeros, and using the next 32 bytes for something else).


Thoughts / objections?


Trevor
_______________________________________________
Noise mailing list
Noise at moderncrypto.org
https://moderncrypto.org/mailman/listinfo/noise