[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Kocher timing attack in RISKS



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

[via Steven Weller]
> Reproduced here from RISKS digest:
> 
> ------------------------------
> 
> Date: Tue, 26 Dec 1995 17:23:09 -0100
> From: Saso Tomazic <[email protected]>
> 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 <[email protected]>
*** 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-----