Security Analysis of XTR Exponentiation Algorithms Against Simple Power Analysis Attack
Jaewook Chung, Anwar Hasan · 2002
A security analysis of XTR exponentiation algorithms against simple power analysis attack is presented. Under very reasonable assumptions, we prove that there exists a one-to-one correspondence between power trace and XTR operation sequence. With this result and our obser- vations on the behavior of the simultaneous XTR double exponentiation, we show how simple power analysis attack helps reduce the search space for two input exponents. Our experimental results show that it takes U 1.25 tries for determining both exponents where U = max(a, b) and a, b are the input exponents. Moreover we show that it takes U 0.625 tries for an adversary until he/she correctly finds the secret key used in two XTR single exponentiation algorithms presented in (16). We also point out a calculation error in (14) and discuss the effectiveness of the Markov method in the attack described here.