# How can I show RSA-OAEP is not IND-CCA secure if G always outputs 0 (i.e. there is no hash function)?

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

• 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? Apr 6, 2020 at 23:08
• 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)?
– fgrieu
Apr 7, 2020 at 9:26
• 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.
– fgrieu
Apr 7, 2020 at 9:31
• $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? Apr 7, 2020 at 10:04
• $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.
– fgrieu
Apr 7, 2020 at 10:13

$$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.
• 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! Apr 7, 2020 at 10:31