Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


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?

share|improve this question
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… – 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. :)

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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