# 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? – remana Apr 6 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 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 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? – remana Apr 7 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 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! – remana Apr 7 at 10:31