Archive

Archive for the ‘Conferences’ Category

BSides Phoenix 2012 Badge Puzzle

February 19, 2012 Leave a comment

Sitting at home yesterday morning, watching cartoons with the kids and checking my Twitter feed, I saw a tweet from Georgia Weidman with a picture of the badge from BSides Phoenix. It looked like an awesome badge, made out of hefty chrome and with an integrated bottle opener. It also had a puzzle on it. There goes the rest of my morning….

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 to see just the images needed to solve the puzzle, click here: BSidesPHX 2012 Images.

The badge has a hexadecimal string all around the edge. And also some other text — SNOW, and the con name:

SNOW 0E071A1F4D495C09001848140240462117025EF BSIDES PHX 2012

The first thing I did was to count the hex digits. There were 39. Really, 39? That’s an odd number — usually hex is presented in two-digit pairs (each pair representing a single byte). Why the extra digit?

I looked at two ways to split the string up. Either the trailing “F” was unnecessary (or at least unnecessary for the time being), or the leading “0″ was. Splitting the digits up the first way, I got:

0E 07 1A 1F 4D 49 5C 09 00 18 48 14 02 40 46 21 17 02 5E F

Grouping them like this, the first digit of each pair is one of only 5 numbers: 0, 1, 2, 4, or 5. This actually looks very promising, as most ASCII text is limited to only a few initial digits as well (all printible characters being in the 2x-7x range). If this is the right arrangement, then it’s extremely likely that this is a simple XOR code.

But just to be sure, let’s look at it the other way:

E0 71 A1 F4 D4 95 C0 90 01 84 81 40 24 04 62 11 70 25 EF

In this case, the leading character is much more random, being chosen from 13 of 16 possible values: [01246789acdef]. Again, this tells me that the first arrangement was right, and that the string is ASCII, but with bits flipped via XOR.

Naturally, I have a tool that does this for me. The first thing I tried was obvious keys from the badge itself: SNOW, or BSIDES, etc. My tool took each byte in the key and used the eXclusive OR (XOR) operation against corresponding byte(s) in the ciphertext. It occurrs to me that I’ve never explained how this works, so here’s a quick digression.

Take the ciphertext stream 0E 07 1A 1F and look at each
as bits (I'll just do 0E):

    0000 1110  (hex 0E, 1st byte of ciphertext)

Now take the first character of your key and write it
underneath the ciphertext bits. I'll start with "B" 
for "BSides":

    0000 1110  (hex 0E, 1st byte of ciphertext)
    0100 0010  (hex 42, "B" in ASCII)

Now, for each bit position, we XOR the key bit
against the ciphertext bit. This works like a 
normal logical OR operation, except for the 
exclusivity requirement: If BOTH input bits 
are 1, then the output is 0. That is (here I'll 
use ^ to represent XOR), 0^0 = 0, 0^1 = 1, 
1^0 = 1, and 1^1 = 0.  So the result, written 
below, would be:

    0000 1110  (hex 0E, 1st byte of ciphertext)
    0100 0010  (hex 42, "B" in ASCII)
    0100 1100  (hex 4C, or "L")

Repeat this with the next ciphertext byte, and the 
next key byte. When you reach the end of the key, 
start over with the first byte of the key, and keep going.

Trying “BSides” as the key, I get “LTs{(” as the beginning of the decryption. Doesn’t look right. SNOW isn’t much better: “]IUH”. And they both have bunches of control characters and other non-printable bytes in the output. After trying a few different keys, I tried a few different plaintexts. The neat thing about an XOR code is that it works both ways. If you try a plaintext as the key, the result is actually the key that would generate that plaintext. So I tried “WWW” and “bit.ly” and a few other URL shorteners, but got nothing that looks like a real key.

Now I’m wondering about the non-printable characters, and I begin kind of staring at the 1st character (or nybble) in each byte. They seem to be not randomly distributed, and I kind of separate them like this:

0011 445 001 4 10 44 2 10 5

This looks sort of interesting. But I can’t think of how a key might produce such a pattern — or what kind of plaintext would match it. Four characters in one block (like all caps) then 3 in another block (maybe lowercase?) etc. xxxx-yyy-xxx-y-xx-yy-z-xx-y. In fact, it looks like an all-lowercase key guarantees me all printable characters, but that still doesn’t help. This is getting me nowhere, and the kids are clamoring for lunch. So I make lunch, while staring at the code, and as we’re eating, I cast about on a key hunt.

While looking at the BSides PHX home page, I saw an image with the stenciled, painted words “F SNOW” (the page referenced Snowmageddon from 2010, and how there’d be no snow in Phoenix). So I tried FSNOW as the key, and got this:

HTTP…GOO.GL..gDL.

Success! goo.gl/gDL. No. Didn’t work. I’m still missing something in those unprintable characters… What if…the first “.” after “HTTP” is supposed to be a “:”? What key letter would produce that? Changing my key to “FSNO:”, I get:

HTTPw..GO”.GL.|gDL

So I should use a lowercase w instead of uppercase? Wait, didn’t I already determine that the key should be all lowercase anyway? Stupid me. Let’s try “fsnow”:

http://goo.gl/1Gdl1

There we go, much better. It also fits that “xxxx-yyy-xxx-y-xx” pattern I noticed earlier. Also, I should note that I’d tried forcing keys based on a plaintext that started with www or bit.ly or other similar URLs, but never tried “http”. If I’d tried that, I would have had the key like 5 minutes into the game.

The URL redirects my browser to a photo of Caesar’s Palace in the snow. Cool, snow in Vegas. Is there something hidden in the image? Using “strings” I find, at the very end of the image file, the following string:

neupqebtjpafadstkbtqzmqo7o8n6625480731on2731r378pp109paftfyx

Rot-13? Nope. But it almost has to be a simple shift — after all, it was a picture of Caesar. And turns out ROT-14 was the answer. This would correspond to an encryption offset of 12, which might represent 2012, or might just be a coincidence. At any rate, now I have a new URL to visit:

bsidesphxdotorghyphenaec7c8b6625480731cb2731f378dd109dothtml
or
bsidesphx.org-aec7c8b6625480731cb2731f378dd109.html

Hm. Hyphen? That’s weird. And what do I do with the hex? A little playing didn’t get me anywhere, so I tried it as-is, only changed the ‘-’ to ‘/’ because otherwise it wouldn’t do anything.

This loads up a web page that says, simply, “congrats!” with a link. Clicking that pops up a mail window to a gmail address, with the subject “I win” pre-loaded. Rapidly, I fill out the email (worried that someone else might be beating me AT THIS VERY MOMENT) and ask, is there a prize? (I also mentioned that I’m perfectly happy allowing any prize to go to someone who’s actually AT the con, but at any rate, if they have any extras I’d love one of the awesome badges).

I got a response from Skyler Bingham a few minutes later, saying that I was the first to solve it, and that, certainly, he’d mail me a badge. Cool!!

I announced my victory on Twitter, but quickly followed up with a message that people at the con should keep trying, as it was an easy and fun puzzle. I don’t know if anyone else solved it, but did see a couple people tweeting about it. Of course, this was probably a pretty small event, so I don’t think there were that many people even playing.

But… What about that extra “F” at the end of the hex? I never needed that for anything, did I? Well, about 5 minutes after I’d heard from Skyler, it hit me: The F wasn’t part of the hex, it was part of “SNOW” at the top of the badge. That’s right, it wasn’t “SNOW (hex) F,” it was “F SNOW (hex).” The key was right on the badge all the time. Sneaky!

Thanks for the fun puzzle, Skyler!

ShmooCon 2008 Badge Puzzle

February 4, 2012 4 comments

I’ve been having a great time solving puzzles at security conferences. I think the first significant puzzle I’d seen was at ShmooCon 4, in 2008, but I didn’t even try to solve that, partially because the bug hadn’t yet bitten me, and partially because I didn’t have any computer with me at the time.
So now, four years later, I figured it was time to finally complete this puzzle. They gave a rough outline of the solution at the closing ceremony, but for this puzzle the challenge was less of a mystery than an implementation problem.

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 (a file containing an ASCII representation of all the badge data), click here: ShmooCon 2008 Badge Text.

The puzzle was entirely contained on the badges for the conference — 16 different plastic badges, each with a different pattern of dots. Clearly, these were meant to look like punched cards, though apparently many of the attendees at the conference didn’t recognize them as such. Each card had 30 columns along the long edge of the badge, and 12 rows across the short edge. Generally, punched cards were “read” horizontally, but since the badge included a “ShmooCon 4″ logo that needed to be read vertically, that’s how I’ll discuss the cards here. Plus, it’s a lot easier to analyze that way.

Each row (I’ve rotated them, remember?) is therefore a 12-bit word. But which side is the high bit? A little experimentation and analysis of all the cards shows that many cards included “punches” only on the right half of the card. If one interprets those bits as the lowermost 6 bits in the word, then those pretty clearly represent ASCII letters. So it seems that the high bit is on the left (column 0) and least significant bit on the right (bit 11).

This is nice, ’cause that’s also how most people tend to visualize bits in a word.

But two questions remain:

  • How do we put the badges in the right order?
  • What does the non-ASCII code mean?

To put the badges in the right order, the puzzle creators included an extra hint: a series of solid and broken lines at the top of the badge. These represented hexagrams from the I Ching: using the classical King Wen sequence, the badges can easily be placed into the correct order.

The other question is a little more difficult. I couldn’t find an example of this kind of punched card online, and even if I could, the same kinds of cards were frequently used for many different systems. According to the presentation in the closing ceremony, they provided a few hints during the con. One of these told players to think about a “12-bit computer from 1967″ and an admonition to “Please Don’t Participate” in the puzzle. These were meant to lead us to the PDP-8 minicomputer.

When working with these cards, it’s important to remember that octal, rather than hexadecimal, was generally used when dealing with the PDP-8, as the 12-bit word is exactly 3 octal digits. So, let’s take the punched cards and figure out what the octal (and, when appropriate, ASCII) values are for each row.

Here’s what the first card in the sequence starts with:

Punches      Octal  ASCII
.....*..**..  0114   L  
.....*...*..  0104   D  
......*.....  0040      
......**..*.  0062   2  
......**..*.  0062   2  
......*.....  0040      
.....*...***  0107   G  
.....*..****  0117   O  
......*.....  0040      
......**.***  0067   7  
......**.*.*  0065   5  
......*.....  0040      

[.....]

First, I had to find a PDP-8 emulator, and that was troublesome. Eventually, I found one that seemed to run, and seemed to be able to load the data in a format I could readily produce. And, fortunately, it also seemed to be the one they used in the slides in the closing ceremony.

The program, PDP8, was written by Brian Shelburne at Wittenberg university, and while not quite as flashy as some emulators, had the advantage that it worked out of the box. The disadvantage is I had to run it in VMware — a Mac running a Windows emulator running a PDP emulator. Inception, indeed.

Tougher than finding the emulator, though, was figuring out how to get the code loaded up. The different emulators I tried support several object data formats, including several emulated disk and paper tape files, but none of them seemed to work for me. In the end, it turned out that I needed a flat ASCII file formatted like this:

    0000/0114
    0000/0104
    0000/0040
    ....

The first word (in octal) gave the memory address into which the second word is to be loaded. But even this didn’t work for a long while, until I realized that the emulator needed the text file in “DOS” mode — with CR/LF for each line ending, instead of the LF-only ending used in UNIX. Once I passed that obstacle, I was able to easily load the data into the emulator. But it still woudln’t work.

The first words on the first card, “LD 22 GO 75″ seems to be directed at the player, not at a computer. I interpreted this as “load from word 22 and begin execution at word 75″ — meaning skip the first 21 words and begin loading the program from the 22nd word. But several questions remained: Are 22 and 75 in decimal, or binary? Is the 75 before or after you remove the leading 22 words?

After a long while, I looked back at the closing ceremony video, and saw a bunch of what looked like null words at the top of the debug screen (they were hard to read, but looked like they were probalby all 0s). Counting blocks, I saw 18, which, in octal, is 22. So I had it backwards — I had to load the entire data stream, but load it into memory beginning at location 22, instead of starting at zero.

So once I’d worked out the file format and where to load the data, I typed “g 75″ and the program ran:

    R:TMW B3M W:412 M:HAK P: S->H M->O
    MICCKFJBZGDNQIHHYDNBCTKTNKLLTRFCJEJHBZUL 
    PUFIIDLCPJXXSRKHNLPPYJCUYXGTGDFUWDYJEKZDY
    Passwort eingeben:

This is pretty clearly settings for an Enigma machine (the German password prompt was kind of a hint as well). Wheels 4, 1, and 2, in that order. Ring settings for the wheels at T, M, and W. Stecker connecting S to H and M to O, and finally, set the rotors to HAK. Once all that is set up, type in the ciphertext (MICCKF…) and you get:

    xSOUTHxOFxNORWAYxNORTHxOFxMADAGASCARxEASTx
    OFxKYRGYZSTANxWESTxOFxBULGARIAxILITAHSx

So now I’m looking for somethig in some vaguely-defined region in Europe. Of course, there’s one problem: there’s an awful lot of planet that’s both east of Kyrgyzstan and west of Bulgaria. It seems that this is a hint, to read the last word backwards: “ILITAHS” backwards is “SHATILI,” which is a city in Georgia. Entering “Georgia” as the password in the emulator decrypts the final ciphertext and provides the answer:

    FIND X, TELL HIM: SOVIET RED PIRATE QUEEN

I sent that message off to Adam Cecchetti, the principal creator of the puzzle, and he confirmed that this was the right answer. He also confirmed that, as far as he knew, I was the first person (outside of the beta testing) to finish the puzzle. Of course, most people have probably forgotten about the puzzle at this point, anyway…

The hardest part of all this was the PDP-8 emulator: both finding one, and getting the code to properly load and execute. Interestingly, it is possible to solve this without ever actually needing the emulator.

PDP-8 operations use the three highest bits to define the operation code, and the lower 7 bits for data and for memory addressing. Stretches of code that contain just ASCII data, then, have those top three bits set to 0 and are therefore fairly easy to detect, especially when looking at punched cards. There are 5 blocks of ASCII data:

    LD 22 GO 75

    R1JND43L?

    Passwort eingeben:

    R:TMW B3M W:412 M:HAK P: S->H M->O
    MICCKFJBZGDNQIHHYDNBCTKTNKLLTRFCJEJHBZUL
    PUFIIDLCPJXXSRKHNLPPYJCUYXGTGDFUWDYJEKZDY

    ^A,!6G1Mg1*>+I)^N(UR4&7^N;R5,%g5& &=$g4:7"'

and

    HHello World

The first indicated where to load the data in the emulator, the next two blocks are easy to recognize as leading to the Enigma machine, and once one decrypts that, the final key Georgia is found as before. But what to do with it? The last block (Hello World) is an easter egg (a snippet of code just prior to the string actually prints the mssage out). It seems likely, then, that the fifth block (^A,!6G1M…) is a ciphertext. Performing an XOR operation against that string using Georgia as the key produces the final phrase, without ever needing the emulator.

Interestingly, not only was there an easter egg at the end, but a subtle joke embedded in the code. The string “R1JND43L?” was, according to Adam, a reference to earlier plans for the puzzle: They’d first planned to encrypt the final clue with AES (originally named “Rijndael”), then swithced to Lucifer, the precursor to DES. Finally, they simply used XOR.

In the end, this was a fun puzzle, though I have to admit that I’ve criticized it over the last few years. Reliance on a PDP emulator makes for a tough puzzle to solve, and I do prefer those puzzles which can be solved with paper and pencil alone. However, as I mentioned, this can be solved without the emulator, though it requires guesswork and a little luck. Of course, if one were to recognize the code as from a PDP-8, it’s a short enough program that it can easily be figured out just by reading the disassembled instructions.

Either way, I’m glad I finally took the time to finish the puzzle, and wish I’d tried this long ago. Complexity aside, it’s quite an interesting challenge, and I really enjoyed trying to figure out how the PDP-8 instructions worked. (I’d been fortunate enough to do some assembly on a Sperry/Unisys mainframe in college, and this brought back some fun memories).

Thanks especially to Adam Cecchetti (responsible for the PDP-8 code and co-designer of the puzzle), 3ric Jhanson (co-designer), and Aether (badge design), for a great challenge, and my apologies to all for taking four whole years to finish it.

[When trying to finish this, I half-disassembled the code using a script and a whole lot of referring back to Wikipedia. Adam was kind enough to send along a copy of his original source, and I've used that as an additional check / reference, and produced a detailed, annotated copy of the badge data. It's not really meant to be used as a source for an assembler, but instead lets you see what every row on every badge is, both code and data blocks. Click here to download a copy.]

ShmooCon 2012 Badge Puzzle

February 3, 2012 5 comments

For three years running, I (or I with a co-worker) have been the first person to solve the ShmooCon Badge puzzle. (I’m also, I believe, the only outsider to have solved the 2008 badge puzzle, but that’s another post). Seems like it’s time for me to stop playing.

So I asked Heidi if I could do the puzzle this year, and she agreed. We went back and forth many times over a few weeks, and got a lot of advice and suggested changes from G. Mark Hardy (who’d written the last three puzzles). Finally, just a few days before everything had to go to the printers, we put a fork in it and decided the puzzle was “done.”

Since the theme for the con this year was, loosely, gearheads, I chose a puzzle with some mechanical/crypto components. All in all, there were seven gear-shaped badges, several images in the program, and a couple extra bits of crypto text.

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 first element of the puzzle that everyone saw was, of course, the badge. In addition to the “expected” badge elements (ShmooCon, plus Speaker or Attendee or Staff), the badges featured:

  • Letters all around the edge, in the gear teeth,
  • A six-letter string at the bottom, and
  • A four-digit number at the top.

Hidden in the program was the first hint:

GET YOUR SHMOOS IN LINE! SLASH OR DOT! ONE’S HOT ONE’S NOT!

The hope was that this hint would encourage players to find the correct order for the badges, as well as the fact that they need to line up in some way. The trouble was, how do you order them? A natural guess would be to use the numbers, but are they supposed to go in numerical order or something else?

That was the point of the “slash or dot” element of the hint. If you were to add a slash to the numbers, where would you put it? Turns out, these numbers (selected by G. Mark) were actually the start dates for ShmooCon 1-7. Put them in the proper order by year, and that’s the order for the badges.

So badge data, in order, looks like this:

               Teeth (clockwise from top)
#  Bottom  Top   0 1 2 3 4 5 6 7 8 9 10 11
1  CGARIN  0204  Y I I E O E O E K T A  T
2  OEDNCE  0113  C O T R T A T U D W A  S
3  NATOKX  0323  H C O T M H C H S A U  C
4  NRONRT  0215  H A O T C N R L E U H  N
5  ESPEEE  0206  L E S K A E O K U D N  B
6  CRTCAT  0205  G A A D E R W W E S E  T
7  TEULDC  0128  A Y S H R H N Y L C S  E

That was “Stage 0.” The goal of Stage 1, then, is to read the message hidden in the six-character badge strings by stacking the badges in order and reading down the columns.

What’s interesting is that you could bypass the entire ShmooCon date index altogether. For example, if you looked at the frequency analysis for Stage 1 (the six-letter strings), you’d see something that looks remarkably like normal English text, with E being the most common letter, and C, N, and T tying for 2nd. It’s a small sample size, but even still definitely doesn’t look like a typical sustitution cipher output. This should tell the player that it’s some kind of transposition cipher — that is, the letters are simply scrambled, not changed.

So to solve this in that way, it’d be necessary to try to re-arrange the letters until you get words. As I mentioned later, “it’s best to try the easy approaches first,” so the easiest approach here would be to assume each six-letter string needs to stick together, and it’s just a question of re-arranging them to build words. If you look at the last letter of each row, there are only 5 letters in use: C, E, N, T, and X. So immediately, one might consider the words “CENT” and “NEXT.”

There are four ways to do this: The N and X remain constant, but you have to try two different rows for E and for T.

  CGARIN CGARIN CGARIN CGARIN
  OEDNCE ESPEEE ESPEEE OEDNCE
  NATOKX NATOKX NATOKX NATOKX
  CRTCAT NRONRT CRTCAT NRONRT

In two of these, the 2nd column spells “GSAR,” but in two of them, it spells “GEAR.” The other columns don’t do much, but there are only three other rows to try to add to the bottom to build new words with, so it should fall out pretty quickly. For example, if you add ESPEE next, then the first column becomes “CONCE” or “CONNE”, depending on what you picked for the fourth row, while the 3rd column ends with “TOP.” And so forth.

I don’t know if anyone actually tried this approach. I’m hoping some people at least considered it.

Regardless of whether you used the number index or just brute-forced the strings, the result of Stage 1 is instructions for Stage 2:

CONNECT GEARS READ TOP TURN ONE CLICK READ NEXT ETC

Again, thanks to G. Mark for taking one of our rough ideas (“wouldn’t it be cool if people had to actually connect the badges together and turn them to get a message?”) and making it into something that actually works. But how do you connect the gears? There was a hint for that, in the program:

Putting all the gears, in order, in an arrangement like that yields the first “machine” for this puzzle. To read this Stage 2 message, you’d:

  • Look at the top of a gear and read the letter
  • Turn the gears one click (top gears go clockwise, bottom counter-clockwise)
  • Look at the top of the next gear
  • Repeat

At the top of the first gear is “Y.” Turn the gears one click, and now the “O” that was at 1 o’clock on the 2nd gear is now at the top, so write down “O.” Turn gears again, and now the “U” that was originally at 10 o’clock on gear 3 is at the top. Keep doing this and eventually you get the message:

YOU TURNED THE GEARS
NOW REACH BACK
A CLASSIC CODE
YOU MUST ATTACK
WHO WON LAST THREE
HIS HANDLE THE KEY

I’d considered several different keys for Stage 3, but eventually picked my own handle. I did this partially because there’s a history of the puzzle-maker using his handle as a key or hint (about half of G. Mark’s puzzles feature GMARK as a key at some point). I also hoped that, in looking up my handle, players would find my writeups from past puzzles and see that one particular cipher appears again and again. That’s the “classic code” that’s used for Stage 3.

Plugging Stage 3 into a Vigenere decoder, then:

  • Ciphertext: JAKAL EPTYV UJXRR SEZVE KMORA PLUSG KVSCE
  • Key: DARTH NULL
  • Plaintext: GATHER VINS USE KEY TO SET THE GEARS PROFIT

Which brings us to Stage 4. As I was wandering around Friday night, I watched a table full of people working on the puzzle, and they’d already figured out how this stage works, even before they’d solved a single stage. Which was vaguely encouraging to me, to know that my contraption wasn’t that obscure.

Stage 4 required three elements: A ciphertext, a cipher, and a key.

The ciphertext was hidden on little “auto repair slips” scattered through the program (the “GATHER VINS” part of the clue). Collecting all 5, and putting the VINs in order based on the number in the middle of each, gives the following final ciphertext:

ZFFLKJBV1WHNNHPIB
FCJVBJRD2APJEYOPQ
HJJTZPQM3XLJYUQFH
ZJHIYZZP4WNJBNOVD
PVVEWBLG5SPHISYEJ

The cipher is a keystream-based cipher, where the keystream is generated by a 3-gear machine printed in the program.

That machine produces a different keystream (or, more accurately, a different segment of a single very long keystream) depending on what position the gears are initially set to. That starting position is the final “KEY” mentioned in the clue. In the image in the program, the gears are initally set to “TSG.”

But what’s the actual key you need to use? I thought and thought for a while on this one… Originally I wanted to use “OCT” (for ShmooCon 8), and figured that “10″ in octal would be an interesting sort of hint, until G. Mark reminded me that “10″ also looks like binary. Doh. So after about 20 minutes of brainstorming, we finally came up with “CAR” (Duh!!), and then I decided on something slightly more evil.

The key for the final stage is “KEY.”

I hope that annoyed…er, amused…at least some of the players.

Anyway, once you set the gears to start at KEY, you then read the top of each gear, turn, read the top of each gear, turn, etc. Not quite the same as the first machine, but I thought reasonably obvious (and as I said, at least one team figured that part out on Friday afternoon).

To solve this final stage, you take the ciphertext:

ZFFLKJBVWHNNHPIBFCJVBJRDAPJEYOPQHJJTZPQM
XLJYUQFHZJHIYZZPWNJBNOVDPVVEWBLGSPHISYEJ

and subtract the keystream:

BRLEKOXSIUJSDYKFBRYINNMPJWCATGCQWHCTOEMZ
RHQKYISLSJOGYIWBSVIKTMRLWNKTPBQCECGXEWUR

to get the plaintext. In this case, we’re numbering the alphabet from 0 (so A is 0, and Z is 25). So Z-B is 25-1 or 24, which is Y. F-R wraps around and gets you O., etc. You can also use the standard Vigenere tableau (it’s essentially the same operation, mathematically), or the “One Time Pad” tool on my favorite cipher puzzle site rumkin.com. No matter how you attack it, the final ciphertext decrypts to:

YOU HAVE DONE VERY WELL
NOW FOR THE FINAL CHALLENGE
TO WIN WHAT CAR DOES BRUCE STILL HAVE ON BLOCKS

I wasn’t in the building when the winning team came in with their answer, but apparently they actually walked up to Bruce and asked him. Informed that he would not be able to answer the question, the winners huddled over the con program for a while, then after additional input from Heidi, went off to “ask the Internet.” Ten minutes later, at about 12:40 on Saturday, they returned with the right answer: “Volvo.”

Congratulations to Mike Herms and Matthew Bocknek for solving the puzzle! I hope you enjoyed it.

(click here for the solution presentation from the closing ceremony.)

How to Lose $1000 in Vegas Without Even Gambling

August 30, 2011 1 comment

On July 15, Fidelis Security Solutions announced that they’d be running a crypto puzzle at Black Hat. And that the prize would be $1000. So, naturally, I was quite interested. I went to their site, downloaded the puzzle, and set to work:

^
¥Ð§µ    
¶®Æä
æ©×ä
÷ijŒĐ
ƆķėIJ
ŦůŶū
ƂƐƔƆ
ŦƉƶǴ
ƆƅƦƬ
džƹɇʃ

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. The text above is all that you need to get started, or you can click here to see the ciphertext and the hints that were revealed during the conference.

It’s immediately obvious that we’re not looking at straight ASCII. I figured it would be UTF-8 encoded, and verified that quickly. But the question then was whether the decoding work should be in UTF-8 or if, for example, I needed to convert it to UTF-16 first. I even considered that maybe I needed to look to the official Unicode name for each character, instead of the binary representation of it. Here’s the hexdump of the ciphertext, in UTF-8 (with newlines dropped for clarity):

5e 
c2 a5 c3 90 c2 a7 c2 b5 
c2 b6 c2 ae c3 86 c3 a4
c3 a6 c2 a9 c3 97 c3 a4
c3 b7 c4 b3 c5 92 c4 90
c6 86 c4 b7 c4 97 c4 b2
c5 a6 c5 af c5 b6 c5 ab
c6 82 c6 90 c6 94 c6 86
c5 a6 c6 89 c6 b6 c7 b4
c6 86 c6 85 c6 a6 c6 ac
c7 86 c6 b9 c9 87 ca 83

The little ^ character at the beginning made me think of XOR — since in many languages, that’s the operator used for that. So I need to find some binary key stream that, when XORd with the ciphertext, will give me plaintext.

I played with that for a while, then watched their little promo video again. And there, at the very end of the video, the phrase “ALL YOUR ¥Ð§µ ARE BELONG TO US” zooms past the viewer. So “¥Ð§µ” == “BASE”? Okay, that’s something else I can work with.

Another interesting thing that I noticed: in UTF-16, the first byte of each two-byte pair (each character is represented by two bytes) increases gradually over the entire ciphertext:

005E 
00A5 00D0 00A7 00B5 
00B6 00AE 00C6 00E4 
00E6 00A9 00D7 00E4 
00F7 0133 0152 0110 
0186 0137 0117 0132 
0166 016F 0176 016B 
0182 0190 0194 0186 
0166 0189 01B6 01F4 
0186 0185 01A6 01AC 
01C6 01B9 0247 0283

In the UTF-8 version, the first byte varies among c2, c3, c4, c5, etc., but is generally increasing (just not quite as clearly in the UTF-8 version). So it seems pretty likely that the first byte is irrelevant.

After a few days, pulling the puzzle out every now and then, the original puzzle page was removed and replaced with something that essentially said “You’re too early. Come back later for the puzzle.” Damn — maybe what I’ve been playing with was just a teaser, and not the real puzzle. Okay, I’ll forget about it for a while (and finish my talk slides…)

Fast forward to Black Hat, I stop by the Fidelis booth. And discover that the original puzzle is in fact the real puzzle. Arrgh! I could’ve been working on this all along!

Every few hours over the course of the conference, they sent out hints via Twitter. Predictably, the first few hints don’t help me at all, though one tweet “get to know xxd” helps. As sending the original ciphertext through xxd would just give me a straight UTF-8 dump in hex, I now know I’m supposed to use that encoding and not convert to UTF-16.

But that’s not helping me any. They tell me in person that the “BASE” bit wasn’t meant to mean anything, so that was just a red herring. They also tweet some of the plaintext (“Fidelis” is in it), but still I’m getting nowhere. I tried writing some tools that’d drag “Fidelis” across the ciphertext, looking at what the XORd keystream would have to be in order to produce that plaintext. That gets me nowhere.

A later tweet says that there are only 20 characters in the plaintext. Ooooh, that changes things. Now I’m playing with XORing two bytes in a row (like A5 ^ D0, then A7 ^ B5, etc.) but again, no luck. Another hint tells me that ¥ and µ are the same, but that doesn’t help either (one’s encoded as A5, the other as B5), and if we’re talking about two-character sequences, then now I’m really confused).

Finally, at 1:07 on Thursday, they released this hint: “‘C2A5′ =~ /.{3}(.)/”. This tells me that for every four-character hex sequence, I only need to look at the last character.

I get off the escalator, pull up the ciphertext hex on my phone, and start decoding ASCII in my head. “P…u…n…d…” Oh, crap. Finding a corner to sit in, I open the hex in a text editor and pull up an ASCII chart. What I end up with is this:

a5 90 a7 b5 
b6 ae 86 a4
a6 a9 97 a4
b7 b3 92 90
86 b7 97 b2
a6 af b6 ab
82 90 94 86
a6 89 b6 b4
86 85 a6 ac
86 b9 87 83

becomes:

5 0 7 5 
6 e 6 4
6 9 7 4
7 3 2 0
6 7 7 2
6 f 6 b
2 0 4 6
6 9 6 4
6 5 6 c
6 9 7 3

which then becomes:

50 75 6e 64 69 74 ....

or

Pundits grok Fidelis

I immediately went to the Fidelis booth, walked up to Will (the creator of the puzzle), looked him in the eye, and simply said “Really? REALLY!?” That got a laugh. Apparently, in his words, I gave him “too much credit.” I was looking for an actual, cryptographic solution, when really the answer was staring me in the face THE ENTIRE TIME.

And if I’d taken the time to really think about it, I should have solved this in 10 minutes just by visual inspection. Remember when I said that I’d determined pretty quickly to drop the initial byte of each pair? The “c2″ and “c3″ and so forth? Well, part of figuring out whether it was UTF-8 or UTF-16 involved me looking at the Wikipedia pages for UTF. Which told me that when a pair begins with c2 through cf, the next byte MUST start with 8, 9, a, or b. So I knew, almost from the beginning, that not only did the first byte have no real bearing in the puzzle, but the next nybble (the first character of the 2nd byte) had no bearing either. But that fact just never registered.

In fact, hindsight has helped me to recognize not just one, but two different ways to look at the data and quickly solve the puzzle. Let’s look at the hex dump again (with column headers to make the discussion easier):


AB CD EF GH IJ KL MN OP
-----------------------
c2 a5 c3 90 c2 a7 c2 b5 
c2 b6 c2 ae c3 86 c3 a4
c3 a6 c2 a9 c3 97 c3 a4
c3 b7 c4 b3 c5 92 c4 90
c6 86 c4 b7 c4 97 c4 b2
c5 a6 c5 af c5 b6 c5 ab
c6 82 c6 90 c6 94 c6 86
c5 a6 c6 89 c6 b6 c7 b4
c6 86 c6 85 c6 a6 c6 ac
c7 86 c6 b9 c9 87 ca 83

Looking at the columns, it should have been even more obvious. I’ve already discussed dropping columns A, B, E, F, I, J, M, and N (I came to this conclusion shortly after I originally started the puzzle). But what I didn’t “grok,” but should have, was that I needed to drop columns C, G, K, and O as well. What’s left after that? Column D is either a 2, 5, 6, or 7. Column H is 0, 3, 5, 7, 9, e, or f. Column L: 2, 4, 6, or 7, and finally the last column, P, which is 0, 2, 3, 4, 5, 6, b, or c. So two columns (H and P) with truly random-looking numbers, and two columns (D and L) with 2, 4, 5, 6, or 7. In ASCII, a byte that begins with 4 or 5 is a capital letter, and 6 and 7 denote lowercase letters. Bytes beginning with 2 are punctuation — in this case, the 2 is always paired with a 0, or a space.

Another way to look at this, mathematically, is in terms of bits of entropy. Columns A, E, I, and M have 0 bits, since they never change. Columns B, F, J, and N have 4 bits, since they’re anything between 2 and a. Similarly, columns C, G, K, and O only bring 2 bits to the game (since 8, 9, a, and b are all 10xx in binary, it’s just the last 2 bits that change). And D and L have only 3 bits of entropy (2, 4, 5, 6, and 7 all fit within 0xxx in binary). Finishing it up, we have:


AB CD EF GH IJ KL MN OP
-----------------------
04 23 04 24 04 23 04 24

One can pretty readily see what might’ve been obscured before: That each line has 2 repeated pairs (04 23 04 24). Looking at the UTF-16 version, again, we see that the characters are taken from increasingly higher code pages in the Unicode alphabet…which further strengthens the supposition that columns B, F, J, and N are all meaningless (since they’re largely derived from the Unicode pages as well). So instead we have “00 23 00 24″ or just “23 24″. That’s 11 bits….but we only need 8 bits for letters (or really, 7 bits for ASCII). But wait — the 2s here are also largely driven by the Unicode layout…if we drop those, now our data has “03 04″ bits, or 7 bits total. Just enough to build ASCII data. And sure enough, that’s what it does.

The plaintext wasn’t even encrypted. Just hidden in noise.

I should have walked into their booth first thing Wednesday morning, handed them the solution, and walked away $1000 richer.

To say I was frustrated…well….that doesn’t begin to cover it.

So in the end….was this a good or bad puzzle? As much as it pains me to admit it, this was an excellent puzzle. It made me think about UTF-8 encoding (which many, especially us old dumb-terminal types, overlook in favor of flat ASCII). It had a red herring (the ^ making me think of XOR). It had obvious, blatant signs that should have been seen, at least by experienced cryptographers. Like most good riddles, it had a simple, obvious, easy-to-execute solution. Also like most most good riddles, I felt like a complete idiot for having missed the answer.

Thanks, Fidelis, for reminding me to keep my eye on the basics, and for driving home the first rule of cryptanalysis, as defined by the late Robert Morris: “Check for plaintext.”

Great Googly Moogly! I’m speaking at Black Hat!

July 28, 2011 1 comment

One week from today I’ll be presenting a talk at Black Hat. Black Hat! Wow. I’m still a little amazed at this turn of events, but am trying not to dwell on it for fear of slipping into a blind panic. :)

But I think I’m ready. I submitted a nice long white paper a couple of weeks ago, and sent in my presentation yesterday. I’m comfortable with the material. I (think) I’ll be able to intelligently field questions. I’m pretty sure I won’t be a complete, blithering idiot on stage. And to settle my nerves, I’ve put in an early order for a bottle of Drambuie. Though I think I’ll save that for the obligatory post-talk celebration.

Of course, this isn’t the first time I’ve spoken at a conference — I was lucky enough to get a spot on the closing panel at ShmooCon this past January. There were four of us on the panel, so I didn’t get to speak long (only about 10 minutes). But being the closing session, most of the con was there — perhaps as many as 1000 people. I haven’t seen the video, but people tell me that I did well, so I guess there’s really no reason to be nervous here.

I still have yet to write up anything about that ShmooCon appearance, and hopefully I’ll finally do something soon. There’s been quite a bit happening in the password cracking / authentication business in the past six months, and I have a lot of interesting ideas swirling around that I really need to put down for others to comment on. Maybe I’ll write some on the flight to Vegas. You know, to keep my mind off of my talk.

It’s actually my talk that I’m writing now, to, er, talk about. Since joining Intrepidus Group, I’ve spent a good deal of time helping to assess risk and craft security guidelines for iOS devices in large enterprises. A large part of securing iStuff in the enterprise relies upon the use of Mobile Device Management technology (MDM). MDM has been around for a while, especially for some of the older, more corporately-established mobile devices (like BlackBerry or Windows Mobile). Last summer, though, Apple jumped into the arena, adding support for their devices as part of iOS 4.0.

Unfortunately, the way that MDM works for iOS hasn’t been very well described, publicly. Which makes it difficult when you’re trying to demonstrate to a customer that it will make their enviroment more secure.

So I set about doing everything I could to understand, at a deep, technical level, exactly how the technology worked. We were already pretty satisifed, abstractly, with the features and capabilities of Apple’s MDM, but we felt it necessary to go that extra step to truly know what it’s doing. The end result of this is that we now have a mostly-complete understanding of how the protocol works.

Which is what I’ll be talking about next week. I start with how iOS settings work, move into additional features available through the iPhone Configuration Utility, and then start talking about MDM. The talk shows in detail how MDM uses the Apple Push Notification Service, and describes the message format used to make that notification. It’ll also document the interaction between device and server, from authentication and enrollment to receiving commands and providing responses. Enough detail is provided to enable you to write your own experimental MDM server (or, you could simply use the one I’ll be releasing at the talk).

Finally, I’ll talk about some limitations and weaknesses I’ve uncovered, and their potential security ramifications. There might even be a surprise for those hardy enough to sit through the whole talk.

This is going to be quite the experience for me. If your work involves securing iOS devices, especially at the enterprise level, please drop by and give a listen. If you can’t make it, check out the Intrepidus Group website after the conference — I hope to write up some of the more interesting bits of the talk for a standalone post, and we should also have the slides, white paper, and source code available for download at some point.

See you in Vegas!

Categories: Conferences, iOS, Security
Follow

Get every new post delivered to your Inbox.