Cipher Challenge Essays

Essays by the runners-up, Jim Gillogly and John Palagyi, joint winners of the £1000 one year prize.

Please note that Jim's essay was written before the complete Cipher Challenge had been solved.

Jim Gillogly's Essay

Spoiler warning: this note gives away the cipher type of several of the Stages.

As soon as the book was published in the U.S. my friend Thom Fallis (Kapitan Crypto of the American Cryptogram Association) of Atlanta, Georgia started typing in the ciphers and mailing them to me until my copy came in the mail. He sent me Stages 2 and 5 on 17 Sep of last year, by which time the first four had already been solved and acknowledged in Britain. I solved Stage 2 immediately, and identified Stage 5 as probably a Beale-type cipher, but wasn't able to make progress with it. Thom sent me Stage 4 later that day, and I solved that immediately as well: for a long time I've had programs that solve many kinds of classical ciphers. I'd been hoping that because of Simon Singh's instructions the plaintext for Stage 4 might contain a hint for Stage 5, but no such luck.

Stage 5 was a real killer -- unlike the other problems there was no way to make progress: you either solved it or you got nothing. It's like fighting in total darkness. You lose your arrows in all directions, but until you hear a scream you don't know whether you've even gotten close.

Thom sent me Stage 6 the next day, commenting that it looked like it might be a Playfair. I concurred: a frequency count indicated that it had the right distribution for that, and the lack of a J or any repeated digraph in a single pair confirmed it. I had a ready-built Playfair program also, and solved it without much fuss. At this point I was excited because I thought I was going to be on the leaderboard, having solved a higher numbered cipher. However, I didn't have my book with the instructions yet, and didn't realize I had to have all the previous ones as well.

I received and solved Stage 3, the homophonic, the same day (18 Sep), and then Thom sent me Stage 8, which was obviously an Enigma cipher. The rotors and reflector were given, and I recognized them as the standard Wehrmacht Enigma from World War II. It took me a couple of days to solve this one using an adaptation of a program I'd written a few years earlier as part of my research on cracking an Enigma without a crib: in WW2 the boffins of Bletchley had some lovely methods for attacking Enigma when they knew part of what a message said, and used that to find the keys to enable them to crack a day's traffic. My method didn't require that crib. This was finished on 23 Sep 1999.

By this time I'd received and solved Stage 1 as well, and had started working on Stage 7 -- as you can see, I solved most of them out of order. It wasn't until 3 Oct that I finished Stage 7 -- I'd taken a number of wrong turns, and finally finished slogging through the morass. Of course, the insidious Stage 5 was still niggling away at me. The idea, I felt, must be to find the right key-text (presumably something published somewhere) and use that to identify the meaning of the individual numbers that constituted this Stage. It seemed to me that in order for it to be a fair challenge, there had to be a clue in the book or in the nature of the problem itself -- otherwise it would be an unfair challenge: "Out of all the possible texts in the world, which one did I pick as the key to this cipher?" There were a lot of obvious possibilities: a passage from The Code Book itself, including the plaintext of one of the earlier stages; The Gold Bug by E. A. Poe, an early cryptanalysis story; a Sherlock Holmes story; one of the books mentioned in The Code Book, such as David Kahn's "The Codebreakers"; a play by Shakespeare; and so on. I kept looking for clues and deconstructing things Simon had said, with no luck.

The solution to Stage 8 gave the precise nature of Stage 9 -- I suppose it won't be too much of a spoiler for your readers to learn that it's encrypted with DES, the Data Encryption Standard that will be replaced on Monday 2 Oct 2000 with the Advanced Encryption Standard, which will be rolled out at 11AM Eastern Time. Stage 8 also gave enough bits of the key so that the final key length was 48 bits. This is a substantial computation effort for a single CPU, but I knew a man who'd built a multi-CPU machine specifically for the purpose of breaking DES -- John Gilmore of the Electronic Frontier Foundation, who'd funded the building of this machine in order to show how ludicrous the U.S. export regulations were in preventing the export of 56-bit DES. I sent John email on 5 Oct 1999 inviting him to try his machine on it. He answered in the affirmative, and in the evening of 8 Oct he and his dinner guests, Landon Noll and Simon Cooper, brought up as much of Deep Crack (the DES-cracking machine) as would easily come up, I provided the initial 8 bits of key and my guesses as to the nature of the cipher mode, and they had at it. We had a couple of false starts as we established parameters for recognizing a correct result, but it all went smoothly and the solution arrived in 80 minutes of run time.

At this point I went back to studying Stage 5 -- I now had in hand all the solutions except for Stages 5 and 10, with an elapsed time of only three weeks. I kept trying key-texts that looked like they had some justification: reasonable crypto-related texts, things that were implied by various readings of The Code Book, and eventually in desperation all the on-line text I could get my hands on, including the Oxford Text Archive, most texts from the Gutenberg Project, various editions of Bibles and other religious books, the Beale Ciphers themselves, various government documents like the Declaration of Independence that was used to encrypt Beale #2, and so on. No luck. I started setting it aside for longer periods as I worked on other projects. At this point my feelings were much like Gollum's in "The Hobbit", when Bilbo asked him the rather unfair riddle "What have I got in my pocket?"

If you spend all your time working on a single intractable or barely tractable problem, you miss the rest of life's challenges -- for example, I've been working on the so far unreadable Voynich Manuscript, which first surfaced in about 1600, for 30 years without having made much progress on it. There are plenty of interesting unsolved ciphers in the world to work on, and I was no longer confident that this one was realistically solvable.

Then in December Andrew Plater finally solved Stage 5, followed shortly by Lin Bird. This meant at least that it was solvable, and that someone who's thinking in the right direction had a chance of getting the solution. This is an important aspect of cryptanalysis: if you know a solution is possible, or you are confident that you can break it, you have a much better chance of it.

However, I still couldn't get a handle on it. At the beginning of April 2000 the handwriting was on the wall: several people had the solution to Stage 5 (though I still hadn't found it), and Chris Card had formed a Brute Squad to attack Stage 9 using a large number of normal workstations. The idea was that the solution would be shared amongst all of them, so the first Stage 5 solver in the group would move to the top of the Leaderboard, assuming he or she had finished all the other Stages from 1 to 9. I estimated that it would be only a few weeks before they finished, and thus a team would have gotten to the top of the leaderboard within a month. This being the case, I decided I might just as well be on such a team, so I offered to share solutions with the first interested Stage 5 solver to write back -- this was John Palagyi, Jr., and we promptly made common cause and sent our solutions to Simon.

The contest is still going strong: there's one more Stage to go, and it consists of finding the solution either to a very difficult RSA problem or an almost impossibly difficult triple-DES problem. My group, which now includes Alec Muffett, is working on the RSA end of it, and racing about five other groups. Despite the apparent head start we had from solving Stage 9 early on, I'd felt there was plenty of time to learn more maths before getting started on Stage 10 -- after all, the contest runs for 10 years -- and I didn't do anything on it before eliminating Stage 5. I reckoned without Chris Card and the Brute Squad, though, so all the Stage 10 factoring groups started at about the same time. It's still a real race, with the bigger brass ring waiting for us.

John Palagyi's Essay
My Cipher Challenge Experience or 'How To Get From Here To There In 9 Stages' by Johnny Palagyi

This essay tells how I solved the stages and does contain explicit spoilers. Those that want to solve on their own are advised to look away now.

I purchased my book on Sunday, January 2nd after having survived the dreaded Y2K rollover at work with no meltdowns. I had read Simon Singh's previous book about Fermat's Last Theorem and found it interesting. This history of codes and ciphers looked good too, so I bought it. I noticed the challenge right off but promised myself that I wouldn't work any of the stages until I'd completed the book.

That promise lasted all of two days and on Tuesday the 5th I solved stage 2 while watching a baseball game on TV. I used the Vigenere square in chapter two to look for what LZA could be. I ran through the alphabet twice and got no English words. I did note that "est" came out once though. When I went back to that line and the first word was "faber" I realized it was in Latin. A Caesar shift in Latin, I was amused. I solved stage 1 later that evening just using pencil and paper. Thank goodness it was in English (for me).

Having read far enough to understand the next two stages, I decided to tackle stage 4 next as that had a clear explanation in the book. It took longer than it should have because I didn't read carefully the explanation of how to do it. A mistake I was to repeat more than once. After I learned to count between repeated characters properly, stage 4 was complete. Thank goodness for high-school French.

Now back to stage 3 and the dreaded homophones. By now the language pattern had emerged and I had from the library David Kahn's "The Codebreakers", so a little reading was in order before tackling stage 3. From this I narrowed it down language wise, it went quickly, and I had the first four stages in four days.

I then decided to check out the web site and see how the challenge was going. I was surprised to find that the challenge (and the book) had been out since September. The surprise was due to the fact that I visit the bookstore weekly and I had missed seeing "The Code Book" all that time. From there I found the discussion list and signed up. Seeing as how stage 5 was occupying much of the discussion I decided to tackle stage 6 next. With the use of the Playfair program from the discussion list and Helen Gaines' book, stage 6 took up all of Saturday afternoon. This was the only stage where using my favorite cribs of "stage", the stage number, "code", "codeword", etc proved of any use.

I then decided to work on stage 8 and/or stage 7 while trying various things on stage 5 as they occurred to me. Fortunately for me, something occurred to me and it was correct! The most obvious choices (I thought) were "The Code Book", "Fermat's Enigma", or something referred to in "The Code Book" itself. I tried the book itself first (language invariant portions), the Declaration of Independence, the poems mentioned in the book. Then I picked up "Fermat's Enigma". When I looked for something in there that would be fair in a world wide challenge, only one thing stood out and when I tried it out came the solution. Here is was, the 27th of January and I was only two stages behind Andrew Plater who sat atop the Cipher Challenge leader board. I was flying high because as far as I could tell I was only 1 of 4 that had a stage 5 solution and from the egroups discussion stages 7 and 8 could be done with a little programming which I felt I was up to

It was at this point that work and life interrupted my code cracking for about a month and a half. However, in March, I was able to devote all of Saturday to first stage 8 (complete 4 March). This was due to Jim Gillogly's enigma paper which he consented to be posted on the net. Stage 7 took longer than it should have because once again, I made it harder than it needed to be. When I coded a trigraph checker I included too many trigraphs which skewed the results. I lowered the number of trigraphs to the most significant and decryption followed rapidly (complete 18 March).

I'd caught back up again, but now had nowhere to go. I knew stage 9 was beyond my resources, but I tinkered with it anyway. Then came the announcement of a group effort for stage 9 for which I signed up. Shortly after that got underway, Jim Gillogly made his offer and I began a discussion with him. We originally began by trading hints, me offering stage 5 hints and him stage 9 information. This was no easy matter given the nature of the key text for stage 5. Eventually we just decided to team up and we sent off our solutions. As the team from Sweden can tell you, there's nothing like getting a phone call and the voice on the other end says, "Hello, this is Simon Singh"!

My heartiest congratulations and regards to the Cipher Challenge solvers!

Special thanks to whom they are due. Simon Singh, for the book. Sandy MacPherson, for the e-groups list. Terry Froggatt, for digests 1-139. Richard Kaplan, for the Beale-O-Matic (TM). Mark Vande Wetting, for the enigma simulator. Jan Stumpel, for the Playfair program. Chris Card, Jonathan Vaugh, Jean-Baptiste Yves and Gilles Brochier, the stage 9 "brute" founders. All the e-groups posters, it's interesting reading. And of course, Jim Gillogly. My apologies to anyone I forgot to mention and if I misspelled anyone's name.