Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Fri Aug 21 1998 - 17:18:59 ADT
Mike Rosing (eresrch@msn.fullfeed.com)
Wed, 24 Jun 1998 15:07:18 -0500 (CDT)
On Wed, 24 Jun 1998, burt rosenberg wrote:
>
> this solution, to fill time, is most likely faster, and possibly
> simpler, but it doesn't fully cover the calculation's tracks.
> i do not see how to prove that no information is then leaked
> through timing analysis. this will make the timing data more
> subtle, perhaps to the point of uselessness, but perhaps not.
How do you mean it doesn't cover the calculations tracks? Every
y^x will take the exact same time no matter what x is. This is slower,
not faster, but it's a defense.
> kocher provides the thought experiment of a certain squaring
> that takes a grotesquely long time. by chosing y correctly,
> you can tickle this squaring and check that the i-th bit of x is 0.
>
> however, we can take this thought experiment one step further
> and assume that for a certain x all y^x's take a longer time
> on average than other x's. then kocher's proposed solution,
> premultiply y by a random number before exponentiation, also fails.
and we can completely defeat the attack if time is accounted for
in every step. You don't need anything fancy, a few well placed nop's
will work fine.
> on the other hand, randomly splitting x will not disclose information
> _unless_ y^x' and y^{x-x'} somehow correlate, for randomly drawn x'.
> that is, they are not like y^x' and y^x'' drawn independently at random.
> assuming independence, a proof of no information leakage might be possible.
>
> do y_x' and y^{x-x'} act as independent algorithms, for random x'?
> gee ...
I'm not arguing that this might help defeat the attack, but you can
elminiate the attack completely with very little effort. The choosing of
the random x might leak info because of the time it takes the random
generator to run, unless you take the same care to count clock cycles.
Patience, persistence, truth,
Dr. mike
The following archive was created by hippie-mail 7.98617-22 on Fri Aug 21 1998 - 17:18:59 ADT