5
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ Can you add more details? Specifically, what is the formula obtained before picking r? $\endgroup$ Dec 21, 2016 at 8:53
  • $\begingroup$ @RitamBhaumik please use the links in the question $\endgroup$
    – CaptainRR
    Dec 21, 2016 at 9:30

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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! $\endgroup$
    – CaptainRR
    Dec 31, 2016 at 8:22
6
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – CaptainRR
    Dec 21, 2016 at 9:55
  • $\begingroup$ 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. $\endgroup$ Dec 21, 2016 at 10:03

Your Answer

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

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