# Is perfect-forward secrecy achieved with RSA?

I am new to cryptography and am going through the book Understanding Cryptography by Paar and Pelzl.

From what I understand Symmetric key distribution systems like Kerberos do not provide PFS because an attacker will be able to decrypt every session key ever encrypted with a compromised KEK.

In the book, on page 342, they say that Asymmetric ciphers like Diffie-Hellman or RSA, when used for key distribution, will provide FPS. I understand that Diffie-Hellman will provide PFS because each session key will have nothing to do with any other session key. However I've been stumped for a few days now trying to figure out how RSA will provide PFS. Am I missing something or just misunderstanding what they wrote?

-
You can achieve forward secrecy with RSA if you generate short lived key-pairs. But most protocols that provide forward secrecy use Diffie-Hellman, probably because generating DH keys is cheap and easy compared to RSA keys. – CodesInChaos Aug 1 '14 at 8:13

This expands CodesInChaos's comment into an answer.

Forward Secrecy (that is, maintaining confidentiality of messages enciphered before compromise of the long term key) can be achieved in a protocol using a public-key signature scheme with a long-term public key, and a public-key encryption scheme with a per-session key; but in the case of RSA signature and encryption, that's inefficient, thus unusual.

As an example: Bob has a long-term RSA key pair $(Mpub_B,Mpriv_B)$ used for signature, with $Mpub_B$ trusted by Alice (perhaps by way of some certificate). In order for Alice to send a confidential message to Bob:

• Alice
• draws a 256-bit random $R$
• sends $R$ to Bob
• Bob
• generates a new RSA key pair $(Tpub_B,Tpriv_B)$ used for encryption,
• RSA-signs the (hash of the) message $R\|Tpub_B$ using $Mpriv_B$ giving signature $S$
• sends $Tpub_B\|S$ to Alice
• Alice
• gets $Tpub_B$ and $S$
• verifies that $S$ is a valid signature with respect to $Mpriv_B$ for $R\|Tpub_B$, where $R$ is from the recent first step
• generates a random symmetric session key $K$
• RSA-enciphers $K$ using $Tpub_B$ yielding $X$
• enciphers the plaintext message $M$ using key $K$ by a symmetric algorithm (say, AES-CTR will implicit zero IV) yielding ciphertext $C$
• forgets $K$
• sends $X\|C$ to Bob
• Bob
• gets $X$ and $C$
• RSA-deciphers $X$ using $Tpriv_B$ yielding $K$
• forgets $Tpriv_B$
• deciphers ciphertext $C$ with key $K$ yielding plaintext message $M$
• forgets $K$.

$K$ allows $M$ to be large, when RSA encryption only directly allows short messages. $R$ protects against replay of an earlier $Tpub_B$.

The scheme is inefficient because generation of a new RSA key pair is relatively expensive (and normally rare, thus not optimized for speed). That's a good reason why (EC)DH is most used in practice.

It is possible to send several messages using the same $K$, or/and reuse $(Tpub_B,Tpriv_B)$ across multiple sessions, improving performance. But Forward Secrecy triggers only when $K$ and $Tpriv_B$ are forgotten, and $R$ is not longer accepted.

Note: the scheme provides confidentiality, but not integrity or proof of origin; that can be added.

-
You don't need a per session key. You can reuse it for other sessions as long as you discard it after a short time. For example you could use RSA keys rotated once a minute, that way the key generation cost is amortized over several connections andis no longer a limitation, even with RSA. The main downside ia that it complicates the protocol compared to per session keys. – CodesInChaos Aug 2 '14 at 6:32
One may note that SSL used to support ephemeral RSA keys. It was defined as part of the "RSA_EXPORT" cipher suites, in SSL 3.0 and TLS 1.0 (support was dropped in TLS 1.1). When an RSA_EXPORT cipher suite was chosen and the server's public key length was 513 bits or more, the server had to send a ServerKeyExchange message with a RSA key pair in it. I am not sure many SSL implementations supported it, though. – Thomas Pornin Aug 3 '14 at 16:31

You're missing that key generation would occur inside the box (if there was one for RSA key agreement), like for $k_{pr,A}$ and $k_{pub,A}$ on page 343, rather than outside the box, as happened for $k_{pub,CA}$ on page 347.

-
This is a bit cryptic for those without access to the book. – otus Aug 1 '14 at 8:03