Back in 2008, at DEF CON 16, G. Mark Hardy presented his second crypto challenge. I didn’t go to DC16, so I didn’t see the challenge (and even if I had, I wasn’t really tracking these at the time). But in 2010, at ShmooCon, he dusted the challenge off and handed it out again, as nobody had solved it yet. I’d managed, with a buddy, to solve the ShmooCon badge puzzle that year, and after I got home I started on the DC16 puzzle. It took me a few days, but I managed to beat it.

I’ve held off on writing this one up, because the original included a phone number, and I didn’t want to publish that without G. Mark’s approval. And though we’re in frequent contact, it wasn’t until recently that I remembered to ask him about it. At his request, I’ve modified the puzzle slightly, with a different phone number (which I’m sure you’ll recognize). The method to arrive at the solution is still the same as the original.

The puzzle was handed out in five pieces, each printed on old computer punch cards. Each card included some additional text and two lines of code. Here are the five cards (again, modified for a different endgame):

VFLASGGGGIUGAAGYBDAWHOEVHUUVLLHGJYOLGFGP
GHALGGGOAAGGJPLLHZIHBFMHWIHSRYOIFPMIFVTF

XBMGRMBULEMPBMSRGMEBYRGMGRGHFMAGNMRLRZOM
GXMJRMLNBMEMUAZEGNVSOSFCUMXDSLDPFFUMXDVY

BVQZWOOBPPUSAZJEAUBTMATDFAJTTAUIFDSAQPVI
PFTIBOPWAUFOFHFAAJBUGBQBBCNXLQJMBUJVQDGN

QRJRWGDNMCZQTGYRZGFWRLRJRUFRSYWWKARAGMLS
RRGSKGMWYZKGSREOAVSXAQRZWHDKEQICCVMVUSAQ

KCPNCEJPKPPAFFFZZKDKEPEPZZFXRCOKLAVDYDKO
XTXEJHKKPPEKECMSKKWAMCLAADOJDADZKSNXIJJQ

As always, if you’d like to try to solve this yourself, then STOP now, as the rest of this post is full of spoilers. The text above is all that you need to get started.

One of the first things I did was to try the simple attacks: ROT-13, for example. After those gained me nothing, I wrote a simple python script to output letter frequencies for each card. The results looked something like this:

A :    7     2     9     5     6   
B :    2     5     9     0     0   
C :    0     1     1     3     5   
D :    1     3     3     2     6   
E :    1     4     1     2     6   
F :    6     4     6     2     4   
G :   15     8     2     7     0   
H :    8     1     1     1     1   
I :    5     0     3     1     1   
J :    2     1     5     2     5   
K :    0     0     0     4    12   
L :    7     4     1     2     2   
M :    2    15     2     4     2   
N :    0     3     2     1     2   
O :    4     2     4     1     3   
P :    3     2     5     0     8   
Q :    0     0     5     5     1   
R :    1     7     0    12     1   
S :    2     4     2     6     2   
T :    1     0     5     1     1   
U :    3     4     6     2     0   
V :    4     2     3     3     1   
W :    2     0     2     6     1   
X :    0     4     1     1     4   
Y :    3     2     0     3     1   
Z :    1     2     2     4     5

So the five cards have distinctly different frequency distributions, but none of them are really flat. The first card had more Gs than any other letter, the second, slightly more Ms than Gs, etc. Pretty quickly I’d noticed a pattern: GMARK. I later saw this as a recurring theme in his puzzles, but this was the first time I’d seen it, and so I was kind of stoked. First, I tried shifting the letters back such that the most common letter was E, but that didn’t seem to look right. Remembering that he often uses Z for a space, I then shifted them back to Zs (G -> Z, M -> Z, etc.), and now my texts looked like this:

OYETLZZZZBNZTTZRUWTPAHXOANNOEEAZCRHEZYZI
ZATEZZZHTTZZCIEEASBAUYFAPBALKRHBYIFBYOMY

KOZTEZOHYRZCOZFETZROLETZTETUSZNTAZEYEMBZ
TKZWEZYAOZRZHNMRTAIFBFSPHZKQFYQCSSHZKQIL

AUPYVNNAOOTRZYIDZTASLZSCEZISSZTHECRZPOUH
OESHANOVZTENEGEZZIATFAPAABMWKPILATIUPCFM

YZRZEOLVUKHYBOGZHONEZTZRZCNZAGEESIZIOUTA
ZZOASOUEGHSOAZMWIDAFIYZHEPLSMYQKKDUDCAIY

ZRECRTYEZEEPUUUOOZSZTETEOOUMGRDZAPKSNSZD
MIMTYWZZEETZTRBHZZLPBRAPPSDYSPSOZHCMXYYF

But this still didn’t give me a cleartext. Some kind of wild guess made me think that I was dealing with a columnar transposition, which I’d never tried to break before. So I resolved to do this one, and to do it “by hand” (without resorting to brute-force computer programs). I tried some simple rearrangements of each card’s text, but got nowhere…

Then I realized, that I might be able to do an attack “in depth”: Since I had 5 different ciphertexts, if they were all encoded with the same key, then I could use bits of one to help solve another. I lined all the text up in five columns, and started trying to rearrange the rows such that words formed. For example, if I found a Q in the first column, I’d then look for another row with a U in the first column, and put them together. I did that for all the Qs I could find, then looked in the other columns to see if other obvious digraphs were being formed.

This way, I figured, I might start with “QUI” in one column, and notice “HIS” in another. Then I’d just have to put a row with “T” above HIS" and I’d have another word built. Repeat, and repeat, and eventually I’d solve all of them.

Except that this wasn’t how the puzzle worked. :(

As I realized that I was getting nowhere, I noticed that there were two rows which read “Z Y O U Z.” And for the first time, I saw the word “YOU” in the middle of two Zs. And realized that I was being an idiot.

I eliminated some spaces, to make it easier to read, and found the plaintext. [I was working vertically, but to save space I’ll rotate it here, in two blocks. The first block is the 1st half of each card’s shifted text, placed one on top of the next, the 2nd block is the same for the 2nd half of each card].

OYETLZZZZBNZTTZRUWTPAHXOANNOEEAZCRHEZYZI
KOZTEZOHYRZCOZFETZROLETZTETUSZNTAZEYEMBZ
AUPYVNNAOOTRZYIDZTASLZSCEZISSZTHECRZPOUH
YZRZEOLVUKHYBOGZHONEZTZRZCNZAGEESIZIOUTA
ZRECRTYEZEEPUUUOOZSZTETEOOUMGRDZAPKSNSZD

ZATEZZZHTTZZCIEEASBAUYFAPBALKRHBYIFBYOMY
TKZWEZYAOZRZHNMRTAIFBFSPHZKQFYQCSSHZKQIL
OESHANOVZTENEGEZZIATFAPAABMWKPILATIUPCFM
ZZOASOUEGHSOAZMWIDAFIYZHEPLSMYQKKDUDCAIY
MIMTYWZZEETZTRBHZZLPBRAPPSDYSPSOZHCMXYYF

Reading down each column in the 1st block, then continuing in the 2nd, we get:

OKAYZYOUZREZPRETTYZCLEVERZZNOTZONLYZHAVEZYOUZBROKE 
NZTHEZCRYPTOZBUTZYOUZFIGUREDZOUTZHOWZTOZTRANSPOSEZ 
ALLZTHEZTEXTSZTOZCREATEZONEZCONTINUOUSZMESSAGEZZGR 
ANTEDZTHEZCAESARZCIPHERZKEYZISZEPONYMOUSZBUTZIZHAD 
ZTOZMAKEZITZSOMEWHATZEASYZZNOWZYOUZHAVEZTOZGETZTHE 
ZRESTZZNOZCHEATINGZREMEMBERZWHATZIZSAIDZ

Or, cleaned up:

OKAY YOU RE PRETTY CLEVER  

NOT ONLY HAVE YOU BROKEN THE CRYPTO BUT YOU FIGURED OUT HOW 
TO TRANSPOSE ALL THE TEXTS TO CREATE ONE CONTINUOUS MESSAGE  

GRANTED THE CAESAR CIPHER KEY IS EPONYMOUS BUT I HAD TO MAKE 
IT SOMEWHAT EASY  

NOW YOU HAVE TO GET THE REST  

NO CHEATING REMEMBER WHAT I SAID

Woohoo! Of course, that’s not all. There’s still a block of text at the end that’s not right:

BAUYFAPBALKRHBYIFBYOMY
IFBFSPHZKQFYQCSSHZKQIL
ATFAPAABMWKPILATIUPCFM
AFIYZHEPLSMYQKKDUDCAIY
LPBRAPPSDYSPSOZHCMXYYF

So there’s more to decode. Fortunately, G. Mark gave us a big hint when he said “NO CHEATING.” That’s his clue, made clear in his Tales from the Crypto talk, that this stage requires the Playfair cipher. But what key? Well, for his Mardi Gras puzzle, he used the title of his talk, so what talk did he give at DEF CON 16? “A Hacker Looks Past Fifty.”

Plugging this into a friendly online Playfair decoder reveals the final cleartext:

TEXTTHEPHRASEFIFTYISNI
FTYTOSEVENTIMESSEVENFO
URTHREETIMESFOURTWOEIG
HTFIVEZERONINEANDTHEFI
RSTPERSONTOSOLVEWINSIT

Or, cleaned up:

TEXT THE PHRASE FIFTY IS NIFTY TO 
SEVEN TIMES SEVEN FOUR THREE TIMES FOUR TWO EIGHT FIVE ZERO NINE 
AND THE FIRST PERSON TO SOLVE WINS IT

Still not quite finished. So now we’ve got to do some math and number manipulation. At first, I thought it was several different multiplaction operations, somethng like:

7 * 7, 4, 3 * 4, 2, 8, 5, 0, 9 == 49 4 12 2 8 5 0 9 or 494-122-8509

I texted the phrase to that number, but got no response. After a while, I sent an email directly to G. Mark, who confirmed that I’d broken the cipher, but did the math wrong.

It wasn’t a bunch of separate operations, but a single operation, like this:

7 * 743 * 428509

Which yields the following (obviouly faked for this blog entry) phone number:

222 867 5309

This was a fun puzzle! I took some wrong turns, tried some new techniques, had some good luck, and made some stupid mistakes. A little of everything. Of course, tweaking the puzzle so I could (finally) publish the writeup was fun, too, especially factoring numbers to get them to fit into the ciphertext space available. Interesting bit of trivia: Turns out that 8675309 is a prime number. :)

(view Archived Comments from the old site)