1
$\begingroup$

Here is what I understand the algorithm to be:

Let $G, H$ be one-way functions, where G outputs the 0 string.

πΈπ‘›π‘π‘œπ‘‘π‘’

  • Select a random $π‘˜$-bit integer $π‘Ÿ$.
  • Pad out $π‘š$ with $0$s to length $𝑙=|𝑁|βˆ’π‘˜.$
  • Compute $𝑋=𝐺(π‘Ÿ)βŠ•π‘š_{π‘π‘Žπ‘‘π‘‘π‘’π‘‘}$ (i.e. $X = π‘š_{π‘π‘Žπ‘‘π‘‘π‘’π‘‘}$)
  • Compute $π‘Œ=π‘ŸβŠ•π»(𝑋)$
  • Return $𝑋||π‘Œ$

π·π‘’π‘π‘œπ‘‘π‘’

  • Compute $r = Y \oplus H(X)$
  • Compute $m_{padded} = X \oplus G(r)$ (i.e. $m_{padded} = X$)
  • Strip off the $0$s from $X = π‘š_{π‘π‘Žπ‘‘π‘‘π‘’π‘‘}$ to recover $π‘š$

IND-CCA Game

The IND-CCA game in this case is as follows:

  • The adversary selects two messages $π‘š_0,π‘š_1$ and submits them to a decryption oracle $O$.
  • The decryption oracle samples $π‘βˆˆ\{0,1\}$ and computes $𝑐*= \textrm{RSA-OAEP}(π‘š_𝑏)$.
  • The adversary is free to perform more decryptions, except for the one condition that $O(cβˆ—)$ will return $βŠ₯$.
  • To conclude, the adversary must guess $𝑏$ corresponding to the message that was encrypted.

Work towards showing that algorithm is not IND-CCA secure

The adversary need only recover $X$ from $c$, where $c = \textrm{RSA_OAEP}(m_b) = \textrm{RSA}(X||Y)$. Very basic question, but is $m_b \in \{b||m_1, b||m_2\}$? If so, then the adversary would know that $X||Y$ differs by $|X|$ significant digits depending on the value of $b$. However, $Y$ will always differ since $b$ is random, so $c = \textrm{RSA}(X||Y)$ will also always differ.

Unsure of where to go from here, any help would be much appreciated!

The adversary wants to output either the plaintext or $\bot$. For RSA-OAEP, $βŠ₯$ is output when either the adversary tries to decrypt $c*$, or if the first half of the padding is not the 0 string then the decryption fails. Could we try multiplying $m_0 = 0...0$ and $m_1 =$ random with $2^e$ mod $N$?

$\endgroup$
  • $\begingroup$ Thanks for the help and the welcome! I reintroduced $G$ to my question to make what I'm asking clearer - initially I just removed $G$ from the algorithm for brevity. However, I am not sure that the same plaintext will encrypt to the same ciphertext, given that $m$ will encode to $X||Y$ rather than just $X$. Also, for the basic question, if $m_b$ is just one digit, does it need to be padded for length requirements? $\endgroup$ – remana Apr 6 at 23:08
  • $\begingroup$ Independently of the defective $G$, the question's OAEP is not RSAES-OAEP as practiced, which includes consistency check in the Decode procedure. Combined with the defective $G$ (RSAES-OAEP's MGF), that allows an attack in the IND-CCA2 game (not IND-CCA1). Hint: what if having received a ciphertext $C_b$ for $m_b$ from the encryption oracle, the adversary submits $Nβˆ’C_b$ to the decryption oracle (which IND-CCA2 essentially allows)? $\endgroup$ – fgrieu Apr 7 at 9:26
  • $\begingroup$ Independently of the above comment: the defective $G$ allows the adversary to choose values of $m_b$ that consistently make $X\mathbin\|Y$ relatively small, and that makes the RSA primitive less resilient, especially for low $e$ and narrow $H$. But that attack is not specific to IND-CCA, thus probably this is not what the problem's author has in mind. $\endgroup$ – fgrieu Apr 7 at 9:31
  • $\begingroup$ $N - C_b$ undergoes RSA decoding, $(N - C_b)^d$ mod $N = (-C_b)^d$ mod $N$ = $\pm m_b$ mod $N$, since ${C_b}^d$ mod $N$ decrypts to $m_b$ by definition of its encryption. So it decrypts to either $N - m_b$ or $m_b$ depending on whether $d$ is even? $\endgroup$ – remana Apr 7 at 10:04
  • $\begingroup$ $d$ is always odd in RSA. Somewhat you think that $m_b={C_b}^d\bmod N$, and but that has no reason to hold. Check more carefully how encryption works: it applies the encoding, then applies raw RSA encryption. $\endgroup$ – fgrieu Apr 7 at 10:13
0
$\begingroup$

$b$ is random

Yes, but it is random in the set $\{0,1\}$. $b$ reflects the coin toss made by the decryption oracle / challenger in the IND-CCA game to decide if s/he encrypts $m_0$ or $m_1$ at the second bullet.

Does $m_b \in \{b\mathbin\|m_1,\ b\mathbin\|m_2\}$ ?

No in general, and that holds even if we fix the indices to be in $\{0,1\}$ rather than $\{1,2\}$. The intended meaning of $m_b$ is: $$m_b=\begin{cases}m_0&\text{if }b=0\\m_1&\text{if }b=1\\\end{cases}$$ otherwise said, $b=0\implies m_b=m_0$, and $b=1\implies m_b=m_1$. Thus $m_b \in \{m_0, m_1\}$ with no concatenation involved. Note: the IND-CCA game allows to choose the two messages $m_0$ and $m_1$ equal, but that's a silly move.

| improve this answer | |
$\endgroup$
  • $\begingroup$ I see, I was thinking of $b \in \{0,1\}$ as being part of the encryption, rather than relating to the subscript of the two messages $m_0$, $m_1$ generated by the adversary. Thank you! $\endgroup$ – remana Apr 7 at 10:31

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.