So now it’s time to start again. I’ve changed over the blog system to something simpler than the WordPress system I was using before — Marco Arment’s Second Crack. It’s cleaner, a lot simpler, a whole lot faster, and also lets me easily publish things like slides, papers, or other media. It’s also got a simple applet that I can use to post “link posts,” and I’ll try again to start pulling out interesting looking things for comment.
Unlike WordPress, this site won’t have comments (I never got many anyway), nor does it have a “subscription” option (for the 3 or 4 people who received copies of posts in email). A RSS feed is available, and hopefuly I’ll have automatic tweeting of stories working as well.
Soon, hopefully, I’ll be able to put up a writeup of the 2014 DBIR puzzle (which I and Alex Pinto won first place on as a team!), and then maybe I’ll look for other puzzles which I haven’t written up yet, and talk slides which haven’t been posted. I’ll also keep hacking the Second Crack engine (I’ve got a short list of features I’d like to add).
So for the few of you who read the silly things I’ve posted here, thanks for reading, and hopefully soon you’ll have more content to wade through. 🙂
Last year, I had a great time trying to solve the Fidelis Security’s Decode This! puzzle at Black Hat. But I wasn’t fast enough (and I missed a couple of things that should have been obvious). This year, I resolved to not make the same mistakes. And in the end, it paid off! I was the first to solve, and won a $1000 prize! Read on to see how I did it.
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 the ciphertext and hints posted through twitter (try not to read those until you’re ready), click here.
First, the ciphertext (see the link above — it’s too big to repeat here). It was posted a few weeks before Black Hat, so I had some time to work on it. They also started posting some hints on twitter:
1. RFC2781 from Planet Bigend 2. Grok the last one 3. It ain't as long as it looks 4. 73 64 64 22
The first hint told me that the text was in UTF-16 format, which was something I’d considered for the last puzzle (which hint # 2 helped reinforce, in my mind). Also, hint 3 made me think that it used a similar encoding to last year’s, where only every other byte, or every 3rd nybble, or something like that, mattered. So I toyed with it off and on for a few days, but got nowhere.
Then hint 4 came out (a full week before Black Hat), and I thought, okay, I’ve got to find those numbers somehow. I still wasn’t sure how to proceed, but tried all kinds of ways to make them show up. No dice. So I put it aside again.
On Thursday before I left for Las Vegas, another hint came out:
5. Take ^ to heart this time Keep deleting CRLF
This kind of refered back to a comment I’d made last year, that I was SURE the ^ at the beginning of the ciphertext meant something. In many programming languages, that symbol is used for a bitwise exclusive-OR (XOR) operation, and I’d lost many hours trying to find the right XOR method to solve it. Turns out, it was just put in there “because it looked good.”
This year, however, it looks like it’s somehow significant. So once I got onto the plane for Vegas, I pulled out my laptop and started again. I spent the entire 5-hour flight looking at ways to slice-n-dice the ciphertext: XORs of different combinations of bytes, nibbles, or even partial bit-slices. No matter what I did, I couldn’t figure out how to coax out the “73 64 64 22” bit.
Finally, somewhere over Colorado, I thought, what if I need to convert it from UTF-16 to UTF-8? But how do I do that? I’ve not done a lot of work with various Unicode formats, and I didn’t have Wi-Fi access on the plane…But…the python libraries are all in uncompiled python, and I was able to find some Unicode conversion tools in there. Problem is, I kept getting errors, telling me that the text wasn’t valid UTF-16.
Then it hit me: It’s not in UTF-16. It’s in UTF-8, and I need to convert it to UTF-16. I’d even experimented with an online UTF converter weeks ago, but the results weren’t making sense, and I dropped it. Dammit!
Here’s a hex dump of the first 32 characters of the ciphertext, as provided for the puzzle:
0000000: c9b3 64e2 9da4 c4a2 c9ae 6ac5 bad1 a8c8 ..d.......j..... 0000010: b5e2 8191 d198 e29c b6e2 97be d28c d08b ................
And here’s a dump after I’ve converted it from UTF-8 to UTF-16:
0000000: fffe 0273 0064 2764 0122 026e 006a 017a ...s.d'd.".n.j.z 0000010: 0468 0235 2051 0458 2736 25fe 048c 040b .h.5 Q.X'6%.....
The first two bytes (“fffe”) are a header documenting the byte order for the file. But look what comes after that: 0273, 0064, 2764, 0122. 73 64 64 22. Finally, I’ve caught up to where I was supposed to be a week ago. Now I’m starting to get anxious.
Interestingly, too, I can see the same ‘s d d ” n j z’ sequence repeated multiple times all through the text. Which ties back to the “It ain’t as long as it looks” hint. All this, combined with the XOR hint from earlier in the day, tell me that I’m probably really close to solving the puzzle. But, “Ding! We’ve now begun our descent.” I have to shut down my laptop!
Once we land, and taxi to the gate, I pull out the laptop again and copy down what I’ve got so far, so I can stare at it while walking to the baggage claim. My wife thinks I’m crazy, but I told her “I’m within 5 minutes of solving this, I’m sure of it.”
And sure enough, not long after I landed (about 10 am Vegas time), hint number 6 comes through. It’s a link to an image of a spiral. I looked at the picture, then at my wife, and said “I know the key.”
See, the spiral that was drawn is frequently used to illustrate the Golden Ratio. And an interesting property of this ratio is that it’s closely related to the Fibonacci sequence, a mathematical series of numbers that starts with “1 1 2 3 5 8 13 21..”
We get into the terminal, and, sitting at the first table I find, I start applying the Fibonacci sequence to the (now vastly shortened) ciphertext. But where do I begin? With 1 1? or with 1 2? Turns out, I had to start with 0:
Ciphertext: 73 64 64 22 6e 6a 7a 68 35 51 58 36 fe 8c 0b Fibonacci: 00 01 01 02 03 05 08 0d 15 22 37 59 90 e9 0179 Result: 73 65 65 20 6d 6f 72 65 20 73 6f 6f 6e 65 oa
I simply took each byte of the ciphertext and XORd it with bytes from the Fibonacci sequence, to get:
"See more soone."
Hm. That doesn’t seem right. Still, I sent a DM to Will, the proprieter of the puzzle, telling him that I think I solved it. We went back and forth a little on that last character (turns out I should have used “79” instead of “01”, to get “See more sooner”), and finally he calls it: If I can be the first to his booth, then I win.
We rushed out of the airport, over to Caesar’s Palace, and got in touch with folks from my company who had shared passes for the Expo floor at the conference. Next thing I know, I’m posing in front of a giant novelty check for $1000, and am officially this year’s winner!
Thanks so much to everyone at Fidelis for another great puzzle! (even if I did, again, miss the obvious and get bogged down in a rabbithole).