# 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 the 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 no 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