# Bleichenbacher 1998 “Million message attack” on RSA

I have been reading Bleichenbacher's 1998 paper on a forged message attack on RSA. The paper assumes access to an Oracle that takes a ciphertext $c$ and will check the decrypted text for valid PKCS #1 padding and returns the validity of the padding. This side-channel can be used for an attack since we can send a forged ciphertext by selecting random integers $s$ and compute:

$c' = cs^{e}\, \mbox{mod}\, n$

If $c'$ is PKCS conforming we know that the two most significant bytes of $ms = c'^{d} \mbox{mod}\,n$ were equal to 0x00 0x02. If we define

$B=2^{8(k-2)}$

where $k$ is the length of $n$ in bytes, then we know

$2B\leq ms\,\mbox{mod}\,n<3B$

Now we have a range $M_{0}$ in which we know $ms$ to lie:

$M_{0} = {[2B, 3B-1]}$

The attack now proceeds by iteratively generating more valid forged ciphertexts for integers $s_{i}$ and with the gained knowledge reduce the range of $M_{i}$

I am having trouble understanding Step 3 in the paper which deals with narrowing the set of solutions:

$M_{i} \leftarrow \cup_{a, b, r} \lbrace [\mbox{max}(a, [\frac{2B+rn}{s_{i}}]), \mbox{min}(b, [\frac{3B-1+rn}{s_{i}}])]\rbrace$

for all $[a,b] \in M_{i-1}$ and $\frac{as_{i}-3B+1}{n}\leq r< \frac{bs_{i}-2B}{n}$

How would this be implemented in code? It looks to me that we would need to compute each range for every $r$ within the specified bounds e.g.:

for (r=r_min; r<r_max; ++r)
max(a, x);
min(b, y);


However this seems to be intractable to me and I think I am making an error in trying to convert the math to code. Anyone maybe see where I am going wrong?

-
Yes, you have to compute the interval for each possible $r$ (by looping over $r$). The reason is that for big $s_i$ the current interval $[a, b]$ can be stretched by multiplying with $s_i$ so long that it intersects $[2B+rn, 3Brn-1]$ for several $r$. (In the line starting with $M_i \leftarrow$ you should have $s_i$ in the denominator). – j.p. Oct 19 '13 at 13:12
This might help crypto.stackexchange.com/questions/12688/… – Bush Oct 1 '14 at 10:33
Even though late, still appreciated, however the link leads to a 404 – Pankrates May 28 '15 at 23:29
@Pankrates Is this still unanswered in your opinion? Note that if you've solved it you can self-answer as well. I currently see a single answer that was posted long after you've asked the question, but I'm not sure if it answers your particular question. – Maarten Bodewes Apr 11 at 11:15
@Maarten I just saw your comment and the answer you are referring to. It has been a while since my question and it is difficult to recall whether this solves my issue. I might try to revisit it in the near future to see if it does but right now I don't have the time unfortunately. – Pankrates Apr 12 at 1:31

I implemented this padding oracle attack some time ago in Python and remember this part being a bit confusing to wrap my head around, my code is as follows:

newM = []
for (a, b) in M:
# util.ceiling rounds arg1 / arg2 to the next highest integer
rlow = util.ceiling((a*s - 3*B + 1), n)
rhigh = (b*s - 2*B) / n

for r in range(rlow, rhigh + 1):
newa = max(a, util.ceiling(2*B + r*n, s))
newb = min(b, (3*B - 1 + r*n) / s)
newM.append((newa, newb))

M = list(set(newM))


So basically for each (a, b) pair in the set M you have to calculate the range of possible r values and create a new pair for each r. Since the pairs (a, b) are such that a <= b, calling max for the first element and min for the second element ensures that for any (a, b) the new value of a can only increase and b can only decrease. Said another way, you never increase the range, you are always narrowing it down. So while the amount of pairs in M does increase for a while it eventually does decrease back down to one pair (a, b) where a = b.

Hope that is somewhat helpful. :)

-