Abstract
Attacks on cryptosystem implementations (e.g. security fault injection, timing analysis and differential power analysis) are amongst the most exciting developments in cryptanalysis of the past decade. Altering the internal state of a cryptosystem or profiling the system’s computational dynamics can be used to gain a huge amount of information. This paper shows how fault injection and timing analysis can be interpreted for a simulated annealing attack on Pointcheval’s Permuted Perceptron Problem (PPP) identification schemes. The work is unusual in that it concerns fault injection and timing analysis on an analysis technique. All recommended sizes of the PPP schemes are shown to be unsafe.
Chapter PDF
Similar content being viewed by others
References
D. Boneh, R. A. DeMillo, and R. J. Lipton. On the importance of checking cryptographic protocols for faults (extended abstract). In Walter Fumy, editor, Advances in Cryptology-EuroCrypt’ 97, pages 37–51, Berlin, 1997. Springer-Verlag. Lecture Notes in Computer Science Volume 1233.
P Chardaire, J C Lutton, and A Sutter. Thermostatistical persistency: a powerful improving concept for simulated annealing. European Journal of Operations Research, 86:565–579, 1995.
A. Fiat and A. Shamir. How to Prove Yourself:Practical Solutions of Identification and Signature Problems. In Ed Dawson, Andrew Clark, and Colin Boyd, editors, Advances in Cryptology-Crypto’ 86, pages 186–194. Springer Verlag LNCS 263, july 1987.
D.E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, 1989.
S. Goldwasser, S. Micali, and C. Rackoff. Knowledge Complexity of Identification Proof Schemes. In 17th ACM Symposium on the Theory of Computing STOC, pages 291–304. SACM, 1985.
Giddy J.P. and Safavi-Naini R. Automated Cryptanalysis of Transposition Ciphers. The Computer Journal, XVII(4), 1994.
S. Kirkpatrick, Jr. C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science, 220(4598): 671–680, May 1983.
Lars R. Knudsen and Willi Meier. Cryptanalysis of an Identification Scheme Based on the Permuted Perceptron Problem. In Advances in Cryptology Eurocrypt’ 99, pages 363–374. Springer Verlag LNCS 1592, 1999.
P. C. Kocher. Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. In Neal Koblitz, editor, Advances in Cryptology-Crypto’ 96, pages 104–113, Berlin, 1996. Springer-Verlag. Lecture Notes in Computer Science Volume 1109.
Robert A J Mathews. The Use of Genetic Algorithms in Cryptanalysis. Cryptologia, XVII(2):187–201, April 1993.
David Pointcheval. A New Identification Scheme Based on the Perceptron Problems. In Advances in Cryptology Eurocrypt’ 95. Springer Verlag LNCS X, 1995.
A. Shamir. An Efficient Scheme Based On Permuted Kernels. In Advances in Cryptology-Crypto’ 89, pages 606–609. Springer Verlag LNCS 435, 1997.
Richard Spillman, Mark Janssen, Bob Nelson, and Martin Kepner. Use of A Genetic Algorithm in the Cryptanalysis of Simple Substitution Ciphers. Cryptologia, XVII(1):187–201, April 1993.
Jaques Stern. A New Identification Scheme Based On Syndrome Decoding. In Advances in Cryptology-Crypto’ 93, pages 13–21. Springer Verlag LNCS 773, 1997.
Jaques Stern. Designing Identification Schemes with Keys of Short Size. In Crypto’ 93, pages 164–173. Springer Verlag LNCS 839, 1997.
Forsyth W.S. and Safavi-Naini R. Automated Cryptanalysis of Substitution Ciphers. Cryptologia, XVII(4):407–418, 1993.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Clark, J.A., Jacob, J.L. (2002). Fault Injection and a Timing Channel on an Analysis Technique. In: Knudsen, L.R. (eds) Advances in Cryptology — EUROCRYPT 2002. EUROCRYPT 2002. Lecture Notes in Computer Science, vol 2332. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46035-7_12
Download citation
DOI: https://doi.org/10.1007/3-540-46035-7_12
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43553-2
Online ISBN: 978-3-540-46035-0
eBook Packages: Springer Book Archive