Random Masking of Padded RSA Ciphertext through homomorphism

Question

I had asked a question related to this before: Oblivious Decryption: Decrypting with a private key, without knowing the message

@rikhavshah has an answer, which I would like to discuss the security of.

Simply put:

• Alice has an RSA public key $(e, N)$ and a private key $(d,N)$
• There's a ciphertext $x$, padded and encrypted using Alice's public key.
• Bob doesn't know what the padded plaintext $m_p$ is, but has the ciphertext $x$.
• Bob randomly chooses a mask $r$ from $\{1,\cdots,N-1\}$, calculates $x\,r^e\bmod N$ and sends it to Alice.
• Alice decrypts $x\,r^e$ by computing $(x\,r^e)^d\bmod N$, which is also $x^d\,r\bmod N$, and sends it to Bob
• Bob multiples the value by $r^{-1}$ (the modular multiplicative inverse of $r$ modulo $N$, which with overwhelming odds is well-defined) to extract $x^d\bmod N = m_p$. And later on removes/decodes the padding to extract $m$.

This way, Alice decrypts $x$, without knowing what $m_p$ is. Bob knows the value of $m_p$ without knowing the value of Alice's private exponent $d$

Is there a known attack, that this scheme is vulnerable to? Can the choice of $r$ make this more or less secure? Or simply, how can we approach this scheme and make it secure?

Note: as @rikhavshah has also mentioned in their answer, this has a potential attack where Bob can get Alice to decrypt anything encrypted with her public key. But this is actually what the scheme requires. So I wouldn't consider this as a vulnerability. And please assume, they are using a signature scheme to verify each-others identity.

Answer 1

In the last bullet of the question, Bob computes $x^d\bmod N=m_p$. This the padded message $m$. Padding must be removed from $m_p$ by Bob to get back $m$. And serious problems can occur if Bob leaks at what step the padding check fails, just like in James Manger's A Chosen Ciphertext Attack on RSA Optimal Asymmetric Encryption Padding (OAEP) as Standardized in PKCS #1 v2.0 (in proceedings of Crypto 2001).

If Bob leaks where the padding fails (e.g. by timing), and allows that to occur often enough (some thousands times) for different $x$ chosen by an adversary, then an active adversary can decipher a message, unbeknown to Bob, even though Alice would have refused to decipher the message should the adversary have asked Alice directly (because Alice authenticates who she accepts messages from).

---

There is no proof that having $(N,e)$ and the capability to raise to the power $d$ modulo $N$ (by querying Alice) does not allow Bob to factorize $N$ and get at $d$ (or an equivalent). That's only widely conjectured.

It should also be emphasized that Bob does not have $d$, but has access to something almost as good: the capability to raise to the power $d$ modulo $N$. And he can share that capability (by forwarding requests to Alice and her answers, or just revealing his credentials w.r.t. Alice).

Also: even with secure padding such as OAEP verified by Bob without leaking anything other than success/failure, Bob should still be careful that messages deciphered with the help of Alice that pass the padding check are in no way authenticated. For example, if a (genuine) message $x$ has deciphered to "the winner is Carol", and Bob later gets a message $x'$ that decipher to "repeat: winner is Malory", Bob should not leak that he is surprised, for that would reveal that the winner is not Malory to whoever (e.g. Malory) generated the bogus $x'$.

Aside of these, and standard implementation attacks on Alice and Bob (e.g. side-channel leakage), I see no other attack specific to the protocol.

Per comment: I do not see that the protocol is sensitive to minor imperfection in the generator for $r$, including w.r.t. Alice trying to get at $m$.