Skip to main content
5 of 5
Typo
fgrieu
  • 145.5k
  • 12
  • 319
  • 611

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.

fgrieu
  • 145.5k
  • 12
  • 319
  • 611