Providing forward secrecy with RSA

Question

Forward secrecy with RSA is asked here:

• Is perfect-forward secrecy achieved with RSA? and fgrieu gave an answer based on creating temporary RSA keys and signing them. And, in the end, he mentions

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<x< n$.
• 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<y< n$
• 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?

Answer 1

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.}