Archive

Archive for May, 2010

QuahogCon Flag Puzzle

May 20, 2010 1 comment

Shortly after completing the ShmooCon 2010 badge puzzle, G. Mark Hardy told me in that he’d be contributing a puzzle for QuahogCon, the last weekend of April. I knew I wouldn’t be attending, so I offered to proofread the puzzle before he published it. I never heard back, so a couple days before the con I asked if I could play along at home (provided, of course, it was okay with the conference organizers).

He forwarded my request to the con, which reacted by posting a note on the
official QuahogCon website:

G. Mark couldn’t make it to QuahogCon, but he put together this great puzzle for us. David Schuetz, a veteran puzzle solver also can’t make it to QuahogCon, but will be solving the puzzle remotely for fun. It’ll be a beat the clock scenario to see who solves it first, David or an attendee.

D’oh! This was posted about midday on Saturday (I saw it a little before 1:00 in the afternoon). I’d hoped to leisurely play along for fun (and, I’ll admit, bragging rights), but I really hadn’t expected a gauntlet to be so publicly thrown down. I wasn’t even at home when I saw the message, and worse, the conference attendees had received the puzzle the previous evening. Fortunately, we were on our way home at the time, and I was lucky enough to get a “pass” to focus on the puzzle for a couple hours. I mean, once my name was used, I really didn’t have a choice, did I?

While still in the car (not driving!), I was able to look at the puzzle:

Solve Me First
Solve Me First
  Then Solve Me
Then Solve Me

If you’d like to try to solve this yourself, then STOP now, as the rest of this post is full of spoilers. Those two images are all you need (from the con, anyway) to solve the puzzle. Click on each image for a higher-resolution copy.

I counted squares, and immediately concluced that the first stage was a Sudoku puzzle. I didn’t have a Sudoku solver on my phone, so I tried to be patient. Once we got home, I gathered up a netbook and a pad of paper, and set to work. First, I had to convert the nautical flags to letters. This was pretty simple, thanks to the wonders of Wikipedia. Turns out, the flags spell out (on the diagonal) “QUAHOGCON”.

Q   O     U A    
  U     Q     H  
C   A     N     O
      H     O C G
        O        
N         G   U  
O A         C    
  C H     A   O  
U Q G O         N

Problem is, that’s only eight letters, and we need nine, to map to the numbers 1-9. Well, shoot. Let’s just try and solve it anyway. So with pencil and paper, and as it turns out, only one easily-rectified mistake, I solved the Sudoku puzzle.

Q N O C H U A G  
G U   A Q O N H C
C H A G   N U Q O
A   U H N Q O C G
H G Q U O C   N A
N O C   A G Q U H
O A N Q G H C   U
  C H N U A G O Q
U Q G O C   H A N

The trick here is to just trust your instincts and go with it. Assume the last number is a “space,” and that you simply don’t have any on the board when you start. Getting a Sudoku puzzle with one number missing altogether probably doesn’t happen much, but that doesn’t mean it’s impossible. At this point, it’s nearly 2:00 and I have a completed Sudoku square. What’s the second square spell?

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

Random text. Okay, so we’ve got an 81-character string of random text, in a 9×9 grid, and another string of not-quite-random text, in another 9×9 grid. One’s the ciphertext, the other is the key. Put ‘em together, and you’ve solved it. At this point, I’m getting pretty excited — it’s a one time pad. Simple. Surprisingly simple. But wait, how do I do it?

I figure that the trick here is to take every character in stage 2 and offset it by some number based on the key found in stage 1. But what are the offsets? Do the letters Q, U, A, H, O, G, C, and N (and space) map to 1-9, in order? (that is, do I assume Q = 1, U = 2, etc.)? Or is it alphabetical? (A = 1, C = 2,G = 3, etc.) Does the space come first, or last, in the list? Should the numbers be 0 through 8, or 1 through 9?

I set up a couple of squares in a spreadsheet to do the alphabet addition for me, and tried a bunch of the possibilities. After about an hour, I’d gotten nowhere. And I can hear the kids starting to get out of hand outside (plus, I felt a little guilty playing a game while my wife’s doing yard work). So I decide to take a break. During a pre-break visit to in the little cryptographer’s room, it hits me — I’m doing it wrong.

The letters QUAHOGCN don’t equate to 1-8 (nine, with space). They equate to QUAHOGCN. That is, I don’t have to convert the letters to numbers, I simply use the letters as-is. Duh.

What do I mean by that? It’s simple modular arithmetic, using letters as a base-26 number system. Take A, for example, and “add” B to it. B is the 2nd letter of the alphabet, A is the first, so 2 + 1 = 3, or C. A + B = C. C + D = G. And so forth. When you reach the end of the alphabet, wrap around — so Z + A = A. In this case, the first square of the key is Q, and the first square of the ciphertext is C. Q + C = T. The second squares are N and A. N + A = O. O + Z = O. The plaintext starts with “TOO.” How should I handle the spaces in the key? Let’s just treat them as zeroes, so we’ll replace them with Z (since Z plus any letter gives the original letter).

I tweak my spreadsheet, and out comes the answer. No further decryption necessary. But, wait, there’s a bug. One of the lines is wrong. No matter, it’s pretty easy to see what it’s supposed to mean. At 3:15, I send off a quick tweet to @quahogcon, they follow me, and I send them the solution in a direct message. Puzzle completed, challenge met. Woohoo!

Here’s the result grid:

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

And the final message, with corrections and punctuation (keeping with tradition, “Z” is read as a space):

Too bad we didn’t get Seth MacFarlane to talk. We will try for that next year. G. Mark.

So in just about two hours of actual work, I’d solved the puzzle. And I’d managed to be the first, too. I was now able to go outside and help with the yard work. :)

Later that night, I hadn’t seen any activity on twitter talking about the puzzle, and it occurred to me that I might’ve scared people off. I wrote the con organizers, and suggested that they remind people that I wasn’t playing for a prize, and a little after 11 that night, they did just that. I’m told they also provided a few hints during the closing ceremony. But over the next several days, I never heard of anyone working the puzzle.

It’s now been over three weeks since the con, and I can only presume that people have given up completely. Why is that? Was the puzzle too hard? I wouldn’t think so. Personally, I thought it was pretty easy (I mean, even with the better part of an hour spent in a blind alley I still solved it very quickly) (and I’m famous for going down crazy blind alleys). Everything about it was pretty straightforward.

The few people I heard from said they stumbled on the Sudoku bit. As I said, I just ignored the problems and forged right ahead, which may be part of why I was able to get that stage solved quickly. Over-analyzing the puzzle there could certainly slow you down.

But even then, how obvious is it that you’d add the two parts together? Well, it’s clear that stage 1 can’t have any real meaning, at least not in a linguistic sense, as it’s really the result of a mathematical process. It can’t be text. And it doesn’t give any kind of “Ah-Ha!” feeling when you solve it, other than the satisfaction a Sudoku usually does. So it must mean something else.

Stage 2 is more clear. It looks pretty random, and has a fairly nice distribution of letters — unlike the first stage, which has only eight letters and a space. So it should be pretty obvious that one’s the key while the other is the ciphertext. At least, obvious to the kinds of folks who enjoy these sort of challenges.

And that’s probably where the game fell down. There’s only a limited fraction of any community that enjoys these kinds of puzzles. Even in the hacker / security community, where that’s likely to be larger than in the general public, it’s still a limited fraction. And of those, only some fraction will even feel in the mood to try, and only some fraction of them will keep at it beyond a few initial attacks. Especially so if there are interesting talks to hear or parties to attend. Add to that the fact that QuahogCon had only about 150 attendees, and you can see that the potential pool of players was probably pretty small.

That pool can be enlarged somewhat if the prize is good enough. But I’m not sure what the prize was, here — it wasn’t shown on the web site, and I didn’t see the opening or closing ceremonies. So maybe it wasn’t cool enough to drive more people to try. Or maybe it was, but people still couldn’t figure it out. I don’t know.

Maybe there’s a lower limit to the size of a con, below which it’s just not going to be worth having this kind of contest. Even at ShmooCon, with 10 times as many people, only two teams solved the badge puzzle. Then again, maybe we just need to get more people to develop their skills. Which, I suppose, is part of why I’m trying to document these contests. It should be obvious that I really like being the first to solve puzzles. But it’s also a lot more exciting when there’s competition. Hopefully, we can start getting more people involved, especially if the puzzles remain as good as this one was.

UPDATE! I had the pleasure of meeting Dennis Brown, the designer of the QuahogCon badge, at a talk at DEF CON 18. He’d tweeted a few days earlier that they had a couple extra badges lying around, and I asked if I could have one as a prize for solving the puzzle. He generously agreed, and gave it to me at the talk. It’s really cool, and was fun watching it get totally owned by the other QuahogCon badges in the audience. Too bad I only have one, and can’t participate in any new Zombie battles….

Categories: Conferences, Cryptography

THOTCON 0×1 Puzzle

May 11, 2010 2 comments

So on April 23rd, while I was waiting for the QuahogCon puzzle to post, over in Chicago THOTCON was starting. And a few days later, I saw a tweet from @sak3bomb saying:

I am sad that no one found any of the links I hid in the #thotcon program. Maybe next year…

My immediate response was to ask “There’s a puzzle?” He replied that he wanted to give the attendees from the conference a couple more days, then on April 30th, the program was posted to the THOTCON site. I kind of glanced at it, saw a few URLs hidden in the front page ASCII art, and forgot about it (as I had a trip coming up and had to prepare).

On May 4, he tweeted that the challenge was live. And that there was a prize. I guess I hadn’t realized it was a full-out challenge. Damn. And here I was, thousands of miles from home, with only a new iPad and a laptop with BackTrack3 on a CD (no hard drive) (long story). Could I do this? Well, I guess I’d better try.

So I checked into my hotel room, grabbed the iPad, and went out to dinner. While there I sort of skimmed the program again, figured out what I was up against, and formulated some next steps in my mind. I got back to the hotel, and started in earnest.

If you’d like to try to solve this for yourself, then STOP reading now. The rest is full of spoilers. As of right now, the contest is still online. Start by grabbing the THOTCON program. I may try and figure out how to archive all the needed bits later.

The inside of the program had some QR codes. I didn’t really relish the idea of finding the right apps to install on BT to be able to cut them out and then send them to an online QR reader, so I sort of crossed my fingers and hoped they wouldn’t be pertinent to the puzzle. And instead, I focused on the big ASCII art on the front page. Embedded in that were the following strings:

One of these (I’m not gonna say which one! :) ) is a RickRoll. I closely watched the entire video, just to be sure there wasn’t a clue spliced in the middle. Never actually sat through the whole thing before. Another resolved to a Yahoo! address that didn’t give me anything other than an error. But the hax.by/sakebomb address looked intriguing. Clicking on that gives the following text:

HAX? I should learn to spell.

6148523063446f764c3364336479356f5958686965584e6861325669623231694c6d4e766253397063323973646d566b6447686c624746745a574e79655842306279383d

That’s a big string of hexadecimal numbers, which when decoded, gives this:

aHR0cDovL3d3dy5oYXhieXNha2Vib21iLmNvbS9pc29sdmVkdGhlbGFtZWNyeXB0by8=

Now we’ve got a base-64 string. Just like the hex string, Google finds an online decoder pronto, and I find this:

http://www.haxbysakebomb.com/isolvedthelamecrypto/

At that URL is a very simple page with a single link:

Don’t be so audacious, enjoy the music.

Standing – VNV Nation

So far, it’s gone pretty fast, but at this point I hit my first roadblock. The link is to a file called, simply, “standing,” with no extension. But it has a title attribute (seen when you hover the mouse over the link) of “WAV”, so it’s obviously a sound file. My browser refuses to play it. At this point, I gotta give up on the iPad and boot up BackTrack. Downloading it, I see that it’s actually an MP3 file, and so I listen to it. Just like the RickRoll video, I endure the entire clip (actually, this wasn’t too bad). At the very end of the song was a short burst of high-frequency noise.

Armed with basic command-line utilities on BT like sox and such, I cut out the last couple of seconds, and slow them down to about 20% of normal speed. I can barely make out a voice, possibly computer generated, reciting a new URL:

http://www.haxbysakebomb.com/theplotthickens

Ah. The plot thickens.

The browser finds itself pointed at the new page, and I see three pictures: Iron Man, the Star Wars cast, and a Dalek. All made to look steampunk. Very cool stuff, actually.

Pretty quickly, all the images were downloaded, and hit with the strings command to look for hidden text. After the image data in ironman.jpg is:

At least you are looking…

and after the data in starwars.jpg is:

If I were you, I would look for a 4th image ;-)

There’s nothing at the end of the dalek.jpg image. However, near the beginning of that file, in a JPEG comment field, is the word:

dec0de

So now I’ve got a pretty strong incentive to look for a 4th image. I’m not sure what the dec0de text means – maybe it’s significant, maybe it’s not. I look up the source on the web page, and find a 4th image listed after a couple screenfuls of blank lines. It’s got a “display=none” attribute so the browser won’t show it. I download that image and look at it.

It’s actually a funny picture – sort of a rook/castle looking thing, but with a big door and windows. The way it’s rotated, it looks like it’s got a wide-open mouth and is screaming. Or maybe that’s just a side effect of the caption, which reads, simply, “AAAAAAAAAAAAAHHHHH!!” I’m not sure. Either way, there’s nothing that I can find in the image file. No extra data, no comments, no useful EXIF data, etc. I did find the original (or another copy) of the image online, and the file was definitely different, so perhaps it’s been modified for the contest. Or perhaps Sak3bomb just used a different source. Hard to say.

AHH.jpg

So my first thought is that maybe there’s some kind of steganographic hidden message in the last picture. Or maybe it’s hidden in dalek (and that’s the actual “4th image,” while AHH.jpg is just a red herring.) (arguing in favor of this is the fact that this 4th one isn’t steampunk, and can really be viewed as a visual expression of my frustration at this point of the game.) I search some for JPEG stego tools, and find a bunch of different tools (like jphide and jsteg). But most of them are pretty old. And none of them give me anything useful, though I try the tools against all four images, using no password, “dec0de,” “AAAAAAAAAAAAAHHHHH!!”, and other such words. Nada. Zip. Zilch.

It’s late, so I go to bed and put it off until the next evening.  I have a little back-and-forth with Sak3bomb via twitter direct messages, but don’t really get much that’s helpful. Though eventually the conversation does confirm in my mind that, yes, there’s some kind of steganography going on here. Further searching eventually gets me the tool StegHide. But it’s a Windows application. I try running it under Wine, but I’m missing some key DLLs. I find those DLLs, and extract an installer. Which then installs the DLLs. Which then, finally, lets me run the app. Dammit, for all this work, this better be the right one.

And, yes. It is. Using the password “dec0de” against AHH.jpg gives me a bunch of odd-looking binary data. Trying it with a different password gives an error message – so instead of getting essentially random binary data, like the other apps gave me, I’m getting some confirmation right out of the gate that I’ve found the right tool. And I can trust the data I got to be the next stage.

But what does this data mean? Here are the contents of the file, seen in a classic hex dump view:

0000000: eff1 feee f1fe eef0 feee f1ee eee0 fefe
0000010: f1ee eef0 eeef e0ee eef0 fefe e0ee eff0
0000020: eeef f0fe eef0 eefe f0ef fef1 eeef e0ee
0000030: fef1 eeee f0fe eff1 effe f1ef fef1 eeee
0000040: f0fe eef1 efef f1ee fef0 eeee e0fe fef0
0000050: eeef f0fe eff1 effe f0ef eee0 fefe f0ef
0000060: fef0 efee f0fe eef1 eeee e0ee eff0 eeef
0000070: f0fe fee0 eeee f0fe eef1 feef f0ef fef0
0000080: feef f0ee eee0 efef f1fe eff1 feef f0ee
0000090: eee0 eeee f0ee fef0 effe f1ee eef1 feee
00000a0: f1ee eff0 effe f1ee eef0 feef f0ef efe0
00000b0: fefe e0fe eff0 eeef f0fe eff0 eefe f0fe
00000c0: eef0 eeef e0ef eef0 efee e0ef eee0 eeee
00000d0: f1fe eef1 eeee e0ee eff0 eefe

Looking at the text with strings, or cat, or anything else, just shows me a bunch of extended Latin characters. My first thought was that this is a bitstream to create a picture. I write up some tools to spit it out, in ASCII, at varying resolutions. There are 220 characters of 8 bits each, so that means 1760 pixels total. That can be, obviously, 1760×1, or 880×2, 440×4, 220×8, etc., etc. Lots of possible ways to slice it. And it can be mapped out left-to-right, row-by-row, or top-to-bottom in columns, or maybe across then down one character at a time. Everything I try just doesn’t quite work. I can barely see numbers forming, lots of 3s and 9s and such, but nothing that quite looks actually readable. At this point, everything, not just the ASCII output, looks blurred, and I notice it’s after midnight. Damn. I feel like I’m so close, too!

The next morning, I write down some notes that I can sneak looks at while at work. And one of the first conclusions I come to is that I wasted at least a couple hours trying to force this into a picture – there simply isn’t enough information here to be a picture. For one thing, there are only 6 values used throughout the entire message: e0, ee, ef, f0, f1, and fe. But I really don’t have much chance to look at it during the day, and it’s put on hold until I get back to the hotel.

Once back in my room, I try and look a little closer for other hints. Maybe the bits spell out Morse code – “E” being “1110” could be a dash followed by a dot…etc… But, no, that doesn’t really work out either. Again, not enough information. But there’s definitely something about threes here – the first byte of each 3-byte block seems to always be ee, ef, or fe, and the 2nd byte seems to always be e0, f0, or f1. The stego key had three bytes, and was conveniently a hex string as well. So I try doing a bitwise exclusive or using dec0de as the key, scribbling it by hand on paper. And I see this:

ef f1 fe
ee f1 fe

turn into this:

1 1 <space>
0 1 <space>

Damn, that looks like I’m onto something! Okay, this is too much to do by hand (and I’ll probably screw it up at some key point), so let’s write a script. The output, once I turn multiple consecutive spaces into line endings, looks like this:

11 01 00 0100
100001 000
010010 000 01 101 0 1000 111 11 1000 011110 000
0010 111 010
01 0100 0100 010010
000 01 101 0 1000 111 11 1000 0000 01 1001 010101 1000 1011
10010 100 0 0001 10010 10 001 0100 0100

The extra spaces within each block of numbers tell me this can’t be binary. But could it be Morse code after all? I try assuming that 1s are dots and 0s are dashes, and get “INMY” for the first “word,” but then the rest of it quickly turns into mush. Okay, switch it around: 0 is a dot, 1 is a dash. That produces:

mail
-s
"sakebomb's for all"
sakebombhax.by
/dev/null

Wow. Okay, the mail address is wrong… Not sure if that’s a bug or if I’ve messed up in the decode. I’m going to assume it’s really “sakebomb [at] hax.by” and now my completed result is this:

mail -s “sakebomb’s for all” sakebomb[at]hax.by /dev/null

Normally, I’d just pop open a terminal window and run that. But I’m on BackTrack, and don’t really have a mail server. So I log into webmail and send a “Hope I got this right” email to sakebomb with “sakebomb’s for all” as the subject. And then I get worried, that maybe this is some kind of auto-response server that’s actually looking for a completely blank email, and send a blank message as well. Finally, at 5:58 (my time), while hitting refresh to see if another clue got mailed back to me, @sak3bomb tweets that I’ve just won the contest. W00t!!

This makes the fourth major puzzle I’ve solved so far this year. And I think that, of those four, it’s the most complicated. Perhaps not the most difficult, cryptologically, though the steganography bit was very tough to crack. It was pretty obvious that the “dec0de” string could be used as a password, but the problem is that there are literally thousands of ways that one could encode data inside a JPEG image. It was only through sheer perseverance that I finally found the right tool to extract that data. And then it was a bit of a leap to get the XOR working, especially after some hours trying to force it into a bitmap, and another leap to Morse Code (not as big a jump since I’d already wondered about Morse anyway). Though it was harder than most, it did have one very important thing going for it: multiple clear stages. It really helped to be able to say “Okay, got this part, what’s next?” without worrying that an early mistake could ruin future progress.

So, let’s sum up the solution:

  • Stage 1:
    • Read the program, find the hidden URLs, get Rick-Rolled, and eventually land at a page with a long hex string.
    • Convert that hex string into ASCII, and get a base-64 string as a result.
    • Decode that base-64 string and get a new URL as a result.
  • Stage 2:
    • Download the music file linked on the webpage.
    • Extract the last 4 seconds of the file.
    • Slow that snippet down to about 20% speed.
    • Listen to the result, and get a third URL.
  • Stage 3:
    • Download all three images
    • Find hidden text in each image, especially the key “dec0de”.
    • Find and download hidden fourth image.
    • Locate a copy of CryptoBola and extract hidden data from the fourth image, using dec0de as a key.
  • Stage 4:
    • Take the output of the steganography tool and XOR each byte in turn against de c0 de to get a new text of 1s, 0s, and spaces.
  • Stage 5:
    • Read that text as Morse code, with 0 representing dot and 1 representing dash.
    • Follow the directions in the result (send email to the given address with the subject “sakebomb’s for all”).

The first two stages went pretty fast, possibly less than an hour (I didn’t record times in my notes). I spent another couple hours on Stage 3, and then maybe another hour the next evening. That second evening I spent about three hours fighting with Stage 4. Then on Thursday, maybe an hour to find the right solution to Stage 4, decode it in Stage 5, and win the contest.

What did I win here? Well, I don’t know. There’s some sort of prize, but it’s going to be a couple of weeks before it gets to me. I’ll update the post when I find out. :)

Thanks again to @sak3bomb for a great puzzle!!

Updates:

  • Full disclosure: I feel a little guilty that I glossed over an error in decoding the Morse code. In letting my excitement get the better of me, I misread one letter and made a bad assumption on another, and got the wrong address. Thankfully, it looked odd to me, and I tried emailing to what I figured was the right address as well, and that one won me the contest. I only verified my mistake when testing the Morse code in an automatic decoder applet this morning. That’s what you get for doing stuff manually.
  • Sak3bomb tells me that I missed a of couple key clues. For one, in the very top of ironman.jpg are the words “Steg” and “Hide.” I have NO IDEA how I could have missed those. That would have saved me hours right there, cemented the “it’s stego” thoughts, and even given me the right tool to use. Shoulda flown right past that in minutes, rather than hours over two days.
  • Also, when I extracted the data with steghide, I specified the output file (didn’t want the binary to go straight to the screen). Turns out, if I hadn’t done that, then the file created would have been named “1and0is1but1and1is0″. This, of course, describes bitwise XOR. That would have definitely saved me another day, and wouldn’t have gone down the “is it a picture?” rabbit hole. So, really, this should have been solvable on just the first day… I’m not sure how I feel about learning these little bits…I was really a lot closer than I thought, much earlier. Dammit! Then again, making things harder than they need to be is a long-standing problem of mine, so I’ll just think of this as a learning experience.
Categories: Conferences, Cryptography
Follow

Get every new post delivered to your Inbox.