Mark Stamp
Department of Computer Science, San Jose State University, San Jose, California, USA
Fabio Di Troia
Department of Computer Science, San Jose State University, San Jose, California, USA
Miles Stamp
Los Gatos High School, Los Gatos, California, USA
Jasper Huang
Lynbrook High School, San Jose, California, USA
Download article
Published in: Proceedings of the 1st International Conference on Historical Cryptology HistoCrypt 2018
Linköping Electronic Conference Proceedings 149:11, p. 39-46
NEALT Proceedings Series 34:11, p. 39-46
Published: 2018-06-13
ISBN: 978-91-7685-252-1
ISSN: 1650-3686 (print), 1650-3740 (online)
Previous work has shown that hidden Markov models (HMM) can be effective for the cryptanalysis of simple substitution and homophonic substitution ciphers. Although computationally expensive, an HMM-based attack that employs multiple random restarts can offer a significant improvement over classic cryptanalysis techniques, in the sense of requiring less ciphertext to recover the key. In this paper, we show that HMMs are also applicable to the cryptanalysis of the well-known Vigenère cipher. We compare and contrast our HMM-based approach to recent research that uses Vigenère cryptanalysis to supposedly illustrate the strength of a type of neural network known as a generative adversarial network (GAN). In the context of Vigenère cryptanalysis, we show that an HMM can succeed with much less ciphertext than a GAN, and we argue that the model generated by an HMM is considerably more informative than that produced by a GAN.
Taylor Berg-Kirkpatrick and Dan Klein. 2013. Decipherment with a million random restarts. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, pages 874–878.
Robert L. Cave and Lee P. Neuwirth. 1980. Hidden Markov models for English. In J. D. Ferguson, editor, Hidden Markov Models for Speech, IDA-CRD, Princeton, NJ, October 1980, pages 16–56. https://www.cs.sjsu.edu/~stamp/RUA/CaveNeuwirth/index.html.
W. Nelson Francis and Henry Kucera. 1969. The Brown Corpus: A standard corpus of present-day edited American English. http://www.nltk.org/nltk_data/.
William F. Friedman. 1987. The Index of Coincidence and Its Applications in Cryptography. Aegean Park Press.
Aidan N. Gomez, Sicong Huang, Ivan Zhang, Bryan M. Li, Muhammad Osama, and Lukasz
Kaiser. 2018. Unsupervised cipher cracking using discrete GANs. https://arxiv.org/abs/1801.04883.
Thomas Jakobsen. 1995. A fast method for the cryptanalysis of substitution ciphers. Cryptologia, 19:265–274.
Friedrich W. Kasiski. 1863. Die Geheimschriften und die Dechiffrirkunst (Cryptography and the Art of Decryption). Mittler und Sohn, Berlin. http://pages.mtu.edu/~shene/NSF-4/Tutorial/VIG/Vig-Kasiski.html.
Dar-Shyang Lee. 2002. Substitution deciphering based on HMMs with applications to compressed document processing. IEEE Transactions on Pattern Analysis and Machine Intelligence, 24(12):1661–1666, December.
Lawrence R. Rabiner. 1989. A tutorial on hidden Markov models and selected applications in speech recognition. Proceedings of the IEEE, 77(2):257–286.
Mark Stamp. 2004. A revealing introduction to hidden Markov models. https://www.cs.sjsu.edu/~stamp/RUA/HMM.pdf.
Rohit Vobbilisetty, Fabio Di Troia, Richard M. Low, Corrado Aaron Visaggio, and Mark Stamp. 2017. Classic cryptanalysis using hidden Markov models. Cryptologia, 41(1):1–28.
WingWong and Mark Stamp. 2006. Hunting for metamorphic engines. Journal in Computer Virology, 2(3):211–229.
