Abstract
We investigate side-channel attacks where the attacker only needs the Hamming weights of several secret exponents to guess a long-term secret. Such weights can often be recovered by SPA, EMA, or simply timing attack. We apply this principle to propose a timing attack on the GPS identification scheme. We consider implementations of GPS where the running time of the exponentiation (commitment phase) leaks the exponent’s Hamming weight, which is typical of a square and multiply algorithm for example. We show that only 800 time measures allow the attacker to find the private key in a few seconds on a PC with a success probability of 80%. Besides its efficiency, two other interesting points in our attack are its resistance to some classical countermeasures against timing attacks, and the fact that it works whether the Chinese Remainder Technique is used or not.
Chapter PDF
Similar content being viewed by others
References
Cascade (Chip Architecture for Smart CArds and portable intelligent DEvices). Project funded by the European Community, see http://www.dice.ucl.ac.be/crypto/cascade
Baudron, O., Boudot, F., Bourel, P., Bresson, E., Corbel, J., Frisch, L., Gilbert, H., Girault, M., Goubin, L., Misarsky, J.-F., Nguyen, P., Patarin, J., Pointcheval, D., Stern, J., Traoré, J.: GPS, an asymetric identification scheme for on the fly authentification of low cost smart cards. Submitted to the European NESSIE Project (2000), Available at https://www.cryptonessie.org/
Boneh, D., Brumley, D.: Remote timing attacks are practical. Submitted to Usenix Security (2003), Available at http://crypto.stanford.edu/~dabo/papers/ssl-timing.pdf
Nessie consortium. Portfolio of recommended cryptographic primitives (2003), Available at https://www.cryptonessie.org/deliverables/decision-final.pdf
Dhem, J.-F., Koeune, F., Leroux, P.-A., Mestré, P., Quisquater, J.-J., Willems, J.-L.: A practical implementation of the timing attack. In: Schneier, B., Quisquater, J.-J. (eds.) CARDIS 1998. LNCS, vol. 1820. Springer, Heidelberg (2000)
Dhem, J.F.: Design of an efficient public-key cryptographic library for RISC-based smart cards. PhD thesis, Université catholique de Louvain – UCL Crypto Group – Laboratoire de microélectronique (DICE) (May 1998)
Girault, M.: Self-Certified Public Keys. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, pp. 490–497. Springer, Heidelberg (1991)
Girault, M., Poupard, G., Stern, J.: Some modes of use of the GPS identification scheme. In: Proceedings of the third Nessie workshop, November 6–7 (2002)
Kocher, P.: Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 104–113. Springer, Heidelberg (1996)
Advanced RISC Machines Ltd. ARM Software Developpment Toolkit version 2.11: User guide. Advanced RISC Machines Ltd, Document number: ARM DUI 0040C (1997)
Poupard, G., Stern, J.: Security Analysis of a Practical on the fly Authentification and Signature Generation. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 422–436. Springer, Heidelberg (1998)
Schindler, W.: A timing attack against RSA with the Chinese remainder theorem. In: Paar, C., Koç, Ç.K. (eds.) CHES 2000. LNCS, vol. 1965, pp. 109–124. Springer, Heidelberg (2000)
Walter, C.D.: Montgomery Exponentiation Needs no Final Subtractions. Electronics Letters 35(21), 1831–1832 (1999)
Walter, C.D.: Montgomery’s Multiplication Technique: How to Make It Smaller and Faster. In: Koç, Ç.K., Paar, C. (eds.) CHES 1999. LNCS, vol. 1717, pp. 80–93. Springer, Heidelberg (1999)
Walter, C.D.: MIST: An efficient, randomized exponentiation algorithm for resisting power analysis. In: Preneel, B. (ed.) CT-RSA 2002. LNCS, vol. 2271, p. 53. Springer, Heidelberg (2002)
Walter, C.D.: Seeing through MIST given a small fraction of an RSA private key. In: Joye, M. (ed.) CT-RSA 2003. LNCS, vol. 2612, pp. 391–402. Springer, Heidelberg (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cathalo, J., Koeune, F., Quisquater, JJ. (2003). A New Type of Timing Attack: Application to GPS. In: Walter, C.D., Koç, Ç.K., Paar, C. (eds) Cryptographic Hardware and Embedded Systems - CHES 2003. CHES 2003. Lecture Notes in Computer Science, vol 2779. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-45238-6_24
Download citation
DOI: https://doi.org/10.1007/978-3-540-45238-6_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40833-8
Online ISBN: 978-3-540-45238-6
eBook Packages: Springer Book Archive