# Providing forward secrecy with RSA

Forward secrecy with RSA is asked here:

The scheme is inefficient because the generation of a new RSA key pair is relatively expensive (and normally rare, thus not optimized for speed)

I will describe a two-pass mechanism; Send a message and receive, done.

As usual, we have Alice with $$(pub_A,prv_A)$$ public-private keys and Bob with $$(pub_B,prv_B)$$ public-private keys with modulus $$n_A$$ and $$n_B$$, respectively. They know the public-keys.

Let $$n = \text{min}\{n_a,n_b\}$$

• Alice chooses a random number $$x$$ and $$1.
• Alice encrypt this with Bob's public key $$c_1 = E(x,pub_B)$$ and sends to Bob.
• Bob receives $$c_1$$ and decrypts $$x= D(c_1,prv_B)$$ to get $$x$$
• Bob chooses a random number $$y$$ and $$1
• Bob encrypt this with Alice's public key $$c_2 = E(y,pub_A)$$ and sends to Alice.
• Alice receives $$c_2$$ and decrypts $$y= D(c_2,prv_A)$$ to get $$y$$
• Finally, Alice and Bob use a KDF to derive the ephemeral key, $$K_{ep} = KDF(x\mathbin\| y)$$ .

It is clear that this doesn't provide integrity. Apart from this

• Is there any security failure? If so, how can we improve it?
• Is there any similar work before?
• Uh, so if both (long term?) private keys are leaked then the scheme would be broken, correct? So you don't claim PFS or do you claim PFS because you need to leak two keys now? – Maarten Bodewes Sep 23 '19 at 21:06
• @MaartenBodewes If both leaked, yes. Is it common? I've seen that from cold-boot attacks. However, a hacker can steal secret by other means. – kelalaka Sep 23 '19 at 21:13
• I see this as a similar scheme as performing an RSA_ ciphersuite using TLS, but by providing a pre-master secret from both sides and including that in the KDF. The advantage of the TLS version is that it also provides authenticity, of course at the expense of possible attacks on the RSA padding method. – Maarten Bodewes Sep 23 '19 at 21:25
• @MaartenBodewes same problem, if private keys can be leaked, pre-master keys, too. If you are in TLS, you can always have authenticity easily, right? – kelalaka Sep 23 '19 at 21:40
• Yeah, sure, but maybe not as efficiently. Just one RSA operation on each side is pretty OK. But your scheme doesn't have Forward Secrecy in my opinion. That it is more secure in most configurations is probably true so it may have practical merit, but that's not the same as having the FS property in a theoretical sense. – Maarten Bodewes Sep 23 '19 at 21:48

Some limitations of the proposed protocol:

1. It only applies when both parties have a private key, not in the common browser-connects-to-server scenario.
2. As noted by others, it is not true Forward Secrecy, for it does not protect from leak of both private keys.
3. Authentication of parties is not provided before knowledge of $$K_{ep}$$ is demonstrated, in a step not illustrated (easily added).
4. The scheme is only marginally less costly than authenticated Diffie-Hellman with long-term RSA keys, which solves 1 and 2.
5. The output of a participant's random generator can be scrutinized by an active adversary with a public key recognized by said participant.
Illustration: Bob or Trudy connects to Alice under his real identity. Alice (accepting Bob, and perhaps Trudy with less privileges) generates a random number using her RNG and sends it encrypted. He deciphers it, gaining insight about what Alice's RNG has output. Poor RNGs and poorly seeded CSPRNGs are legion in the history of security breaches.
6. And if that participant's random generator becomes predictable, that participant's ability to authenticate (per the method in 3) falls apart, and with that the confidentiality of whatever it's willing to transmit encrypted only to selected authenticated participants.
Illustration: Trudy, having learned a defect in Alice's RNG, can impersonate Bob because he can find $$x$$ by trial and error, rather than with Bob's private key. He can then receive and decipher whatever confidential information Alice is willing to send to Bob.
7. Bob has some control on $$K_{ep}$$.
Illustration: Bob is tricked into using rigged software that chooses $$y$$ iteratively so that the top 40 bits of $$K_{ep} = KDF(x\mathbin\| y)$$ are some secret function of the other 88 bits. Even though Bob runs that software in a firewalled VM and has audited that it sends nothing but what it is supposed to send, confidentiality is doomed.
• 7 ist inherent to a two-round protocol though, isn't it? – Maeher Sep 25 '19 at 11:00
• 0. I was considering that they know each others public key beforehand. They know the public-keys I think this is short to cover that. 1. + , 2. + 3 -> 0. 5. I didn't get it 6. I've forgotten to say they have a good CSPRNG 7. If you mean a weak generator, ok, otherwise do you assume that Bob is not honest in two-party communication? If so, he can already sell the key? – kelalaka Sep 25 '19 at 12:40
• @Maeher: indeed, I believe that 7 is avoidable only with an extra round. – fgrieu Sep 25 '19 at 13:04
• @kelalaka: yes, I'm considering that the participants know each other's public key beforehand. This does not prevent an adversary from attempting impersonation, thus authentication is needed. As noted in 3, the protocol almost provides it (only the rightful participants can know $K_{ep}$). For 6 and 7, see updated answer. – fgrieu Sep 25 '19 at 13:52