Archive

Archive for November, 2010

THOTCON Pre-Sale Code Puzzle

November 22, 2010 Leave a comment

THOTCON is an information security conference in Chicago. And they did a puzzle last year, that I solved, and got a really cool Sake decanter as a prize. The guy who did the puzzle, Sak3bomb, did another puzzle for the next THOTCON — this one for a pre-sale prize in advance of next spring’s conference.

Problem is, the puzzle came out while I was at the beach. When I was supposed to be resting. At 1:30 in the afternoon, on September 17th. Of course, I didn’t see it until about 9:00 in the evening. When I was supposed to be resting.

Naturally, I couldn’t leave it alone, so I started to work. First, the puzzle tweet:

[9/17/2010 1:29pm @thotcon] Pre-Sale Puzzle -> FAW2GlImKsT3BL8yKQF= zf-c75-sb-j 60max #thotcon #hacking #infosec #security

As always, if you’d like to solve this yourself, stop now. The rest is
full of spoilers. The big challenge is just that string, you’ll know when
you have it cracked, and then you can come back here to see how the rest of
the game played out. [though you might also want to check out the first couple
of hints below...]

Okay, so we’ve got a base-64 string. What’s the zf-c75-sb-j bit? A subsequent tweet cleared that up:

[9/17/2010 3:12pm @thotcon] Looking for pre-sale puzzle hints? follow @sak3bomb, @jaku, @c7five, and @zfasel now!!!

By the time I started, there were already two hints posted:

[9/17/2010 3:00pm @thotcon] I was born on April 5th. #thotcon0x2

[9/17/2010 3:33pm @Sak3bomb] What do you mean I was part of the Reichstag zu Worms? #thotcon0x2

Okay. Well, first, what’s the Reichstag zu Worms? It sounded vaguely familiar, and a quick trip through Wikipedia explained it to me. Better known to English speakers as The Diet of Worms, a meeting of leaders of the Holy Roman Empire. The Diet of 1521 was famous as the trial of Martin Luther. But which of the attendees are we supposed to be focusing on? Again, to Wikipedia, for a list of people born on April 5, sometime in the 20 years or so before the Diet of Worms (which happened in 1521). Wow! Blaise de Vigenère was born on April 5! But 1521. Hm. Wait, there were several Diets (meetings) at Worms, so he just wasn’t at Martin Luther’s particular meeting.

This is important. This means something. So, alright, there’s a Vigenère cipher in play here. Let’s decode the base-64 string and see if we can guess the key. Unfortunately, the decoder gives me random-looking binary data. And there’s no way I can run that through this cipher — it sort of pre-dates binary codes (well, ASCII at least).

I did, however, notice one interesting thing: The decoded binary string had 14 bytes. THOTCON has 7 characters. It’s not a requirement that a Vigenère ciphertext be a multiple of its key length, but it seemed like an interesting coincidence.

I played with it for a while….trying to force a Vigenère cipher to work with the binary data, basically by using a full 256 characers (8 bits) as the alphabet, instead of simply the letters A-Z. That didn’t get me anything interesting. I also tried doing some bitwise exclusive or (XOR) approaches, again using THOTCON as the key, but again I got nowhere.

I even considered that maybe we were supposed to block out the bits differently — turning 14 8-bit blocks into 16 7-bit blocks, or arrange it into a square and read vertically, or other crazy things. Nothing seemed to help. Finally, I put out a call for help:

[09/17/2010 10:34pm @schuetzdj] Dammit. Another puzzle. Figured out the first two clues and stuck again. :( #thotcon

and about 20 minutes later I struck up a conversation with @c7five:

[09/17/2010 10:57pm @c7five] @schuetzdj where are you stuck?

[09/17/2010 10:59pm @schuetzdj] @c7five Applying cipher to b64 output. Can’t get anything useful. Tho get leading @ a couple ways, which was intriguing.

[09/17/2010 11:01pm @c7five] @schuetzdj hint: the base64 you see needs to be deciphered before it is useful. Follow the clues. You have the algo and key.

[09/17/2010 11:03pm @schuetzdj] @c7five As in, decipher THEN b64 decode? considered that, didn’t explore too long.

[09/17/2010 11:03pm @c7five] @schuetzdj yup.

Cool! That should help! As I said in the tweet, I’d briefly considered that the base-64 string wasn’t really base-64, but was itself enciphered to only look like base-64, but again I was stuck on the problem of a larger-than-normal Vigenère alphabet. However, this hint told me that was the right way to go, after all, and so with renewed enthusiasm I returned to the puzzle, even as those around me started heading off to bed.

I reviewed how the Vigenère cipher worked, and verified that my program was actually doing the decryption properly. But I still got stuff that, once sent through the base-64 decoder, looked like binary gibberish. I wasn’t any closer. Just to be sure, I wrote a simple program to generate a partial Vigenère tableau, saving just the bits that interested me:

alpha = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'

print alpha
for x in alpha:
    i = alpha.find(x)
    o = alpha[i:64] + alpha[0:i]
    if x in ('T', 'H', 'O', 'C', 'N'):

Traditionally, the tableau would be written such that the keyword goes across the top of the paper. But because I didn’t want to deal with 64 character columns, I did it horizontally instead. The script only prints out rows corresponding to the characters in the keyword, and then I’d manually move the rows into the right places in a text editor. The result was this:


ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/

TUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/ABCDEFGHIJKLMNOPQRS
HIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/ABCDEFG
OPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/ABCDEFGHIJKLMN
TUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/ABCDEFGHIJKLMNOPQRS
CDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/AB
OPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/ABCDEFGHIJKLMN
NOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/ABCDEFGHIJKLM

I also made a tableau with the traditional 26-character alphabet, to be sure I really had the method down properly. The way the cipher works is like this. First, take the ciphertext:

FAW2GlImKsT3BL8yKQF=

We’ll ignore the = at the end — that’s a padding character for the base-64 decoding that comes in step 2. Start with the first letter, F, and the first character of the key, T. Find the alphabet starting with “T” in the table, go right over to the capital F, and move up to the header row at the top. You get ‘y’. So the first letter of the plaintext is ‘y’.

The next letter, ‘A’, will have been encrypted with the 2nd letter of the key, so we go to the H alphabet, over to A, and up to 5. Carrying on, we eventually get y5IjEX7TDeA1z+pr89D. Which is exactly what my program produced. So my coding isn’t to blame — I’m simply still not doing it right. And it’s getting late. The next day I’m going to be really busy (last day at the beach and all), and I was going to spend all day Sunday travelling home, and then Sunday night flying out for a week-long business trip. So I really didn’t know when I was going to get to play again, which was pretty annoying. :( I expressed my disappointment to c7five:

[09/17/2010 11:44pm @schuetzdj] @c7five Getting nowhere. Hard to decide on proper alphabet. THINK I’m doing it right, but must have wrong key (output still ugly binary).

[09/17/2010 11:45pm @schuetzdj] @c7five Gonna have to quit soon. Not sure I’ll get to play tomorrow, and spending all day Sunday traveling. :(

and he took pity on me, verifying the key for me:

[09/17/2010 11:46pm @c7five] @schuetzdj THOTCON0X2

So I didn’t have the right key. Though I was pretty close. Hey, look at that — the key was even in the original tweet from @thotcon. Tricky. Let’s plug the correct key in, and…. y5IjEX7yz2Awz46k9cu. Dammit. I should have realized that — the result would be identical up until about halfway through the decryption, and even with the 2nd half being totally different, the base-64 decode would still largely have to be messed up binary. I’m obviously missing something. More back-and-forth tweets ensue.

[09/17/2010 11:49pm @schuetzdj] @c7five I get “y5IjEX….” Output of that (decoded) still ugly binary. Obviously, not doing cipher stage properly.

[09/17/2010 11:51pm @c7five] @schuetzdj you doing Vigenere?

[09/17/2010 11:52pm @schuetzdj] @c7five Yup. But that uses a 26-character alphabet, not 64-character. So improvising. Poorly, it seems. :)

[09/17/2010 11:53pm @c7five] @schuetzdj use: http://j.mp/aQVE3y

[09/17/2010 11:54pm @schuetzdj] @c7five You’re kidding. That’s my go-to cipher tools site. Never even tried. Hang on.

Funny how I never used my standard toolbox on this problem. But that’s not designed to work with a 64-character alphabet, how could it possibly work here? Nevertheless, I’m not going to argue, so I plug the ciphertext and key into the applet, and I get back: MTI2NjUzNzM3NS8wWDI. Plugging this into my favorite online base-64 decoder, I get stage 2:

1266537375/0X2

Clearly, that’s the right answer. But what do I do with that? Again, I’m muttering words like “sneaky,” “evil,” and “bastard” under my breath as I simply paste the result into Chrome’s URL bar, and it takes me to the last step of the puzzle.

How’d that happen? The number 1266537375 was treated as a single 32-bit integer, and broken up into 4 8-bit chunks…which, incidentally, is exactly how IP addresses work. You can do it manually with a little math: Take the big number, divide it by 256^3 (256*256*256), and that’s the first part of the address, the first “octet” (for 8 bits). Then you take the remainder (If you’re using a calculator, take the fractional part and multiply by 256^3. If you’re doing it longhand, just take whatever was left over once you hit the decimal point). Divide that by 256^2, and that’s the 2nd octet. Repeat for 256^1, and finally for 256^0 (dividing, in that last stage, by 1 — just leaving it be). The result is this:

75.125.211.159

You can check it like this: 75*256^3 + 125*256^2 + 211*256 + 159 == 1266537375. W^5. (“Which Was What We Wanted.”) (Blame Fred Whipple, my 12th grade physics teacher, for that little joke).

Anyway, all that magic happens automatically in some browsers (on my Mac, it seems to work in Chrome, but not Safari or Firefox), and it takes you to http://75.125.211.159/0X2. (incidentally, the same magic happens on some command line programs, which is why, in the early 90′s, I constantly cursed myself for naming a bunch of machines after movie titles, ’cause it was impossible to “telnet 2001″. But I’m digressing.)

The browser takes me to a page with what looks a lot like the “640K ought to be enough for everybody” quote from Bill Gates, translated into Russian. And another quote I can’t quite recognize. And a link to the THOTCON ticket sales page. And, finaly, three steampunky / sci-fi-ish pictures. Damn, am I going to have to deal with steganography again, like his last puzzle?

First, let’s make sure there aren’t any hidden images or anything. View the source to the webpage, and — wait. There’s some random text for the alt and title tags on each photo. “VEHPVE,” “NPTJB4M,” and “I0YMDEX,” respectively. Maybe all three together is the code. “VEHPVENPTJB4MI0YMDEX” I jumped to the ticket page, entered the code, and sure enough — it worked. Yay! At just after midnight, I’ve completed the puzzle. And now it’s time for bed.

But first…hm…should I buy a ticket? I’m not sure I’m even going to be able to go — not sure whether work would pay for a small con like that. And it’s not a huge discount, so I’ll wait until I get back to the office and ask. If others have snapped up all the discount tickets, that’s not really a huge deal.

I let c7five know that I’ve solved the puzzle, thank him for the challenge, and go to bed.

[09/17/2010 11:58pm @schuetzdj] @c7five Interesting. I wonder how it’s doing that? Looks like upper/lowercase are automatically mixed in a single alphabet, and ignores nums

[09/18/2010 12:06am @schuetzdj] @c7five Okay, got the code. Cool. Not sure I’m even gonna buy a ticket (not sure company will pay for trip), but thanks for the puzzle!

[09/18/2010 12:07am @schuetzdj] @c7five I really have to figure out how that cipher got implemented. Didn’t seem “pure” enough — I was trying a real 64-char vig table….

[09/18/2010 12:08am @schuetzdj] And, boom, I’ve got the #thotcon0x2 pre-sale code discovered. Fun puzzle, though I’m still a little confused on some of the mechanics. Thx!

So, what did I think of this one?

First off, I both liked and hated the fact that the ciphertext only *looked* like Base-64, but wasn’t quite exactly that. Evil, evil, evil. On the other hand, I really didn’t like that it wasn’t strictly a Vigenère, either. I took sort of a purist approach, modifying the cipher to work with the alphabet before me. But the puzzle took a different shortcut. Essentially, the trick was to take a standard tableau, and ignore (but preserve) case while decrypting. That is, if you (or your app of choice) treated a capital A the same as a lowercase A, but made sure the output was the same case as the input, then you’d be good to go. Provided you also just copied the numbers over, in place, unchanged.

ABCDEFGHIJKLMNOPQRSTUVWXYZ

TUVWXYZABCDEFGHIJKLMNOPQRS
HIJKLMNOPQRSTUVWXYZABCDEFG
OPQRSTUVWXYZABCDEFGHIJKLMN
TUVWXYZABCDEFGHIJKLMNOPQRS
CDEFGHIJKLMNOPQRSTUVWXYZAB
OPQRSTUVWXYZABCDEFGHIJKLMN
NOPQRSTUVWXYZABCDEFGHIJKLM
XYZABCDEFGHIJKLMNOPQRSTUVW

FAW2GlImKsT3BL8yKQF

becomes:

MTI2NjUzNzM3NS8wWDI

Of course, will this really work with all tools? Or will some recognize the extended alphabet and try to go the route I took? Or will some simply fold everything into uppercase and continue from there? (which is really what I’d expected everything to do). It wasn’t until nearly a week later that I finally had a chance to try the ciphertext in several other online tools. The first three were tools I’ve used a lot in the past (and the 1st two I use frequently):

Site Output Comment
Rumkin Cipher Tools MTI2NjUzNzM3NS8wWDI Correct, and what c7five pointed me to.
UCSD MTINJUZNZMNSWWDI Stripped numbers, converted all to uppercase
Sharky’s Vigenere Cipher MTI2NjUzNzM3NS8wWDI Correct
Simon Singh ERROR Told to remove numbers.
Central Edu mtinjuznzmnswwdi Numbers stripped, converted all to lowercase
Oregon State mti*exvjnna*ns*kxni Numbers stripped, key got out of sync and rest totally wrong

So out of a totally unscientific survey of 6 online applets (taken from the first couple pages of Google hits for “vigenere cipher applet”), I have correct answers from only two. As I write this, I believe about half of the ticketshave been spoken for — so fewer than 30 people have solved the puzzle. (well, perhaps more than that, if there are more people like me who solved it but haven’t bought tickets). I don’t know if that’s a good number or not, but somehow I expected more people would get it faster.

I guess since a fair number of people *have* solved it, that proves that the puzzle isn’t too terrible. But I still wonder how many people used the “wrong” online tool and gave up in frustration, or worse, followed a purist’s path like I did and got really annoyed when the “obviously right” approach didn’t work.

The Vigenère ciphertext masquarading as base-64 data was a neat trick. Without a little hint up front, it might be a bit…evil…but I have to admit I like the idea of it. Just not sure whether it’s entirely “fair.” I suppose I’d feel better about it if the decryption were easier than it was….

And the last bit, with the flat number pasted into the browser — very slick as well. Not many people know that’ll work, but I’m betting those who did know and made the leap were quite happy with themselves for knowing that particular bit of IPv4 arcana.

So, all in all, what’s my verdict? I like the puzzle. I’m not thrilled with the Vigenère portion of it, as I’ve said, but the rest was great. Now I’m just wondering with Sak3bomb will come up with for the THOTCON itself, and whether I’ll get a chance to play along at home (or if I’m gonna have to convince my boss to send me to the con).

As always, thanks for the puzzle, everybody!

Follow

Get every new post delivered to your Inbox.