Fault Attacks on the Montgomery Powering Ladder - Information Security and Cryptology-ICISC 2010 - page 405

injections for computational effort. In particular, if we assume a chunk of bit-size
c andanexponentofbit-size t , t/c fault injections are required. For each faulty
computation 2 c values have to be guessed and tested with the corresponding
formulas, which requires an exponentiation each. In the first attack, the maxi-
mum possible bit-size v of the injected fault also needs to be considered. Each
unknown bit doubles the number of required tests.
The attack on a blinded implementation of the algorithm recovers the expo-
nent bit-by-bit. Thus, the number of injected faults equals the bit length of the
exponent. Since the test involves only the computation of the Jacobi symbol, it
does not require extra exponentiations.
8Con lu on
In this paper, we presented new fault attacks on the Montgomery powering lad-
der. We demonstrated that our attacks are feasible for two realistic fault models:
(1) for random register faults that can be guessed and (2) for a manipulation
of the program flow. For both models, we discussed how to determine the se-
cret exponent of an unprotected implementation in bit-chunks. In addition, it is
possible to recognize a successful fault injection by the output of the device.
For the latter fault model, we also showed how to mount an attack on a
blinded implementation. In this attack, the exponent was recovered bit-wise by
measuring the execution time and checking the Jacobi symbol of the output. To
the best of our knowledge, this is the first fault attack on a blinded Montgomery
ladder.
The presented results show that fault attacks on the blinded Montgomery
ladder are possible. All attacks require the adversary to know the plaintext. For
the attack on the blinded version, knowing the Jacobi symbol of the plaintext is
sucient.
We conclude that blinding in combination with a loop-checksum does not pre-
vent all fault attacks on the Montgomery powering ladder. Therefore, additional
protection by exponent blinding or by a check whether the quotient between the
two intermediate variables is correct should be implemented.
Acknowledgements. The work described in this paper has been supported in
part through the Austrian Science Fund (FWF) under grant number P22241-
N23. The information in this document reflects only the authors views, is pro-
vided as is and no guarantee or warranty is given that the information is fit for
any particular purpose. The user thereof uses the information at its sole risk and
liability.
References
1. Boneh, D., DeMillo, R.A., Lipton, R.J.: On the Importance of Checking
Cryptographic Protocols for Faults (Extended Abstract). In: Fumy, W. (ed.)
EUROCRYPT 1997. LNCS, vol. 1233, pp. 37-51. Springer, Heidelberg (1997)