Archive

Archive for December, 2010

Breaking a 147-Year-Old Message

December 30, 2010 1 comment

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.”

The whole ciphertext. It's hard to read.

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).

A closer look at the text, the handwriting, the inkblots, etc. Note the erroneously repeated word block on the 1st line.

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
GEN JOHNSTON

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….

Categories: Cryptography

Nails in the Crypt

December 22, 2010 Leave a comment

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.

Categories: Crazy Ideas, Cryptography

ToorCon 12 Badge Puzzle

December 6, 2010 5 comments

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

LFYQ UNJSJQ
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

LOOK INSIDE
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:

Stage Ciphertext Cipher Key
1 Morse Code n/a n/a
2 Semaphores Naval semaphore code ROT-13
3 T-Shirt Vigenère GMARK
4 Back Cover Multiple Skip 299792458
5 Badge Keyed Vigenère TOORCONTWELVE / KRYPTOS
6 Final Riddle n/a n/a

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]

Threshold: 3
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:

Threshold: 4
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:

Threshold: 5
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]
CONGRATULATIONSYOUHAVEFOUNDTHEHIDDENMESSAGEONELASTCHALLENGEFORYOUTO…

56 [7, 10, 16, 3, 3, 12, 2, 2, 1] [5, 5, 5, 5, 5, 5, 5, 5, 5]
UJNRROTLGEBZHAHJOHRJXORHDTIJEIJDLREAEDIRONEMAIOCAEOWANRATODOESBSBTJT…

67 [12, 8, 3, 2, 6, 17, 13, 1, 1, 4] [5, 5, 5, 5, 6, 6, 5, 5, 5, 5]
UNEDYPIAEPTUHHFVIJVUFGNUDEXNQIDRAVSXEOWLANITEANLOAEANWESUXIWRATLSHI…

77 [11, 2, 12, 4, 2, 7, 4, 2, 5, 11, 17] [5, 5, 5, 5, 5, 6, 5, 5, 5, 5, 6]
OUDFYATOAQSKHOCGVRAWEGDTUAEHNHDSEPIARETFNAIEEDWAWTNUGFYUIMRWOLBC…

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]
ROOOAQDAXAENTOKHQFAQBEUQYBMTVCCEANCNRENSEBXABENAEMSAEBROAVENCYWO…

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.

Follow

Get every new post delivered to your Inbox.