Re: [openssl-users] 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 
>  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

Re: [openssl-users] Why do we try out all possible combinations of top bits in OpenSSL timing attack?

[Salz, Rich via openssl-users]

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

Re: [openssl-users] 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 
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
> 1... 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

Re: [openssl-users] 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 1... 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

[openssl-users] Why do we try out all possible combinations of top bits in OpenSSL timing attack?

[Dipanjan Das]

Hi,



down votefavorite


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