I have been reading up on RSA attacks and came across one that could be called a least-significant-bit (LSB) oracle attack.

For the sake of clarity lets define RSA primes $(p, q)$, private key $d$ and the public key $(e, N)$ where $N$ is the modulus.

Now assume an oracle exists that will decrypt a given ciphertext $C$ using the private key $d$ and checks the parity of the decrypted cipher. i.e. it will return true or false if the decrypted cipher was even or odd respectively.

If an attacker intercepts an encrypted plaintext $C = P^e \mod N$ he could multiply it by $2^e\mod N$ (essentially doubling the original plaintext) and send it to the oracle. The oracle will decrypt and find $2P\mod N$. Now if $2P>N$ then the remainer will be odd, since $N$ is odd. If $2P<N$ then the remainder will be guaranteed to be even. The attacker will now know that either $P<N/2$ (oracle returned even) or $P>N/2$ (oracle returned odd).

This is the part where I am stuck, because apparantly you can somehow iteratively apply this principle and by iteratively shrinking the bounds of $P$ completely recover $P$ in $\log_{2}N$ iterations. I am having trouble seeing how the iteration would work.

If possible I would prefer a hint over a fully written out solution as I will learn more from doing it myself. I just need a little nudge in the right direction. Much appreciated.

  • Have you read e.g. Fischlin and Schnorr's "Stronger Security Proofs for RSA and Rabin Bits"? – K.G. Oct 15 '13 at 10:47
  • Just a small sidenote: N is not prime (4th paragraph), it is odd. It should be ".. remainder will be odd, since N is odd, 2P is even and 2P<2N". – tylo Oct 15 '13 at 15:16
  • @tylo you are completely right, changed the mistake. I was able to solve it yesterday very much like you suggested in your answer. I will be adding my eventual approach as well for completeness, but you have my upvote – Pankrates Oct 15 '13 at 16:17
up vote 8 down vote accepted

Here's the next step in the iteration, which should be easy to understand:

Let's call the oracle on 2P and 4P:

  • Answer (even,even) means, that $P<N/4$ (this is still easy: Otherwise either 2P or 4P would be greater than N).
  • Answer (even,odd) means $N/4<P<N/2$.
  • (odd,even) means $N/2<P<3N/4$
  • and (odd,odd) means $3/4N<P<N$.

Actually, some of those $<$ should be $\le$, but you get the picture.

If you continue with multiplying the factor for P with 2, you get the next round of iteration, where "odd" indicates the upper half of the interval and "even" indicates the lower half.

  • we know that P < N, if 2P is odd, then 2P > N => P > N/2, if 4P is odd, then 4P > N => P > N/4. Where does that 3/4 comes from? – David 天宇 Wong Apr 16 '16 at 15:57
  • 1
    ah, found out why :) the second iteration in an odd odd, you are not using 4P, but rather 2(2P-N) because we already had 2P > N – David 天宇 Wong Apr 16 '16 at 16:45

The approach with which I solved the problem is indeed as @tylo suggested. Initially we know that the target plaintext $P$ is within the bounds $[0,N]$ where the lower bound $LB=0$ and the upper bound $UB=N$.

Now we iterate the following algorithm $log_{2}N$ times to find P from the original intercepted ciphertext $C$

$C' = (2^{e}\mod N) * C$

if (Oracle(C') == even)
    UB = (UB + LB)/2;
else
    LB = (UB + LB)/2;

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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