Can evolution reveal a killer’s mind?

November 14, 2007 – 7:13 am

Computer science professor Dr. Ryan Garlick of University of North Texas has a very interesting setup for his symbolic processing course this semester: Each student’s objective is to contribute towards cracking the unsolved 340-character Zodiac cipher.

From a UNT news article:

Cracking the cipher is a difficult task for more than one reason, which is why Garlick, along with his students, are currently developing several computer software techniques that will hopefully make the process far more feasible.
“There are just too many possible keys to look at them all,” Garlick said. “There are 63 different symbols, and each can represent 26 possible letters (we think), which is just too many possible combinations to evaluate them all.”
This is where the computer techniques they are fashioning will hopefully come in handy. Corey Rosemurgy, an Austin senior and computer science major in Garlick’s class, is currently developing a genetic algorithm to solve the cipher.
“The genetic algorithm that I am developing models itself after the inherent properties of biological evolution and the theory of survival of the fittest where only the strong survive,” Rosemurgy said.

I was very interested to discover this course, since I have been working on a similar approach since around March of this year. In my free time (what little there is), I’ve been running experiments using ECJ, a Java-based evolutionary computing framework. So far, my focus has been on trying to get the algorithm to solve Zodiac’s 408-character cipher, which has a known solution. Using a dictionary-oriented approach, the algorithm was able to find the correct solution using a limited 400-word dictionary. Now I am trying to improve this by adding more words to the dictionary used by the algorithm. The basic idea is to get this test case working well before attempting to have it solve the really difficult 340-character cipher. This has proven to be very difficult, because the search space (number of possible solutions) is extremely large, and there is exactly one correct solution. The needle is tiny, and the haystack is vast. Evolutionary computing methods tend to be better-suited for finding really good solutions, rather than the one best solution, so this approach is quite challenging (if not flawed).

I’m glad that many people are still working on this problem; it would be nice to finally find a solution. Still, there is still a strong possibility that there is no solution, and the cipher is just gibberish designed to keep people unnecessarily busy. If so, then the Zodiac killer succeeded beyond his wildest dreams.

More info:
article | course page (of interest here are the syllabus and powerpoint presentation) | google code page and code repository for zodiac decoder software (this is the repository of software used and developed by students in the course)

  1. 16 Responses to “Can evolution reveal a killer’s mind?”

  2. Hi
    what i dont get is why was the first cipher so easily decoded and not the others if they all follow the same monoalphabetic homophonic substitution cipher?

    could these cipher not be gibberish or more advanced to put resources into cracking these when they were first sent? why did zodiac choose to cipher something he could have easily written in plain english if it wasnt important? (and from the decoded first cipher it indeed wasnt really important) but wrote other h letters in plain english?

    By shez on Nov 18, 2007

  3. Those are very good questions, shez.

    The solved 408-character cipher has 54 unique symbols. We know that each symbol represents one of 26 possible letters of the English alphabet (minor encoding errors notwithstanding). This means that the one correct solution was in a set of 54^26 possible decodings for the cipher. This is a very large number. But, there was enough information in the statistics of the symbols in the 408 cipher for it to be solved by recognizing commonly occurring digraphs (specifically, “ll”). This, combined with some intuition on what the Zodiac was probably writing about, led to the decoding of the original cipher.

    Compare that with the 340-character cipher, which has 63 unique symbols. Thus, there are 63^26 possible decodings we can pick from (assuming that we don’t also include numbers and/or punctuation as well), which is about 5500% larger than the set of possible solutions for the 408-character cipher. So, it’s a little bit harder to find the correct solution for the 340 cipher. The Zodiac killer may have put more effort into hiding the frequency distribution of symbols in the cipher, which helps to stifle decoding attempts that rely on statistical methods. It also may be harder due to the 340 character cipher having less ciphertext to analyze (longer ciphertext can often give more statistical clues that can be used to crack them). It is also possible that the encoding method of the 340 cipher is not the same as the 408 cipher. And, it could very well be gibberish that will never decode to anything. Nobody knows. I have read compelling arguments, however, that the 340 character cipher is a similar homophonic substitution cipher, much like the 408 character cipher, but with a larger solution space. These arguments tend to revolve around statistical properties that the 340 and 408 cipher both share, that they wouldn’t share if the 340 cipher was not encoded using homophonic substitution.

    As for Zodiac’s motivation to cipher something in the first place, who knows. I think he just liked the attention, and reveled in trying to manipulate/confuse people. He probably thought he was smarter than everyone, since he had gone on with his crimes for so long without being caught. I’m sure he had a huge smile on his face when his first cipher was published in the newspaper. The notoriety must have been intoxicating.

    By doranchak on Nov 18, 2007

  4. why not substitute the first few letters of the ciphers with “I” or “the” or any common starting words people use and go from there

    and does your “webtoy”’s randomise function if we pressed it enough times could it “decode” the cipher?

    By shez on Nov 19, 2007

  5. Many people have tried to guess the first few letters of the cipher, but I suppose it is not enough to decode the rest, without figuring out how to decode the most common symbols in the cipher.

    It is extremely unlikely that the webtoy’s randomization will ever produce the correct decoding by luck, especially since the randomization feature does not yet select letters from a distribution that matches their frequencies of occurrence in english.

    By doranchak on Nov 19, 2007

  6. shez, have a look at the solved letters so far: Zodiac uses the same cryptography algorithm. I just saw the movie and don’t understand how the argument about the double “l”: IMHO, Zodiac’s key kept in mind recurrence of letters in English and hence the different symbols: The higher the recurrence, the higher the amount of different symbols to represent the same letter. Cracking the first letters was a great task, because it is “easy” to see now, but hard to get behind it if you don’t know the solution. However, you can make assumptions on repeating symbols (just look at the first line of the first letter). If you compare to the 408 char letter, you will see that just the first line (and maybe also the second, I don’t recall it now) has no repetitive symbols at all… As for to “guess” the first letters: Zodiac may as well have inserted nonsense at the beginning (as he presumably did at the end of the first). However, today’s computational power together with a solid algorithm should be able to solve the problem.

    By pi4630 on Dec 2, 2007

  7. What if the symbols are not substitution with variance (each symbol representing more than 1 character of the alphabet). What if each symbol represents an entire word? The only way this could be solved, just like the unabomber’s ciphers, would be to find a key for what each symbol would represent. The unabomber kept a journal in his shack that showed what each number represented (i.e. 2 = then).
    Why not change the way the Zodiac was writting the ciphers? Maybe it was more of a superiority complex for him, to try to show that he could out think the thinkers.

    By ME on Mar 2, 2008

  8. I’m interested to see any analysis done to determine if the Zodiac cipher could be a book cipher like you describe. I imagine it is possible. The zkdecrypto project folks are able to crack many test ciphers using their program, including the zodiac’s 408-character cipher as well as several homemade test ciphers created with similar statistical properties to the unsolved zodiac 340 cipher. But they still haven’t cracked the 340. All of these years of fruitless effort could very well indicate something wrong with our assumptions about the 340 cipher.

    By doranchak on Mar 2, 2008

  9. Very good discussion of the unsolved 340 cipher. Have you considered also that the 2 shorter ciphers, the My Name is and the Map/Bomb cipher, may well be KEYS to solve the 340 cipher. I saw a comment on Zodiackiller.com where the My Name Is cipher could be translated as I AM CRACKPROOF. You are welcome to email me at sgouge123@yahoo.com or PM me on that site, as Let_Justice_Reign2008.

    By Aceman12 on Mar 17, 2008

  10. Hi, I just googled the 340 cipher after a friend of mine told me about it the other day… It seems there are more than 26 characters in the cipher, but when it comes to the - and + symbols, there are 26 when the two sums are added. If you notice, the “u” in the cipher is lowercase, I suspect the author didn’t want someone to mistake it for another symbol… all other letters are uppercase (and backwards in some cases.) Additionally, there is a letter scratched out, with a different letter written above, as if the author went back and checked the ability to decipher the code and realized a correction was needed. Or is it intentional the letter was scratched out? It wouldn’t be difficult to go back and re-write the whole thing for the sake of eluding the authorities…. ie; if careful measures were taken to avoid leaving fingerprints, it might take a whole day to compose such a letter. Maybe its just a ruse and the whole thing is total bullshit. This killer gets pleasure out of dropping subtle hints to his identity, why would he want to give himself up?

    By jim on Sep 1, 2008

  11. They claim to have solved this cipher on may 22nd 2007 I found it under the following link. I believe they were on the right track, but quite possibly missed something vital.

    http://www.opordanalytical.com/articles1/zodiac-340.htm

    By Wayne on Sep 6, 2008

  12. On the subject of the 408 cipher. The fact that there are multiple symbols that represent a given letter and conversely a given symbol that represents multiple letters in the known solution lends the possibility of a multitude of solutions.

    While the known solution for the 408 is coherent with a few misspellings, there are a few things that I wonder about.

    The errors in the words animal (anamal), paradise (paradice) etc,, I can understand given the errors in his letters , however , the errors in slow (sloi) and stop(atop) within the known solution along with the jumbled final 18 letters make me curious as to wether or not the known solution is infact the solution.

    I heard a saying once that if you are looking for something then you will find it and if you are looking for nothing then you will find nothing, or something like that. It is well known that Harden felt the word I and the word kill would be in the cipher for the zodiac was believed to have quite an ego and he obviously liked to kill.

    Just some ideas

    By Scott A. Bond on Oct 28, 2008

  13. Jim,
    To answer your question about why he would drop subtle hints as to his identity, he sent a letter in on December 20th, 1969. That letter is to Melvin Belli. In the letter he is asking Mr. Belli for help, stating he is having difficulty keeping “this thing” inside him in check, and that he cannot remain in control much longer.

    By Wayne on May 20, 2009

  14. I wish you luck on solving it. But I must tell you that Christopher Farmer, President of Opord Analytical, an intelligence company has solved most of the Zodiac’s riddles etc. Mr. Farmer shows Gareth S Penn to be the Zodiac killer and more and more facts keep adding up to show Penn is most likely Zodiac.
    http://www.opordanalytical.com on the forum you will find a lot of info on Penn.

    By Emil on Jan 27, 2010

  15. I quickly discount Mr. Farmer’s theories because he tends to use a combination of significantly contrived steps and pareidolia to arrive at conclusions which seem significant but do not stand up to real cryptographic tests. An example of this is his use of a Japanese fan to arrive at a ridiculous “solution” to the 340:

    http://www.opordanalytical.com/articles1/zodiac-340.htm

    It’s just not convincing.

    Many ciphers can be made to say whatever you want them to say provided you go though enough steps to construct a candidate solution.

    Nevertheless, any attempt at a solution is welcome and might shed some light on the mystery.

    By doranchak on Jan 27, 2010

  16. Maybe Zodiac solved the cipher himself.

    By DGH on Feb 7, 2010

  17. The 340 is intresting because you can read the word zodiac in 6 locations in the text, two of which over lap each other.(one ever char and the other every other char)1 location is vertical(the top right). Also some of the text is the same as the “my name is” cypher kwt and twk (with the t upside down in one). Given the vertical text it may be a crossword of sorts. this isnt un heard of as BTK did the same thing. with D. Rader hidden in the text… so we may have a coded crossword puzzle… nasty indead.

    By Will Foster on Mar 9, 2010

Post a Comment