Bayesian Inference for Zodiac and Other Homophonic Ciphers

Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics, pages 239–247, Portland, Oregon, June 19-24, 2011. c⃝2011 Association for Computational Linguistics Bayesian Inference for Zodiac and Other Homophonic Ciphers Sujith Ravi and Kevin Knight University of Southern California Information Sciences Institute Marina del Rey, California 90292 {sravi,knight}@isi.edu Abstract We introduce a novel Bayesian approach for deciphering complex substitution ciphers. Our method uses a decipherment model which combines information from letter n-gram lan- guage models as well as word dictionaries. Bayesian inference is performed on our model using an efficient sampling technique. We evaluate the quality of the Bayesian deci- pherment output on simple and homophonic letter substitution ciphers and show that un- like a previous approach, our method consis- tently produces almost 100% accurate deci- pherments. The new method can be applied on more complex substitution ciphers and we demonstrate its utility by cracking the famous Zodiac-408 cipher in a fully automated fash- ion, which has never been done before. 1 Introduction Substitution ciphers have been used widely in the past to encrypt secrets behind messages. These ciphers replace (English) plaintext letters with ci- pher symbols in order to generate the ciphertext se- quence. There exist many published works on automatic decipherment methods for solving simple letter- substitution ciphers. Many existing methods use dictionary-based attacks employing huge word dic- tionaries to find plaintext patterns within the ci- phertext (Peleg and Rosenfeld, 1979; Ganesan and Sherman, 1993; Jakobsen, 1995; Olson, 2007). Most of these methods are heuristic in nature and search for the best deterministic key during deci- pherment. Others follow a probabilistic decipher- ment approach. Knight et al. (2006) use the Expec- tation Maximization (EM) algorithm (Dempster et al., 1977) to search for the best probabilistic key us- ing letter n-gram models. Ravi and Knight (2008) formulate decipherment as an integer programming problem and provide an exact method to solve sim- ple substitution ciphers by using letter n-gram mod- els along with deterministic key constraints. Corlett and Penn (2010) work with large ciphertexts con- taining thousands of characters and provide another exact decipherment method using an A* search al- gorithm. Diaconis (2008) presents an analysis of Markov Chain Monte Carlo (MCMC) sampling al- gorithms and shows an example application for solv- ing simple substitution ciphers. Most work in this area has focused on solving simple substitution ciphers. But there are variants of substitution ciphers, such as homophonic ciphers, which display increasing levels of difficulty and present significant challenges for decipherment. The famous Zodiac serial killer used one such cipher sys- tem for communication. In 1969, the killer sent a three-part cipher message to newspapers claiming credit for recent shootings and crimes committed near the San Francisco area. The 408-character mes- sage (Zodiac-408) was manually decoded by hand in the 1960’s. Oranchak (2008) presents a method for solving the Zodiac-408 cipher automatically with a dictionary-based attack using a genetic algorithm. However, his method relies on using plaintext words from the known solution to solve the cipher, which departs …

Content truncated to 500 words