<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On 6 February 2017 at 05:30, Michael Wojcik <span dir="ltr"><<a href="mailto:Michael.Wojcik@microfocus.com" target="_blank">Michael.Wojcik@microfocus.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><br>
The OP had three questions regarding the second paragraph ("Initially, our guess g of q...") of section 3 of the classic Brumley & Boneh paper "Remote Timing Attacks are Practical". Note this paper is from 2003 and refers to OpenSSL 0.9.7. Timing attacks and timing-attack defenses have moved on considerably since then, as have other side-channel attacks. While this paper is a good introduction to the theory and general techniques, it's not a recipe for attacking modern TLS implementations.<br>
<br>
The questions and my responses:<br>
<br>
Q: Does the initial guess of g start from an arbitrary range?<br>
<br>
A: No. First, g *is* the guess; there is no "guess of g". Initial g and the algorithm for refining it is explained here and in the following paragraphs. g is a guess for q. N=pq, q < p. Thus q must be less  than the square root of N. If N is < 2**1024 (a 1024-bit modulus), then q < 2**512. The initial range for g amounts to "g has either its most-significant bit or its second-most-significant bit set, or both". Start with binary 10000... for g.<br>
<br>
Q: What's the rationale behind trying out top 2-3 bits?<br>
<br>
A: Read the algorithm. At each iteration, it proceeds by taking a g that's been found to match q in the i-most-significant bits, and determining the (i+1)th bit. So initially you probe (using timing) the four or eight combinations of the most-significant bits, so you have a starting point.<br></blockquote><div><br></div><div><br></div><div>Thanks a lot for your responses. Probably I should have rephrased my question to make it sound clearer. In the flow of the paper, the technique to determine the top 2-3 bits was introduced before the binary search algorithm (which I understand). What is still not so clear to me what or how they "try out top 2-3 bits". Assuming we are trying out top 2 bits, I assume that 'g' is constructed as follows:</div><div><br></div><div>    - Set the two most significant bits to each one in the set => {00, 01, 10, 11}, one after another</div><div>    - For each of the above cases, fill the remaining 510 bits with *some* bits (are those assumed to be all zero bits?)</div><div><br></div><div>My first doubt is, what will the remaining 510 bits of initial guess 'g' be? Determining the starting point is where I am struggling at the moment. Once I know the top bits, I perfectly understand how the i-th bit is extracted given top (i-1) bits are already known.</div><div><br></div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
Q: What will the remaining bits be in this case?<br>
<br>
A: In what case? At this point in the algorithm you don't know them. You iterate the steps of the algorithm until you know, based on timing differences, that the more-significant half of the bits in your g match those in q (with high probability). Then, as the paper says, you use Coppersmith's algorithm to finish the factorization. (It's been a long time since I looked at Coppersmith's algorithm, so I forget how it works and what constraints there are on it.)<br>
<br>
All the side-channel attacks I can think of offhand do this sort of bit-at-a-time extraction, by the way (which gives them logarithmic time complexity obviously; note B&B characterize it as a "binary search"). So if you're learing about side-channel attacks expect to see more of this.<br>
<span class="HOEnZb"><font color="#888888"><br>
--<br>
Thanks & Regards,<br>
Dipanjan<br>
</font></span></blockquote></div><br><br clear="all"><div><br></div>-- <br><div class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><span><div><div dir="ltr"><p>Thanks & Regards,</p>
<div>Dipanjan</div></div></div></span></div></div>
</div></div>