Monthly Archives: March 2008

The joys of breeding

Last week was a good week for my strange little diversions with genetic algorithms. Two things happened that helped to validate the legitimacy (in my mind) of using genetic algorithms to solve certain problems. The first was receiving a copy of the March issue of Muse Magazine, a children’s magazine about science, art, and history. A little blurb about my evolutionary art project for last year’s GECCO conference appeared in the magazine.


I wish I had the time to continue to improve the art generated by that technique. It was a lot of fun to play with. There are many other ideas I want to try, such as adding new measurements to compare things like texture and composition, but, alas, not enough time to explore them. One day I hope to return to this.

Meanwhile, I’ve been wasting way too much free time trying to develop a genetic algorithm to attack the unsolved Zodiac killer cipher. The results have been somewhat minimal so far, but it’s a start. I’ve been playing with this stuff since March of last year, so I figured I should have something to show for all the time I’ve put into this research. I decided to write and submit a research paper to this year’s GECCO conference on evolutionary computing, and my paper was accepted as a poster presentation. W00t! I had a lot of fun at last year’s GECCO conference; I look forward to absorbing all the fascinating cutting-edge presentations this year. Here is the title and abstract from my paper:

Evolutionary Algorithm for Decryption of Monoalphabetic Homophonic Substitution Ciphers Encoded as Constraint Satisfaction Problems

A homophonic substitution cipher is a substitution cipher in which each plaintext letter maps to a set of one or more ciphertext symbols. Monoalphabetic homophonic ciphers do not allow ciphertext symbols to map to more than one plaintext letter. The selection of ciphertext symbol mappings is intended to conceal language statistics in the enciphered messages. Statistical-based attacks that are known to be quite effective on simple substitution ciphers are very difficult to apply to homophonic substitution ciphers that employ good selections of ciphertext symbol mappings. Word boundaries are often not known, increasing the difficulty of decryption. We present a dictionary-based attack using a genetic algorithm that encodes solutions as plaintext word placements subjected to constraints imposed by the cipher symbols. For a test case to develop the technique, we use a famous cipher (with a known solution) created by the Zodiac serial killer. We present several successful decryption attempts using moderate dictionary sizes of up to five hundred words. Attempts are ongoing to increase the robustness of this technique by making it work with larger dictionaries and a variety of test ciphers.

Since then, I’ve gotten the technique to work against the test cipher with dictionary sizes of 1200 words, but the algorithm is very sensitive to various parameters when it is running, so it’s not very robust yet. There is still a lot of work to do.

Maybe I should get a normal hobby.

Zodiac cipher solver program updated

A new version of zkdecrypto is available for all you cipher enthusiasts. The zkdecrypto team has been very busy adding new features and fixing bugs.

* Program is now both smaller and MUCH faster
* Ability to now open both ASCII and numeric ciphers
* Ability to now save the loaded cipher
* Exclusions and locked letters are now saved in the “key” file
* New Redo function in addition to Undo
* New pattern analysis and sequential analysis reports
* 1-click ability to add full alphabet to “Additional Key Letters”
* New “Word List” feature that lists words found in the plaintext

…and more.

Click here for more information and download links.

The lolbots are coming

From the collective superintelligence of the Internet masses came the lolcat phenomenon, a sign to future anthropologists of the advancement of our species.

Lolcat specimen, circa 2007.

The popularity of lolcats has led to many other similar phenomena, such as the lolrus, lolhamster, loldog, lolcode, even lolthulhu.

And now, even our local grocery store is getting in on the game and expanding the loltaxonomy:


And did you see the cashier name?

Clearly, the LOL phenomenon is a sign that the robot invasion is coming soon.