One evening, a number of years ago, I casually started looking at the then-unsolved Z340 cipher that the Zodiac Killer had sent to authorities back in 1969. Over the next couple of years, I devoted well over 1,000 hours to breaking down the problem and trying to solve it, and I made some really great progress. The work was looking promising, and I had a pretty clear game plan for how to use it to tackle Z340.
The system grew into a multi-level suite of models and tools for systematically attacking and breaking homophonic substitution ciphers. Before long, it encompassed a few dozen notebooks, about 10,000 lines of Python code, almost a terabyte of generated training data, and several machine-learning and predictive models, including deep neural networks (convolutional and recursive) and genetic algorithms.
By late 2020, the solver system was looking extremely promising. What remained was to analyze its performance on ciphers with increasing levels of homophonicity, and then extrapolate from those results to determine how much generated training data and computing power would be statistically required to ensure success with the actual Zodiac Cipher.
(Theoretically, the amount of information remaining in an encrypted message depends on both the length of the message and the homophonicity of the cipher key. So predicting the solver's likelihood of success would also require estimating whether the Zodiac Cipher was fundamentally solvable at all.)
Then, on December 11, 2020—a date that will live in... well, let's just say I won't forget it—I woke up to an email from David Oranchak saying that he and two colleagues had just solved the Zodiac 340 Cipher. In about five seconds, my previous years of work seemed to implode! And just when all the work had been getting exciting. I had even been sharing some of my early results with fellow researchers working on the Zodiac Cipher, including David. In fact, I was in the middle of packaging some of the main software up for David who had requested it to try out.
Oh well.
Make no mistake though—the achievement of David and his team was well deserved! David had spent many years working on the problem and sharing his findings through lectures and videos, and there was probably no one with a better understanding of the statistical characteristics of the Zodiac cipher than David.
In fact though, there was still a great deal of work to be done before my efforts were likely to actually break the cipher. I anticipated having to determine—using further statistical analysis and machine-learning models—which transpositions the Zodiac Killer had probably used in combination with his substitution cipher key. Working out that part of the problem was going to require a sizable research effort in itself.
As it turned out, the first transposition I had already placed on my workplan was the very one that played a critical role in the solution. But the full set of transpositions ultimately required was rather complex, and David would not have succeeded without his clever and insightful manual inspections.
While the work is certainly worth continuing, my enthusiasm for doing so took a hit once the particular problem that had launched the entire effort was solved. At some point, however, I expect to regain both the time and the motivation to continue the research.
This work produced some surprisingly successful and valuable results, including a novel design for a powerful genetic algorithm, and a unique approach for the feature engineering and scoring used in combination with a deep convolutional neural network. It also resulted in developing a useful metric for quantifying the complexity of a homophonic cipher key, which I dubbed "homophonicity," along with techniques to generate random cipher keys having specific values of homophonicity. Those details will be covered in a separate article; Primer on Cipher Metrics..
What follows is a brief overview of the system.
Homophonic Cipher Solver
The Homophonic Cipher Solver is an orchestrated suite of algorithms that I developed over a three-year period. The system is shown schematically in the figure below. The impetus for the research was to ultimately break the well-known Zodiac 340-character cipher, which had remained unsolved since 1969, when it was sent to the police by the infamous Zodiac serial killer.
The solver uses a multistage approach consisting of:
- a Zodiac Killer-specific language model, built by combining the corpus of his 15 or so letters with a larger English-language corpus
- the generation of millions of hypothetical Zodiac-styled test messages, reflecting the Zodiac Killer's particular vocabulary and typical typos
- a technique for generating cipher keys with precise values of "homophonicity," targeted to match the homophonicity of the unsolved Zodiac cipher
- a genetic algorithm for finding an initial candidate key with a high probability of containing a required—and calculated—threshold of correct symbol-to-letter mappings
- a deep convolutional neural network that then performs a directed search for a final solution key that produces a coherent decoded message
On a large test set of ciphers similar to the Zodiac Cipher in size, structure, and language—but with lower homophonicity—the system was able to decrypt 99.5% of the ciphers with 100% "clarity."
Below are two examples illustrating the power of the solver. The first shows a typical result, representative of the vast majority of the test cases. The cipher was solved to 100% clarity in just seven iteration steps, taking only a few seconds on a laptop.
The second shows the cipher that took the solver the longest to reach 100% clarity. This one required roughly 45 iteration steps and about 30 seconds on a laptop.
