The security of encryption devices using common public key cryptosystems depends on the difficulty in the task of factoring large numbers used as moduli in the exponentiation. There is a drastic reduction in security if an attacker can obtain information about the relative computational effort to perform the necessary steps in exponentiation algorithms. Such information may be accessible from electromagnetic sensors placed in the vicinity of the device, or by submitting sequences of chosen texts to a public resource server. Here we report some simple computations which provide an upper bound on the quality of such methods of attack, by placing timing markers at procedure changes in an implementation using C++.

This type of approach may be helpful in evaluating the effectiveness of auxiliary procedures used to obscure the internal operations of a device.

Timing Tags in C++ Code

We used timer.h, under Unix as it uses some of the system variables. The idea is to create an object of type timer and to initialise it at the start of the required timed portion of the program and a evaluate at the end. Here, we require a time for each exponent bit in the square and multiply algorithm. At the end of each exponentiation, the timings obtained are stored into an array which is returned from the exponentiation function. To obtain the sample timing results for a simple message we used following procedure.

FOR p,q of size p_min to p_max in steps of p_incr
FOR e of size e_min to e_max in steps of e_incr
Generate p and q of the required size and
so that q is not equal to p
Compute e
Compute phi
Set e=phi
WHILE (e,phi) not equal to 1
Generate a prime e of the required size
END WHILE
Compute d so that e*d is congruent to 1 modulo phi
Save e*d mod phi into check.dat
Save (e,phi) into check.dat
Set message=12345678
Encrypt message as encr
Decrypt encr as decr
Save data used into data.dat
Save the timings into timing.dat
IF decr is not equal to encr
Save ``Error'' into check.dat
ELSE
Save encr and decr in decimal form
into check.dat
END IF
END FOR
END FOR

Results

As p and q increased, the gap between the time intervals for a zero and a one increased significantly. For example, corresponding to p and q of length 195 bits, we found that for processing a 1 50% more time was used than for processing a 0. The difference in timing increased slightly more than in proportion to the size of p and q.

Conclusions

It is possible to read off the value of the exponent by looking at the time intervals obtained from the modular exponentiation algorithm. The length of the key only has an influence on the overall time of execution of the modular exponentiation algorithm but the time intervals for computing one step of the square-and-multiply algorithm are the same regardless of the length of the exponent. Hence, making the encrypting (or decrypting) key bigger only increases the overall time taken to find its value but does not affect the complexity of the task. Incorporation of an obscuring procedure would complicate, by spurious internal processes, power or timing data obtained by an attacker. The accessible information would be less distinct if it was subject to such obscuring signals. Then the way to test the obscuring procedure is to compare its consequence with that resulting from a mixture of pure timing data and noise of appropriate type. A certain minimum level of noise would be needed to reduce the information content below that which presents a security risk. Since the timing data represents the best possible data obtainable by an attacker, the requisite amount of noise to obscure it acceptably can be measured, so the obscuring procedure may be evaluated.

Preprint