Bleichenbacher attack, binary search, formula for $s_i$

Question

Reading an excellent article explaining Bleichenbacher attack I came across the following statements under the formula for $s_i$:

if we pick $r ≥ 2(bs_{i-1} - 2B) / n$, we obtain

$(2B + 2(bs_{i-1} - 2B)) / b = 2s_{i-1} ≤ s_i$

Can anyone explain to me how the previous equality is obtained? If we try to reproduce it, we'll obviously get:

$(2B + 2bs_{i-1} - 4B)/b=(2bs_{i-1} - 2B)/b=2s_{i-1} - 2B/b$

Why the authors conclude that the result behind is equal $2s_{i-1}$? Moreover, in the code later they use

r = ceil((b*si - B2)*2,n) # starting value for r

as a starting point for $r$...

Answer 1

The statement in the article (I'm the author) is my personal explanation of Bleichenbacher's sentence "We use condition (1) because we want to divide the remaining interval in each iteration roughly in half." (see the original paper at page 4).

But in fact, you are right, equality does not hold. I should have written $(2B + 2(bs_{i-1} - 2B)) / b \approx 2s_{i-1}$, which holds because as you noticed

$$ (2B + 2bs_{i-1} - 4B)/b=(2bs_{i-1} - 2B)/b=2s_{i-1} - 2B/b$$

but $2B/b < 1$ since $b > 2B$ ($b$ is inside the initial interval). Moreover, since we are working with integers $-2B/b$ is ininfluent most of the time. I think this is consistent with Bleichenbacher's "roughly in half", but in fact I've never asked him more detail about how he got that constraint :)

I'll update the article to reflect this discussion (btw I'm glad you liked it).

@Ritam: the attack is very efficient. We have optimised it and implemented on real devices.

Answer 2

Okay, I examined this for a while, and I'm pretty sure this is more of an oversight. They probably wanted to take $r\ge2bs_{i-1}-2B=2(bs_{i-1}-B)$. The same correction should go into the code. (Taking $r=2bs_{i-1}-2B$ is indeed too low a value and does not ensure the doubling of $s_i$ at every successive step, so your observation is correct.)