[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
