Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
7  
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 at 8:13

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer
1  
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 at 6:32
1  
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 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.

share|improve this answer
7  
This is a bit cryptic for those without access to the book. –  otus Aug 1 at 8:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.