Archive

Archive for September, 2010

DEF CON 18 Crypto Challenge

September 2, 2010 1 comment

DEF CON 18. July, 2010. Riviera Hotel, Las Vegas. G. Mark Hardy tells us that he’s just launched another crypto challenge, and the clues are all on the DEF CON CD. The game, as they say, is afoot.

So my buddy Дурак (gypak, Durok) and I start poking around to see what’s on the CD. We’re both using netbooks, so we have to wait until later to hook up the CD drive I remembered to bring, then copy the disc to both netbooks. And read through G. Mark’s presentation…

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 first clue is on Page 49 — “Look for gold on the DC CD.” So we start searching for files named gold, containing the word gold, etc. I’m not sure that we ever looked for anything with “Au” in it (the chemical symbol for gold), but if we did, we did it wrong (more on that later). Eventually, we just highlight everything in the presentation and look for hidden text.

Sure enough, on page 47, there’s a message, in (almost) white-on-white, so it’s just barely visible:

Congratulations. You have just discovered the secret message. Your patience has been rewarded.
Go to my website subdirectory reciprocal of this page number to six places.

Woohoo! (Aside — the wording of the message grabbed my attention, and there’s a reason for that. As a big Pink Floyd fan, it was like high intensity blinking neon to me, but I didn’t know what to make of it, so just filed it away for the time being. More on this later, as well.)

Anyway, so we do the math (1/47 = 0.021276, to six places). And go to http://www.gmarkhardy.com/021276. Once there, we’re greeted with the first cipher challenge:

AUJKKUHNTPYMJKKHYTGKHMESELMPFKDUJUSGFPEPVAFROPRER
HOBAGYJRAHWHLFVKWYBLZGBQHZZVUWKHMMWRLAERQPAEREORA
VLARALSLMMWRLAEROPRERLUQAKPUQAZTTMBRXLFTSRLMBLKAU
JKKKBNSTUMBFOGLPMKDVMDKORBJKMEPEKIRZGYKMUZPGTSSGL

Time to fire up the crypto engines. Дурак’s got his netbook hooked up to the TV in his room, I’m sitting in the chair mucking about on my own netbook, as other folks hang around giving us “helpful” suggestions while we figure out what we’re doing for dinner.

At some point, I notice that the five most common letters are, in order, K, R, L, M, and A. Four of those letters spell MARK. G. Mark is well known for using variants of his name either as part of the plaintext, or a factor in the encryption, or both. Дурак tries to attack as a plain old cryptogram, while I start playing with other attacks, but we both keep coming back to trying to use GMARK in some way (like GMARK == ETAOI, mapping to the 5 most common English letters). It’s just not working out.

Early Saturday morning, though, the solution hits me. I split the ciphertext into 5 different alphabets, and shift each alphabet by letters corresponding to G-M-A-R-K. That is, ciphertext letters 1, 6, 11, 16, etc., are shifted by “G” (7) letters, such that, for example, the U in position 6 will really be N in the plaintext. Letters in positions 2, 7, 12, etc., get shifted by “M” (13), etc.

This is a simple keyed polyalphabetic cipher. Very much like a Vigenère cipher, but the key’s generated a little differently. However, you can use a standard Vigenère applet to solve the shift, using HNBSL (GMARK + 1) as the key.

  ABCD EFGH IJKL MNOP QRST UVWX YZ
1 HIJK LMNO PQRS TUVW XYZA BCDE FG
2 NOPQ RSTU VWXY ZABC DEFG HIJK LM
3 BCDE FGHI JKLM NOPQ RSTU VWXY ZA
4 STUV WXYZ ABCD EFGH IJKL MNOP QR
5 LMNO PQRS TUVW XYZA BCDE FGHI JK

Decoding is reasonably simple. Take the cipher text (“AUJKKUHNTP…”) and use the above table of alphabets for each character in succession. For example, for the first “A” we use alphabet 1. Find “A” in that line, look to the top, and you get a “T.” That’s the first letter of the plaintext. Then “U” in line 2 maps up to H, J in 3 maps to I, (K, 4) to S, (K, 5) to Z. The 6th letter brings us back to the 1st alphabet, so (U, 1) maps to N, (H, 2) to U, etc.

The final plaintext is:

THISZNUMBERZISZALSOZAZDATEZONZWHICHZSOMEONEZDIEDZ
WHOZONCEZPLAYEDZPLATOZOPPOSITEZAZLEGENDZFINDZTHEZ
DATEZTHEZLEGENDZDIEDZANDZSENDZHIMZAZMESSAGEZATZTH
ISZDOMAINZANDZYOUZWILLZHEARZFROMZBEYONDZTHEZGRAVE

Change the Zs to spaces, fix some wrapping, and you get:

THIS NUMBER IS ALSO A DATE ON WHICH SOMEONE DIED
WHO ONCE PLAYED PLATO OPPOSITE A LEGEND FIND THE
DATE THE LEGEND DIED AND SEND HIM A MESSAGE AT THIS
DOMAIN AND YOU WILL HEAR FROM BEYOND THE GRAVE

Woohoo! First thing, I’m sharing this with my buddies at breakfast. But before that, I naturally have to try to get to the next stage. It’s a pretty easy matter to figure out that an actor named Sal Mineo died on 2/12/1976, and that he played a character nicknamed Plato in A Streetcar Named Desire. Which means the “legend” is of course James Dean. Who I learn, a little more Wikipedia surfing later, died on 9/30/1955.

Of course, I still have some questions. First I tried sending email to the first name (Sal Mineo), trying “sal,” “salvatore,” “mineo,” and other variations, with dates or other information in the subject or body of the message. About 10 minutes later, I tried jamesdean instead, then finally 093055. Still nothing.

About a half hour later, I try surfing to gmarkhardy.com/093055. I get the following message:

Good job on the research.
Bad job on the contacting.
Think of another way
To use this number
To contact the dead.

This confirms that I have to use the date, not the name. I tried the email to G. Mark’s other domain, nationalsecurity.com. Within a minute I get the following email:

You’re almost there.
People have been asking who is this man since the year bin Laden was born.
He has vowed to stop the motor of the world.
His location is highly classified.
But I bet you can find him.
Find the city that bears his name.
Dial his highly classified phone number there.
You will learn the answer.

Again, some funny wording. “People have been asking who is this man” as opposed to “who this man is.” Immediately, I know who he’s talking about: John Galt. “Who is John Galt,” I hear you ask? :) A character (and a frequently repeated question) from the novel Atlas Shrugged. Some quick research confirms it was published in 1957, and that bin Laden was born that same year.

The novel includes a town, called “Galt’s Gulch,” which was based on the city of Ouray, Colorado. Perhaps there’s a phone number in the story, and we need to dial that number, but in the Ouray area code (970). Naturally, I buy the book (iBook for the win — I’ve wanted to finally read this anyway). I do a lot of searching, but can’t find anything obvious.

Now where do we go?

I, for one, go to breakfast, as it’s now 8:00, I’ve been at this for two hours, and I’m hungry. I slowly dole out bits and pieces of what I’ve done, helping Дурак to figure it out on his own, until eventually everyone at the table is up to speed. But none of us knows what to do next.

Right about that same time, G. Mark tweets the first hint:

Did you find your gold on the CD? I bet your chemistry teacher could.

Our task now is to look, not for “Gold,” but for “Au.” (I’d mentioned this earlier). After searching his briefing again, we found “AU” in some of the ciphertext for his Mardi Gras contest. Perhaps the phone number used there? Just as we’re settling into the first talk for the day, he sends another two hints:

If you’re not at the CON and playing from home, I just uploaded DC CD – see my preso in Hardy for 1st clue@ http://www.gmarkhardy.com/DC18/

and

For home players, life will be grand when you follow the clue to “look for gold on the DC CD” (helps you search through the trees)

Of course we have no choice but to immediately follow those up. The second hint makes me think of Joe Grand’s talk, which included pictures of gold-colored badge prototypes, but that doesn’t seem to get me anywhere. It doesn’t take long for us to realize that most of the folders on his site are empty…only his presentation, and a single file “au.bug” in the folder William-LeGrand.

Once again, High School English saves the day. The filename is clearly a reference to “The Gold Bug,” by Edgar Allen Poe. I quickly download that one to the iPad (at least this one’s free), jumping straight to the part of the story where the characters decrypt a secret message. (Also, it turns out even the directory name was a hint — there wasn’t anyone named William-LeGrand at the con, the name came straight from the story.)

The ciphertext on the CD looks like this:

5;46(†‡1)5..46(8
);48*898(50†)5*†
75;—48)‡.50)(?26
8);48*†659‡*†)5*
†—8*)8().5))7‡(†
89.;:).5—8)25—]7
5(†)500—5.)*‡).5
—8)0‡‡]1‡(46††8*

For a start, I try inserting the character mappings right from the story (Poe
was helpful enough to even put it into a nice table for us):

5  represents  a 
†       "      d 
8       "      e 
3       "      g 
4       "      h 
6       "      i 
*       "      n 
‡       "      o 
(       "      r 
;       "      t 

This is easily accomplished with the UNIX command “tr”:

cat au.bug | tr ’5†8346*‡(;’ ‘ADEGHINORT’

which gives the partial-plaintext:

ATHIRDO1)A..HIRE
)THENE9ERA0D)AND
7AT—HE)O.A0)R?2I
E)THENDIA9OND)AN
D—EN)ER).A))7ORD
E9.T:).A—E)2A—]7
ARD)A00—A.)NO).A
—E)0OO]1ORHIDDEN

Finishing the work is pretty easy, revealing the following:

A THIRD OF SAPPHIRES THEN EMERALDS AND WATCHES OPALS RUBIES THEN
DIAMONDS AND CENSERS PASSWORD EMPTY SPACES BACKWARDS ALL CAPS NO
SPACES LOOK FOR HIDDEN

Wow. Okay, what does this mean? BTW, back to the secret message from page 47: “Empty Spaces” is a track on Pink Floyd’s album “The Wall.” It’s got a hidden backwards message. That starts with “Congratulations, you have just discovered the secret message.” Sound familiar? Of course it does. Didn’t help me any, though.

However, it seems likely that this is an important connection, because G. Mark’s next hint talks about music:

Once you find your gold, listen to some music, follow your riches, find the music, and you’ll find the next hidden message.

Still, this doesn’t help me much. With a little further prodding (he told Дурак to ‘read the book’), I finally figure out what we’re missing for the gold bug puzzle: The story’s detailed inventory of treasure, in quantities of sapphires, emeralds, etc. Specifically:

[...] There were diamonds — some of them exceedingly large and fine — a hundred and ten in all, and not one of them small; eighteen rubies of remarkable brilliancy; — three hundred and ten emeralds, all very beautiful; — and twenty-one sapphires, with an opal. [...]

All the counts from the story that are pertinent to this puzzle:

Censers 5
Diamonds 110
Emeralds 310
Opals 1
Rubies 18
Sapphires 21
Watches 197

The puzzle literally translates to “1/3 * 21 then 310 and 197 1 18 then 110 and 5.” After some futzing around, I decide it’s 7 then 310+197 1 18 110+5″ or “7 507 1 18 115.” Take these numbers, mod 26 (divide by 26 and keep only the remainder), and you get 7 13 1 18 10. Convert those numbers to letters — the 7th letter is G, 13th letter is M, and I don’t really need to spell out the rest, do I? G-M-A-R-K.

I catch up with G. Mark in the hallway to tell him where I am so far. He confirms that I’ve got that part right, and really that was actually supposed to have been the first stage of the puzzle. It was supposed to work like this:

  • The password “EMPTY SPACES” backwards was to unlock the PDF of his presentation so I could search,
  • The phrase “Empty Spaces backwards,” researched online, was supposed to help me dig up the hidden backwards message, which, once I searched for that in the presentation, would lead me to…
  • Page 47, and the next stage of the challenge.

However, apparently the folks mastering the DEF CON CD didn’t want anything hidden or password protected on it. Instead of being completely invisible and only discoverable via the search, the hidden text on page 47 was much easier than expected to find. We had jumped straight past the first puzzle into the middle of the whole challenge.

We keep on talking for a while, about Galt’s Gulch and so forth. G. Mark asks me if I’d looked for Galt in Google Maps — of course, I hadn’t. I was so sure that the town in the book was what I was looking for, not for an actual city with his name (turns out there are a few, but the biggest is in California). He also asks me what “Highly Classified” means. I replied, “Well, to me, that means TOP SECRET, but I that doesn’t get me a phone number. Maybe look for government installations nearby the town, and somehow a number there is a clue?” After a couple more “you’re overthinking it” comments, we part ways.

At this point, it’s after 5:30 on Saturday. I need a break. Though solving this first part of the puzzle was satisfying, we’re no closer to the solution now than we were at 8:00 this morning, and that’s frustrating.

Дурак and I talk about it at dinner for a bit, but we don’t dwell on it ’cause we need a rest and don’t want to bore the rest of the table. Just before 9:00, another tweet from G. Mark suggests he’ll have a “special Q&A at Hacker Jeopardy,” so we head over there after dinner and hang around for a bit. When it’s clear that there’s too much for him to do to prepare for the tournament, which means that he probably won’t be answering any questions, we move on.

Later that night, when I was definitely over tired (and the music from the IO Active party two floors up was making my room shake), I continued the search for a phone number. Eventually, I did find a phone number in Atlas Shrugged: OR-6-5693. It was actually the number used at a pivotal point in the story, to get in touch with John Galt, so I figured that must be the answer. I tried calling that number, in the 209 area code (for Galt, CA), and I get a Google Voice message! That’s GOTTA be it…Google Voice forwarded to G. Mark’s cell or something. I can’t quite make out the message, but to my sleep-deprived and freakshow-saturated ears, it might almost have said John Galt on the message. I left a hesitating message, then went to bed.

Sunday morning. Дурак immediately rains on my parade and says the message doesn’t sound anything like John Galt. Damn. The next couple hours are spent trying to figure out just where the answer is hidden (and eating breakfast). About 10:00, the last hint comes through:

So, nbr can’t be in the phone directory. Think about the term you are seeking.

Again with the term. At this point, we’ve searched classified ads in newspapers near Galt, tried craigslist, and tried all kinds of other crazy ideas. We had a couple twitter direct messages where he tried to coax us out of the rabbit hole we’d dug:

“You are really overthinking the problem. It’s far simpler than that. Dial a ‘highly classified’ number.”

To which I responded:

“Like the white house, NSA, or national security corp, but with diff area? If TOP SECRET had 7 letters we’d’ve used that in a heartbeat.”

and

“Just not getting it. RED-FONE? PRI-VATE? Most synonyms for highly classified don’t fit in 7 chars. Or are exactly 6.”

Finally, he told me:

“You told me the answer yesterday. Think outside the box.”

As is typical with one of his puzzles, we’ve now passed the fun part and are into the “Aaarrgh!” stage.

Finally, I leave whatever talk I was in, and retrace the steps we took the afternoon before when we chatted in the hallway. I must’ve looked crazy, standing in the lobby, gesturing to empty space with my eyes closed as I tried to remember how the conversation went. “What does ‘highly classified’ mean?” “Well, to me, it means ‘TOP SECRET.’” TOP SECRET. 9 letters. Too long for a phone number. Or is it? Can it be that easy? Dammit.

Sure enough, when I dial 209-TOP-SECR (the ET just drop on the floor), I get a Google Voice screening message, asking me to leave my name for “TOP SECRET.” The words Top Secret are unmistakably spoken by G. Mark Hardy. I’ve arrived at my destination.

The next thing I know, I’m talking directly to him. He runs through a rehearsed litany of questions, asking me for solutions to every stage of the puzzle: Who was the (original) author (Poe), who was the legend (Dean), what was the artist (Pink Floyd), etc., etc. Good thing we’d gone back to finish the half of the puzzle we’d skipped, or I wouldn’t know what he was talking about. After I answered all the questions, he congratulated me, and informed me that at 12:40 on Sunday afternoon, I was officially the winner.

What was crazy, was not only did I tell him the answer the day before, I’d even tweeted it directly to him a couple hours prior, discounting it in the process. He must’ve really enjoyed the irony.

A little while later, I give a couple hints to Дурак (especially the bits about we’ve said it before, and to think outside the box). Not too long after, he makes the last intuitive jump himself, calls the number, and earns second place.

At the closing ceremonies, G. Mark gives us both free airline drink coupons (symbolic of the plane tickets he’s buying us as prizes). For first place, he also gives me $140 in cash to cover the DEF CON ticket. Which means my DEF CON experience ended up being completely paid for by G. Mark. Definitely a pleasure doing business with him.

To sum up, here are some of the specific bits of knowledge we were supposed to accumulate (as best as I can remember), and the approximate path the challenge was supposed to take:

  1. Presentation, p. 49 – “Look for gold on the DEF CON CD”
  2. Find au.bug file (Author: Edgar Allan Poe, Character: William-LeGrand). Decrypt it.
  3. Solve the riddle — find treasure counts in story, group appropriately and sum up, to get “GMARK”
  4. Search online for “empty spaces backwards” and find hidden Pink Floyd message
  5. Look in the PDF, unlock it using the password from the previous step, search for phrase from Empty Spaces, find clue on page 47.
  6. Solve the riddle, fetch gmarkhardy.com/021276
  7. Download and decode the cipher
  8. Solve the riddle, identify actor (Sal Mineo), Legend (James Dean), and date of death (9/30/1955)
  9. Use previous information to send email to 093055 at G. Mark’s domain
  10. Solve the final riddle (Author: Ayn Rand, Character: John Galt, City: Galt, California, etc.)
  11. Make final intuitive leap: Call “TOP SECRET”
  12. Answer questions to prove you’ve figured out each step of the puzzle

This was a fun one. I definitely like having multiple stages, and having the stages be more than simply “decrypt instructions for the next one.” Having to puzzle out the meaning of each clue exercises different parts of the brain than straight cryptanalysis does.

I was actually sort of surprised that the first puzzle used the same substitutions (mostly, at least) as the Gold Bug short story. Perhaps he didn’t want that part to slow people down too much. It seems like it was really designed to go fairly quickly at first (Gold Bug to Floyd to PDF to cipher #2). Cipher two was probably supposed to be the first real challenge, though we luckily got through that one fast as well.

The hardest part was the final leap for the phone number. I’m still not 100% sure how I feel about that. Like most riddles, the answer is absurdly simple, once you see it. Perhaps a better hint, like “it’s a word or phrase” or something might’ve helped keep us from searching for numbers. Putting “Highly Classified” in quotes, or rephrasing the riddle to make it look more like you’re searching for a synonym for that, might have telegraphed the answer too clearly. Though looking back, I see he did just that in a tweet to me, and it didn’t help me, so who knows. As always, it’s a fine line between too easy and too hard.

It’s too bad that the password-protected PDF idea didn’t pan out. Then again, perhaps that’s for the best — I think it may be risky to make elements of the puzzle too dependent upon how any given application might deal with a password or render white-on-white text. The challenge should be about the content, not about the tools you need to solve it. And it worked out in the end.

All in all — another great puzzle from G. Mark. It was hard, but not too hard, and the fact that it was solvable during the con (though just barely) is another indicator that it was probably about Just Right. It’s also quite the thrill to hear your name called out during the closing ceremonies.

Looking forward to next year, G. Mark! Thanks!

Follow

Get every new post delivered to your Inbox.