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$?
$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&amp;\text{if }b=0\\m_1&amp;\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.