Darth Null

On July 15, Fidelis Security Solutions announced that they’d be running a crypto puzzle at Black Hat. And that the prize would be $1000. So, naturally, I was quite interested. I went to their site, downloaded the puzzle, and set to work:

^
¥Ð§µ    
¶®Æä
æ©×ä
÷ijŒĐ
ƆķėIJ
ŦůŶū
ƂƐƔƆ
ŦƉƶǴ
ƆƅƦƬ
džƹɇʃ

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, or you can click here to see the ciphertext and the hints that were revealed during the conference.

It’s immediately obvious that we’re not looking at straight ASCII. I figured it would be UTF-8 encoded, and verified that quickly. But the question then was whether the decoding work should be in UTF-8 or if, for example, I needed to convert it to UTF-16 first. I even considered that maybe I needed to look to the official Unicode name for each character, instead of the binary representation of it. Here’s the hexdump of the ciphertext, in UTF-8 (with newlines dropped for clarity):

5e 
c2 a5 c3 90 c2 a7 c2 b5 
c2 b6 c2 ae c3 86 c3 a4
c3 a6 c2 a9 c3 97 c3 a4
c3 b7 c4 b3 c5 92 c4 90
c6 86 c4 b7 c4 97 c4 b2
c5 a6 c5 af c5 b6 c5 ab
c6 82 c6 90 c6 94 c6 86
c5 a6 c6 89 c6 b6 c7 b4
c6 86 c6 85 c6 a6 c6 ac
c7 86 c6 b9 c9 87 ca 83

The little ^ character at the beginning made me think of XOR — since in many languages, that’s the operator used for that. So I need to find some binary key stream that, when XORd with the ciphertext, will give me plaintext.

I played with that for a while, then watched their little promo video again. And there, at the very end of the video, the phrase “ALL YOUR ¥Ð§µ ARE BELONG TO US” zooms past the viewer. So “¥Ð§µ” == “BASE”? Okay, that’s something else I can work with.

Another interesting thing that I noticed: in UTF-16, the first byte of each two-byte pair (each character is represented by two bytes) increases gradually over the entire ciphertext:

005E 
00A5 00D0 00A7 00B5 
00B6 00AE 00C6 00E4 
00E6 00A9 00D7 00E4 
00F7 0133 0152 0110 
0186 0137 0117 0132 
0166 016F 0176 016B 
0182 0190 0194 0186 
0166 0189 01B6 01F4 
0186 0185 01A6 01AC 
01C6 01B9 0247 0283

In the UTF-8 version, the first byte varies among c2, c3, c4, c5, etc., but is generally increasing (just not quite as clearly in the UTF-8 version). So it seems pretty likely that the first byte is irrelevant.

After a few days, pulling the puzzle out every now and then, the original puzzle page was removed and replaced with something that essentially said “You’re too early. Come back later for the puzzle.” Damn — maybe what I’ve been playing with was just a teaser, and not the real puzzle. Okay, I’ll forget about it for a while (and finish my talk slides…)

Fast forward to Black Hat, I stop by the Fidelis booth. And discover that the original puzzle is in fact the real puzzle. Arrgh! I could’ve been working on this all along!

Every few hours over the course of the conference, they sent out hints via Twitter. Predictably, the first few hints don’t help me at all, though one tweet “get to know xxd” helps. As sending the original ciphertext through xxd would just give me a straight UTF-8 dump in hex, I now know I’m supposed to use that encoding and not convert to UTF-16.

But that’s not helping me any. They tell me in person that the “BASE” bit wasn’t meant to mean anything, so that was just a red herring. They also tweet some of the plaintext (“Fidelis” is in it), but still I’m getting nowhere. I tried writing some tools that’d drag “Fidelis” across the ciphertext, looking at what the XORd keystream would have to be in order to produce that plaintext. That gets me nowhere.

A later tweet says that there are only 20 characters in the plaintext. Ooooh, that changes things. Now I’m playing with XORing two bytes in a row (like A5 ^ D0, then A7 ^ B5, etc.) but again, no luck. Another hint tells me that ¥ and µ are the same, but that doesn’t help either (one’s encoded as A5, the other as B5), and if we’re talking about two-character sequences, then now I’m really confused).

Finally, at 1:07 on Thursday, they released this hint: “‘C2A5′ =~ /.{3}(.)/”. This tells me that for every four-character hex sequence, I only need to look at the last character.

I get off the escalator, pull up the ciphertext hex on my phone, and start decoding ASCII in my head. “P…u…n…d…” Oh, crap. Finding a corner to sit in, I open the hex in a text editor and pull up an ASCII chart. What I end up with is this:

a5 90 a7 b5 
b6 ae 86 a4
a6 a9 97 a4
b7 b3 92 90
86 b7 97 b2
a6 af b6 ab
82 90 94 86
a6 89 b6 b4
86 85 a6 ac
86 b9 87 83

becomes:

5 0 7 5 
6 e 6 4
6 9 7 4
7 3 2 0
6 7 7 2
6 f 6 b
2 0 4 6
6 9 6 4
6 5 6 c
6 9 7 3

which then becomes:

50 75 6e 64 69 74 ....

or

Pundits grok Fidelis

I immediately went to the Fidelis booth, walked up to Will (the creator of the puzzle), looked him in the eye, and simply said “Really? REALLY!?” That got a laugh. Apparently, in his words, I gave him “too much credit.” I was looking for an actual, cryptographic solution, when really the answer was staring me in the face THE ENTIRE TIME.

And if I’d taken the time to really think about it, I should have solved this in 10 minutes just by visual inspection. Remember when I said that I’d determined pretty quickly to drop the initial byte of each pair? The “c2″ and “c3″ and so forth? Well, part of figuring out whether it was UTF-8 or UTF-16 involved me looking at the Wikipedia pages for UTF. Which told me that when a pair begins with c2 through cf, the next byte MUST start with 8, 9, a, or b. So I knew, almost from the beginning, that not only did the first byte have no real bearing in the puzzle, but the next nybble (the first character of the 2nd byte) had no bearing either. But that fact just never registered.

In fact, hindsight has helped me to recognize not just one, but two different ways to look at the data and quickly solve the puzzle. Let’s look at the hex dump again (with column headers to make the discussion easier):

AB CD EF GH IJ KL MN OP
-----------------------
c2 a5 c3 90 c2 a7 c2 b5 
c2 b6 c2 ae c3 86 c3 a4
c3 a6 c2 a9 c3 97 c3 a4
c3 b7 c4 b3 c5 92 c4 90
c6 86 c4 b7 c4 97 c4 b2
c5 a6 c5 af c5 b6 c5 ab
c6 82 c6 90 c6 94 c6 86
c5 a6 c6 89 c6 b6 c7 b4
c6 86 c6 85 c6 a6 c6 ac
c7 86 c6 b9 c9 87 ca 83

Looking at the columns, it should have been even more obvious. I’ve already discussed dropping columns A, B, E, F, I, J, M, and N (I came to this conclusion shortly after I originally started the puzzle). But what I didn’t “grok,” but should have, was that I needed to drop columns C, G, K, and O as well. What’s left after that? Column D is either a 2, 5, 6, or 7. Column H is 0, 3, 5, 7, 9, e, or f. Column L: 2, 4, 6, or 7, and finally the last column, P, which is 0, 2, 3, 4, 5, 6, b, or c. So two columns (H and P) with truly random-looking numbers, and two columns (D and L) with 2, 4, 5, 6, or 7. In ASCII, a byte that begins with 4 or 5 is a capital letter, and 6 and 7 denote lowercase letters. Bytes beginning with 2 are punctuation — in this case, the 2 is always paired with a 0, or a space.

Another way to look at this, mathematically, is in terms of bits of entropy. Columns A, E, I, and M have 0 bits, since they never change. Columns B, F, J, and N have 4 bits, since they’re anything between 2 and a. Similarly, columns C, G, K, and O only bring 2 bits to the game (since 8, 9, a, and b are all 10xx in binary, it’s just the last 2 bits that change). And D and L have only 3 bits of entropy (2, 4, 5, 6, and 7 all fit within 0xxx in binary). Finishing it up, we have:

AB CD EF GH IJ KL MN OP
-----------------------
04 23 04 24 04 23 04 24

One can pretty readily see what might’ve been obscured before: That each line has 2 repeated pairs (04 23 04 24). Looking at the UTF-16 version, again, we see that the characters are taken from increasingly higher code pages in the Unicode alphabet…which further strengthens the supposition that columns B, F, J, and N are all meaningless (since they’re largely derived from the Unicode pages as well). So instead we have “00 23 00 24″ or just “23 24″. That’s 11 bits….but we only need 8 bits for letters (or really, 7 bits for ASCII). But wait — the 2s here are also largely driven by the Unicode layout…if we drop those, now our data has “03 04″ bits, or 7 bits total. Just enough to build ASCII data. And sure enough, that’s what it does.

The plaintext wasn’t even encrypted. Just hidden in noise.

I should have walked into their booth first thing Wednesday morning, handed them the solution, and walked away $1000 richer.

To say I was frustrated…well….that doesn’t begin to cover it.

So in the end….was this a good or bad puzzle? As much as it pains me to admit it, this was an excellent puzzle. It made me think about UTF-8 encoding (which many, especially us old dumb-terminal types, overlook in favor of flat ASCII). It had a red herring (the ^ making me think of XOR). It had obvious, blatant signs that should have been seen, at least by experienced cryptographers. Like most good riddles, it had a simple, obvious, easy-to-execute solution. Also like most most good riddles, I felt like a complete idiot for having missed the answer.

Thanks, Fidelis, for reminding me to keep my eye on the basics, and for driving home the first rule of cryptanalysis, as defined by the late Robert Morris: “Check for plaintext.”

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.

About two weeks ago, G. Mark Hardy asked if I was planning to attend CarolinaCon at the end of April. He had a puzzle set to go and was even thinking of using me as a clue. I replied that I wouldn’t be at the con, but would love to see the puzzle. So he sent me a copy.

Here is what he sent me, which was printed on the conference badge:

Unfortunately, I was already busy with another puzzle — THOTCON — and was eyeing a third (the Verizon DBIR). Plus, the Easter weekend was fast approaching. So I didn’t really have the time to hit it full force. But I did eventually solve the puzzle.

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 image above is all that you need to get started.

The cipher text, then, is just this:

OOAI YELL MBOP QXTY EBPL JJHQ KIPW FWAL VPHW OHYC ELJU WQCV CAIL AIJJ
RHNK UCNP JIGY XYJD WNAU LJCY GAIL VSNB WMTH GCLX XPTJ CWQI WRHA
BLCA EQMN XRKM VVQS PJXE OWHE SVGP HTTH EKSA VQKH YCTB MVRV XWNQ
QGPL RACG RLRF EFMW ITFP KHFS TPTZ UUBX XFVB SRSI WHCD JHZB VVUM
AYDY LKBF FEOA NTYF LZWP YWMY MMLG DMFL VIGU WGNA MQBP

Beyond that, there wasn’t much to go on. During the con, G. Mark tweeted a couple of clues trying to focus people on the flag — and to lead them to Google searches on Confederate cryptography. He also tried to help people recognize the kind of cipher it likely was, and those it was not.

Of course I didn’t need any of those hints. Having written an extensive post about a Civil War message, I not only knew what kind of cipher the Confederacy used, I also knew the three keys they used most frequently.

Not wanting to make it too easy on myself, I chose to try a crib first. I guessed the message might start with CONGRATULATIONS, and after three letters, I knew what the key was. But for illustration, here’s a way that one could have tested a crib using an online tool (I already discussed a more manual approach in the Civil War post).

A site I frequently use for crypto tools (and suggested by G. Mark in one of his hints at the con) is Rumkin Cipher tools. Using the Vigenère tool, enter the ciphertext and select “decrypt.” Then, instead of the key, enter the start-of-message crib. In this case, I tried “CONGRAT” (to account for the possibility it was abbreviated). Doing this gives something like this for the start of the plaintext:

key: CONGRAT
MANC HESJ YOIY QERK RVYL QHTD ERPD DINF EPOU AUSL
ESHG JKLV JYUY URJQ PTAE DCUN VVAH XFHP JHJU SHOL

So the first 6 letters represent the key that would spell CONGRAT in the plaintext. Change the key to MANCHES and now we see this:

key: MANCHES
CONG RATZ MOMI MFHY RZIH RXHD IBLE TWNJ OLPK OUWV
ATXU JOVR KOIY YBFR FHAI NYVD JVER TGXD JLTQ TXCL

Now, if this were the whole key, then we’d see words pop out later in the output. There’s “D IBLE” in the first line, but nothing anywhere else. So start adding As to the end of the key, and eventually we find:

key: MANCHESAAAAAAAA
CONG RATL MBOP QXTM EONE FRHQ KIPW FWOL INAS WHYC
ELJU WECI ATET AIJJ RHNK ICAN CEOY XYJD WNAI LWAR

It looks like “OLINAS” on the first line, which must be “CAROLINAS,” so figure out which letters in the key correspond to the WFW just in front of it, and change them to CAR.

key: MANCHESAAAAACAR
CONG RATL MBOP OXCM EONE FRHQ KIPU FFOL INAS WHYC
ELHU FECI ATET AIJJ RFNT ICAN CEOY XYJD UNJI LWAR

The three characters in question are now UFF, so that’s the next key fragment. Replace CAR with UFF and look for another place to stretch the key out:

key: MANCHESAAAAAUFF
CONG RATL MBOP WSOM EONE FRHQ KIPC AROL INAS WHYC
ELPP RECI ATET AIJJ RNIF ICAN CEOY XYJD CIVI LWAR

We’re definitely on the right track, as line 2 now includes “CIVIL WAR.” In the second line is “IF ICAN CE,” which is probably SIGNIFICANCE. Do the same trick: replace the end of the AAA with SIG, see the corresponding plaintext letters change to RBL, and change the letters in the key from SIG to RBL, and now we see:

key: MANCHESAARBLUFF
CONG RATL MKNE WSOM EONE FRHQ THEC AROL INAS WHYL
DAPP RECI ATET AISI GNIF ICAN CEOY XHIS CIVI LWAR

Let’s reformat to maybe make it easier to find the missing words:

CONGRAT LM KNEW SOMEONE FJHQ THE CAROLINAS OHYLD
APPRECIATE LAI SIGNIFICANCE GYXHIS CIVI LWAR

We still have two letters left to guess in the key, and there’s a two-letter bit in the first line that looks like it should be “SI.” Insert SI into the key, retrieve “TE” from the plaintext, put those in place of SI, and bingo:

key: MANCHESTER BLUFF

CONGRATS I KNEW SOMEONE FROM THE CAROLINAS WOULD
APPRECIATE THE SIGNIFICANCE OF THIS CIVIL WAR
CIPHER CH RHHH TAET FWPS BLWD RFHN ZEYI LMVM MXFH
JVDQ IFFL KFGT YQBD HGRA ASZW EPZN TXHB ZTKR FDJZ
PVVG MOCT PENN LBVV XZAK YHSQ MLBG QDAM DAQP SEQB
SPJZ SGOH QQIM NWWU TRXO ETUV IHYS JSSX FSVX BSGB
RMSJ OEOB SPMP SLWD

And bingo! We’re — wait, what? Dammit.

At this point, I was stumped for a while. For one: do I use the “decrypted” output of the first stage? One other G. Mark puzzle worked that way, so it seemed reasonable. Plus, that would make the second stage dependent upon solving the first. Or, should I just find the original cipertext that corresponds to what didn’t decrypt and use that?

In the end, I tried both avenues with a variety of approaches. I tried the other two commonly-used Confederate keys, ruled out Playfair and simple Caesar shifts, and just tried lots of different keys. I also tried dragging a crib back and forth. This is essentially the same as what I described above, but I try the word (“THE” is what I tried) against every position in the ciphertext, and hope that I’ll see an obvious 3-letter sequencde pop out. None of these met with any success.

I was sure this was a Vigenère, based on the historical connection, so I kept plugging away. In addition to crib dragging, I tried various other tests to help guess a key size, and even started noodling with some new techniques of my own devising. But no luck. (Though I did learn a lot more about Civil War cryptography in the process.)

After a few days not getting far, I regrouped and tried simplifying (per G. Mark’s inevitable admonition that I’m making it too complicated.) Looking at the remaining text, I decide to try an “offset” key. Basically, I took COMPLETE VICTORY and just started rolling letters off the beginning and onto the end. When I hit TORYCOMPLETEVIC I found success.

UNFORTUNATELY BAD CRYPTO MAY HAVE LED TO THE DEFEAT OF LEE IN THE WAR OF
NORTHERN AGGRESSION BUT YOU CAN MAKE UP FOR IT

But even that didn’t get everything. There’s still a block of cipher text at the end. Of course, now I know what to do. I simply put the entire original cipher text into the online applet and use each of the three Confederate keys in sequence. The first decoded the first block, when replaced with the second it decoded a chunk in the middle, and when I replaced it with COME RETRIBUTION the last message was decrypted:

TO CLAIM THE PRIZE FOR SOLVING THIS YOU MUST TELL G MARK THIS WHOLE TEXT
BY THE END OF THE CON

In the end, a very simple, almost trivial, solution. Especially since all the keys were available in the Wikipedia article on Vigenère. But mashing all three texts together the way he did totally ruined my attempts at traditional cryptanalysis. If I’d known there were three parts to the puzzle, I might’ve figured out the trick earlier. Maybe. Now I’m just trying to figure out if there’s an easy way to “discover” such partitions in the cipher text or if you just have to guess or stumble upon them.

But this was all before the con even happened. Once it started, I periodically checked Twitter to see if anyone was working the puzzle, and if so, whether they were making any progress. Early on, I saw a couple of people post links to the image, or to a pastebin copy of just the text, but not much beyond that. One person did suggest “POTOMAC RIVER,” probably as a possible key, as the battle flag originally came from the Confederate Army of the Potomac.

Finally, late on Sunday, I started to see a few people make progress. Then about 3:45, a tweet from Korotos to G. Mark said, simply, “Solved.” So congratulations to Korotos!

Knowing the secret, being “on the inside,” was an interesting change for me. It was a different challenge having to keep my mouth shut….and I’m glad I did. Both because to say anything would’ve been wrong (it’s not my game, after all!), but also because the few times I did think about what to say, I realized hours later that I would have given away too much. There’s an art to giving hints that are Just Good Enough…

So speaking of hints, what ever happened to the bit about using me as a hint? About midday Sunday, G. Mark tweeted this:

Hint: on CTF network was file named “.notthis”; contents were: a8979e8b df88908a 939bdfbb 9e8d8b97 dfb18a93 93df9b90 c0ff

The file name was a hint as to how to decode the hint: logically invert (or NOT) all the bits. Or, XOR with 0xFF, which is functionally the same. Doing this reveals the hint he’d warned me he might use:

What would Darth Null do?

I don’t know if anyone ever decoded the hint. I do know that nobody viewed my Civil War blogpost during the entire con, so if anyone did decode it, they didn’t take the next step. Of course, the first key was right there in my blog…and even without the hint, a Google search for “G. Mark confederate crypto puzzle” lists my blog as the first hint — proving that sometimes, the direct attack actually is the best choice.

In 2009, the Verizon Business Risk Team released their first public Data Breach Investigations Report. I saw it reasonably soon after release, and noticed a whole bunch of binary numbers in the background on the cover. “Cool,” I thought, but I didn’t bother trying to decode it. A week or so later, I learned that there’d been a contest, and I missed out.

In 2010, I was ready, and tried to solve the puzzle, but failed. That story comes later.

But now, on the eve of the release of the 2011 DBIR, I’m finally documenting the method needed to solve these puzzles. Here’s a quick, fresh look at the 2009 puzzle.

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. If you’d like a copy of just the raw data (in this case, two ciphertexts), click here.

So, I vaguely remembered how this worked. And also that it was a very simple puzzle. Let’s see how quickly I can solve it, without digging too deep into my memory for what needed to get done. First, I pulled down the original PDF. And there, all over the background of the cover, is a whole bunch of binary numbers. Highlight, copy, and paste out into a file.

First, how do we break up the numbers? 8-bits? 7-bits? I removed the line breaks, counted, and divided by 8, but didn’t get an even number of bytes. Found some text in the middle, removed that. Now count again — ah, beter. Looks like it’s 900 8-bit characters.

Next up — a simple script to decode the binary. Doesn’t take more than a few minutes, and now I’ve got a big block of ciphertext.

EVNTXIGYIMWSNEHEIEFOTXBSCWYHRQMWGUZABVYCBBFREYFBVEDKEVMFRIFN
GFNRBFGVKSFPNBUFZJGCEEEWAKHPXEBTZJCZOWGTBSQGTMIAYDPYDRIRYETK
CJRPYHEPWKUOAEKNVTVZHSMZNTTIVIKMMRYSNUIAKBRKQMSTYCGCCRLRRIIR
EFGYTJUBUXHEYSGLEYRVHIYXDEYZCJKVTOSOIXJEHOXEVMWJBNZMTKWZEFOF
CNBWNCUWMYFIUVBKWNPWTYOEYQTIRRYRCMNVFVLRSBNTPWPAOCZPEKHLFCEE
RRVWVUYBVJPUVPOAYMIKQQNSWZGHZKDGYLAEGWPKESGCYZFVJDMEPQKSSLNV
SVPUVVRVYERHDTUTYYMQGEVWRMQSZFNPNRJIGGWAJNNJLKOEQHNETRPUQYDF
ZWCZKVJEXLMCKCSIFTCTSUTLDRRMIKQTNINPGRPQQXPTZDPAIOTCEUAZFEWD
QLLPZRHXLXQGSLRJTBLZRIRVISNZIWLMVYADVOHFEVNAKKGORRXSYGXPUMVG
BOMRJLCREFCMRQVXTMIYMJJVHXNBTSZMTJEFKFGKURFLNHXPKCWLEXMIYLGY
NNRWAKSEWTHPKGZKKXGAZELLUTAYCIEKWISHUNDKEKWARGBYZFGKEPKQGZZS
RIMFLGKARTURAINSNGEEUMEXRVEELZXTISUWVZKOYLTPBHZWEOQWNXNPXPKS
SXJHPANCVFPRYADRLROEWEBQEWHZRGATZDGUCEKLFYHZJNNZIJRGNZRVBOCA
UYEZGKPSJXJIASMVFTDWFXBIDHQZEYKDRTDRIOPPKJRPISSKMCZJFZTBVBJU
GEYANJIGJTDCPTZDEOGUTLZPEKHTNIHTGGUMVGBOMRJLCREFSWFZOCROHEAU

Okay, what kind of encryption did they use? A quick test of ROT-13 and such doesn’t get me anywhere. It’s awfully long, so I really don’t want to try a substitution cipher if I can avoid it. Then I remember that there was a clue somewhere in the report. Skimming through, I found a footnote on page 48:

yr puvsser vaqrpuvssenoyr

Let’s run that through ROT-13, and sure enough, we get a hint:

le chiffre indechiffrable

Aha! That’s French. And one of the most commonly found ciphers, it seems, for hacker crypto challenges was created by a Frenchman. And I also know, because of how often I’ve run against this cipher, that he called it “le chiffre indechiffrable” (or the indecipherable cipher). So which cipher it is has been decided: it’s a Vigènere.

But how long is the key? I found an online applet that would do a Kasiski analysis, which looks for repeated trigraphs in the cipher and measures the distance between them. If you can find a common factor amongst a bunch of repeated trigraph distances, that could very well be the key length. I found 10 repeated trigraphs, but their distances are all over the map, and I can’t see anything that’s a clear common factor.

Next up, the index of coincidence, which is a way of looking at the ciphertext in varying keylengths to see which one seems to have “slices” that are the most internally consistent. That’s a simplification. Truth is, I don’t understand it much beyond a zen-like vagueness, so I’m not going to try to explain it here.

Anyway, the IC applet makes 9 characters look like a good potential key length, though it’s far from certain. But at least one of the Kasiski distances was 72, which is a multiple of 9, and so this is as good a place to start as any.

Next up, I stick the ciphertext into a nice interactive Vigenere applet, set it to a 9-character key, and start sliding the alphabets around to see if anything pops out. Not having anywhere better to start, I make a guess that the plaintext starts with “CONGRATULATIONS.” As I adjust the various alphabets to make this happen, the key starts to appear. C-H-A-N-G-I-N-E. Hm. So close. Let’s change it to CHANGING…and now it’s looking a lot more real. Here’s the beginning of the plaintext:

CONGRATSGFWFHWUYGXFBNPOMAPYULIZQENZNVNLWZUFEYQSVTXDXYNZZPBFA
AXALZYGIEKSJLUUSTBTWCXEJUCUJVXBGTBPTMPGGVKDARFINSVCSBKIESWGE
ACRCSZRJUDUBUWXHTMVMBKZTLMTVPAXGKKYFHMVUIURXKEFNWVGPWJYLPBIE
YXTSRCUOOPUYWLGYYQEPFBYKXWLTACKINGFIGQJRBGKYTFWWVFMGRDWMYXBZ

Except that this is the only plaintext I see. If it were a 9-character key, then a key of “CHANGINGA” would at least give me 8 characters of real text, repeated down the length of the output, with a junk character in between each. At this point, I could think back, remember that the key was actually present in the text, find the two instances of “changing” in the report and have the puzzle solved in less than 30 minutes total. But that’d be cheating. So let’s try something new.

It’s looking pretty likely that the key starts with “CHANGING.” But I don’t know how many characters come next. I didn’t see a repeat at 8 or 9 characters, so let’s add another A, and another, and another, until I see things repeat. Once I get to 26 characters it happens. Now I’ve got plaintext that starts like this:

CONGRATSIMWSNEHEIEFOTXBSCW
WARDGOTOZABVYCBBFREYFBVEDK
COMSLASHGFNRBFGVKSFPNBUFZJ
EVERYONEHPXEBTZJCZOWGTBSQG
RFINSVCSDRIRYETKCJRPYHEPWK
SHAREFINVZHSMZNTTIVIKMMRYS
LNINETEEQMSTYCGCCRLRRIIREF

So now, let’s start changing the letters after CHANGING and see what happens. A is no good, neither is B, nor C, but D — that seems to extend the cleartext words properly. In fact, the ZZZ after GOTO are probably supposed to be WWW. To make that happen, my key now starts with “CHANGING DEF”, which gives me this:

CONGRATSFIRSNEHEIEFOTXBSCW
WARDGOTOWWWVYCBBFREYFBVEDK
COMSLASHDBIRBFGVKSFPNBUFZJ
EVERYONEELSEBTZJCZOWGTBSQG
RFINSVCSANDRYETKCJRPYHEPWK
SHAREFINSVCSMZNTTIVIKMMRYS
LNINETEENINTYCGCCRLRRIIREF

From here, it’s a pretty easy job to finish out the key this way. The result is “Changing default credentials.” (it also appears in the report as “Changing default credentials is key.” Is. Key. Heh. Funny.) The final plaintext tells where to write with your solution, and the rest is a terse, high-level summary of the entire report. Here it is with spaces and newlines entered for clarity.

CONGRATS
FIRST TO CRACK GETS REWARD
GO TO WWW VERIZONBUSINESS COM SLASH DBIRHUNT TO CLAIM
FOR EVERYONE ELSE HIGH LVL STATS FOR FIN SVCS AND RETAIL FOLLOW

PLS SHARE

FIN SVCS
SOURCES EXTERNAL NINETEEN INTERNAL NINE PARTNER TWO
THREATS MALWARE ELEVEN HACKING FIFTEEN DECEIT FOUR MISUSE SIX PHYSICAL TWO ERROR ONE
ERROR SIG CONTRIBUTOR IN FIFTEEN
TOP THREE HACK TYPES SQL INJECTION SEVEN MISCONFIG ACLS SEVEN DEFAULT CREDS TWO
TOP HACK VECTOR IS WEB APP
TEN TOP ASSET IS ONLINE DATA TWENTY SIX AND
ALL RECORDS TOP THREE DATA TYPES AUTH CRED ELEVEN PII TEN PYMNT CARD EIGHT
PYMNT CARD WAS NINETY EIGHT PCT OF RECORDS
TOP UU IS UNKNOWN CONNECTIONS SEVEN
DISCOVERY TAKES WEEKS TO MONTHS

RETAIL SOURCES
EXTERNAL TWENTY THREE INTERNAL ONE PARTNER EIGHT
THREATS MALWARE TEN HACKING TWENTY ONE DECEIT TWO MISUSE TWO PHYSICAL ZERO ERROR ZERO
ERROR SIG CONTRIBUTOR IN SIXTEEN
TOP TWO HACK TYPES SQL INJECTION SEVEN STOLEN CREDS SEVEN
TOP HACK VECTOR IS REM ACCMGT EIGHT
TOP ASSET IS POS ELEVEN AND
OVER HALF OF RECORDS TOP TWO DATA TYPES PAYCARD TWENTY THREE PII NINE
DISCOVERY TAKES MOSTLY MONTHS

My memory was correct in one respect — this was a very simple puzzle. Even the long approach I took, once I’d figured it out, went fast. If I’d received this puzzle new, today, I’m sure I would have solved it in an evening, tops. Two years ago, I almost certainly wouldn’t have been so lucky. For one, the trick of padding out the potential key to look for repeats isn’t something that’d ever occurred to me before, that I can recall, though it’s pretty obvious in retrospect. I’ll definitely have to remember this technique for future puzzles.

Also, having “CONGRATS” as the opening word gave me a really easy crib. Without that, I honestly don’t know where I’d have started.

So though I was right, this was a simple puzzle, I was wrong in another key respect: That its simplicity would mean it wasn’t going to be any fun, especially (subconciously at least) knowing what I needed to do. Learning a new approach to break this cipher was fantastic fun. And proof that even the easy puzzles shouldn’t be ignored.

Thanks to the whole Verizon crew for this one. The 2010 puzzle was a different story, but that’ll wait until later. Hopefully I’ll write that up before next week’s new puzzle starts sucking up all my free time…

Ah, ShmooCon 2011. This time we’re in a new building, The Washington Hilton, and a little earlier than usual: the last weekend of January. But aside from that, it’s still ShmooCon. And it wouldn’t be a ShmooCon without something fun on the badges. For the third year in a row, the puzzle came from the subtle and devious mind of G. Mark Hardy.

This time, I was actually helping out at the con. I’d been a little concerned about whether I’d be able to fairly compete for the puzzle, since I might get exposed to the badges, or programs, or other material, before anyone else is. Heidi did her best to ensure that I didn’t learn anything unfairly — to the point that the Wednesday before the con, when I was helping with some of the check-in code and at the bag stuffing party, she repeatedly told everyone that “David’s not allowed to see inside the programs!” She’s so helpful.

Though I have to admit, it was certainly frustrating being surrounded by 1500 copies of the puzzle, and not being able to do anything about it.

Adding to the stress was the fact that I’d won (or shared winning) this contest in 2009 and 2010. The fact that this drive to keep winning was purely internal didn’t make it less real. And being somewhat not-100%, physically (more on that later) certainly didn’t help. More than once I’d wished I’d simply opted out of the contest at the beginning.

So anyway, the con started, I got my badge, my buddies got theirs, and we were off!

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. If you’d like a copy of just the raw data (ciphertexts and other clues revealed during the contest), click here.

Pretty quickly we decided that there were probably five badges total: one for staff, one for speakers, and three for attendees. Each badge was made to look like a school hall pass, and had fields for the “student”‘s name, the reason they were issued the hall pass, and the teacher who issued it. The names were all amusing, but didn’t really pertain — the important parts were the lines the names were written on. Two of the lines weren’t really lines, but were finely drawn Morse code.

Being hungry, we went off to lunch and, while waiting, decoded all five badges. We ended up with this (first line is hall pass reason, second line is the authorization, right column is the decoded text):

Badge Text	Morse Code	Badge Type
A Room With a Moose	2 YESTERDAY	Attendee
Mr. Shmoo	3 TELEGRAPH
F5 Fingers	0 MOGADISHU	Attendee
Anon E. Moose	1 ARMADILLO
I Haz Barcodes	4 HYPNOTIST	Attendee
Bullwinkle	5 EUCALYPTI
Lost Voice on Alcan	8 ORANGE CAB	Speaker
A Noony Moose	9 STIMULATE
Yearly Migration	6 MICROBREW	Staff/Security
Dr. Doc Doctor, MD	7 OBJECTIVE

It seemed pretty obvious that they needed to be put in numerical order. This gave us:

0 MOGADISHU
1 ARMADILLO
2 YESTERDAY
3 TELEGRAPH
4 HYPNOTIST
5 EUCALYPTI
6 MICROBREW
7 OBJECTIVE
8 ORANGECAB
9 STIMULATE

Almost immediately we noticed “MAY THE MOOSE BE WITH YOU” read down the first column and up the last. So, that’s one part done. What other parts were there to the puzzle?

On the bottom of several pages were individual letters in a large font. Taken together, these spelled out:

RJWUD TKOOA EGPAD CRLUS

Obviously some ciphertext. I tried basic attacks (various Caesar shifts, “obvioius” Vigenère keys, etc.) but didn’t get anywhere.

On page 6 of the program was some base-64 data. I quickly entered that into an online tool and decided it was binary data, likely encrypted output from OpenSSL, and therefore almost certainly not part of G. Mark’s puzzle.

Page 12 had a section titled “Crypto Contest” with the following block of text:

CRYPTOCONTEST
MWHFGYBBXQBJA
OXIHADLIDWXVW
OUXGHIPCSAPHI
SZHWHPGMAXGNI
EYTKNSIYMJPJD

This one I just left alone for the time being. On page 27, we found a word search game:

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

It didn’t take long for us to start finding words and names in the square. Popping out at us were SAVE, HI MOM, EXHIBIT, DECIMAL, and NOT HERE. Also the names G MARK, WINN, GOD MINUS ON(e), and amusingly enough, DARTH NULL. Also, SECRET CODE. And some others. How many of the words we found were deliberate, and how many were accidents of the encoding? That wasn’t a purely academic question, as we figured that whatever letters were left over (not part of words) would themselves constitute a ciphertext.

Finally, the back of the schedule card had the following:

  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A B C D 
A S H M O O C O N A B D E F G I J K L P Q R T U V W X Y Z L 
B H M O O C O N A B D E F G I J K L P Q R T U V W X Y Z S E 
C M O O C O N A B D E F G I J K L P Q R T U V W X Y Z S H S 
D O O C O N A B D E F G I J K L P Q R T U V W X Y Z S H M S 
E O C O N A B D E F G I J K L P Q R T U V W X Y Z S H M O M 
F C O N A B D E F G I J K L P Q R T U V W X Y Z S H M O O O 
G O N A B D E F G I J K L P Q R T U V W X Y Z S H M O O C O 
H N A B D E F G I J K L P Q R T U V W X Y Z S H M O O C O S 
I A B D E F G I J K L P Q R T U V W X Y Z S H M O O C O N E 
J B D E F G I J K L P Q R T U V W X Y Z S H M O O C O N A T 
K D E F G I J K L P Q R T U V W X Y Z S H M O O C O N A B H 
L E F G I J K L P Q R T U V W X Y Z S H M O O C O N A B D A 
M F G I J K L P Q R T U V W X Y Z S H M O O C O N A B D E N 
N G I J K L P Q R T U V W X Y Z S H M O O C O N A B D E F E 
O I J K L P Q R T U V W X Y Z S H M O O C O N A B D E F G V 
P J K L P Q R T U V W X Y Z S H M O O C O N A B D E F G I E 
Q K L P Q R T U V W X Y Z S H M O O C O N A B D E F G I J R 
R L P Q R T U V W X Y Z S H M O O C O N A B D E F G I J K G 
S P Q R T U V W X Y Z S H M O O C O N A B D E F G I J K L M 
T Q R T U V W X Y Z S H M O O C O N A B D E F G I J K L P A 
U R T U V W X Y Z S H M O O C O N A B D E F G I J K L P Q R 
V T U V W X Y Z S H M O O C O N A B D E F G I J K L P Q R K 
W U V W X Y Z S H M O O C O N A B D E F G I J K L P Q R T M 
X V W X Y Z S H M O O C O N A B D E F G I J K L P Q R T U M 
Y X Y Z S H M O O C O N A B D E F G I J K L P Q R T U V W X 
Z Y Z S H M O O C O N A B D E F G I J K L P Q R T U V W X I 
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A B C D 

"Thanks to Gary Phillips for providing the Jim Sanborn font"

The little attribution was clearly to help people unfamilar with the image to narrow their google search a little bit. Jim Sanborn is the artist who created a sculpture at CIA Headquarters called Kryptos. Half of the sculpture is ciphertext, the other half is a keyed Vigenère tableau. The image on the schedule card was likewise a keyed Vigenère, though not properly constructed. I figured this would be used to decode the last part of the puzzle, and didn’t think much more of it. (There’s also a little easter egg in the rightmost column. “LESS MOOSE THAN EVER GMARK MMXI”).

So by now, we’re done with lunch, and have found a place to sit for the opening ceremonies. I didn’t really play too much with the puzzle then, but near the end, I started again. I first tried some of the usual suspects against the code on page 12 (Vigenère, mostly), but didn’t see anything pop out at me. Then I looked a little more closely at it.

The first row “CRYPTOCONTEST” was obviously just a header. What I didn’t notice right away was that the first column also spells something. MOOSE. I had a hunch, tried it, and was quickly rewarded. The key for each of the five rows is the first letter in that row. That is, the first row (after the header) starts with the M in MOOSE, so that row is a Caeser cipher shifted by M (or, in this particular case, what’s commonly called ROT-13). The next two rows were shifted by 15 letters (O), etc. So, about 4:00 on Friday, I’d decoded it:

JUST LOOK DOWN
ITS LOW TO HIGH
FIRST AND LAST
GO DOWN THEN UP
TO FIND THE KEY

This was to be the last progress I made for nearly 24 hours. And even this wasn’t much progress, since we’d already “looked down” (at the badges) and found the key (“MAY THE MOOSE BE WITH YOU.”)

On the other hand, now I know what I’m supposed to do with that phrase. And now that I’m thinking about it, the key has 20 letters, and the text on the bottom of the pages has 20 letters. Woohoo! Let’s just add one to the other, and….er…nothing. Okay, subtract. Subtract the other way? Start with 1 instead of 0? No? Shoot. After about 20 minutes, I give up (plus, the room was getting warm) so we get up to stretch our legs. I played with it a little more during the Keynote, but again, got nowhere.

After the con closed down for the evening, and we’d made (and changed and changed again) reservations for dinner, I ran into G. Mark. I told him a little about what we’d done so far, and mostly tried to get a feel for whether we had the right approach on the word search bit. Naturally, I didn’t get much help.

The next morning, when I woke up, I had a bit of a medical scare. See, I’d slipped on ice a little over a week before and banged my right knee pretty badly. It was still a little swollen, but I was making do. Well, when I got out of bed, I saw huge bruises all over my foot — which hadn’t been injured at all when I fell. Naturally, this Freaked Me Out. I ended up spending most of the morning going to, being at, and returning from, the local urgent care clinic. Fortunately, I checked out fine — the diagnosis was that invisible bruises got exacerbated by all the walking at the con, and also that extended use of Motrin and Alleve made the bruising appear much worse. Relieved, I returned to the con, and to the talks.

I kept playing with the codes, off and on, over the afternoon, but made no progress. In the meantime, G. Mark tweeted a few hints, but they don’t help me much. At 3:51, he tweets that “The tools you received in the challenge will work best without unauthorized modificaions.” What the hell is that supposed to mean? Tools? I can’t think straight, and decide to go upstairs to take a quick nap. On the way to the elevator, I get another tweet from G. Mark: “Serious breakthrough for one of the teams! Competition get hot or eat thier bits!” Great, so now I’m tired, AND bummed out.

Once in my room, I pull out the swag bag and begin going through it. I try opening all the pens, to see if perhaps there’s a clue hidden inside something, but have no luck. Then I look at the schedule card. I look at the tableau on the back. The one that was made incorrectly. I shake my head and quietly muter “No. No, you didn’t.” And then I start copying the tableau onto the computer so it’ll be easier to trace out (the font he used didn’t really line up into nice columns).

Basically, this kind of Vigenère tableau uses a different base alphabet. In the traditional cipher, the key simply switches among different Caesar shifts for each letter in the plaintext. A keyed tableau mixes up the alphabet itself, making it even harder to break. Of course, even in a keyed alphabet, the alphabet can only have 26 letters. It CERTAINLY can’t have the letter O appear three times, as it did in this table. I’d tried using a keyed Vigenère with the “MAY THE MOOSE BE WITH YOU” key many times, with many variants, but got nowhere, because I was always constructing the keyed alphabet correctly.

Here’s what G. Mark’s alphabet looks like:

SHMOOCONABDEFGIJKLPQRTUVWXYZ

and here’s what it should have looked like:

SHMOCNABDEFGIJKLPQRTUVWXYZ

Those extra Os mess everything up. But how bad does it really make it? Well, let’s take the table, and the key we got from the badges, and start decoding. First, take the first letter of the key “M” and find the row that starts with M. Then, I go over to the first letter of the ciphertext “R” and straight up to the header row to find the letter “I.” This is the first letter of the plaintext.

The next key letter is A, with ciphertext J, looking straight up I get P. So now I’ve got “IP.” I keep at this for a while, and eventually turn the ciphertext (top) into plaintext (bottom):

RJWUD TKOOA EGPAD CRLUS

IPADD RE??S HMOOC ONVII

Only two letters, both of which are key letter O paired with cipher letter O, are ambiguous. Each could be R, S, or U. It’s pretty easy to see what the right decryption is just by looking at the context. So the letters at the bottom of the page decrypt to:

IP ADDRESS SHMOOCON VII.

Woohoo! Finally! Progress! Now I just need to open a browser…and…er…hm.

Okay, maybe it’s telling me to get the ip address for the shmoocon.org site and surf to that by IP, not by name. This will almost certainly give me different data that way. But then what do I do with the VII? Also, since I’ve been helping out with the ticket sales system, I know a little bit about how the ShmooCon server is configured. And one bit of knowledge worries me — the address on the webserver itself is not the same as the address that browsers go to, because there’s a load balancer in between the server and the world. So I’m wondering — did they account for this when they set it up?

I sent a note to G. Mark mentioning I had a concern, and went back down to the conference. Not long after getting there, he walks by, and we talk for a bit. Not to worry, he tells me, everything is working fine. Cool. He asks me what parts I have left, and I told him the only piece of the puzzle I haven’t used is the word search, and talk again about how to get a ciphertext out of the puzzle by eliminating words, etc. He looks at me and tells me “back off.” I’m not sure if this means “back off asking questions, I won’t tell you anything” or “back off from that approach, it’s wrong.” Either way, I know that’s where I need to go next, so I run over to the Intrepidus Group table and pull out the program.

But how am I supposed to get an IP address out of the puzzle, using “SHMOOCON VII” as the key? S appears in the first column twice, and also once in column 2. There are 3 Hs in column number 4, and it appears twice in column 3. Maybe it’s the column with the most of each letter? No, there are 2 Ms in both columns 6 and 9. Maybe the total number of occurrences of each letter? That probably wouldn’t work either, ’cause then you’d have 3 digits forced to the same number, which seems unlikely.

After a little while, I remember that the table has 11 rows, which had struck me as a little odd, not for any particular reason, but just that there must be a reason for 11 rows. This little bit of trivia had been completely forgotten until this moment. “SHMOOCON VII” has 11 letters. One letter per row?

Let’s see… There is only one S in the first row, and it’s under column 0. Hm. One H in the second row, under 3. Only one M in the third row, and it’s beginning to look like I’m on to something, though the number still seems weird. In the end, I get this:

03448155389

Heh. Tricky. IP addresses are just big 32-bit numbers, but we typically split them into four 1-byte blocks for easy readability. For human convenience. However, many applications don’t care and can take a single big number just as easily as a dotted-quad address. However, I’m not 100% sure about the iPhone browser. And when I try entering that number, sure enough, it doesn’t work. So I convert it to hex and get CD86ACFD. Converting each pair of digits to decimal, I get 205, 134, 172, and 253. So the address I need to surf to is:

http://205.134.172.253/

Now I’m getting excited. I get back a simple web page, with the title “Well done!”, and the following text:

Good things come in threes.
Add this to the other plaintexts.
Tell that person you solved it.

KVATY DBKZA BZICB USYWO

Cool. Okay. So…there are 20 characters there, and I’ve got two other 20 character strings. So I need to get this plaintext and add them all together. Again, I try the usual suspects, and get nowhere. Then I stop and think for a moment. And realize that I’m being an idiot. Of course I can’t take three English strings, add them together, and get English again. (I mean, maybe, but it’d be tough to arrange). I need to add the new ciphertext to the two plaintexts. Basically:

MAYTH EMOOS EBEWI THYOU
IPADD RESSS HMOOC ONVII
KVATY DBKZA BZICB USYWO

Now there are a few different ways you can “add” letters together. First, you can simply number them starting with 1 (so A + A = B, because 1 + 1 = 2). Or you can number them starting at zero (so A + A = A, A + B = B, but B + B = C). The latter is actually an easy way to implement the Vigenère cipher, and since I’ve have some favorite tools to do that online, that’s what I do — enter the first string as the key, and the second string as the plaintext, hit encrypt, and I get the “sum” of the strings. Do it again with that sum as the key and the 3rd string as plaintext, and I get:

EKYPI YRQFK MMAML BMRSQ

Damn. Nothing. Well, let’s assume that it’s been encoded itself, again trying the standby Vigenère, and I’ll use GMARK as the key. Now I get:

YYYYY SFQOA GAAVB VARBG

Oooh! Oooh! That’s important! That pretty much tells me that the string starts with GMARK. So instead of GMARK as the key, I just enter “Y”, and out pops:

GMARK ATSHM OOCON DOTUS

It turns out if I’d used the other way to add, it would have been a lot easier – the “shift by Y” decode kind of undoes the offsets I’d introduced using what was supposed to be a shortcut. If you number M as the 13th letter, I as the 9th, and K as the 11th, you get 13+9+11 = 33. Subtract 26, and you get 7. The 7th letter is G. Similarly, 1 (A) + 16 (P) + 22 (V) = 39, 39 – 26 = 13 (M). And so forth. So, once again, I apparently took the long way around.

Anyway, the instructions said to “tell that person you solved it,” so I quickly sent an email to gmark at shmoocon.us. I also sent him a direct message saying “Check your .us email account.” This was at 6:21 on Saturday. At 6:28, I got a response saying I’d won, and two minutes later he announced it to the world on Twitter.

Whew! My winning streak is safe!

At the closing ceremonies, G. Mark again explained the puzzle and how it worked, which is always great fun. For one, it verified that I’d taken the wrong approach for the final plaintext addition step. It’s also great to see the responses of the crowd as things are revealed. What was really priceless for me, though, was hearing groans and “Not again!” comments from people around me as my name was announced as the winner.

I’m still amazed by my ability to overcomplicate matters, even after solving so many of G. Mark’s puzzles. In this case, I spent a good deal of time trying to determine which words were “real” in the word search puzzle, trying to build a ciphertext out of the puzzle, when really, literally 90% of the letters in that block were fluff.

Also, I’d interpreted the Vigenère table as a hint, telling me what technique to use at some critical stage of the game. In fact, it was not really a hint, so much as the actual method and half the key. G. Mark has made mistakes in his puzzles before, but those mistakes are almost always very minor and had no real impact on solving the puzzle. In this case, I tacitly assumed that the tableau was wrong, and it was wrong simply because he was having fun. What I should have assumed was that it was right, and to use it exactly as provided. Had I really thought more clearly about all that, I might’ve solved the puzzle 24 hours earlier.

In the end, though, it was another great puzzle. I was glad to see him follow somewhat the pattern he took with ToorCon, where each stage tells you where to go next and hints at the method and key to use. It wasn’t quite exactly like that, but you could see some similarities. And it’s also great that there was a stage that wasn’t pure classical cryptography, and a stage that was classical crypto, but with an unexpected twist. Being forced to think outside of the box is the best feature of any puzzle, and once again, I was not disappointed.