Kocher timing attack in RISKS

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

-----BEGIN PGP SIGNED MESSAGE-----

[via 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)
[...]
> 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.

This appears to be a version of something Hal and I and others initially
suggested that doesn't really defeat the timing attack. In particular, the
variable size of R in iteration k affects the time taken to compute either
A or B in iteration k+1.

Futplex <futplex@pseudonym.com>
*** Welcome to Cypherpunks -- Now Go Home ***

-----BEGIN PGP SIGNATURE-----
Version: 2.6.2

iQEVAwUBMOxwKCnaAKQPVHDZAQEapwf+IcCBI6ksBOftZ/ASB7azlmNXAT2Gzvlw
/1ifFUPNY3nF1G2KWOVUi7tfke0W9xzPDM9G5oG4lJ+SoRcalnO9sVcL5UaxQT0d
9mpskePCgyhQhYfYlVcRL7DglcY+7y451TSkHihRCyyUxxV5xfy9PDBPNDlXBwnR
y9JSsEwuB9Amv2BrX/fwI5m6nuGNvRytSNrqFeLw1X8XTXknwx89KIlIlyOTPGYa
ntS90pJ+bbiYnr3caOLrwAzSBsDnHduFA+0IKa66dOZNahF+1OiCC/roOE4lAxfl
vQ8hOH6Y2EMdJ5If3IchnuunC10xBE+PQhRepBoSQCuTxqfbItaDGw==
=izhc
-----END PGP SIGNATURE-----