8
$\begingroup$

Suppose party A generates an ephemeral RSA key and sends the public key to B. Party B then generates a symmetric key, encrypts it with Party A's public key and sends the Ciphertext to Party A. Party A then decrypts the key that party B sent. Parties A and B then use the key that B generated to encrypt data.

Does that meet the definition of Perfect Forward Secrecy? If so does that mean that RSA could still be used in a protocol like TLS and meet the new Perfect Forward Secrecy requirement?

$\endgroup$
9
$\begingroup$

Yes and yes and it already (almost) does.

Forward secrecy is defined with regards to the notion of "long-term secret". The idea is that any secret that is stored for a long time is potentially amenable to ulterior theft. Forward secrecy is obtained when stealing long-term secrets does not allow breaking past communications, and the easiest way to achieve such secrecy is to use ephemeral keys: if a key is not stored anywhere, then it cannot be stolen afterwards.

In older days, SSL/TLS implemented some "export" cipher suites that were meant to comply with the then-strict US export regulation on cryptographic software. When using an "RSA_EXPORT" cipher suite (like TLS_RSA_EXPORT_WITH_DES40_CBC_SHA), the server would have a long-term RSA private key; if that long-term RSA key was longer than 512-bits, then the server would generate a 512-bit ephemeral key pair, sending the public part as a ServerKeyExchange message, signed with the long-term RSA Key. This mechanism was, ironically, meant to support the opposite of forward secrecy, in that the goal was to allow the encryption to be broken through even in cases where the long-term secret was not stolen. However, it demonstrates the mechanism just well: server sends an ephemeral public key for the key exchange, and that public key may be of type RSA.

Some noteworthy details:

  • Though the server sends a RSA public key in a ServerKeyExchange message that it signs itself, and thus can potentially generate an ephemeral key pair, nothing forces the server not to reuse or even store that key pair. In fact, since generating a RSA key pair is a relatively expensive operation, most servers were reusing such key pairs for long period of times; possibly, the 512-bit key pair was stored in a file, or generated upon process startup and reused for weeks. This allows an attacker some time to break the key (512-bit RSA can be broken with relatively little computing power) and use that knowledge in some Man-in-the-Middle attack. This has been dubbed the FREAK attack.

  • Though the "ephemeral RSA" mechanism was defined, it was not updated to longer key lengths, because implementing it was felt to be too clunky and expensive. When SSL/TLS implementations use ephemeral keys, they do so with Diffie-Hellman (DHE cipher suites) or an elliptic-curve variant thereof (ECDHE cipher suites). Diffie-Hellman allows for very efficient generation of a new key pair, contrary to RSA. Moreover, ECDH tends to be a lot more efficient than RSA, both in terms of CPU (less work) and bandwidth (public elements are smaller).

    Using ephemeral RSA key pairs would make sense in the very specific context of an very small, powerless client talking to a big server. On the client side, this would entail only public RSA operations (signature verification, asymmetric encryption) that can be made very fast by using a very small public exponent (e.g. $e = 3$). Clients that are so small that they cannot perform an ECDHE key exchange in reasonable time also have a hard time running a full-fledged SSL/TLS protocol, because of network issues (bandwidth, latency because of the two round-trips...) and lack of readily available implementations that comply to the server constraints of such platforms (code size, very little RAM...).

$\endgroup$
3
$\begingroup$

Yes, the example you present meets the recent definition of Perfect Forward Secrecy. However, I believe the recent definitions created in the wake of surveillance scandals fail to address one feature of forward secrecy that older definitions contained. Some older definitions included the requirement that neither party in the exchange could force the other party to use a key of their choosing. In the example you describe this is obviously not the case. Party B generates the full key. In Diffie-Hellman key exchanges neither party get to force the bits of the shared key to meet some criteria they impose (except for degenerate cases).

When we create key exchanges we want them to be secure for a variety of purposes. The key exchange you present does eliminate long term keys prone to compromise. It doesn't protect against the partial failure of random number generators or prevent one party from forcing bits of the shared key.

$\endgroup$
  • 2
    $\begingroup$ I've got the definition from the STS paper (1992) for you: "An authenticated key exchange protocol provides perfect forward secrecy if disclosure of long-term secret keying material does not compromise the secrecy of the exchanged keys from earlier runs. The property of perfect forward secrecy does not apply to authentication without key exchange." - no mention of "no key control". $\endgroup$ – SEJPM Oct 10 '15 at 16:48
  • 2
    $\begingroup$ If A never reuses the key, it's not clear to me what B-as-adversary can gain by forcing the key to have some property. It looks like the most B can get from that is breaking the encryption on messages B already has. I mean, B could convince A that the messages have been transferred securely when that is not actually the case, but that buys B nothing since B could just forward the messages in cleartext to C after the fact. $\endgroup$ – Kevin Oct 11 '15 at 4:20
3
$\begingroup$

Does that meet the definition of Perfect Forward Secrecy?

If you discard this freshly generated key directly after usage: yes.
Perfect forward secrecy means that an attacker can't learn anything about future session if he breaks the confidentiality of a key of the current session. Applied to this scenario that means that compromise of the ephemeral RSA key must not compromise any other session which is the case.
However this approach has its problems.

If so does that mean that RSA could still be used in a protocol like TLS and meet the new Perfect Forward Secrecy requirement?

Theoretically yes.
Practically allowing usage of RSA for TLS v1.3 wouldn't likely change the current situation concerning RSA usage which was the aim of the TLS WG.
The reason for this is that generating an RSA key is really computationally intensive meaning you want to avoid this whenever possible.
This is especially a severe issue if you compare it with the available alternatives: DHE and ECDHE. The first of these requires two large modular exponentiations per key exchange (requiring f.ex. 11 million cycles) and
the latter only needs two group multiplications and is usually the fastest available method (requiring f.ex. 10 million cycles).
Generating a RSA key on the other hand requires you to find two large primes and not just work with them and finding such primes requires many expensive exponentiations (f.ex. for the Rabin-Miller primality test) and then afterwards you need to perform the RSA decryption operation which by itself is barely competitive with the other key-agreements performance-wise (f.ex. 11 million cycles only for that).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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