Generate shared secrets using RSA

Question

Before explaining my question, please let me introduce the scenario:

• There are 2 type of actors: 1 server and N clients
• Each actor has a RSA 2048 bit private/public key
• The server knows all the clients public keys
• The clients know the public key of the server

The desired goals are the following:

• Clients must authenticate themselves to the server
• Integrity must be guaranteed for all exchanged messages
• Secrecy is a plus but not mandatory

A solution that came to my mind is to share a secret between all server-client pairs and then proceed by sending the messages concatenated to the MAC

Server ---- M | MAC(M) ----> Client
Client <--- M | MAC(M) ----- Server

Then on top of this, a challenge-response protocol is used to guarantee the authenticity of the clients.

However, by searching online I was not able to find a "standard" way to generate a shared secret using RSA. I was only able to find DH or ECC protocols for this.

There is a well-defined scheme based on RSA to obtain a shared secret or the aforementioned goals?

Answer 1

What you want to do is establish a shared, authenticity guaranteeing channel assuming both sides know a fixed public key (either RSA or ECDH based) of each other.

Transport Layer Security (TLS) can do that and really should be used if possible, given that it also takes care of things like state management and replay-prevention for you. If you need a list of embedded-friendly TLS libraries have a look here and also note that TLS does offer cipher suites which only perform authentication and no encryption if the cost of encryption is unbearable to you (though many implementations don't actually have them).

Alternatively if TLS is really not an option and you have the replay-protection figured out, you can also just use RSA signatures (not to be confused with the integrity guarantees provided by RSA encryption!). This can be done either by using RSA-PSS (preferred these days) or by using RSA-PKCSv15 signatures, both of which are supported by LibTomCrypt (your currently preferred library) and guarantee that the signed message actually came from the owner of the associated public / private key and was not altered and can be verified just using the public key.

But now to the question you asked (but probably didn't mean to ask):

There is a well defined scheme based on RSA to obtain a shared secret or the aforementioned goals?

The standard way to do this (and the way TLS does it) is that one side of the exchange picks a random number (e.g. 64 bytes long) and then encrypts it with the other side's public RSA key (and e.g. RSA-OAEP).

If you also want to ensure that the sender is actually who they claim to be, simply sign the resulting ciphertext and enforce signature-checking on the receiver-side.

In addition to this how can I avoid reply attacks?

If there is a a relieable clock on the devices one could e.g. send nonce+timestamp pairs and clean nonces from the cache after e.g. an hour (assuming the nonces are covered in the signed data). Alternatively one could have the recipient send a fresh nonce and the next message must use that nonce so that only one nonce needs to be stored.

That means the first approach would mean this message format:

$$\text{Timestamp}\parallel \text{SenderNonce}\parallel M\parallel \operatorname{Sign}(\text{Timestamp}\parallel \text{FreshSenderChosenNonce}\parallel M)$$

and discard nonces from memory after one hour. Or alternatively

$$\text{ReceiverNonce}\parallel \text{SenderNonce}\parallel M\parallel \operatorname{Sign}(\text{ReceiverNonce}\parallel \text{SenderNonce}\parallel M)$$

where ReceiverNonce was transmitted as the nonce to be used on the next transmission from the receiver to the sender.

Answer 2

It is asked (among other things)

a well defined scheme based on RSA to obtain a shared secret

The NIST has a recommendation SP 800-56B Rev. 1, titled Recommendation for Pair-Wise Key-Establishment Schemes Using Integer Factorization Cryptography. There's a draft Rev. 2. These propose several key agreement schemes based on RSA (not requiring DH or ECDH). The key established will be used for integrity and (optionally) confidentiality, using symmetric cryptography and some authenticated encryption.

In the situation where both parties have a public/private key pair and know the other party's public key, KAS2 or KTS-KEM-KWS with Key Confirmation are applicable. KEM is conceptually simpler, thus probably better.

Beware that

• The security analysis assumes that RSA public/private keys used by these schemes are used exclusively for the purpose of key establishment.
• These schemes do not provide forward secrecy (which is difficult with RSA).
• Security is lost if the Random Number Generator used to generate the shared key is predictable.

---

That other answer hints at other solutions, including some that solve the above issues, make use of RSA and asymmetric keys as in the question, but additionally require DH or ECDH.