# Security of RSA-KEM against cube root attack

In the Key encapsulation article of Wikipedia, the RSA-KEM is described shortly, as follows;

1. Generate a random element $$1 then drive your symmetric key by $$M=\text{KDF}(m)$$
2. Then compute the ciphertext and transmit $$c \equiv m^e \pmod{n}$$
3. The reciever decrypts $$m \equiv c^d \pmod{n}$$ and apply $$M=\text{KDF}(m)$$ to derive the key.

Q1: The random selection should be $$\sqrt[3]{n} due to cube-root attack?

Now at the end the document it says;

An attacker who somehow recovers $$M$$ cannot get the plaintext $$m$$. With the padding approach, he can.

Q2: How can the attacker recover the $$M$$ while there is formal proof of OAEP.

• Is this question about RSAES-OAEP or RSA-KEM? The title says one thing while the body seems to primarily about the other Commented Dec 30, 2021 at 19:06
• @eddydee123 It is about Wikipedia's Key Encapsulation page-related questions. Commented Dec 30, 2021 at 19:15
• @kelalaka Then I suggest changing the title. I asked a closely related question about RSA-KEM and missed this one because of the title Commented Dec 30, 2021 at 19:33

## 1 Answer

Q1: The random selection should be $$\sqrt[3]{n} due to cube-root attack?

Suppose $$n$$ is 2048 bits long. Then $$\sqrt[3] n < 2^{700}$$. If $$m$$ is uniformly distributed in $$\{1, 2, \dots, n - 1, n\}$$, what is $$\Pr[m < \sqrt[3] n]$$? Is this probability large enough that you have to worry about it?

Now at the end the document it says;

An attacker who somehow recovers $$M$$ cannot get the plaintext $$m$$. With the padding approach, he can.

Q2: How can the attacker recover the $$M$$ while there is formal proof of OAEP.

I don't know exactly what the article is getting at here, but what really matters is that even if the adversary has a collection of $$(c, H(m))$$ pairs where $$c = m^e \bmod n$$ and $$H$$ is a random oracle, it doesn't help them to predict $$H(m)$$ given a $$c$$ not previously seen before. Usually the way we use this to encrypt a real message—an arbitrary bit string—is:

1. Use RSA-KEM to generate $$(c, k)$$ where $$k = \operatorname{KDF}(m)$$ and $$c = m^e \bmod n$$.
2. Use $$k$$ as the key for a symmetric authenticated cipher like crypto_secretbox_xsalsa20poly1305 to encrypt the actual plaintext.
3. Transmit $$c$$ along with the authenticated ciphertext.

The recipient can recover $$m = c^d \bmod n$$, and then $$k = \operatorname{KDF}(m)$$, etc.

This composition of a KEM and a DEM (data encapsulation mechanism; an authenticated cipher serves as a DEM) provides the standard of IND-CCA2/NM-CCA2—ciphertext indistinguishability and nonmalleability under adaptive chosen-ciphertext attack.

• I think the revision author confuses the term of his reference article on page 4. For several years, it was widely believed that the security proof for OAP could be extended to the more general model in which the adversaryis allowed to send decryption queries during the entire attack and so on. Commented Sep 14, 2019 at 12:37