17

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?

Ben Lamm
  • 273
  • 1
  • 2
  • 6
  • 12
    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 01 '14 at 08:13

2 Answers2

15

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.

kelalaka
  • 48,443
  • 11
  • 116
  • 196
fgrieu
  • 140,762
  • 12
  • 307
  • 587
  • 5
    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 02 '14 at 06:32
  • 7
    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 03 '14 at 16:31
1

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.