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$?

Improve this question
$\endgroup$
7
  • $\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, 2020 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, 2020 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, 2020 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, 2020 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, 2020 at 10:13

1 Answer 1

Reset to default
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$
1
  • $\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, 2020 at 10:31

Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.