The Story Behind the Solution of the Zodiac’s 340 Cipher

Recently Dave Oranchak and I have been working on a long-overdue academic paper on our solution of the Zodiac’s 340-character cipher (Z340). It’s getting to a point where we are ready to drop it on arxiv and eventually submit it to a journal. It’s been a large piece of work, so hopefully some people will want to read about the decades-long story.?

Prior to releasing our paper to the public we shared it with some experts for review. One of these experts was Elonka Dunin. Elonka posed the following question to Dave, Jarl and myself:

I never thought anybody would be interested in the story behind the story of solving the Z340. In response to Elonka’s question, I put together the following scattered recollections of my work on the Z340.?

Prior to working on Z340, I had been working on a long unsolved problem related to my PhD thesis off and on for about 12 years. I was getting burned out on it and was looking for a new challenge. Ideally something that I could play with on a Sunday night and leave the programs/experiments running for the week and check in from time to time. At the time I had access to The University of Melbourne's supercomputer, Spartan, so I had a convenient way to run large experiments that would not be possible otherwise (I would often have access to 1000-2000 cores). I also had the patience to work on a difficult problem. I don’t mind working on an unsolved problem for a long time without success, as I find the journey enjoyable.?

In 2017, The History Channel premiered a 5-part investigative series The Hunt for the Zodiac Killer. In the final episode a completely fallacious (pseudoscientific) solution of the Z340 was presented to much fanfare (you can read more about it here). David Oranchak was one of expert cryptologists who participated in this series (but did not provide the solution to Z340). I subsequently watched two of Dave's lectures on the Z340. Unlike the non-cryptanalytic solution presented in The Hunt for the Zodiac Killer, Dave’s lectures were excellent and I liked his approach to solving the cipher. I originally reached out to Dave via a youtube comment:?

In response to (a few sparse cases of) COVID 19, Melbourne, Australia endured 262 days of lockdowns. We were limited to a 5 km radius from our homes and couldn’t be outside after 8 pm. Basically everything was closed, even golf courses (where if you play like me, you’ll be well and truly socially-distanced from your playing group.) This gave me plenty of free time to fill in with a new side project.?

For about a year Dave and I would chat on facebook messenger about experiments we'd like to run then we would both run them independently. I used zkdecrypto (as I didn't have access to a windows VM on Spartan) and Dave used AZdecrypt. We would run thousands of candidate transpositions of the Z340 through both solvers. These candidate transpositions were from a larger pool of (many millions of) candidates that I would sieve based (usually) on repeating bigram counts.?

At around 11pm on December 3, 2020 (Melbourne, Australia time) I saw a message from Dave on Slack asking me about one of the candidate transpositions:?

The phrases "TRYING TO CATCH ME" and "GAS CHAMBER" seemed too good to be true. Especially when I googled and found out that was the method of execution in California in the 1960s (I have no doubt that Dave would have been aware of this fact). These were my (very eloquent) thoughts on it at the time:?

I went off to bed and to be honest, when I woke up in the morning I had forgotten about it and I went off to the beach to make the most of some non-lockdown time in 2020. I eventually checked my emails (as I didn't have slack on my phone back then) and saw this:

It was one of those moments where I recall exactly where I was. I was temporarily speechless, but I do recall thinking over and over to myself how it could be possible that this is anything other than a partial break of the cipher. I called Dave via facebook messenger and he explained to me what he'd done overnight. Essentially Dave used those keywords from the original AZdecrypt candidate solution as cribs in the first 9 lines of the cipher and re-ran AZdecrypt on just those 9 lines with the cribs locked in as constraints (a very nice feature of AZdecrypt). It's a shame Dave or I didn't record that phone conversation. We discussed the reference to the TV SHOW and problems with the remaining sections. Dave was most definitely on an (intellectual) high! I was coming to terms with what had just happened.?

I immediately left the beach and headed home to my computer. On the way home I dropped in to see my former PhD Advisor to tell him the good news. He found the geometry/number theory of the transposition used by Zodiac to be especially interesting. I discussed the number theory behind the possible choices Zodiac had when making this scheme here:

Dave and I looked at the final 11 lines of the cipher that afternoon. In particular we tried to work out what was going wrong with the transposition scheme for the second 9 lines. Dave asked me if I would mind him reaching out to Jarl van Eycke. I thought this was a great idea as I knew from reading the zodiac cipher forum and studying azdecrypt that Jarl was an expert cryptologist.

Dave had already worked out that the final two lines used a completely different transposition scheme, where some words were reversed. (Fortunately it used the same substitution key as the first 9 lines.)

At this point I was basically a passenger watching Jarl unravel the issues (disruptions to the 1-down, 2-across transposition) with the second 9 lines. It was brilliant to watch:?

Dave and I were so impressed with how quickly Jarl isolated the issues with the second section of Z340:

We were confident in our solution of the Z340. Unlike previous efforts, our solution did not require artistic creativity in order to browbeat words out of the ciphertext. It was now a case of presenting the steps required to reproduce our solution in an easily understandable way. Dave put together a summary for the FBI. When I realised our work was going to the FBI was the moment when I thought "shit just got real". Dave's email hilariously understated what had just happened (Daniel and Jeanne are from the FBI CRRU):

At some point I got a bit carried away:?

We were asked to not publicly disclose our solution until the FBI had a chance to notify the families of the victims. We wanted to respect this request. It also made me realise that this was a small part of a very important and sad piece of history. We decided to dedicate our efforts to the victims of the zodiac killer. Looking back at this now, it was an especially nice way to finish off this piece of work.?

Well, I more or less thought that would be it. Dave would have a cool new video for his youtube channel and the FBI would have one less cipher on their list of unsolved ciphers. Dave was told (possibly by the FBI) to expect press coverage, but I naively assumed it would be limited to an article by Kevin Fagan in the San Francisco Chronicle and maybe a paper in Cryptologia.?

In confidence, I informed the School of Computing and Information Systems at The University of Melbourne what I'd done and how I had used Spartan as a key part of this research. This is when things got super stressful. I was questioned at length as to why I didn't seek ethics approval prior to commencing my research. The university was seemingly wanting to distance themselves as far as possible from this work and I was concerned I was going to be formally reprimanded or dismissed for working on the Z340. This all occurred on a Friday afternoon, the story broke over the weekend and by Monday morning I got a call from the previous person's bosses, bosses, boss who asked me how they could assist me in promoting this work and asked me why I hadn't mentioned the university in any of my media appearances... They seemingly liked the positive worldwide publicity, but had no interest in supporting my research in any substantive or ongoing way.?

After my last interview on Saturday, it was time to celebrate with friends. I didn’t make it to the morning show appearance on Channel 9 the following day:?

In the period between solving the cipher and the FBI releasing their statement, Dave had been hard at work making a video for his Youtube series Let’s Crack Zodiac. His video has had over 2 million views!?

I never expected what would follow. Between TV, radio, podcasts and news articles I did well over 30 interviews. I felt compelled to do these as it was the one time in my life where I could promote what I love doing to a wider audience. Getting to be the top story on the NY Times until one of Trump's supreme court appeal rejections knocked it off was a highlight! Michael Coggan from ABC (Australia) wrote a particularly nice article:?

And we made it to the top story in the San Francisco Chronicle:

Another highlight was going to Canberra to give a guest lecture at ASIO. This lecture wasn’t recorded, but it was more or less the same lecture I gave at CSIRO & Macquarie university which you can watch on Dave’s youtube channel:?

That’s pretty much all my recollections from that time. It was a wild ride.

Sometime after, a shrewd reader told Dave that we solved the Z340 on the 340th day of the year. This was a funny coincidence.?

I have often wondered if there are any alternative ways to solve Z340. In particular, if there are any completely algorithmic ways to solve Z340 without having to generate so many candidate transpositions. Perhaps recent advances in large language models will provide a new way to solve Z340??

I’m often asked if I’m working on any other unsolved ciphers. One unsolved cipher that I find particularly interesting is the final unsolved cipher, K4, in Kryptos. I have ran many interesting experiments on K4 and wrote a slippery shotgun hillclimber in C for solving Quagmire I, II, III, and IV ciphers.?