Last weekend, the Associated Press published a story about a Confederate Army message that was recently decrypted. It had been written on a small sheet of paper, rolled up tightly and placed in a glass vial with a bullet (probably so it could be sunk into a river in the event of imminent capture). The vial sat in The Museum of The Confederacy for years, until it was unrolled early in 2009. The article didn’t say when the message was decoded — presumably it sat untouched for a while and they only just sent it out to the experts (one at the CIA, one at the Navy).
I’d been celebrating Christmas, so I didn’t see the story until G. Mark Hardy emailed it and challenged me to “extract the key.” The first thing I had to do was to get the ciphertext, which, natrually, wasn’t included in the story. A little digging got me some low-resolution photos, and I could get most of the ciphertext out of those, but it wasn’t great. Also, it was hard to avoid seeing the plaintext (which was in all the articles I found).
However, I think I can demonstrate breaking this code without any knowledge of the plaintext. Also, keep in mind that knowing more about the context of the message (who sent it, who it was sent to, the words and phrases frequently used in such messages, etc.) would have provided an actual wartime cryptanalyst a lot more leverage than I had.
After a couple days spent ignoring the challenge, I mentioned the story to my brother. He’s also a bit of a computer geek (but more into web technology and other such things), and is also a history buff. He actually once discovered a hitherto-unknown example of Lincoln’s signature while working at the National Archives. So I figured he’d enjoy this story, and within 5 minutes, he located a high-resolution copy of the ciphertext. So now that I could actually distinguish letters from inkblots, I set to work.
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 ciphertext (as written, plus a “cleaned up” copy, and one with no word breaks for a different challenge), click here.
The first thing I noticed was that the writer of the message preserved word breaks. That seems, to me, a huge mistake, as now I can use those breaks to help guide my attack. For example, near the end of the message, I see four singleton letters — in plain English, those would either be “I” or “A”, though in something like this there’s always the chance they’re abbreviations, initials, cardinal directions, etc. But I’d bet at least one of them is “I.”
Also, I notice that 3 of the 4 singletons are encrypted with different ciphertext, which makes me think that this is a polyalphabetic cipher. The Vigenère cipher was used frequently in the Civil War, so I’ll start with that. I first have to figure out what the key length is.
In the first line is a four-letter word that’s repeated — this either means the same four-letter word is repeated in the plaintext and we have a 4-character key (which seems possible, but unlikely) or a key with a 4-letter repeat (which seems even more unlikely), or it was an astounding coincidence (with appropriate likelihood), or it was an error in transcription and shouldn’t have been repeated (I’ll go with that for now).
Dropping the extra word, I now have a ciphertext of 220 characters. The letters “SEA” appear at the very beginning of the message, and again 210 characters later. This might be a hint as to the key length — 210 is probably not the key length itself, but a multiple of the key. So 3, 7, 10, 21, 30….all possible key lengths. Also, the singleton M letters are 30 characters apart, so I’ll assume for now that the key is 30 characters long.
The first thing I’ll do is work on my assumption that the singletons are all the letter I. Changing the last one (J) to I means the key letter for that position will be “B.” I’ll repeat that key backwards and forwards, at 30-character intervals, and decode the plaintext appropriately. Interestingly, one of the other singletons fell on an interval, and now it’s decoded to A. I’m pretty confident now that I’ve at least got that key letter correct. Trying the other ones (the Ms), and here’s what I have (the first row is the ciphertext, the next is the key stream, and the last is the plaintext):
SEAN WIEUIIUZH DTG CNP LBNXGK OZ BJQB FEQT XZBW JJOA TK FHR TP b e b T X I ZWK PBW RYSQ VOWPZXQQ OEPH EK WASFKIPW PLVO JKZ HMN NVAEUD XY e b e V O L F DWRJ BOYPA SF MLV FYYRDE LVPL MFYSIU XY FQEO NPK M OBPC FYXJF b e b e E O T I HOHT AS ETOV B OCAJOSVQU M ZTZV TPIY DAW FQTI WTTJ J DQGOAIA FL b e b A I I WHTXTI QMTR SEA LVLFLXFO e b S N
Not a lot to go with, but there’s a two-letter word in the 3rd line that’s half decrypted. Not too many two-letter words start with O, but the likely candidates are OF, ON, and OR. Let’s try each. First, OF:
SEAN WIEUIIUZH DTG CNP LBNXGK OZ BJQB FEQT XZBW JJOA TK FHR TP b ea b T XN I ZWK PBW RYSQ VOWPZXQQ OEPH EK WASFKIPW PLVO JKZ HMN NVAEUD XY ea b ea VW O LW F DWRJ BOYPA SF MLV FYYRDE LVPL MFYSIU XY FQEO NPK M OBPC FYXJF b ea b e a E OF T I O HOHT AS ETOV B OCAJOSVQU M ZTZV TPIY DAW FQTI WTTJ J DQGOAIA FL b e a b A I Z I WHTXTI QMTR SEA LVLFLXFO ea b SH N
Hm. That gives me XN, VW, and LW digraphs, and a word starting with Z. Not entirely impossible, but seems harder to work with. Let’s try ON next:
SEAN WIEUIIUZH DTG CNP LBNXGK OZ BJQB FEQT XZBW JJOA TK FHR TP b es b T XV I ZWK PBW RYSQ VOWPZXQQ OEPH EK WASFKIPW PLVO JKZ HMN NVAEUD XY es b es VE O LE F DWRJ BOYPA SF MLV FYYRDE LVPL MFYSIU XY FQEO NPK M OBPC FYXJF b es b e s E ON T I W HOHT AS ETOV B OCAJOSVQU M ZTZV TPIY DAW FQTI WTTJ J DQGOAIA FL b e s b A I H I WHTXTI QMTR SEA LVLFLXFO es b SP N
That looks much better. There’s still one pair that looks troublesome (XV in the first line), but transcription errors are not uncommon for a coded message written in the field, and one bad digraph is much better than three. So I’ll let it stand for now. But there’s still not much else to go on, as very few letters have been decoded at this point. Since I’ve got nothing else to work with, let’s try shortening the key. Trying a key length of 15 (half 30, but still fitting the intervals I’m working with), I get:
SEAN WIEUIIUZH DTG CNP LBNXGK OZ BJQB FEQT XZBW JJOA TK FHR TP es b es b es b EM T XV N TH I ZWK PBW RYSQ VOWPZXQQ OEPH EK WASFKIPW PLVO JKZ HMN NVAEUD XY es b es b es b es VE V TY O LE N AC F DWRJ BOYPA SF MLV FYYRDE LVPL MFYSIU XY FQEO NPK M OBPC FYXJF b es b es b e s b E ON E IN T I W E HOHT AS ETOV B OCAJOSVQU M ZTZV TPIY DAW FQTI WTTJ J DQGOAIA FL e s b e s b e s b O M A I H S E E I WHTXTI QMTR SEA LVLFLXFO es b es b SP H HN N
Several more plausible letters now pop out. In the second-to-last line is another two-letter word, this time ending with O. Best guess: it’s TO.
SEAN WIEUIIUZH DTG CNP LBNXGK OZ BJQB FEQT XZBW JJOA TK FHR TP hes b hes b h es b h PEM T EXV N M TH I I ZWK PBW RYSQ VOWPZXQQ OEPH EK WASFKIPW PLVO JKZ HMN NVAEUD XY es b hes b hes b hes VE V STY O BLE N TAC F DWRJ BOYPA SF MLV FYYRDE LVPL MFYSIU XY FQEO NPK M OBPC FYXJF b h es b h es b h e s b E T ON E E IN T D I W E HOHT AS ETOV B OCAJOSVQU M ZTZV TPIY DAW FQTI WTTJ J DQGOAIA FL he s b h e s b he s b h TO M A N I H S ME E I E WHTXTI QMTR SEA LVLFLXFO es b hes b SP H OHN N
If I knew the key players in the war, this would be all over now, as a General’s name is now popping out. But I don’t know that, so I have to keep working. That last change didn’t make anything terribly messy, so let’s keep trying. In the first line is a four-letter word starting with TH. Good candidates include THAN, THEM, THIS, THEY, and others. For brevity, let’s just look at one wrong answer (THEM):
SEAN WIEUIIUZH DTG CNP LBNXGK OZ BJQB FEQT XZBW JJOA TK FHR TP hesxk b hesxk b h esxk b h PEMXY T EXVAW N M THEM I I ZWK PBW RYSQ VOWPZXQQ OEPH EK WASFKIPW PLVO JKZ HMN NVAEUD XY esx k b hesx k b hes xk b hesx k VEN F V STYT E O BLE SB N TACG N F DWRJ BOYPA SF MLV FYYRDE LVPL MFYSIU XY FQEO NPK M OBPC FYXJF b h es xk b h esxk b h e sxk b E T ON PB E E INBI T D I WEF E HOHT AS ETOV B OCAJOSVQU M ZTZV TPIY DAW FQTI WTTJ J DQGOAIA FL he sxk b h e sxk b he sxk b h TO MWE A N I HWP S ME EWJ I E WHTXTI QMTR SEA LVLFLXFO esxk b hesxk b SPWN H OHNON N
Looks worse. Now, let’s try THIS:
SEAN WIEUIIUZH DTG CNP LBNXGK OZ BJQB FEQT XZBW JJOA TK FHR TP heste b heste b h este b h PEMBE T EXVEC N M THIS I I ZWK PBW RYSQ VOWPZXQQ OEPH EK WASFKIPW PLVO JKZ HMN NVAEUD XY est e b hest e b hes te b hest e VER L V STYX K O BLE WH N TACK T F DWRJ BOYPA SF MLV FYYRDE LVPL MFYSIU XY FQEO NPK M OBPC FYXJF b h es te b h este b h e ste b E T ON TH E E INFO T D I WIL E HOHT AS ETOV B OCAJOSVQU M ZTZV TPIY DAW FQTI WTTJ J DQGOAIA FL he ste b h e ste b he ste b h TO MAK A N I HAV S ME EAP I E WHTXTI QMTR SEA LVLFLXFO este b heste b SPAT H OHNST N
Much better. I bet that’s “RIVER” straddling the first and second lines (LIVER just doesn’t seem likely), “TACK” could be part of “ATTACK,” “TO MAK? A” is probably “TO MAKE A”, etc. I’ll try a few of those (and, in fact, fixing RIVER changed TACK to TTACK, which just strenghens my guess):
SEAN WIEUIIUZH DTG CNP LBNXGK OZ BJQB FEQT XZBW JJOA TK FHR TP nc hesterb nc hester b nch este rb n ch NL PEMBERT AN EXVECT N ROM THIS SI E RI ZWK PBW RYSQ VOWPZXQQ OEPH EK WASFKIPW PLVO JKZ HMN NVAEUD XY est erb nchest erb nches terb nchest er VER LKV JNSTYX KNO SIBLE WHEN ATTACK TH F DWRJ BOYPA SF MLV FYYRDE LVPL MFYSIU XY FQEO NPK M OBPC FYXJF b nch es ter b nch esterb nch e ster b E LNT ON THE E INE INFORT AND I WILL E HOHT AS ETOV B OCAJOSVQU M ZTZV TPIY DAW FQTI WTTJ J DQGOAIA FL nc he ster b nch e ster b nche ster b n ch UR TO MAKE A ION I HAVE S SOME EAPS I N DE WHTXTI QMTR SEA LVLFLXFO esterb n chesterb SPATCH N JOHNSTON
Wow. Now it’s just filling in the blanks. And the key is pretty clear, too, or at least would be if I knew much about Civil War history, which I don’t. But it looks like my assumption about the XV being an error is borne out — looks like it’s supposed to be EXPECT. I’ll change the ?AN before EXPECT to CAN, N? to NO, ?ROM to FROM, ???SIBLE to POSSIBLE, and see what happens:
SEAN WIEUIIUZH DTG CNP LBNXGK OZ BJQB FEQT XZBW JJOA TK FHR TP manc hesterbl hm anc hester bl hm anch este rbl h man ch GENL PEMBERTO MU CAN EXVECT NO JP FROM THIS SID D THE RI ZWK PBW RYSQ VOWPZXQQ OEPH EK WASFKIPW PLVO JKZ HMN NVAEUD XY est erb l h manchest erbl hmanches terb l hma nchest er VER LKV G J JOJNSTYX KNOW POSSIBLE WHEN Y AAN ATTACK TH F DWRJ BOYPA SF MLV FYYRDE LVPL MFYSIU XY FQEO NPK M OBPC FYXJF b l h manch es ter bl hm anch esterb l hma nch e ster bl h E S C POLNT ON THE EN WS LINE INFORT M JSO AND I WILL EN Y HOHT AS ETOV B OCAJOSVQU M ZTZV TPIY DAW FQTI WTTJ J DQGOAIA FL manc he ster b l hmanch e ster bl hma nche ster b l hman ch VOUR TO MAKE A D CCSION I HAVE SE WOW SOME EAPS I S HOIN DE WHTXTI QMTR SEA LVLFLXFO esterb l h man chesterb SPATCH F K GEN JOHNSTON
Pretty much legible now. Though there are several obvious errors. The only thing that I can work with is the word straddling lines 3 and four — might it be ENDEAVOUR?
SEAN WIEUIIUZH DTG CNP LBNXGK OZ BJQB FEQT XZBW JJOA TK FHR TP manc hesterblu fhm anc hester bl ufhm anch este rblu fh man ch GENL PEMBERTON YMU CAN EXVECT NO HEJP FROM THIS SIDG OD THE RI ZWK PBW RYSQ VOWPZXQQ OEPH EK WASFKIPW PLVO JKZ HMN NVAEUD XY est erb lufh manchest erbl uf hmanches terb luf hma nchest er VER LKV GENJ JOJNSTYX KNOW KF POSSIBLE WHEN YQU AAN ATTACK TH F DWRJ BOYPA SF MLV FYYRDE LVPL MFYSIU XY FQEO NPK M OBPC FYXJF b lufh manch es ter blufhm anch esterb lu fhma nch e ster blufh E SCMC POLNT ON THE ENEMWS LINE INFORT ME AJSO AND I WILL ENDEY HOHT AS ETOV B OCAJOSVQU M ZTZV TPIY DAW FQTI WTTJ J DQGOAIA FL manc he ster b lufhmanch e ster bluf hma nche ster b lufhman ch VOUR TO MAKE A DIVCCSION I HAVE SEOT WOW SOME EAPS I SWBHOIN DE WHTXTI QMTR SEA LVLFLXFO esterb lufh man chesterb SPATCH FSOK GEN JOHNSTON
That filled in all the rest, but, again, there are lots of errors. YMU, HEJP, SIDG, OD, all in the first line. Three of those have errors under the same key letter, and that key position continues to look wrong through the rest of the message. Looking at the key, I can guess what it’s supposed to have been. Changing it from “MANCHESTER BLUFH” to “MANCHESTER BLUFF”, I now have:
SEAN WIEUIIUZH DTG CNP LBNXGK OZ BJQB FEQT XZBW JJOA TK FHR TP manc hesterblu ffm anc hester bl uffm anch este rblu ff man ch GENL PEMBERTON YOU CAN EXVECT NO HELP FROM THIS SIDG OF THE RI ZWK PBW RYSQ VOWPZXQQ OEPH EK WASFKIPW PLVO JKZ HMN NVAEUD XY est erb luff manchest erbl uf fmanches terb luf fma nchest er VER LKV GENL JOJNSTYX KNOW KF ROSSIBLE WHEN YQU CAN ATTACK TH F DWRJ BOYPA SF MLV FYYRDE LVPL MFYSIU XY FQEO NPK M OBPC FYXJF b luff manch es ter bluffm anch esterb lu ffma nch e ster bluff E SCME POLNT ON THE ENEMYS LINE INFORT ME ALSO AND I WILL ENDEA HOHT AS ETOV B OCAJOSVQU M ZTZV TPIY DAW FQTI WTTJ J DQGOAIA FL manc he ster b luffmanch e ster bluf fma nche ster b luffman ch VOUR TO MAKE A DIVECSION I HAVE SEOT YOW SOME EAPS I SWBJOIN DE WHTXTI QMTR SEA LVLFLXFO esterb luff man chesterb SPATCH FSOM GEN JOHNSTON
And that’s about it. Of the remaining errors, several seem to be confusing U with W, which might even be a consequence of the transcriber’s writing style. Others are simple off-by-one errors in encoding. If I completely clean it up, here’s what we get:
SEAN WIEUIIUZH DTG CNP LBHXGK OZ BJQB FEQT XZBW JJOY TK FHR TP manc hesterblu ffm anc hester bl uffm anch este rblu ff man ch GENL PEMBERTON YOU CAN EXPECT NO HELP FROM THIS SIDE OF THE RI ZWK PVU RYSQ VOUPZXGG OEPH CK UASFKIPW PLVO JIZ HMN NVAEUD XY est erb luff manchest erbl uf fmanches terb luf fma nchest er VER LET GENL JOHNSTON KNOW IF POSSIBLE WHEN YOU CAN ATTACK TH F DURJ BOVPA SF MLV FYYRDE LVPL MFYSIN XY FQEO NPK M OBPC FYXJF b luff manch es ter bluffm anch esterb lu ffma nch e ster bluff E SAME POINT ON THE ENEMYS LINE INFORM ME ALSO AND I WILL ENDEA HOHT AS ETOV B OCAJDSVQU M ZTZV TPHY DAU FQTI UTTJ J DOGOAIA FL manc he ster b luffmanch e ster bluf fma nche ster b luffman ch VOUR TO MAKE A DIVERSION I HAVE SENT YOU SOME CAPS I SUBJOIN DE WHTXTI QLTR SEA LVLFLXFO esterb luff man chesterb SPATCH FROM GEN JOHNSTON
Or, looking just at the plaintext:
GENL PEMBERTON YOU CAN EXPECT NO HELP FROM THIS SIDE
OF THE RIVER LET GENL JOHNSTON KNOW IF POSSIBLE WHEN
YOU CAN ATTACK THE SAME POINT ON THE ENEMYS LINE
INFORM ME ALSO AND I WILL ENDEAVOUR TO MAKE A DIVERSION
I HAVE SENT YOU SOME CAPS I SUBJOIN DESPATCH FROM
Total time to break the message (using, obviously, modern tools): negligible (it took me longer to write the interactive tool I used than to actually break the code). Could a professional cryptanlyst have cracked this by hand, 147 years ago? Almost certainly.
As I said before, knowing more about the context of the message would definitely have provided quite a bit more leverage. Knowing the names of key generals would have helped with three of the longer words in the message. Knowing who messages important enough to be encoded were generally sent to might’ve helped, too (if that would lead one to guess that the message was more likely to open with “GENL:” as opposed to “DEAR SIR:”). And, certainly, knowing that you’d cracked dozens of previous messages with the key “MANCHESTER BLUFF” would have meant this would have been broken just minutes after receipt. Three very strong strikes against the message right there.
But even without any of that knowledge, I was able to break it, and I’m just a beginner at this. I really think it was the word breaks that did it for me. If those hadn’t been there, there’d have been nothing I could do — nowhere to start, and almost all of my analysis (like the two- and four-letter word guesses) wouldn’t have been possible. I suppose I would have looked for a history of similar messages, to see what the message might have started with, and gone from there. What would that have gained me?
SEANW IEUII UZHDT GCNPL BHXGK OZBJQ BFEQT XZBWJ JOYTK FHRTP manc manc manc manc GENL UCAN PFRO THER ZWKPV URYSQ VOUPZ XGGOE PHCKU ASFKI PWPLV OJIZH MNNVA EUDXY manc manc manc JOHN OSSI ANAT FDURJ BOVPA SFMLV FYYRD ELVPL MFYSI NXYFQ EONPK MOBPC FYXJF manc manc manc POIN SLIN SOAN HOHTA SETOV BOCAJ DSVQU MZTZV TPHYD AUFQT IUTTJ JDOGO AIAFL manc manc manc manc VOUR RSIO OUSO OIND WHTXT IQLTR SEALV LFLXF O manc GENJ
Adding the T in POINT makes OSSI into OSSIB, which isn’t too hard to read as POSSIBLE:
SEANW IEUII UZHDT GCNPL BHXGK OZBJQ BFEQT XZBWJ JOYTK FHRTP manch es f manch es f manch es f manch GENLP EM O UCANE XP L PFROM TH F THERI ZWKPV URYSQ VOUPZ XGGOE PHCKU ASFKI PWPLV OJIZH MNNVA EUDXY es f manch es f manch es f manch es VE L JOHNS TO P OSSIB LE C ANATT AC FDURJ BOVPA SFMLV FYYRD ELVPL MFYSI NXYFQ EONPK MOBPC FYXJF f manch es f manch es f manch es f E POINT ON Y SLINE IN L SOAND IW A HOHTA SETOV BOCAJ DSVQU MZTZV TPHYD AUFQT IUTTJ JDOGO AIAFL manch es f manch es f manch es f manch VOURT OM E RSION IH Y OUSOM EC J OINDE WHTXT IQLTR SEALV LFLXF O es f manch es SP M GENJO HN
And now it’s all over. Finish out ATTACK, make a couple of other educated guesses, and the message is complete. So even without word breaks, it’s possible, but it’s only easy if you’ve got a good crib (the “GENL” at the beginning). Although I probably wouldn’t have been able to do it, honestly (just based on my own experience with this cipher type).
The ease with which I broke this makes me wonder if any of the Confederacy’s coded messages were safe from the North. Especially considering they used the same key over and over again. What would have helped them? I can think of three important rules right off the bat (all of which apply even today):
- Don’t provide any context to the attacker. Remove all word breaks and present the message as short blocks of text.
- Don’t reward the attacker for good guesses. Ensure the message doesn’t start with a predictable word.
- Don’t use the same key day after day after day.
How could they have accomplished that last recommendation? When G. Mark first challenged me to “extract the key,” I predictably jumped to an overly complex solution. Getting “the key” is simple, if you know the plaintext (which is in the articles) and the ciphertext (which is in the pictures). So perhaps the key for this message is just a secondary key, and there’s a larger master key I need to recover, and that’s what G. Mark was asking for?
Obviously, that’s not the case here, but it did make me think about how you could at least change the key daily. Take a long phrase, say for example, the Confederate Motto “With God our Vindicator.” Encrypt that phrase with the date of the message (“JULY FOUR”), and you get “FCEF LCX FDL GGSRCTJNZP”. Use that as the key for the message. If you change up the secondary key (maybe on odd days it’s “month day” and on even days it’s “day month”, and change the phrase periodically (every 6 months or so), then you’ve got a pretty good key schedule, for its time, at least. And every bit of it is easily memorized and applied, even in the field, so there are no codebooks to get lost.
On the other hand, I don’t know what the codebreaking skills of either side were like in the Civil War — it’s possible that nobody even gave these codes a second glance, and even simple ROT-13 messages would have been secure. But somehow, I doubt that. I guess it’s time to break out my copy of The Codebreakers and refresh my knowledge of crypto history….
Some time ago, I started wondering why I couldn’t find any Rainbow Tables for old-school Unix crypt(3) passwords. After some research, I learned that the salt was the culprit — that virtually anyone who’d asked about such tables went away chastised, told that the salt made it impossible to generate Rainbow Tables, unless you went through the trouble to create 4096 different tables (one for each salt). And who’s going to do that?
Somehow, that just didn’t sit right with me, and it wasn’t long before I decided that the conventional wisdom was wrong, and that there would be an easier way to build crypt(3) tables. But I didn’t really do anything with it for a long time, until I finally decided to try, once and for all, to see if I was right. And it turns out — I was right. Changing the standard rainbowcrack programs to support crypt(3) password hashes was trivial. In only one evening, I had something (more or less) working, and a couple of nights later, it was able to actually read, write, and process crypt(3) hashes in their native form (as opposed to a flat hexadecimal dump of the hash).
“Wow! This is cool,” I thought. “I should totally submit this for a security con.” Which I did. But I didn’t get accepted.
So what do I do now? Do I sit on my findings and resubmit, again and again, until a conference accepts it? Or should I just admit that maybe it’s not quite as cool as I think, and maybe it won’t get accepted ever? (As cool as I think it is, it’s certainly possible that it’s not that cool, or that perhaps someone else has already done this and I’ve just not found the code yet — and I’m okay with that.)
It seems silly to just keep this in my back pocket for the sole purpose of getting up in front of a room full of people to talk about it. So rather than hiding it away, I decided to turn it into a more detailed paper, and post it.
So I’ve now posted it to my company’s website. All the crazy details are there, including 50-some-odd lines of proof-of-concept code that need to be inserted into the linux rainbow table crack source. It’s not entirely turnkey (you’ll have to work some to get it compiled yourself), but then again the tables aren’t built, either, so it’s not like you could just make the changes and start cracking passwords. It’s also verly likely far from optimal.
I’m hoping that Rainbow Table experts can see what I’ve written and roll it back into some canonical, actively maintained source tree, and that people can start building and using tables for crypt(3).
Before you go running to read the paper (if you haven’t already noticed, I’m a little long-winded, and the paper is 12+ pages long), here’s a quick preview:
- Instead of generating 4096 tables of 1-8 character passwords, just create 1 table of 3-10 character passwords, and use the 1st two characters of the plaintext passwords as the salt. (That part will make more sense if you read the paper.)
- It’s still kind of slow: 9x slower than LM hashes, for example. But CPUs are much faster than they were in 2003, when people first started building tables for LM hashes.
- It also takes a lot of storage. But storage, likewise, is much cheaper than it was seven years ago.
- So, in the end, I think it may be worth the effort, finally.
Why would anyone care? Well, even though crypt(3) hash technology is something like 35 years old, it still shows up from time to time. It’s a simple, well-understood, and almost universally-supported format. So it’s tempting when building systems to just use crypt(3) and forget about it.
That’s apparently what happened with Gawker Media, who had over 1 million emails and password hashes leaked last week, most of which were crypt(3) based.
So anyway, it’s a fun little hack, and I’m hoping people can run with it.
You can read my corporate blog-post, with the paper linked at the end, right here.
UPDATE – I presented my original slides (with appropriate updates) at the Northern Virginia Hackers Association (NoVAHA) in April. You can download those slides here.
In the middle of October, G. Mark Hardy emailed to ask if I or my puzzle-busting buddy would be making it to ToorCon, in San Diego, as he had a puzzle on which he was putting the finishing touches. I told him no, but that I’d love to play along at home for “bragging rights instead of prizes.”
The weekend of the conference I was actually at a cousin’s wedding. So I didn’t expect to have much time to play. However, I did bring along some gear, and spent some time Friday night and Saturday afternoon playing with the little information that had leaked out from the Con.
In particular, someone tweeted a very good picture of the badge. Unfortunately I forget who it was, and the picture isn’t showing up in a search any longer. But it was a great picture, and immediately got me thinking.
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.
The times listed all around the perimeter of the badge really grabbed my attention right at the beginning. G. Mark was giving the keynote at the con, entitled “Pwning Time,” and so this was clearly part of the puzzle. He’s also had a history of using different symobologies in past puzzles — Naval signal flags at QuahogCon, and Morse Code and barcodes at ShmooCon. And knowing that he’s a retired Navy Captain — well, I almost immediately decided the times had to be Naval Semaphore code.
Unfortunately, a closer inspection showed that this would be problematic. Nearly half of the codes had the same “hour,” which seemed really unlikely for just about any simple substituion cipher. I played with the times for a while, trying all kinds of crazy sequences, counting tricks, etc., but just couldn’t get anything useful out of it. As it turns out, those were part of a totally different contest, and not even related to G. Mark’s puzzle.
About that time I also received word that there were multiple stages, requiring more than just the badge picture. The conference program apparently had several clues, and also a T-Shirt had some kind of ciphertext. So there was absolutely nothing I could do right away….which was good, since it was time to go to the wedding.
Of course, I still had my phone with me, and it buzzed multiple times that night and the next day with hints and information from @g_mark (all times given in Eastern, as that’s where I was):
10/23/2010 18:00 TOORCON crypto puzzle first hint – Start on the edge!
10/23/2010 20:33 TOORCON – I’ve asked if they would post images of badge, t-shirt, and program to website. Remember – start on the edge … But of what? 😉
10/24/2010 13:40 TOORCON – Each crypto clue contains a riddle, a pointer to the next clue, and the encryption key. Follow the chain to the final answer.
10/24/2010 17:22 Your TOORCON badge is not a clock if you want to check the time. Could a clock face tell more than time? Could it send a signal?
10/24/2010 18:15 TOORCON if you have trouble getting started, .-.. — — -.- ..-. — .-. -.-. — -.. .
Interesting. So even in the middle of the afternoon on the last day of the con, he’s still giving pretty early hints. I wonder how many people were playing… And that definitely leaves the field wide open for me to snatch victory! 🙂 Also, one of those clues (clock sending a signal) certainly reinforced my thoughts about semaphores.
Late Sunday night, I got some additional information from G. Mark, including a not-for-redistribution copy of the program and the text from the back of the con t-shirt (THANKS!!). So I sort of started my “official” clock at 11:00 that night. Not long after, I saw a final tweet:
10/24/2010 23:13 TOORCON thanks to players who purchased clues and raised $172 for Toorcon foundation. Farthest progress = stage 5 of 6. Thanks for pla …
So people could BUY clues? Hm. New wrinkle. And still nobody solved it, although some people came close (though I wasn’t sure if this meant the farthest people were “at” stage 5, or had “solved” stage 5).
Anyway, I’m now looking through the program, and seeing clocks on nearly every page. With a different time displayed on each clock. And they’re analog clocks. So the hands really do look like semaphores. Always nice when a gut feeling turns out to be right.
However, his first hint said to “start at the edge,” and another tweet (in Morse code) said “LOOK FOR CODE.” So I pull myself away from the clocks and find some Morse code printed right on the edge of the last page (the dots were about cut in half — it bled right off the edge).
.-.. — — -.- .- – – …. . – .. — . -….- .. – .—-. … .—- …– — .—-. -.-. .-.. — -.-. -.-
Ah, that’s more like it. Pretty quickly I decoded “LOOK AT THE TIME” and moved on to the next phase, the clocks. Later, G. Mark mentioned something about “13 O’Clock” having confused some people, which in itself confused me — I had no idea what he was talking about. Then I realized — while reading the code, zoomed in on an iPad, I’d only seen (and decoded) the top half. I’d missed a whole half of the clue! The 2nd half was a hint that the text from the clocks was ROT-13 encrypted, which I’d sort of guessed automatically anyway. The full text from the Morse code was:
LOOK AT THE TIME – IT’S 13 O’CLOCK.
But I digress. The clocks, finally getting to try my semaphore idea. Using the Wikipedia page as a key, I converted the clock faces to text.
PURPXL SBEFVK BFRXRL SSASGR
which, ROT-13 decoded, gave me:
CHECKY FURSIX USEKEY FFNFTE
Obviously, there was something wrong, and I eventually decided that it
was supposed to be:
CHECK YOUR SIX USE KEY OF NOTE
Apparently a few of the clocks got messed up when the program graphics were created. “Check your six” is military jargon. Six being short for 6 o’clock, which basically means behind or back. So “Check your six” is telling me to check my back. Back of the T-Shirt. So now I need the T-Shirt code, and use a key that’s somehow related to the keynote address. Here’s the ciphertext:
U FIDO YFAENY ETZVR
MT JZKQD FP RUGYD
YA UJO EAUI CQULC
DU SAZX OZSZQNF
OW DNQ BRMQ OOMOX
IHVX EAU KBE
KOL GOXL USYOOMOX
ZEN CKORVDY EHFGKP
TYOXQ SFYT IICV HQ
IW IUG DVMUPE
NSZT KVI UR C
But what’s the key? It should be related to the Keynote, somehow. So I tried several words — KEYNOTE, TIME, PWNING, PWNINGTIME, GMARK, etc., and got nowhere. I also tried more direct attacks using online Vigenère apps, but also got nowhere. Because of a transcription error of my own, even after correcting the result of the clock phase I also got stuck down another blind alley for a bit. Finally, the next morning, I again tried the old standby — “GMARK.” Only instead of being a shift to Z as he’s used in the past (using Z as a space), it was a classicial Vigenère cipher. I know I tried that before, but must’ve messed something up. The result was:
O TIME STANDS STILL
AT SPEED OF LIGHT
SO USE YOUR SKILL
TO GAIN INSIGHT
OF THE BACK COVER
WHEN YOU TRY
YOU WILL DISCOVER
NEW SECRETS SHOWED
THERE SOON WILL BE
IF YOU DECODE
WITH KEY OF C
Now I’m getting somewhere. The inside back cover of the program had a big ciphertext string.
OCRUG HUCOW OUUGO WJZAN JYEQD KGHFO YSNNX RLARZ XTXOE CUPAL OMTXL GAXZQ IAEKN TPVJH MNBTI YSWTB IOVCS KUKZH NHSQA PYFMZ KOAQZ CHGJU OHUPV XBORZ AGZFD WHIJV WJDUB SEYON UQMYX FDOPS RUFGC DNBUU MCHVD WTIVG ZUCSJ HCCUB NEAVE CBXSL IHZMX NQHBV IKDJK VDDXK VEDSU CEJLN RMEAM VHXWC ESQLP RNGBS DPRII ESBXR BXNZX AIGPR BEOWX SOLTG FTFUN GEZMA MFCNG L INCVI STYAL OVEMN SFXRW UEVJT VCGJA HSEMD ALPBF RONLO LWMAN AXWVE WRLDT EZKNB UANAP GNHWA IWWBE BFTDJ OKCDX RYWTO QSBYO OFEYS BIPNU XISXY WRDTI PJBMW OBRBW NCGVS AOBTZ LJBQT VSCBV PJHEP LMLRV UXSHO MZTWO CPVOG SIHSL KVPCR YHPLD MOPOJ WWCNJ NFTWO RQOWP HKAOZ IQDFA RBXFB VKXTK CPKQO YQIBU PZXSO LUWWC AZHGB RLPCZ FPVEL HVQDH LQJTE DUNUX MRIRL PKJUB ESGAF CBAOF ZOZJY RSYYY IMLRC KDNSF KJVKA WTFNE UFZGS PMXYJ VLKTH WCJNJ VZLSH IAWKV TQAYE TQFYH KJMHP ISGTL BQRIS OYYLA XXFLI GHTCC OVXNZ DULNO MKEXT SHLIY LCVVO TIUIB KSBMF XLYTE BAQLB UOMIK IFWGV SXAOV WZOZY NOVOM UQMMF RFTLZ VH NPFAY KYCMT XUSWT ZAYVW TSTWC PAHPS TRSFV EBHKR WQWAD DZDSG DNXLK UEBHY DNDZR KNUVX RBQPD WRNBI DAWRB PYVSL QRYQX AF
I played with this for a while, trying all kinds of things. Obviously, the speed of light (represented in scientific notation by a capital C) must play into it somehow (unless he’s going for a musical key), so variations of “two nine nine…” and “one eight six…” (speed of light in meters/second and miles/second) are tried without success. I also numbered the alphabet from 0 (or from 1) to convert the speed to cjjhjcefi, etc. The previous page in the program included a list of people to whom the conference was expressing gratitude — including Kernighan and Ritchie. Hm. K&R are the “fathers” of the C programming language. But that also got me nowhere. I even tried cribbing text — basically, assuming that the sequence “GMARK” will show up somewhere, and brute-forcing solutions that make that happen. If it works in one place, then I try that key fragment elsewhere to see if other words pop out, and if so, that means I’ll have part of the key figured out. It’s a classical attack, that I’ve never tried before, but it was totally useless here. Damn.
However, I’m convinced that there’s a polyalphabetic cipher at play here, and not a columnar transposition (though “Key of C” also made me check out at least a few columnar attacks, what with the word column starting with C). As a possible variant of that, I even tried sliding rows and columns back and forth based on the digits in C (kind of like his ShmooCon 2009 puzzle). Ultimately, though, none of these worked. And because the frequency distribution of the letters is very flat, it really almost has to be a polyalphabetic cipher.
Finally, after about a day of running a bunch of crazy attacks, and even some drawn-out brute force and dictionary attacks, I put it aside.
Then late on the 28th (or early the 29th, I forget), G. Mark pokes me with a sharp stick, surprised that I hadn’t made any more progress. So I pull the ciphertext out again and keep trying. He confirmed for me that the frequency distribution is “designed to be very flat.” Then he asks me what I think the key is. “299792458,” I respond (the speed of light in meters / second). That’s the right key, he tells me. Now how do I use that? Don’t change it at all, “Use it AS IS,” I’m told. Less than 10 minutes later, I was writing “c…o..n…g…r…” on a post it, and reached for the computer.
Start with the key “299792458.” Begin at the beginning of the ciphertext. Go to the 2nd character, in this case, “C,” and write that down. Then go over 9 characters (“rughucowO”) and write down “O.” Then over another 9 (uugowjzaN). “N.” Over 7 (G). Over 9 (R). And so forth. Here’s the final plaintext:
CONGRATULATIONS YOU HAVE FOUND THE HIDDEN MESSAGE ONE LAST CHALLENGE FOR YOU TO SOLVE LOOK DOWN WHAT YOU ARE HERE FOR IS KEY WHAT THIS LOOKS LIKE IS YOUR PASSPHRASE HURRY X
I wasn’t quite sure how to handle it when I reached the end of the text and wrapped back to the beginning, and so I played a little with the script to see if there was more — but once you reach the end, that’s it. All the rest of the letters are noise. In fact, G. Mark told me they came from a site using, literally, atmospheric radio noise to generate random letters. Hence the very flat frequency distribution.
What’s next, then? Well, “LOOK DOWN” could mean for you to see your badge. That’s the next ciphertext. He talks about “KEY” and “PASSPHRASE” as two different items, which immediately makes me think about a keyed Vigenère, as used on the Kryptos sculpture. KEY might then be “TOORCON,” or “CONFERENCE,” or “TALKS” or somesuch. But what does “WHAT THIS LOOKS LIKE” refer to? The badge itself? Gear, or sprocket, or clock? Or something else?
Another prod from G. Mark makes me look at the last ciphertext itself (the big block of text). What does that look like? “Good luck googling THAT :)” he says. He also tells me it’ll be an “AHA! Moment” when I get it. So I try to relax and just let the answer come to me.
I think about rows of text…prose…paragraphs. Squinting, I can almost imagine it’s marching soldiers — so I play with rank and file and other such words. Then I set it aside again, knowing this isn’t something I can force. About an hour later, it hits me — the Kryptos sculpture. It’s rows and rows of letters, broken up into four blocks (not visually, but there are four different sections to the puzzle).
Finally, I’ve broken the last code. The ciphertext on the badge:
EJGNE EBKJY LEPNS LFQSO UBSNN TIOAC YQRRL KJNYO CRRGG RLPOO TRRML NSGGY IVRTE PYEC
is a keyed Vigenère cipher, using “TOORCONTWELVE” as the alphabet key, and
“KRYPTOS” as the passphrase. This gives me the following plaintext:
IHIDE WITHT HEMAN WHOST OPPED THEMO TOROF THEWO RLDDI ALMEB YNAME ANDIW ILLAN SWER
Or, reformatted for easier reading:
I hide with the man who stopped the motor of the world. Dial me by name and I will answer.
ARRRGH! Not only is it Atlas Shrugged again, just like the DEFCON 18 puzzle, but it’s also another BLOODY PHONE NUMBER SNIPE HUNT! Grr. I fight with it off and on over the afternoon, thinking of phone numbers based on characters in the story, looking them up in Google, and finding that most of them have either non-existent area codes or (after I tried calling) are disconnected or local businesses.
Later that evening, though, literally as I was putting my oldest child to bed, it hit me. Quite annoyed that I’d missed it earlier that afternoon, I texted the right answer to G. Mark. (At his request, I won’t post it here — he doesn’t want me to keep burning his various Google Voice numbers 🙂 ).
So, went from zero to the big ciphertext in just a few hours (there was sleep in there somewhere), then put it aside for a few days, then once I went back at it had the whole thing solved in another 12 hours. Not bad. Granted, I was getting some helpful hints from G. Mark, but then anyone at TOORCON would’ve had that as well. In fact, it appears that G. Mark was even selling hints for charity at the con. I don’t know what hints he sold (and would be curious to see them), but I imagine the help I received wasn’t significantly different from they got.
To summarize the various stages of the puzzle:
|2||Semaphores||Naval semaphore code||ROT-13|
|4||Back Cover||Multiple Skip||299792458|
|5||Badge||Keyed Vigenère||TOORCONTWELVE / KRYPTOS|
The most intriguing part of this puzzle, for me, was the encipherment of the back cover text. The “multi-skip” cipher (I’ve no idea if there’s a name for this, so I just made that up) was really interesting, especially with the use of the noise to give the overall ciphertext a very flat frequency distribution. That distribution could easily send an attaker into a polyalphabetic rabbit hole, exactly as happened with me.
Another interesting thought I had about this cipher: You could easily fit a second message in the noise, using a different key. Perhaps additionally hidden with ROT-13 or something else, or perhaps simply hiding in plain sight alongside the more “obvious” primary message. (I’ve already searched, and found no additional messages here. Which doesn’t mean there aren’t any, only that I didn’t find one.)
But is there a way to cryptanalyze this? G. Mark himself gave me a suggestion in that respect — he said that if you looked at a histogram “with period 55,” you’d see spikes corresponding to the digits of the key.
Naturally, I had to write a script to do exactly that. Not being entirely sure what the best approach was, I ended up with something that worked like this:
- Select an overall period of repetition (this works out to the sum of all the digits in the key)
- Sort the ciphertext into that many bins
- See if any of those bins contain an odd distribution of characters
Really, it’s just reformatting the text into X columns, and seeing how the distribution of letters looks for any given column.
The theory here is that for any period, you’d get a mix of hidden plaintext characters and the random filler noise, until you hit on exactly the right period, in which case some number of bins (containing only plaintext, but no noise) would have markedly different frequency distributions. Of course, this tool would have to be simple, fast, and the results easy to scan. Something that made me actually look at full-alphabet distribution graphs for each bin for each period tested — well, that simply wouldn’t work. So I came up with a simple scoring method.
Using the frequencies of letters in the English language, I assigned each letter in each bin a score. “A” shows up 8.17% of the time, so any “A” in a bin is worth 8.17 points. “B” shows up 1.49%, so those are worth 1.49 points, and so forth. I add ’em all up for a bin, then divide by the size of the bin, and that gives me the average frequency of the letters in the bin. More or less.
Next, running this script against the ciphertext, I had to figure out what the appropriate threshold would be. Too high a threshold would only show me periods with bins containing only very common letters, and since even the uncommon letters happen occasionally, that wouldn’t work. Too low a threshold and I’d have too many things to look at. Because of the way the cipher worked, I’d at least be able to throw out any potential key where the last bin in the period wasn’t over the threshold (if the period didn’t end with a key-recovered plaintext letter, then that “key” would really have a shorter period, and so it’d be invalid) (it’s hard to describe, just trust me on this, or better, try it yourself.)
So, running the script with the threshold set at 3 (so the average frequency of the letters in each bin is at least 3%), I get the following: [and note that for all these outputs, I only show the first five lines — they go on for hundreds of lines]
4 [1, 1, 1, 1] [4, 3, 4, 3]
5 [1, 1, 1, 1, 1] [4, 4, 3, 3, 4]
6 [1, 1, 1, 1, 1, 1] [3, 3, 4, 3, 4, 3]
7 [1, 1, 1, 1, 1, 1, 1] [3, 3, 3, 4, 3, 4, 4]
8 [1, 1, 1, 1, 1, 1, 1, 1] [4, 3, 4, 4, 3, 3, 4, 3]
Clearly, this isn’t the right cutoff. Virtually every period (the first number on each line) is a candidate. The “keys” generated (the first bracketed sequence, ‘[1, 1, 1, 1, 1]’) are pretty useless. In the case of ‘1 1 1 1 1’ as a key, that’d just be the ciphertext repeated back, in order, with no skipping at all. Have too many 1s and 2s in the key and the solution might be viewable just by looking at the ciphertext and squinting. Finally, the peaks themselves (the second bracketed sequence) don’t look interesting. Increasing the threshold to 4%, we reduce the output somewhat:
11 [2, 1, 2, 4, 2] [4, 4, 4, 4, 5]
14 [1, 2, 2, 2, 2, 2, 2, 1] [4, 4, 4, 4, 4, 5, 4, 4]
15 [1, 1, 3, 1, 1, 5, 3] [4, 4, 5, 4, 4, 4, 4]
20 [1, 1, 1, 2, 6, 1, 3, 2, 2, 1] [4, 4, 4, 4, 4, 4, 4, 4, 4, 4]
21 [1, 1, 2, 2, 3, 2, 1, 1, 1, 7] [4, 4, 4, 4, 4, 5, 4, 4, 4, 4]
But there are still far too many candidate solutions. And, again, the keys and peak frequencies look, well, uninspiring. Finally, putting the threshold at 5% generates something interesting:
55 [2, 9, 9, 7, 9, 2, 4, 5, 8] [5, 8, 6, 5, 5, 5, 6, 6, 6]
56 [7, 10, 16, 3, 3, 12, 2, 2, 1] [5, 5, 5, 5, 5, 5, 5, 5, 5]
67 [12, 8, 3, 2, 6, 17, 13, 1, 1, 4] [5, 5, 5, 5, 6, 6, 5, 5, 5, 5]
77 [11, 2, 12, 4, 2, 7, 4, 2, 5, 11, 17] [5, 5, 5, 5, 5, 6, 5, 5, 5, 5, 6]
79 [3, 6, 2, 4, 4, 5, 1, 13, 20, 4, 1, 2, 14] [5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5]
Almost all the candidates on this run look interesting, at least from looking at the keys. The first candidate, at key period 55, looks really interesting. Over half of its bins meeting the threshold are actually above the threshold — there are 4 5’s, 4 6’s, and even one at 8%. Finally, the key itself should appear familiar — it’s the speed of light in meters/second. Clearly, this is the answer. Adding in a line to decrypt using each candidate key as it’s derived, we see the plaintext jump right out:
Threshold: 5 (with decryption)
55 [2, 9, 9, 7, 9, 2, 4, 5, 8] [5, 8, 6, 5, 5, 5, 6, 6, 6]
56 [7, 10, 16, 3, 3, 12, 2, 2, 1] [5, 5, 5, 5, 5, 5, 5, 5, 5]
67 [12, 8, 3, 2, 6, 17, 13, 1, 1, 4] [5, 5, 5, 5, 6, 6, 5, 5, 5, 5]
77 [11, 2, 12, 4, 2, 7, 4, 2, 5, 11, 17] [5, 5, 5, 5, 5, 6, 5, 5, 5, 5, 6]
79 [3, 6, 2, 4, 4, 5, 1, 13, 20, 4, 1, 2, 14] [5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5]
It almost appears that I’ve developed a pretty simple tool for detecting, and decrypting, occurrences of this nifty multi-skip cipher. Even if it doesn’t always find the answer right off, it might be a good tool to narrow down to a few ideas to test. So how could G. Mark have prevented this kind of attack? The use of atmospheric noise to make a very random set of filler letters seems, at first, to be pure genius. But because the distribution of the noise is totally unlike the distribution of the plaintext, a script made by a crypto-kiddie like me can (theoretically) bust it open.
So here is what I believe to be an “improved” version of the back cover ciphertext:
ECRRT IREYS OASHT TRFWN NHHUE MGYEA ECLOR RAADV CTANH EULAS ORKML KATOE ONNEH TSBHO AHWWI OSBTN OOEYM ASHEH NASRE HYNBT ROVTR OTRAU SHTON RHAUS AHTHK TNFOV SAUTH TEAWO OKSEA FYOCR RUEMT TNEHE YOUID NTACH IACLB HNNNY AWSOE LANRV THODW OAEFE IODVO RDOTT OEOED SAIIN PMIGH ELHON EOARY OTHUS TNABE ASRHY UREUD AEGEY HEHDU TOILU PYGSN YEWEO RTRDO L KHRNM AAEAS HNRRN SSSRS GTANT OCIOI HYHOV ALHNE RIHLE LENKE INEUE UOHOK SEUNO HIAAN GIGIR TWANE RFSRU OSHUO RNMHC AIWYF OELWI UIOTU IASHG SESTE AOROT OGMNO EEYUS TOOST LTOEA VBWYV TSAEN LFGEE FEIAO DEWTO ROHOH YOENC KPEAE ONHYD YOGSD WFORT NYAOA OSEWA HSYFL EPRUA BDHGL SLVTH AFLRU YPEEE TCTEO IUTON AAESH ROHAF WFHEE HENEU GODAE HRGKN OAARH TOVRV EGOAG OTCEF TOSOR RDUTE IKYIS ALRSW KNNSM OSTTE ANSSV STSYN DUNOE WOGVA SAMEH TAOIT TSEIE TUETL NGOHL INFTO TSYNS HFSEN YHRLT KNTSA OSWER TBHNO YKSAK SUNTB LRVOH MVIIH KSTNO YEAWE SLOTR ALYIE OLTSO SUETI SHIDY OORSS UVETT RVFOA NAVPO AYYES TOTTS HGSAE DLISH HSDSR PAHHH EAAYH LRONH AGUOE SVRIS CIAEA HYAYY ELSEU DDHAE UTWRI ESGRM RYLVE DTYLY YXYIR TRATO GRASF CVKSL YUUHG RTEHT ARREE ONEE ARIYS HTNEE AOTFR OENNA AOMON ONOTE TYHUD VXTHD TENAT UVGIO YTAEE SLEDL EKCVE EBLHG HTYOU EHLFO TAETT TNNEO OOSAI EX
In this case, the filler data is random letters taken from the plaintext itself. So the filler has exactly the same frequency distribution as the plaintext. Which means that my silly little cryptanalysis script is rendered completely worthless. Every key generated, for every key length, is simply “1 1 1 1…..” Anyone attacking this new ciphertext will probably get sucked down into a different rabbit hole (this time, a transposition cipher rabbit hole).
Is it really better? I don’t know. It might be, but then again, I’m just a beginner here. I could be missing something important.
Anyway, the bottom line is that this was yet another fun puzzle from G. Mark. I’m glad he was able to share with me the details of the puzzle after the con completed, so that I could have the thrill of solving the challenge. And finding a totally new crypto scheme (and possibly even improving upon it) definitely made this a memorable victory.
Thanks again, G. Mark!
UPDATE: For fun, I tweaked the “improved” back cover ciphertext. Sharp-eyed readers may notice that it’s a little bit longer than the original. There’s now a second message embedded in the noise… I’ll even give you a hint: Counting begins at position 4, not 1 (to avoid crashing into the original hidden text). And the key is in this page’s URL.