Why RSA-KEM is more secure than Textbook-RSA?

Question

I am studying RSA-KEM but I can not see why it should be as secure as padding RSA messages (e.g with RSA-OAEP) when exchanging a key between two parties (say A and B).

It is easy to see that Textbook-RSA is problematic, as sending a key with $k_1^{e_B} \bmod n$ leaves the possibility for an attacker to analyze the message. Let's say that by coincidence A sends to B a second key $k_2^{e_B} = (42 k_1)^{e_B} = 42^{e_B} k_1^{e_B}$ (in the following $\bmod n$ is always omitted). An attacker could easily notice this as it could divide $k_2^{e_B}$ by $42^{e_B}$.

Now let us suppose that A and B are using RSA-KEM to exchange keys. An attacker cannot detect anymore if e.g. $k_2 = 42 k_1$ as a key encapsulation key is used to encrypt the shared key. However, the random integer to generate the key encapsulation key is still encrypted over Textbook-RSA.

Why is this not a problem? An attacker is still able to perform e.g. statistical analysis on the randomly exchanged integer, e.g. if A and B again perform two key exchanges and it happens that $r_2 = 6943 r_1$ an attacker may be able to notice this and eventually even find out the random integers, thus breaking the shared key as it depends on these integers.

Answer 1

Why is this not a problem?

Because for two different encryptions the random integers are drawn independently and uniformly at random over the whole range of the multipicative group $\mathbb Z_N^*$ (in practice this is usually approximated as $[1,n)$). The RSA assumption now literally states that it's difficult to recover the random value from its textbook RSA encryption if it is sampled in this way.

if A and B again perform two key exchanges and it happens that $r_2 = 6943 r_1$ an attacker may be able to notice this and eventually even find out the random integers

Actually this won't happen because both $r_1,r_2$ are independently random, so is their group combination $r_1/r_2$ which has a chance of $2^{b-n}$ to be smaller than $2^b$ for $n$-bit RSA moduli, so for a really generous estimate suppose you are betting on $r_1/r_2$ to be guessable small, say smaller than $2^{60}$ and using weak 1024-bit RSA encryption, then you have a chance of $2^{60-1024}\approx 2^{-940}$ of the quotient being sufficiently small. This is a really negligible probability and likely won't ever be observed.

Answer 2

The standard criterion for security is indistinguishability under adaptive chosen-ciphertext attack, or IND-CCA2. What this means is that the adversary is given:

• the public key $(n, e_B)$, and
• an oracle that answers queries of the form: What is the plaintext for the ciphertext message $c$?

The adversary's task is to find any pair of messages with a pattern they can distinguish in the corresponding ciphertexts. Specifically, perhaps after interacting with the oracle, the adversary chooses two messages $m_0 \ne m_1$, and asks to be challenged with the ciphertext $c_b$ for $m_b$ where $b$ is a secret coin toss not known to the adversary; the adversary then wins the game if they guess correctly what $b$ was.

If ‘encryption’ is $m \mapsto m^{e_B} \bmod n$, then this is very easy! The adversary can furnish any pair of plaintexts $m_0 \ne m_1$, and check whether $c_b \stackrel?= {m_0}^{e_B} \bmod n$ or $c_b \stackrel?= {m_1}^{e_B} \bmod n$ to determine what $b$ was. What this illustrates is that public-key encryption must be randomized so that the adversary cannot simply confirm guesses about what the plaintext is.

---

‘But,’ you object, ‘I said the plaintext is a random key which the adversary cannot predict!’ Well, security in your scenario is weaker than security in the IND-CCA2 scenario, because you've added extra assumptions about how the legitimate users use the cryptosystem. But OK, let's say you add that assumption.

For example, let's say the legitimate users use RSA-2048 to encrypt AES-256 keys for AES-GCM, and let's say they pick the exponent that gives the best performance: $e_B = 3$. Now when you send me $$c = {k_1}^{e_B} \bmod n = {k_1}^3 \bmod n,$$ I can simply compute the real number cube root $\sqrt[3] c$ to recover what $k_1$ was, because as an integer, $0 \leq k_1 < 2^{256}$, so that ${k_1}^3 < 2^{768} \lll n$, which means the $\bmod n$ part never kicked in with parameters of this size! Oops.

You might object that $e = 3$ is bad, but even with larger exponents like $e = 65537$ there are all manner of elaborate attacks using black magic like continued fractions or lattice algorithms on structured messages such as 256-bit strings. The problem is that the RSA trapdoor permutation $x \mapsto x^e \bmod n$ is bad at concealing structured messages. It's only good at concealing uniform random elements of $\mathbb Z/n\mathbb Z$.

What's different about RSA-KEM is that you choose a secret integer $x$ uniformly at random below $n$ independently for each message, and then hash it to derive your AES-256 key $k_1 = H(x)$ while transmitting the encapsulation $y = x^e \bmod n$ so the recipient can recover $x$. Note that $x$ is not restricted to $0 \leq x < 2^{256}$; it is only restricted to $0 \leq x < n$. This means that any adversary defined in terms of a generic hash function $H$ can easily be shown to be able to compute arbitrary $e^{\mathit{th}}$ roots modulo $n$, meaning that such an adversary is guaranteed to be able to solve the RSA problem.

(And the most efficient exponent 3 is just fine with RSA-KEM, as it is with any serious public-key encryption scheme built out of RSA.)

Answer 3

RSA-KEM is not working as you described. RSA-KEM mitigates the attack that you have described, RSA-KEM simply as follows;

1. First generate a random $x \in [2..n\hbox{-}1]$, $n$ is the RSA modulus.
2. Encrypt the $x$, $c \equiv x^c \bmod n$
3. Send $c$
4. The other side will decrypt to get $x = c^d \bmod n$. Now both side has $x$.
5. To derive a key both sides use a Key Derivation function on $x$, $key= \operatorname{KDF}(x)$

If you send the key itself you will need a padding scheme like OAEP to prevent the attacks on textbook RSA. KEM eliminates this by using the full modulus as message.

How to use it to encrypt a message

Per message choose a new random $x$ and derived a new $key$ to encrypt messages. Use an authentication on the encryption like HMAC or better use Authenticated Encryption like AES-GCM or ChaCha20-Poly1305.

$$ciphertext = \operatorname{AES-GCM}(m, key)$$

Encapsulate the Key $$c = x^e$$

Now send the other side $$(c,ciphertext)$$

The other side, first decrypts $c$ to get $x$ then will use $ \operatorname{KDF}(x)$ to find the encryption key and finally will decrypt AES-GCM.

• If there is an integrity error, then you know that an attacker played with the transmitted message or there is a transmission error.

• Can the attacker guess my key? If I used a bad random number generator, yes. Otherwise no since there is $1/2^{128}$ if you generate the key for AES-128.