Can you please explain how Manger's attack against RSA OAEP works?

I searched but found nothing except the original paper, and I can't wrap my head around it. Can you help me by giving an overview and then if possible, a short explanation of the algo?

The big picture

In RSAES-OAEP, for a public modulus $$n$$ of $$8k-7$$ to $$8k$$ bits, a valid ciphertext $$c$$ is (among many other conditions) such that $$(c^d\bmod n)\,<\,2^{8k-8}$$. Manger's attack assumes that adversaries can send queries to a device intended for decryption, which performs that check (as it should), and somewhat leaks if this condition is met or not; which is an implementation error: normally the device should not tell what went wrong with an invalid $$c$$ that it that it received (at least, when a first test that $$c\in[0,n)$$ passes). The leak could be by a specific error code, or by timing.

Given the public key $$(n,e)$$ and any $$c\in[0,n)$$, by sending a number of carefully crafted $$x_i\ne c$$ and analyzing the bits of information $${x_i}^d\bmod n\overset?<2^{k-8}$$ leaking from the device, Manger's attack manages to find $$m=c^d\bmod n$$. If $$c$$ is a valid ciphertext, that can be used to decipher it. If the key is also usable for signature, that could also be used to sign.

Details

The adversary computes and sends $$x_i=c\,{s_i}^e\bmod n$$ for appropriate values of $$s_i$$, and thus learns from the decryption device $$(m\,s_i\bmod n)\overset?<2^{8k-8}$$. By choosing the $$s_i$$ wisely, the adversary narrows down on $$m$$.

[I'm making this a community wiki and leave it to others to detail the steps and remove that note]. This explains it.

• In other words, it uses essentially the same logic as Bleichenbacher's attack against PKCS#1 v1.5 encryption... Jul 12, 2021 at 20:12