Feeds

Codebreaker II Our winner reveals all

Mark Wutka explains his attack

  • alert
  • submit to reddit

Combat fraud and increase customer satisfaction

In response to readers' requests for our Codebreaker II supremo, Mark Wutka, to explain how he attacked the problem, we are pleased to print the following from the man himself. Enjoy:

When I first saw the Codebreaker II Challenge, I did what any cryptanalyst would do with an unknown cipher - I counted the occurrences of each letter. In normal English text, the letters ETAONIRSH occur most frequently, with E appearing about 13% of the time. You also expect letters like J, Q, X and Z (the high-point Scrabble letters) to appear very infrequently, if at all.

Because Codebreaker II was 587 letters long, you might expect to see some of the low-frequency letters appear once or twice. When I counted the letters, however, I saw the following numbers: Q:28 Y:28 G:28 R:28 U:28 T:27 A:27 I:25 H:25 C:23 F:23 V:22 X:22 W:22 P:21 E:21 S:21 L:21 N:20 Z:20 O:20 B:19 K:19 J:18 D:17 M:13. Notice that all 26 letters appear, and that the lowest frequency is roughly half the highest one. The highest value should have been around 76 (13% of 587). Obviously, this was not a simple substitution.

Instead, it was likely to be a polyalphabetic cipher where a letter can represent different letters at different times. In conversations on the rec.puzzles newsgroup, Jim Gillogly suggested several possibilities and ruled out others. For example, many polyalphabetic ciphers use a 5x5 square to encrypt letters, using the same letter to encrypt both I and J. In this cipher, however, all 26 letters appear, so it couldn't be any of those (like Playfair, for instance).

Jim suggested something in the Vigenere family of ciphers, which use a set of 26 different alphabets, or possibly a mechanical encryption like Enigma. Enigma was an obvious choice since The Register is in the U.K. and Britain is very proud (rightly so) of their work on breaking the Enigma during World War II. At one point, I had been very close to the correct settings. I guessed that the set of rotors might be a permutation of the submission date (04/05/01) and that the initial position for the rings might be REG, but I never would have guessed the 23/06/12 (Alan Turing's birthday) for the ring setting.

It was at this point that Jim Gillogly was too smart for his own good. He reasoned that if this was an Enigma encryption, then the letters ETAONIRSH should appear less frequently than the others because the Enigma never encrypts a letter as itself. That is, if you type an E into an Enigma machine, you'll get anything BUT an E as the output. Jim performed tests on several English texts to verify his hypothesis, and it looked correct. We never suspected that the text might have been encrypted some other way first. Jim is an expert at classical cryptography and has written a program that is quite good at cracking Enigma cipher.

After the smoke cleared, he ran his program on the Codebreaker II and found that it did, in fact, figure out the correct settings, including the plugboard. He also wrote a paper describing his Enigma cracking technique, which is available here. After incorrectly ruling out Enigma, we floundered around with variations of Vigenere ciphers, but obviously never got anywhere. We finally got discouraged and realized that we desperately needed a clue.

When clue time arrived, I immediately recognized the clues as Enigma settings. I didn't know much about the internals of the Enigma when the contest started but by the time the clue arrived, I had read several papers describing its operation. I grabbed an Enigma simulator off the net and decrypted the text. The SO FAR SO GOOD at the end was the only clue that I had done it right, although the supplementary encrypted text also told me that I had the right settings.

Now that I had this newly decrypted text, I went back to the beginning and did a frequency count again. This time, it was much more in line with a simple substitution cipher: U:77 L:57 F:51 D:51 S:50 M:37 K:37 N:36 J:27 O:24 W:21 B:21 X:18 T:17 P:14 Q:11 C:10 E:9 A:5 G:5 R:5 H:2 V:1. Notice that U appears 77 times, just a hair over 13% of the time. I assumed that this was English text and substituted E for U and T for L. I also employed another technique which is to count the number of times various letters contact each other. In the case of L (which I assumed was T), I noticed that it came before M 19 times. I figured that M must represent H, because H frequently appears after T.

At this point, I noticed several occurrences of TH T (where the blank was an S in the ciphertext, making me think that S must represent A. By this time, I was beginning to think that I was wrong about M representing H, because I saw HH appear several times, and you don't normally see that in English text. I did notice, however, that HATH occurred several times, so I got the impression that this was old English.

Next, I looked for the pattern T THE, expecting TO THE to occur somewhere, but I didn't find it. Going back to the contact frequencies, I noticed that J appeared after U 9 times - the most frequent letter to appear after U. In English, the letter that most frequently comes after E is R, so I guessed that J represented R. Now, looking at the beginning of the cryptogram, I had A TER, with a T representing the blank spot. I guessed that T represented F. Next, I looked for the F R pattern, figuring that FOR must appear somewhere. I saw several places, each with F representing the blank spot. I guessed that F must represent O.

At this point, I noticed a piece of a phrase - THATTHEROOTEOFA - that really made me realize I was on the right track. First, I began to suspect that this was something like Chaucer, because of "roote", which you may remember if you ever had to memorize the opening to the Canterbury Tales, that included the line "The Droute of March hath perced to the roote". Since the next two letters after A were the same letter (B), I guessed that B was probably L. I also noticed FOR OOTH, which certainly looked like it should be FORSOOTH, so I substituted S for K. The introduction of S into the text also brought about another piece of phrase that looked solveable - THATHESO LEHATHLOSTTHE. Since ROOT was spelled ROOTE, I thought maybe SOUL was spelled SOULE and substituted U for the P that represented the blank spot.

Now, all is fair in love, war, and Codebreaker challenges, so at this point, I decided to bring the Internet to bear on the problem. I went to www.altavista.com and typed +"that the soule hath lost the" (Actually, I tried Google first, but because it always breaks up the words, it didn't find anything that looked like a match). Altavista gave me three results, all containing Chaucer's "The Parson's Tale". After that, it was a simple matter of completing the substitutions.

Had I not taken that shortcut, my probable next step would have been to substitute ND for DW, since I saw FOU and would assume that it was probably FOUND. You would then be able to solve the rest quite easily.

This was a fun and challenging puzzle and I look forward to see what torture Lester dreams up for Codebreaker III!

If you are interested in cryptograms of all sorts, you might consider joining the American Cryptogram Association. Although the name says "American", they welcome members from all nationalities (although most of their cryptograms are in English).

I'm the author of Special Edition Using Java Server Pages and Servlets, and also Special Edition Using Java 2 Enterprise Edition. I can be reached here.

Bootnote

Thanks to Mark for sharing that with us. You can find the Codebreaker II solution here.

High performance access to file storage

More from The Register

next story
Spanish village called 'Kill the Jews' mulls rebranding exercise
Not exactly attractive to the Israeli tourist demographic
Oz bank in comedy Heartbleed blog FAIL
Bank: 'We are now safely patched.' Customers: 'You were using OpenSSL?'
Happy 40th Playmobil: Reg looks back at small, rude world of our favourite tiny toys
Little men straddle LOHAN, attend tiny G20 Summit... ah, sweet memories...
Forget the beach 'n' boardwalk, check out the Santa Cruz STEVE JOBS FOUNTAIN
Reg reader snaps shot of touching tribute to Apple icon
Lego is the TOOL OF SATAN, thunders Polish priest
New minifigs like Monster Fighters are turning kids to the dark side
Dark SITH LORD 'Darth Vader' joins battle to rule, er, Ukraine
Only I can 'make an empire out of a republic' intones presidential candidate
Chinese company counters pollution by importing fresh air
Citizens line up for bags of that sweet, sweet mountain air
Google asks April Fools: Want a job? Be our 'Pokemon Master'
Mountain View is prankin' like it's 1999...
prev story

Whitepapers

Securing web applications made simple and scalable
In this whitepaper learn how automated security testing can provide a simple and scalable way to protect your web applications.
3 Big data security analytics techniques
Applying these Big Data security analytics techniques can help you make your business safer by detecting attacks early, before significant damage is done.
The benefits of software based PBX
Why you should break free from your proprietary PBX and how to leverage your existing server hardware.
Top three mobile application threats
Learn about three of the top mobile application security threats facing businesses today and recommendations on how to mitigate the risk.
Combat fraud and increase customer satisfaction
Based on their experience using HP ArcSight Enterprise Security Manager for IT security operations, Finansbank moved to HP ArcSight ESM for fraud management.