2
$\begingroup$

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

  1. Generate a random element $1<m<n$ 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}<m<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.

$\endgroup$
3
$\begingroup$

Q1: The random selection should be $\sqrt[3]{n}<m<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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – kelalaka Sep 14 at 12:37

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.