3
$\begingroup$

I was reading an article about breaking RSA with PKCSv1.5 padding (http://mslc.ctf.su/wp/google-ctf-spotted-wobbegong-crypto-100/). It says that while retrieving the message we multiply by the inverse fraction and take modulus of a power of 2 rather than modulo N.

But how do we determine which power of 2 to be used ? Is it a trial and error or can we determine it from the length of the message ?

$\endgroup$
3
$\begingroup$

First of all, this attack assumes that we have a decryption Oracle; that is, an Oracle that we can submit any ciphertext to (except for, apparently, the challenge ciphertext), and it will tell us that the padding is bad, or it will give us the decrypted message (minus the padding).

In the attack, we're given the challenge ciphertext $(Pad + M)^e$, and we select a simple rational value $r/s$ near 1, we submit to the Oracle the ciphertext $(r s^{-1})^e (Pad + M)^e$, and if $Pad+M$ happens to be a multiple of $s$ (and the padding looks valid), we get the lower $n$ bytes of $r/s (Pad + M)$

Your question really is: given the lower $n$ bytes of $r/s (Pad + M)$ (which we will call $R$), how can we recover the lower $n$ bytes of $Pad + M$? That's actually fairly simple; essentially we need to compute $s/r R \bmod 2^{8n}$. Now, the divide by $r$ is slightly tricky (and computing $r^{-1} \bmod 2^{8n})$ is the wrong approach); however we know that the full value $r/s (Pad + M)$ is a multiple of $r$, and so one way to do is is to find the value $0 \le k < r$ such that $R + ks^{8n}$ is a multiple of $r$, and then divide that by $r$; that'll give the same lower bytes as the original $r/s(Pad + M)$.

Now, going back to looking at this attack in general, we find this attack is less powerful than the Blechenbacker attack, which will allow us to decrypt any message, and makes weaker assumptions on the Oracle (namely it doesn't have to give us the decrypted text on success; only notify us that success did happen). This attack does have the advantage that, if successful, it requires fewer queries (but it won't always be successful, perhaps $Pad+M$ doesn't happen to have any small divisors), and it is easier to understand.

$\endgroup$

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.