Research papers

• Nuhn, Malte, Julian Schamper, and Hermann Ney. "Beam Search for Solving Substitution Ciphers." ACL (1). 2013.
  • Abstract: "In this paper we address the problem of solving substitution ciphers using a beam search approach. We present a conceptually consistent and easy to implement method that improves the current state of the art for decipherment of substitution ciphers and is able to use high order n-gram language models. We show experiments with 1:1 substitution ciphers in which the guaranteed optimal solution for 3-gram language models has 38.6% decipherment error, while our approach achieves 4.13% decipherment error in a fraction of time by using a 6-gram language model. We also apply our approach to the famous Zodiac-408 cipher and obtain slightly better (and near to optimal) results than previously published. Unlike the previous state-of-the-art approach that uses additional word lists to evaluate possible decipherments, our approach only uses a letterbased 6-gram language model. Furthermore we use our algorithm to solve large vocabulary substitution ciphers and improve the best published decipherment error rate based on the Gigaword corpus of 7.8% to 6.0% error rate."
• Berg-Kirkpatrick, Taylor, and Dan Klein. "Decipherment with a Million Random Restarts." EMNLP. 2013.
  • Abstract: "This paper investigates the utility and effect of running numerous random restarts when using EM to attack decipherment problems. We find that simple decipherment models are able to crack homophonic substitution ciphers with high accuracy if a large number of random restarts are used but almost completely fail with only a few random restarts. For particularly difficult homophonic ciphers, we find that big gains in accuracy are to be had by running upwards of 100K random restarts, which we accomplish efficiently using a GPU-based parallel implementation. We run a series of experiments using millions of random restarts in order to investigate other empirical properties of decipherment problems, including the famously uncracked Zodiac 340."
• Ravi, Sujith, and Kevin Knight. "Bayesian inference for Zodiac and other homophonic ciphers." Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies-Volume 1. Association for Computational Linguistics, 2011.
  • 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 language 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 decipherment output on simple and homophonic letter substitution ciphers and show that unlike a previous approach, our method consistently produces almost 100% accurate decipherments. 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 fashion, which has never been done before."
• Basavaraju, Pallavi Kanagalakatte. "Heuristic Search Cryptanalysis of the Zodiac 340 Cipher." (2009).
  • Abstract: "The Zodiac 340 cipher is one of the most famous unsolved ciphers of all time. It was allegedly written by “the Zodiac”, whose identity remains unknown to date. The Zodiac was a serial killer who killed a number of people in and around the San Francisco Bay area during the 1960s. He is confirmed to have seven victims, two of whom survived [1], although in taunting letters to the news media he claims to have killed 37 people. During this time, an encrypted message known as the Zodiac 408 cipher was mailed to 3 different newspapers in the San Francisco bay area. This was a homophonic cipher and was successfully decoded. Within a few days he sent out another cipher that was 340 characters long [4]. This cipher, which is known as the Zodiac 340 cipher, is unsolved to date. Many cryptologists have tried to crack this cipher but with no success. In this project, we implemented a novel genetic algorithm in an attempt to crack the Zodiac 340 cipher. We have attacked the cipher as a homophonic cipher where each cipher symbol is mapped to only a single English letter, but each English letter can be mapped to multiple cipher symbols. In the genetic algorithm, we implemented two variants of crossover: simple and intelligent. The simple crossover looks for commonly occurring substrings, without looking for actual English words in a putative decrypt. The intelligent crossover counts the number of actual English words that can be found in a putative decrypt when evaluating each solution. We implemented a dictionary lookup for quickly identifying English words for the intelligent crossover. The genetic algorithm using a combination of simple and intelligent crossovers was able to identify many English words in various putative decrypts but no solution was found."
• Banks, Michael James. "A Search-Based Tool for the Automated Cryptanalysis of Classical Ciphers." The University of York Department of Computer Science May (2008).
  • Abstract: "The field of classical cryptography encompasses various forms of simple pen-and-paper ciphers that were in widespread use until the early 20th century. Although these ciphers have long been surpassed by modern cryptographic systems, they can still be challenging to break using manual methods alone. Indeed, there exist several well-known classically-encrypted cryptograms which, at present, remain unbroken. Automated cryptanalysis of classical ciphers has been carried out in existing research, using optimisation techniques in conjunction with appropriate heuristics to evaluate the validity of decryptions. However, this work is largely limited to a few kinds of simple ciphers and the results obtained by some researchers have been criticised by others as being suboptimal. Building on the approaches used by earlier work, a flexible software tool is constructed to perform automated cryptanalysis on texts encrypted with various kinds of classical ciphers. The tool is expressly designed to support the tailoring of cryptanalysis to particular styles of ciphertext, featuring an extensible framework for defining ciphers and supporting different evaluation heuristics and optimisation algorithms. The efficacy of the tool is investigated using a selection of sample ciphertexts and unsolved cryptograms. Topics for further research into automated cryptanalysis are proposed."
• Dao, Thang. Analysis of the zodiac 340-cipher. Diss. San Jose State University, 2007.
  • Abstract: The main purpose of this project is to determine whether the method used in the Zodiac 340-cipher (Z340) letter was a homophonic substitution, an improved version of the well-known simple substitution. A homophonic substitution employs a "one-to-many mapping" technique, as opposed to the "one-to-one mapping" of a simple substitution. Due to the complexity of the homophonic substitution, an exhaustive solution to the Z340 is not possible in a feasible amount of time. This research proposes an approach to implement an automated solution to a homophonic substitution based on a hill-climb technique. The software will be used to attempt to solve the Z340. Even if the software fails to solve the Z340, useful conclusions could be drawn. The objective is to reduce the number of methods that could have been used to encrypt the original message.
• Delman, Bethany. "Genetic algorithms in cryptography." (2004).
  • Abstract: Genetic algorithms (GAs) are a class of optimization algorithms. GAs attempt to solve problems through modeling a simplified version of genetic processes. There are many problems for which a GA approach is useful. It is, however, undetermined if cryptanalysis is such a problem. Therefore, this work explores the use of GAs in cryptography. Both traditional cryptanalysis and GA-based methods are implemented in software. The results are then compared using the metrics of elapsed time and percentage of successful decryptions. A determination is made for each cipher under consideration as to the validity of the GA-based approaches found in the literature. In general, these GA-based approaches are typical of the field. Of the genetic algorithm attacks found in the literature, totaling twelve, seven were re-implemented. Of these seven, only three achieved any success. The successful attacks were those on the transposition and permutation ciphers by Matthews, Clark, and Gr¨undlingh and Van Vuuren, respectively. These attacks were further investigated in an attempt to improve or extend their success. Unfortunately, this attempt was unsuccessful, as was the attempt to apply the Clark attack to the monoalphabetic substitution cipher and achieve the same or indeed any level of success. Overall, the standard fitness equation genetic algorithm approach, and the scoreboard variant thereof, are not worth the extra effort involved. Traditional cryptanalysis methods are more successful, and easier to implement. While a traditional method takes more time, a faster unsuccessful attack is worthless. The failure of the genetic algorithm approach indicates that supplementary research into traditional cryptanalysis methods may be more useful and valuable than additional modification of GA-based approaches.
  • List of attacks mentioned in the paper
• Spillman, Richard, et al. "Use of a genetic algorithm in the cryptanalysis of simple substitution ciphers." Cryptologia 17.1 (1993): 31-44.
  • Abstract: This paper considers a new approach to cryptanalysis based on the application of a directed random search algorithm called a genetic algorithm. It is shown that such a algorithm could be used to discover the key for a simple substitution cipher.
• Language models - A list of a few papers that involve the use of probabilistic language models for cryptanalysis.