Grab Bag 400

I just love crypto contests, so I was counting down the days for most of the year until Defcon CTF 2011 Quals, priming my crypto tool chest... and then they had no crypto category this year. However, there was one crypto problem in the "Grab Bag" category, but it defied all of my cryptanalysis as well as that of my friend Israel Torres, and he makes his own crypto challenges.

After the contest part of the answer was revealed, but not the complete solution. I began working on it and after putting in 10-15 hours on it over a week hit a roadblock and contacted some help. We then worked on it together for another week or 2 to finally come to this: how to solve the problem. (I think.)

The challenge:

QDVEFEBEFDHOUWFCQDYN BGTFQGCSQHI SJCSYJESGEVIJCFFOMMJFT TLPRJDGPVWAVGSMLPR WAXIRZXIVNYKRAY
Hint: We lost our lemma ... crest ... hype. Find it, and we'll share the goods.

Step 0: Identify the cipher

I do not know how you would do this unless you were already familiar with "headline puzzles" in which case you may have recognized that this is not one cipher but 5, and 5 ciphers + 3 keys is a headline puzzle.

Step 1: Break at least 3 of the 5 ciphers

This is impossible by any method or tool that I know of. (A friend disagrees as she thinks it may be possible to get a toehold with some tools, so I will append this statement with "within the time span of a 400 opening up towards the end of a weekend contest.") The ciphers are too short for frequency analysis, are missing their spaces, the most diverse one only has 13 unique letters, and it turns out many of the words are not even words but puns and play-on words from Bin-Laden-related porn titles. The released solutions are:

1. death to the nymphidels
2. talibang bus
3. dead men dont wear rubbers
4. persian rug munchers
5. youre turban me on

Step 2: build a 26 letter chain

This is complex and takes a good hour or 2 to do, and is based on the fact that all 5 alphabets used to encipher the 5 headlines are interrelated. There are many papers on it here and elsewhere. (The puzzlemaster from that site put in countless hours on this puzzle and helped me get past steps 4+ which I may never have figured out on my own.) This will look familiar if you have ever cracked a playfair cipher, but basically you take 2 of the partial alphabets you deciphered, build tables, use those tables to solve more (unused) letters from the alphabets, and keep going until you have solved enough to build a 26-letter chain.

As a completely random example pulled out of my ass and that is not based on GB 400, let's say you are using the alphabets from cipher 1 and 2, and that in cipher 1 plaintext A encoded to S and that plaintext S encodes to D. You would write the chain:

A
S
D

Now let's say in alphabet two that S encodes to X and D encodes to C, so:

A 
SX
DC

Guess what? You have just learned that in alphabet 1 the letter X encodes to C even though X was never used! Write that down, continue for hours making 3 or more tables with different alphabets, swapping between them, learning a new letter here and there, and finally you can build a "chain" (like [ASD] or [SX]) out to 26 letters.

The chain in GB 400 is:

WIBMYRFQNEJXACPUOGLZHDSTVK 

Step 3: find the "setting"

With that 26 letter chain we can now complete all 5 alphabets and the list them under their plaintext either in alphabetical order or by offsetting their decimations as I did here:

P: TBQAGSIFXODWRJUHKYEPZVMNCL
1: EPZVMNCLTBQAGSIFXODWRJUHKY
2: BQAGSIFXODWRJUHKYEPZVMNCLT
3: VMNCLTBQAGSIFXODWRJUHKYEPZ
4: FXODWRJUHKYEPZVMNCLTBQAGSI
5: ZVMNCLTBQAGSIFXODWRJUHKYEP

Thus it seems the first key or "setting" is "Aries" under the "index" W. 1/3 done, woot.

Step 4: Find the "key"

This is easy enough with the right tools. Simply plug the chain into a chain decimator that builds a MOG table and scores each decimated chain based on how many letters are in order, then work on de-anagram-ing all the letters that come after Z in that highest scoring chain:

1   XIAHNROZWEVGBQUCFYDSPTKJML   0
3   EKJLFMPGVQSUWRCXYBZHADTNIO   1
5   QTNOYIAUSRHCVMXEBWGLJZDFKP   1
7   RDFPBKJCHMLXSIEQWVUONGZYTA   0
9   MZYAWTNXLIOEHKQRVSCPFUGBDJ   1
11  IGBJVDFEOKPQLTRMSHXAYCUWZN   1
15  TCVFHGBRADJMPZIKLOQNWEXSUY   1
17  DXSYLUWMJZNIAGKTOPRFVQEHCB   1
19  ZEHBOCVINGFKJUTDPAMYSRQLXW   0
21  GQLWPXSKFUYTNCDZAJIBHMROEV   1
23  UROVAEHTYCBDFXZGJNKWLIMPQS   1
25  CMPSJQLDBXWZYEGUNFTVOKIARH   0

Oh look, they are all 0 or 1 point, how useless. Of course I tried them all many times, but in hindsight I know to use the chain with the most reasonable looking letters -- #3. First we take it's opposite (for lack of better word) #23, then the standard alphabet, then #3, stack them and get:

23 UROVAEHTYCBDFXZGJNKWLIMPQS
   ABCDEFGHIJKLMNOPQRSTUVWXYZ
 3 EKJLFMPGVQSUWRCXYBZHADTNIO

Now you take each letter after Z in the bottom row and highlight them in the top row and you get the key:

UROVAEHTYCBDFXZGJNKWLIMPQS
ABCDEFGHIJKLMNOPQRSTUVWXYZ
EKJLFMPGVQSUWRCXYBZHADTNIO

Oh look, it's gibberish. With the aid of hindsight we know to press on to the next step anyway and build the table using the vertical columns that are highlighted ([OCJ] [AEF] etc.) and sticking together the ones that overlap ([THG] and [HGP] etc.)

O A T I N
C E H V R
J F G D B
  P L
        U    

Ok, that looks like crap right now, but it seems to indicate the key is two lines of the table not one like they usually are. Let's put them in alphabetical order. We know B was not used in the key in the first 2 lines, so it must be the first letter after the key on the third line, so [NRB] must be the first column of the table. C is used, so [AVD] is next. Order them all, then add the rest of the alphabets from the 3 line table we built above from the MOG table and get:

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

So, that is the complete table, and the key is "niatorvehc" which is "chevrotain" backwards, which I guess the author did because he felt the puzzle was too easy otherwise? A chevrotain is a horned dwarf deer mouse thing, from the same suborder as sheep, a.k.a. ovis aries, or maybe Aries the ram, a celestial horned male sheep. So, it seems we have an animal theme, perhaps all from that same suborder. Or a horned theme. Whatever, 2/3 done.

Step 5: Find the "hat"

Plug the chain into the chain decimator tool being sure the "index" letter W is the first letter or this wont work. Take the decimation table:

1 WIBMYRFQNEJXACPUOGLZHDSTVK
3 WMFEAULDVIYQJCOZSKBRNXPGHT
5 WRJUHKYEPZVMNCLTBQAGSIFXOD
7 WQPDBEOTYXLKFCHINUSMJGVRAZ
9 WELIJZBXHMADYCSRPTFUVQOKNG
11 WXSQLMPKJDFGBCVEHROIATNZYU
15 WUYZNTAIORHEVCBGFDJKPMLQSX
17 WGNKOQVUFTPRSCYDAMHXBZJILE
19 WZARVGJMSUNIHCFKLXYTOEBDPQ
21 WDOXFISGAQBTLCNMVZPEYKHUJR
23 WTHGPXNRBKSZOCJQYIVDLUAEFM

25 WKVTSDHZLGOUPCAXJENQFRYMBI

And take line 3 as that corresponds to the line 3 from the MOG table we used earlier.

3 WMFEAULDVIYQJCOZSKBRNXPGHT

Note it starts with WMFEA which is the third column from our table

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

but backwards. So that means the the third column is the first column used when encrypting this puzzle so the order is ??1??. Next ULDVI is the 2nd column used so the order is ?21??. Then YQJCO so ?21?3 then ZSKBRN and XPGHT so the order of our last key or "hat"is:

42153

This means the letters in a five-letter word are in that alphabetical order, so the word could be something like "DBAEC" or "BAACB" or "QFAZN" or a bazillion other possibilities.

I had a huge dictionary from my Boggle-clone-solving and friend-dominating program and wrote a python program to go through it

f = open('web2.txt', 'r')
lines = f.readlines()
for line in lines:
if (len(line) == 6): #counting \n
if ord(line[2]) <= ord(line[1]) <= ord(line[4]) <= ord(line[0]) <= ord(line[3]):
print line,

And it returned the list:

caama
feaze
feere
feeze
gease
heath
heave
hecte
heeze
keawe
keeve
khaki
kiaki
laang
lease
leash
leath
leave
ledol
mease
meese
miasm
miaul
neath
neese
neeze
ngapi
onion
pearl
pedro
pedum
peeve
phasm
picul
piezo
plasm
polyp
ponto
raash
rearm
reask
reave
recti
recto
recur
redue
redye
reese
reesk
reeve
rheum
robur
scase
scaul
scaum
scaup
scaur
scawd
scawl
seave
sebum
sedum
shaul
shaup
shawl
shawm
sheth
sibyl
skewl
slaum
teave
teaze
tecum
teeth
thatn
thats
thawn
ticul
tonus
trews
trout
uncus
uncut
unfur
upcut
weeze
whewl
whewt

I don't even know if half of those are real words, but I didn't want to miss a single point in Boggle. Anyway, we figure the answer must be an animal, and 2 (or 3?) of those are animals: trout, which fits the pattern but isn't elegant (why is the first T used after the second T when encrypting?), and scaup, a kind of duck, and it fits the pattern perfectly. Scaups have a small black nail on the tip of their bill, kind of like a horn? Good enough for me. And I'm sure that has something to do with lemma, crest and hype.

The answers (probably) are: Aries, chevrotain and scaup.