Quantcast

Why do we try out all possible combinations of top bits in OpenSSL timing attack?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Why do we try out all possible combinations of top bits in OpenSSL timing attack?

Dipanjan Das

Hi,

In the paper titled Remote Timing Attacks are Practical, the authors mention the following:

Initially our guess g of q lies between 25122512 (i.e. 2log2(N/2)2log2(N/2)) and 25112511 (i.e. 2log2(N/2)12log2(N/2)1). We then time the decryption of all possible combinations of the top few bits (typically 2-3). When plotted, the decryption times will show two peaks: one for q and one for p. We pick the values that bound the first peak, which in OpenSSL will always be q.

I don't understand the following:

  • Does the initial guess of g start from an arbitrary range?
  • What's the rationale behind trying out top 2-3 bits?
  • What will the remaining bits be in this case?

--

Thanks & Regards,

Dipanjan

--
openssl-users mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Why do we try out all possible combinations of top bits in OpenSSL timing attack?

Michael Wojcik
[Snipped HTML content, since Outlook can't quote it properly and it was garbled anyway.]

openssl-users doesn't really seem like the right place to discuss this (the sci.crypt newsgroup or a relevant area of the sprawling StackOverflow empire would be better), but it's a low-traffic list, so what the heck.

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.

The questions and my responses:

Q: Does the initial guess of g start from an arbitrary range?

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.

Q: What's the rationale behind trying out top 2-3 bits?

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.

Q: What will the remaining bits be in this case?

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

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.

--
Thanks & Regards,
Dipanjan
--
openssl-users mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Why do we try out all possible combinations of top bits in OpenSSL timing attack?

Dipanjan Das


On 6 February 2017 at 05:30, Michael Wojcik <[hidden email]> wrote:

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.

The questions and my responses:

Q: Does the initial guess of g start from an arbitrary range?

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.

Q: What's the rationale behind trying out top 2-3 bits?

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.


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:

    - Set the two most significant bits to each one in the set => {00, 01, 10, 11}, one after another
    - For each of the above cases, fill the remaining 510 bits with *some* bits (are those assumed to be all zero bits?)

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.


 

Q: What will the remaining bits be in this case?

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

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.

--
Thanks & Regards,
Dipanjan



--

Thanks & Regards,

Dipanjan

--
openssl-users mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Why do we try out all possible combinations of top bits in OpenSSL timing attack?

OpenSSL - User mailing list

Michael was kind to post some replies.

 

I think a better forum to discuss this is one of the following, which has more focus on cryptographic science and less on “how do I use the CLI”

      http://www.metzdowd.com/mailman/listinfo/cryptography

    https://www.irtf.org/mailman/listinfo/cfrg


--
openssl-users mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Why do we try out all possible combinations of top bits in OpenSSL timing attack?

Viktor Dukhovni

> On Feb 6, 2017, at 10:07 AM, Salz, Rich via openssl-users <[hidden email]> wrote:
>
> Michael was kind to post some replies.
>  
> I think a better forum to discuss this is one of the following, which has more focus on cryptographic science and less on “how do I use the CLI”
>       http://www.metzdowd.com/mailman/listinfo/cryptography
>     https://www.irtf.org/mailman/listinfo/cfrg

Actually, very much NOT the CFRG list.  That's an IRTF working group, and
discussion needs to be about IRTF work.

--
        Viktor.

--
openssl-users mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-users
Loading...