2
$\begingroup$

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?

$\endgroup$
2

1 Answer 1

2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.