# Bleichenbacher attack, binary search, formula for $s_i$

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$...

• Can you add more details? Specifically, what is the formula obtained before picking r? – Ritam Bhaumik Dec 21 '16 at 8:53
• @RitamBhaumik please use the links in the question – CaptainRR Dec 21 '16 at 9:30

## 2 Answers

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.

• Thanks for the explanation (and for the article)! Recently I implemented the attack and carried out several experiments with the constant $r$. The both ways actually work, but original $r = ceil((b*si - B2)*2,n)$ leads to less number of iterations. Anyway, thanks once again! – CaptainRR Dec 31 '16 at 8:22

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

• I removed previous comment, sorry for misleading you. I the original paper at hal.inria.fr/file/index/docid/704790/filename/RR-7944.pdf , Page 6, Step 2c they use $r_i >= 2\frac{bs_{i-1} - 2B}{n}$, so is this a typo in the paper? – CaptainRR Dec 21 '16 at 9:55
• Looks like it, yes. It is best to mail them for a clarification. (The algorithm may work even for this starting value of r, but the guarantee of halving the search space does not seem to work. – Ritam Bhaumik Dec 21 '16 at 10:03