Darth Null

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.