Kocher timing attack in RISKS

[stevenw@best.com (Steven Weller)]

Reproduced here from RISKS digest:

------------------------------

Date: Tue, 26 Dec 1995 17:23:09 -0100
From: Saso Tomazic <saso.tomazic@fer.uni-lj.si>
Subject: Re: Timing cryptanalysis of RSA, DH, DSS (Kocher, RISKS-17.53)

The timing attack presented by Paul C. Kocher in his extended abstract
of the paper "Cryptanalysis of Diffie-Helman, RSA, DSS, and Other
Systems Using Timing Attacks"
  (ftp://ftp.cryptography.com/pub/kocher_timing_attack.ps)
is really worth consideration, however I would like to stress there is no
need for panic, mainly for two reasons:

1) Security of practical cryptosystems do not rest solely on security of
crypt algorithm. In fact, cryptoanalysis attacks are rare, due to strong
crypto algorithms that are presently known. More often cryptosystems are
broken using other weak points of cryptosystems as insecurity of keys, bad
key management, easy to guess passwords, computer screen radiation,
monitoring the keystrokes of computer in network, ...  The timing attack can
be considered just as one of them, not the most dangerous one. For practical
cryptosystem, it would be extremely difficult to measure exact timing of
encryption process, at least much more difficult as to monitor keystrokes or
to capture entire message from the screen. The intruder, who would be able
to measure the exact timing of encryption in a multitasking environment,
would probably also have access to everything else (i.e., secret message,
secret key, passwords, ...) and thus no need to measure timing.

2.) It is not so difficult to rewrite algorithms to be resistant to timing
attacks, i.e., to have execution time independent of secret key.  For
example, the algorithm to compute R = y^x mod n given in the Kocher paper
can be simply rewritten as:

Let R = 1.
Let A = 1.
Let z = y.
For i=0 upto (bits_in_x-1):
   If (bit i of x) is 1 then
         Let A = (R*z) mod n
   Else
         Let B = (R*z) mod n
Let y = y^2 mod n.
Let R = A.
End.

to be resistant to timing attacks.

------------------------------

-------------------------------------------------------------------------
Steven Weller                      |  "The Internet, of course, is more
                                   |  than just a place to find pictures
                                   |  of people having sex with dogs."
stevenw@best.com                   |       -- Time Magazine, 3 July 1995