Timing Attack Against Blakley’s Modular Multiplication Algorithm

Timing Attack Against Blakley’s Modular Multiplication Algorithm

Abstract

The published timing attack schemes against modular exponentiation implementations are based on the large variations in their time measurements, while it is assumed that the running time of each step of the algorithm is independent of the running time of other steps. In this paper, we propose a new timing attack scheme against Blakley’s modular multiplication, which has rather small timing variations with respect to modular exponentiation. We show that the assumption of independency of the running time of different steps is not valid for Blakley’s algorithm. We mathematically model the correlations between the running times of different steps. It is assumed that a set of known inputs multiplied by the same constant and the running time of each multiplication are given, but the multiplication result is not known. In addition, a machine similar to victim machine is not available In some applications, such as Digital Signature Standard, the constant is the secret key. We take advantage of the obtained correlation to present our timing attack scheme for obtaining the constant parameter, which is the secret key. In addition to the attack scheme, an error detection scheme is presented. We also propose an error correction method in order to improve our attack efficiency. Practical implementation of our attack against DSS shows that error probability is less than 0.15, and the 160-bit secret key is found using 1,500,000 timing measurements.

References