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:

CarolinaCon Flag

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 CIVIL WAR

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.

(view Archived Comments from the old site)