Forward Secrecy with Symmetric Cryptography?

In cryptography, forward secrecy is a property of key establishment protocols. The Handbook of Applied Cryptography (HoAC) defines a protocol to have forward secrecy if the compromise of long-term secrets (e.g. long-term keys) does not compromise past session keys. In other words, all previous sessions – e.g. past communication sessions with an online banking site or an online store like Amazon – remain securily locked in the past. It should be noted that this post refers to the forward secrecy property of cryptographic key establishment protocols; forward secrecy in the context of random number generators is a different topic.

Intuitively, in the context of key establishment protocols, the term forward secrecy is somewhat misleading since it has the word forward in it, but actually says something about the past sessions. Basically, the idea behind forward secrecy is that the entire message traffic prior to the compromise of the long-term key(s) cannot be easily decrypted by the attacker, i.e. the traffic is locked securily in the past. Here, ‘easily’ means that the attacker cannot efficiently decrypt the traffic unless she knows a polynomial-time algorithm for solving the underlying mathematical problem of the cryptographic scheme, e.g. an algorithm for solving the Diffie-Hellman Problem (DLP) for the Diffie-Hellman (DH) key agreement protocol. Problems like DLP are believed to be computationally intractable – NP-hard in the complexity theory parlance – because since decades (DH, for instance, was introduced in 1976), no one was able to come up with an efficient method to solve them. That is essentially the reason why such problems form the basis of widely used modern cryptographic protocols like TLS.

Why Woul You Want to Have Forward Secrecy?

Imagine two embassies exchanging messages on political matters. To ensure confidentiality, the embassies encrypt their communication sessions using session keys. Obviously, it would be disastreuous if an attacker, say another nation state, could read the messages transmitted during all previous sessions just by compromising a single long-term key.

With forward secrecy, the attacker has to spend the same amount of work to decrypt any single previous session. In other words, even if the attacker succeeds in compromising the long-term key, she has to spend the same – practically infeasible – effort to decrypt any previous session as if she had no knowledge of the long-term key.

For a more day-to-day example, assume the private key of a service like Gmail or Twitter gets compromised. Even if the compromise is noted by the service provider, without forward secrecy the attackers can read all previous sessions of every user. And there’s nothing you can do about it, because the works even if your own machine is perfectly secure. With forward secrecy, even if an adversary is currently recording all Twitter users’ encrypted traffic, and later cracks or steals Twitter’s private keys, the attacker won’t be able to use those keys to decrypt the recorded traffic.

The Definition Zoo

There seems to exist a definition zoo for forward secrecy. Compared to other some other topics, the forward secrecy zoo is quite small. Nonetheless, the subtle differences in the definitions do lead to confusion and heated debates whether a certain scheme has forward secrecy or not.

According to the seminal Handbook of Applied Cryptography by Menezes, van Oorschot, and Vanstone, a protocol is said to have forward secrecy if compromise of long-term keys does not compromise past session keys. The discussion of the definition goes on to explain how forward secrecy can be achieved (namely, using the Diffie-Hellman key agreement) and that, if long-term keys are compromised, future sessions are (nonetheless) subject to impersonation by an active adversary.

Noteworthy is that the above definition assumes an active attacker. This assumption implies that the compromise of long-term keys always leads to a complete break of the key exchange scheme. Because the adversary is allowed to impersonate any of the compromised parties, she can always actively participate in the key agreement phase and thus retrieve that specific session key.

In Security Engineering, Ross Anderson introduces the notion of forward secrecy under the name forward security. Anderson starts by introducing autokeying, a mechanism where two or more parties who share a key hash it at agreed times with the messages they have exchanged since the last key change: \(K_{i+1}=h(K_i,M_{i1},M_{i2},\ldots )\). If an attacker compromises one of the parties and steals their key, then as soon as the legitimate parties exchange a message which the attacker doesn’t observe or guess, the attacker can no longer decrypt their traffic (i.e. the security is restored). Anderson refers to this property as forward security mentioning that the use of asymmetric crypto allows a slightly stronger form of forward security. Namely, that as soon as a compromised party exchanges a message with an uncrompromised one which the opponent doesn’t control, the security can be recovered even if the message is in plain sight.

In Cryptography: Theory and Practice, Stinson defines a key exchange scheme to have the forward secrecy property if the attacker cannot learn the values of previous session keys. Stinson describes scenarios where the adversary learns the value of a particular session key or the long-term keys of one or more participants. Now the purpose of forward secrecy according to Stinson is to limit the damage that is done in these types of attacks.

The BSI Technical Guideline on Cryptographic Mechanisms and Key Lengths defines forward secrecy as a property of a key exchange protocol where an attacker who knows (i.e. obtained in some way) the long-term secrets of one or both communicating parties, is not able to determine the session key for any session she has not compromised.

The BSI definition is similar to the Anderson definition in that it is not limited to past sessions. In contrast to the HoAC definition, the BSI definition trades the adversarial strength for additional guarantees in the time dimension. Essentiall, by saying that the adversary is not able to determine the session key for any session she has not compromised, the BSI definition assumes a weaker adversary than the HoAC definition. Concretely, the BSI definition includes an attacker who, after she compromised the long-term key of one of the legitimate parties, can only eavesdrop on the communication. In other words, the BSI definition allows a passive attacker (after the key compromise) while the HoAC definition explicitly states that the attacker is allowed to impersonate any of the compromised parties, i.e. it allows/assumes an active attacker.

On the other hand, for the chosen attacker type, the BSI definition implies a qualitative difference between e.g. Diffie-Hellman scheme and a symmetric primitive-based protocol. In particular, under the BSI definition, Diffie-Hellman is stronger than any symmetric primitive-based protocol because in case of a passive attacker, future Diffie-Hellman session keys (i.e. the session keys established after the long-term key compromise) are not affected, while the future session keys derived by any symmetric scheme are compromised.

In HMQV: A High-Performance Secure Diffie-Hellman Protocol, Krawczyk presents HMQV – a variant of the MQV protocol – that provides the same performance and functionality, but for which all the MQV’s security goals can be formally proved in the random oracle model (under the computational Diffie-Hellman assumption). For the HMQV protocol, Krawczyk introduced the notion of weak forward secrecy.

As summarized by Cremers and Feltz, Krawczyk sketches a generic attack where the adversary actively interferes with the legitimated communicating parties by injecting self-constructed messages. This enables her to compute the session key if she later learns the long-term secret keys of the parties. When the long-term keys are compromised, the weak forward secrecy property guarantees that previously established session keys remain secret, but only for sessions in which the adversary did not actively interfere.

The notion of weak forward secrecy turns out to be interesting in applied cryptography, because in practice mounting an active attack is much harder than simply recording past communications, and, as a result, can typically be performed on a smaller number of sessions.

Can you achieve forward secrecy without asymmetric crypto?

The short answer is: it depends. It depends on the definition you choose, that is.

Forward secrecy is typically associated with Public Key Cryptography (PKC) and, in particular, with key agreement schemes based on PKC like the Diffie-Hellman key agreement. Achieving forward secrecy in such protocols requires that the session keys do not depend on the long-term secret as discussed in Forward Secrecy and Its Application to Future Mobile Communications Security by Park, Boyd, and Moon. Moreover, forward secrecy in key agreement protocols can only be achieved if the ephemeral keys are generated using a random number generator that guarantees the enhanced backward secrecy (see the BSI Technical Guideline on Cryptographic Mechanisms and Key Lengths for details).

The fact that the session keys must not depend on the long-term secret implies that there cannot be a symmetric crypto-based key agreement scheme achieving forward secrecy. Nevertheless, according to the definition of forward secrecy in the Handbook of Applied Cryptography, it is possible to achieve using a key update scheme like the one recommended by the BSI Technical Guideline on Cryptographic Mechanisms and Key Lengths.

In a key update scheme, the parties synchronuosly update the session key without an explicit communication. In such a setting, the master key K is updated at the time point t by both (or all) communicating parties. For this purpose, the BSI Technical Guideline on Cryptographic Mechanisms and Key Lengths recommends the following mechanism.

At a time point t both legitimate parties know the (symmetric) key \(K_t\). To establish a new session key, both parties compute

\[K_{t+1}=KDF(s, Label, Context, L, K_t)\]

where \(KDF\) denotes a cryptographic key derivation function, \(s\) is a salt used in the key extraction step, and Label and Context denote the purpose of the derived key and the protocol context, respectively. Furthermore, \(L\) denotes the length of the key \(K_{t+1}\). The BSI technical guideline requires (actually, recommends) to delete \(K_{t}\) and any intermediate results right after the computation of \(K_{t}\) is finished.

Getting back to the original question of this post, the above key update scheme clearly achieves forward secrecy if we only account for the past sessions, i.e. the sessions before the long-term key compromise. Basically, because the KDF in the above key update scheme is a cryptographically secure hash function such as HMAC-SHA-256/384/512 or AES-CMAC, it is assumed to be one-way such that the key \(K_t\) cannot be computed from \(K_{t+1}\). Therefore, once the previous key \(K_t\) is deleted, it’s impossible to reconstruct any of the previous session keys \(K_t, K_{t-1}, K_{t-2}, \ldots\).

On the other hand, if future session keys are considered like in the definitions by Anderson and the BSI, the key update scheme does not offer forward secrecy since by compromising the key \(K_t\) the adversary can infer every future session key \(K_{t+1+i}, i\in \mathbb{N}\).