14
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • $\begingroup$ 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). $\endgroup$
    – j.p.
    Oct 19, 2013 at 13:12
  • $\begingroup$ This might help crypto.stackexchange.com/questions/12688/… $\endgroup$
    – Bush
    Oct 1, 2014 at 10:33
  • $\begingroup$ Even though late, still appreciated, however the link leads to a 404 $\endgroup$
    – Pankrates
    May 28, 2015 at 23:29
  • $\begingroup$ @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. $\endgroup$
    – Maarten Bodewes - on strike ♦
    Apr 11, 2016 at 11:15
  • $\begingroup$ @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. $\endgroup$
    – Pankrates
    Apr 12, 2016 at 1:31

1 Answer 1

Reset to default
4
$\begingroup$

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. :)

Improve this answer
$\endgroup$
1
  • $\begingroup$ Note that when you do that, you're effictivrpy taking the intersections between previous intervals and newly calculated intervals. You need to dismiss incorrect ranges ( [a,b] where a > b ) $\endgroup$
    – David 天宇 Wong
    May 16, 2018 at 11:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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