Apple, Forensics, Law Enforcement, and FUD

May 13, 2013 2 comments

Just like the perennial discussion on location-based services and Apple’s ability to track you, the question of accessing an iOS device’s data when the device is locked seems to come up every few months. This time around, the discussion was inspired by a CNET article, with the sensational title “Apple deluged by police demands to decrypt iPhones.”

The article seemed to be built around a single paragraph in a blurry copy of a search warrant affidavit from ATF, which stated that the writer “contacted Apple” and was told by “an employee [...] who is part of their Apple Litigation Group” that Apple “has the capabilities to bypass the security software” on the iPhone.

That’s it. That’s all we know. An ATF agent reports having talked to a single person at Apple, who told him that they can “bypass the security software” on iOS devices. And from that tenuous hold, the Twitters exploded with “See! I TOLD you Apple had a back door!” and other related Fear, Uncertainty, and Doom.

But is any of it warranted? What could Apple really be doing, and is that any different from what we already know? Let’s review what we know, and don’t know, about iOS security, passcodes, and encryption.

Filesystem Access via Boot Images

iOS devices will only boot from a drive with a boot image properly signed by Apple. This image is (usually) on the device itself, but the Device Firmware Update (DFU) mode can allow the device to boot from an external drive via USB. For older devices, an bug in the bootrom allowed unsigned drives to be booted. That’s since been fixed, but it’s always been an “open secret” that Apple could probably still boot from DFU (since, obviously, they would be able to create a signed external boot image).

Once booted off an external drive, the internal device can be mounted, and unprotected information read. Most built-in Apple apps do not provide extra encryption (to my knowledge, only the Mail application separately encrypts its data at this time). One reason is that some data needs to be accessible while the device is locked: Inbound SMS messages and phone call information have to be written to the disk, the Contacts list needs to be available for displaying the name of inbound calls (and for making outbound calls), etc. So there’s a fair amount of data that can be retrieved at this stage.

So far, we’ve simply replicated what commercial forensics providers do: Boot off an external drive, and find “easily extracted” data. The difference is that forensics tools take advantage of the DFU bug (and thus can’t extract data from iPhone 4S or 5), while Apple doesn’t need any stinking bugs and can do this magic with any device.

Encryption

“But wait, iOS devices also have crypto! Crypto that uses ALL the bits! And this article PROVES that Apple can bypass that! They must have a back door.”

Well, yes, there are multiple layers of cryptographic support, but again, there’s no proof that Apple has any kind of way to get around that. First, let’s start with the device’s unique ID (UID). This isn’t the same as the “UDID” that’s been used by app developers to track devices and their users. This is a deeper ID, that’s “fused into the application processor during manufacturing.” Apple says that “No software or firmware can read [the UID] directly; they can only see the results of encryption or decryption operations performed using them” (see the excellent iOS Security overview paper, last updated October 2012).

This UID is used as the basis for all the rest of the keys on the system. At the lowest level, it’s used to derive the overall disk key, which provides a built-in full disk encryption for the iOS device. This means you can’t simply remove the flash drive from one iPhone and move it to another, since the key will still be back in the first device.

Additional encryption protection (alluded to above) can be added to a file’s data if the developer requests it, simply by setting an attribute when writing data to the disk. These files have their own encryption keys (it gets complicated — you really need to read that Apple paper. And when you do, keep this HITB 2011 presentation open in another window, it’ll help…) The keys for all the files are themselves protected with class-level keys (now we’re getting kind of hierarchical and/or meta), and those keys are stored in a keybag, which is itself encrypted using yet another key.

This last key is derived using the user’s passcode and the aforementioned UID device-unique key. Because the UID is tied to a device, any brute-force attempts to break the passcode have to happen on that device. And because “The UID is unique to each device and is not recorded by Apple or any of its suppliers” (again, the iOS Security paper) it is not possible to move any of these operations to another system, or to speed it up in anyway.

Possibilities?

So how could apple “bypass” security? Several possibilities have been speculated on:

  1. They could have an escrow keybag that only they know about. True, this is possible. But this security system has been subject to some pretty heavy scrutiny, if there’s a hidden escrow bag, it’s very well hidden, and nobody’s discovered the mechanism for creating and updating that.
  2. There could be a back door in the crypto. Not likely, again, given the 3rd party research in the system. If there’s a back door, it’s an “NSA-LEVEL” hole and way beyond anything Apple would be doing.
  3. They could have a way to extract the UID after all. One person on Twitter said that “sending me marketing material a la It’s secure because the vendor says it is is THIS close to insulting my mother.” Okay, fair point. But this is also a very technically detailed bit of marketing material, with far more insight and transparency than just about any other vendor provides. And, again, pretty much everything in that paper has been verified by many other security researchers. Why would Apple risk everything and have a flat-out lie in this paper? It just doesn’t fit.

Finally, I think it’s important to apply Occam’s Razor to the situation. If any of these backdoors existed, then it would take like 10 minutes for Apple to completely unlock a phone, and the alleged “7 month backlog” wouldn’t exist (unless they had thousands and thousands of confiscated devices to process).

Now, there is one final way that Apple might be able to get at the encrypted data on a locked phone: iCloud. If the user has iCloud backups enabled, then there’s a real possibility that Apple has the ability to access that data. After all, you can restore an iCloud backup to a different device, and you can change your iCloud password without losing the data in the backup. But that also shouldn’t take much time at all, and so probably only happens rarely (not contributing to the 7-month backlog).

Conclusions

So, to sum up:

  • Apple almost certainly gets confiscated iPhones sent to them by law enforcement
  • With the proper search warrant, etc., Apple will do what they can to extract data from those phones
  • They almost certainly can boot the phones from a legit, signed external drive, and gain access to much of the unencrypted data on the phone (damned near everything, unfortunately)
  • If they want to get at data protected by a passcode, then they can start a brute-force attack, just as researchers and forensics tool companies have been doing for years
  • If the user’s passcode is strong (5-6 alphanumeric characters), this could take months, if not years, to complete
  • If the device was backed up to iCloud, it’s possible that all bets are off and the data would be easily retrieved from backup

Is any of this new? Any of it at all? Nope. Not a single item in that CNET article told us anything we didn’t already know, except maybe the length of the backlog. Which, really, should be a good demonstration that there isn’t any kind of magic back door, and that if you use a strong passcode and avoid iCloud backups, the data on your phone should be secure against just about anything, including being sent home to Cupertino.

DBIR Cover Challenge 2013

April 29, 2013 1 comment

It’s time for the 2013 edition of the Verizon Data Breach Investigations Report Cover Challenge! This year I didn’t win…but only just barely. It also felt like a bit of a different puzzle this year, not quite as much a series of challenges as just a scavenger hunt with only the barest minimum of breadcrumbs scattered to help us follow the path to victory.

With that in mind, I’ll focus less on the individual puzzle elements, and more on the challenge experience.

My big takeaway this year is: Discipline. Time and again, I found myself stuck, and rather than taking the right approach and stepping back for a moment, I just spun my wheels and got nowhere. While this is well-known weakness of my puzzle-solving skills, it felt more troublesome than usual this time around. Perhaps because each stage had so few obvious next-steps, that once I found the first (obvious) angle, I stopped looking for others. Or perhaps everything was perfectly obvious, and I just Wasn’t Paying Attention. Either way, I know I missed many things along the way, and was lucky to even pull out 2nd place.

The puzzle started, for me, about 9:00 on a Monday night (this particular Monday was April 22). The first thing I did was to try to find hidden text in the report, first by doing a “select all” and copy/paste, then using command line utilities pdf2text and pdf2html. The only thing I found was a single hash: “f38b8e92f812 f9f4f26be4793827d906.” For some reason, I kept getting it copied out with a break in the middle, so I wasn’t sure if it was a single 16-byte string, or a 6-byte and 10-byte together (like a salt and hash).Either way, I couldn’t find any online databases that knew what it was.

I also looked through the document for interesting links, or silly sidebars (like last year’s “Chuck Testa” commentary). I found a github site with a couple of tools put out by the Verizon Risk team, but not much else. Then late that night, the @VZDBIR Twitter feed announced that there was a problem with the document, that something was missing, and they’d post a new version in the morning. What was missing? Usually there’s a big block of hidden encoded text, and I didn’t see anything like that this time. Or perhaps the (fragmented?) hash was an incomplete part of a longer list of hashes, or any of a million things.

1

Tuesday morning, they published the new version, and immediately I discovered a JPEG image hidden in a large block of base-64 encoded, hidden text. The image sent me to the same github account I’d found the night before, so I spent a little time looking for easy signs of steganography in this image, to no avail. I glanced again at the two repositories, then looked at the account avatar, and noticed that the background was transparent, but there was a solid white block at the bottom. I verified that this appeared to contain some kind of hidden data, and spent some time trying to extract that, or to re-format the size of the image to get something visually recognizable out of it. In the end, I never did figure out what was supposed to be in there. (Incidentally — I just heard from someone on the VZ-Risk team, and he had no idea what was in there, saying “That image had been there long before we planned out this challenge.” So…anyone want to try to figure that one out? The original, and data extracted from the white footer bar, are included below.)

github-avatar

footer

So the grand total progress I had made, after 24+ hours, was: I’m on a github site. Which I’d first visited within probably 20 minutes of first opening the report.

The next morning, I had a little time to poke around before a meeting, and I looked at the incident database in the github “Veris” repository. It contained over 1000 individual files, each representing a particular incident for which they had publicly-releasable data. Far too much to review by hand. So I started sorting the data on individual fields. First, I tried URLs from each file, but there were still too many to look at. I also tried searching for likely words, hints, things like pastebin, but still there was too much to process in the little time I had.

Then I saw a tweet from another Dark Lord of the Sith (@darthmdh – Matthew Hawkins), who said “So I’ve made it to ‘Johnson Packaging’, that wasn’t so hard! #DBIRpuzzle” Bingo! That’s the one. Turns out, he simply searched for the hash value found in the beginning of the doc, and there it was. (In fact, that was the sole purpose of that hash, which I’ve been told was just an MD5 hash of a throwaway text like “this is the text for the marker” or something. Sad, I was hoping it’d be “O HAI HASHCAT”).

Also, it turns out that what I could have done was to sort by the master_id. All of the IDs in the file included “osint” except for one: CC2013 (“Cover Challenge 2013″). That one should have been easy to spot. The incident file contained several clues to lead one to Pastebin, to look for a data dump from the “Case of the Mondays Hacker Troupe” (cotMHT).

This dump file contained 5 password hashes, some silly hacker-esque stuff, and a funny ascii logo. The hashes (4 of which were named after Jackson 5 members) decoded to lyrics from “ABC”: Michael / abc, Tito / easy, Jackie / as, Jermaine / 123, and Danzig / iiiiiiiiiiiiiiiiiiii. So…nothing helpful here either.

At that point, I had to get on a train for a meeting downtown, but I was able to do some digging while en route. The “silly hacker” commentary spoke of “epic ukulele solos on the Tube of You”, which, of course, I’d LOVE to watch that while on a crowded subway train. As it turns out, there wasn’t any real content in they lyrics (that’s okay, there probably wasn’t much real content in the song they were parodying either). All the important bits were on the whiteboard in the background.

whiteboard

Prominent bits on the whiteboard included:

* The latitude and longitude of the site of the Wreck of the Edmund Fitzgerald (/me cues up Gordon Lightfoot)
* A large Canadian flag, and other references to Canada
* A quote from the Chinese MoD in response to the Mandiant APT report
* Setec Astronomy
* Colonel J. Henry Haberdasher

At this point, I had arrived at my lunch meeting, and had to put the iPad away. But shortly after returning to the train (and viewing a tweeted hint: “The Colonel has been busier over the past month”) I searched for the right phrase and found the next stage of the puzzle.

whois

The phone number and address didn’t help any (the address is for the Museum of Civilization in Quebec — another Canadian reference), but the site that was registered certainly did: cofthem.ca (again, Case of the Mondays). But there was nothing at the site…just a blank, default “instant site” from GoDaddy. I tried several logins for the owner login panel (names and passwords from the Jackson 5 dump, for example) but eventually decided that it was the actual, legit GoDaddy site management panel and left it alone. I couldn’t view source on the iPad, so I tried several other “obvious” page names, like the unknown hash from before and other words, but found nothing.

I finally returned home, did some work stuff, and quickly decoded a hidden message on the pastebin dump (numbers hidden in the cotMHT logo spelled out “DRINK MORE OVALTINE”), then I dropped the kids off at an evening class and retreated to Panera for a bit. Shortly after sitting down, I looked at the YouTube page again. The ukulele video was posted by “Imstilla Hentz,” obviously a made-up name, but I couldn’t find anything else there, other than a default Google+ account. At this point, I even made a note in my log to check out other social networking / blog sites (I had in mind last year’s use of Pinterest) but didn’t pursue that any further. More on how that cost me first place in a bit.

After some time spent regrouping, trying to figure out just where I was and what I needed to do next, I looked a little more into how the “Instant Site” feature works. Turns out, it can only be used to create single-page sites. So there were no other URLs that one could read at that site, where the next clue might be. Back to square one for cofthem.ca.

After dinner and the kids’ bedtime, I focused on the supporting files for the Colonel’s website (all the while, @VZDBIR was telling us to search for what he’s been up to…which drove me buggy, as this was all I could find….) The javascript and CSS files all seemed to be the stock templates, the background image exactly matched one I found on another site, etc. I just couldn’t find anything at all.

Then, finally, a little before 11:00 pm on Wednesday, I realized that there was another item from the whois page I hadn’t searched for: The email address “haberdasher@mailinator.com”. Interestingly, Google didn’t give me much for that at all, until I tried searching on a 30-day window (which the hints had been telling us to do), and then I found two hits: One for a userid and password in the bugmenot database (which didn’t work on cofthem.ca), and another in “Hank’s Corner,” at “reallyclosetotheend.blogspot.com.”

Haberdasher Puzzle

Two minutes later, I noticed that this page had been created by “Ima Hintz,” the fictitious user from last year’s puzzle. And it was even available on Ima’s blogspot profile page. Which still contained links to last year’s Cupcake and ASCII Art pages. And the YouTube user “Imstilla Hentz” was, clearly, meant to evoke “Ima Hintz” from last year. If I’d thought that through a bit more while at Panera, I would’ve found this final stage 6 1/2 hours earlier than I did, and probably would have had the puzzle won by 7:00. Blast. Even crazier, if I’d decided to spend some time Monday night reviewing how things worked last year…and visited Ima’s page..I might even have found the puzzle within hours of the report’s release. I’m convinced the Verizon team did this deliberately, just to annoy us. Sneaky, sneaky, you magnificent bastards.

Fortunately, I knew exactly what to do with this puzzle, as earlier in the day my brother had sent me a link to the “Haberdasher’s Puzzle” (incidentally created by someone named Henry). Once the pieces were rearranged in the correct manner, the ciphertext would be readable, and I could proceed.

I took a short break to get prepped for bed (I was dead tired by now) but wanted to keep on until I was done, or fell asleep in my chair. Being so tired made getting the pieces lined up exactly right was difficult. Fortunately, a clear pattern was easy to discern — the numbers went “A, B, C, D-E” over and over. By making sure that I preserved that pattern as I read out the ciphertext, I eventually had a nice file with all the right numbers in the right places.

I quickly surmised that this was a book cipher (like had been used in the 2011 DBIR challenge), but which report is it built against? The “-” in the ciphertext broke the numbers up into 5-element groups, the first of which was probably the page number. Given that information, two of the reports were too short, so I first tried the current report. The first three letters were “EMA,” but the fourth one was broken: “16,26,5,6″ didn’t work — there weren’t 26 paragraphs (the 2nd number) on page 16. I glanced at the 2010-2012 reports, they weren’t any better, so I skipped this and tried the next, which was “L,” so this was probably “EMAIL”. (looking back now, I see that a comma got dropped, and I should’ve noticed that “16,26,5,6″ really should have been “16,2,6,5,6″ and the missing “I” would have been right where I expected it).

Though the final message was clear pretty quickly, I kept on decoding right to the final character, and only then did I send the email. The message read:

EMAIL BOOK CIPHER AGAIN? TO DBIR AT VERIZON DOT COM

Which I did. Then I checked Twitter. And saw that someone else had won almost exactly an hour before me. Arrrgh!!

Still, though I didn’t win first prize, it was a fun puzzle, as expected. As I said earlier, this one felt a little different, with very little real cryptography or even puzzle solving, and a lot of finding exactly the right hint at the right time. It definitely needed a different mindset to attack, and I think that hurt me a bit, especially when I found myself mired in stego and website tarpits. Keeping an open mind and regularly stepping back to look at the big picture was key to finishing this challenge.

For fun, I created a flowchart showing the circuitous path I took to complete this puzzle. It’s especially frustrating to see all the dead ends I visited, compared with the “ideal” path straight down the middle. Even more so when I see visually described the opportunity I missed near the end, and most especially when I think about the “Just skip past the entire puzzle and jump straight to the last stage” troll via last year’s Ima Hintz blogger account.

AttackPath

Congratulations go out to Mike Czumak (@SecuritySift, twice before a DBIR Honorable Mention finisher) and his teammates @Blackjack988 and @LaughingWill. They’ve posted a great writeup themeselves, and it’s definitely worth a read.

I’ll get you next year.

Categories: Cryptography, Puzzles

Fidelis Security Systems’ Decode This 2012

August 17, 2012 2 comments

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).

Categories: Uncategorized

2012 Verizon DBIR Cover Challenge

March 28, 2012 3 comments

Every year, the Verizon Business Risk Team publishes a Data Breach Investigations Report (DBIR), analyzing trends and other great statistical information gathered from working hundreds of different, well, data breaches. For the past few years, the report has included a puzzle / challenge / crypto contest. I heard about the 2009 puzzle too late to play, gave up in disgust trying the 2010 puzzle, and skipped the 2011 puzzle (’cause I was actually working another puzzle at the time). This year’s report came out a few days ago, and I immediately launched into trying to solve it. It took a few days, but I managed to not only solve the challenge, but I came in first! Of course, as I’m prone to do, for every little step I took forward I first took about three giant steps sideways (often repeated in two or three different directions.)

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 what you need to complete the puzzle, with no spoilers, click here: Verizon 2012 DBIR Sources.

Where do we begin? Looking at the cover, I see some interesting things…but nothing that I can work with right away. In past years, there was a big block of encrypted text hidden in the PDF, so I pull out some tools and find that (actually, simply a select-all and copy would also find it, hidden behind the image on the front cover).

VGhhbmsgeW91IGZvciBwYXJ0aWNpcGF0aW5nIGluIHRoZSAyMDEyIFZlcml6b24gREJJUiBDb3Zl
ciBDaGFsbGVuZ2UuCldlIGhvcGUgeW91IGVuam95IHRoaXMgY2hhbGxlbmdlIGFzIG11Y2ggYXMg
d2UgaGF2ZSBlbmpveWVkIGNyZWF0aW5nIGl0LiAgCgoKVGhlcmUgb25jZSB3YXMgYSBsYWR5IGZy
b20gTmFudHVja2V0LApXaXRoIHRleHQgc28gd2lkZSB3ZSBjb3VsZCBncm9rIGl0Lgp3ZSBjaG9w
cGVkIGFuZCBzbGljZWQgaXQgYWxsIGRheSBsb25nLApPbmx5IHRvIGZpbmQgc2hlIHdhc27igJl0
IGFsbCB3cm9uZy4KCldpdGggc2tpbGwgYW5kIGVhc2Ugd2UgYmF0dGxlZCB0aGlzIGZpZ2h0LApF
eGNlcHQgc2hlIHdhcyBub3QgdG90YWxseSByaWdodC4KVHdpc3RpbmcgYW5kIHR1cm5pbmcgd2Ug
a2VwdCBvbiBzdHJvbmcsCldlIHNob3VsZCBoYXZlIGJlZW4gc2luZ2luZyBhbGwgYWxvbmc6CgpN
YXJ5IGhhZCBhIGxpdHRsZSBsYW1iLApsaXR0bGUgbGFtYiwgbGl0dGxlIGxhbWIsCk1hcnkgaGFk
IGEgbGl0dGxlIGxhbWIsCndob3NlIGZsZWVjZSB3YXMgd2hpdGUgYXMgc25vdy4KCkFuZCBldmVy
eXdoZXJlIHRoYXQgTWFyeSB3ZW50LApNYXJ5IHdlbnQsIE1hcnkgd2VudCwKYW5kIGV2ZXJ5d2hl
cmUgdGhhdCBNYXJ5IHdlbnQsCnRoZSBsYW1iIHdhcyBzdXJlIHRvIGdvLgoKSXQgZm9sbG93ZWQg
aGVyIHRvIHNjaG9vbCBvbmUgZGF5CnNjaG9vbCBvbmUgZGF5LCBzY2hvb2wgb25lIGRheSwKSXQg
Zm9sbG93ZWQgaGVyIHRvIHNjaG9vbCBvbmUgZGF5LAp3aGljaCB3YXMgYWdhaW5zdCB0aGUgcnVs
ZXMuCgpJdCBtYWRlIHRoZSBjaGlsZHJlbiBsYXVnaCBhbmQgcGxheSwKbGF1Z2ggYW5kIHBsYXks
IGxhdWdoIGFuZCBwbGF5LAppdCBtYWRlIHRoZSBjaGlsZHJlbiBsYXVnaCBhbmQgcGxheQp0byBz
ZWUgYSBsYW1iIGF0IHNjaG9vbC4KCkFuZCBzbyB0aGUgdGVhY2hlciB0dXJuZWQgaXQgb3V0LAp0
dXJuZWQgaXQgb3V0LCB0dXJuZWQgaXQgb3V0LApBbmQgc28gdGhlIHRlYWNoZXIgdHVybmVkIGl0
IG91dCwKYnV0IHN0aWxsIGl0IGxpbmdlcmVkIG5lYXIsCgpBbmQgd2FpdGVkIHBhdGllbnRseSBh
Ym91dCwKcGF0aWVudGx5IGFib3V0LCBwYXRpZW50bHkgYWJvdXQsCkFuZCB3OGVkIHBhdGllbnRs
eSBhYm91dAp0aWxsIE1hcnkgZGlkIGFwcGVhci4KCiJXaHkgZG9lcyB0aGUgbGFtYiBsb3ZlIE1h
cnkgc28/IgpMb3ZlIE1hcnkgc28/IExvdmUgTWFyeSBzbz8KIldoeSBkb2VzIHRoZSBsYW1iIGxv
dmUgTWFyeSBzbywiCnRoZSBlYWdlciBjaGlsZHJlbiBjcnkuCgoiV2h5LCBNYXJ5IGxvdmVzIHRo
ZSBsYW1iLCB5b3Uga25vdy4iClRoZSBsYW1iLCB5b3Uga25vdywgdGhlIGxhbWIsIHlvdSBrbm93
LAoiV2h5LCBNYXJ5IGxvdmVzIHRoZSBsYW1iLCB5b3Uga25vdywiCnRoZSB0ZWFjaGVyIGRpZCBy
ZXBseS4KJHAK

This text decoded, not to an encrypted binary, but to a poem:

Thank you for participating in the 2012 Verizon DBIR Cover Challenge.
We hope you enjoy this challenge as much as we have enjoyed creating it.  

There once was a lady from Nantucket,
With text so wide we could grok it.
we chopped and sliced it all day long,
Only to find she wasn’t all wrong.

With skill and ease we battled this fight,
Except she was not totally right.
Twisting and turning we kept on strong,
We should have been singing all along:

Mary had a little lamb,
little lamb, little lamb,
Mary had a little lamb,
whose fleece was white as snow.

And everywhere that Mary went,
Mary went, Mary went,
and everywhere that Mary went,
the lamb was sure to go.

It followed her to school one day
school one day, school one day,
It followed her to school one day,
which was against the rules.

It made the children laugh and play,
laugh and play, laugh and play,
it made the children laugh and play
to see a lamb at school.

And so the teacher turned it out,
turned it out, turned it out,
And so the teacher turned it out,
but still it lingered near,

And waited patiently about,
patiently about, patiently about,
And w8ed patiently about
till Mary did appear.

"Why does the lamb love Mary so?"
Love Mary so? Love Mary so?
"Why does the lamb love Mary so,"
the eager children cry.

"Why, Mary loves the lamb, you know."
The lamb, you know, the lamb, you know,
"Why, Mary loves the lamb, you know,"
the teacher did reply.
$p

That’s neat. Now what?

Well, there are a bunch of numbers on the cover. There’s a 405 in ‘h4x0r5,’ and phone numbers on another sign. Though these phone numbers are incomplete, and don’t even seem to have a real area code. Maybe I need to use those numbers as an index into the poem — like find the 405th character, the 696th character, etc. If I include the stray “8″ in the poem (“and w8ed patiently about”), then I’d have enough for a 5-letter string, maybe as a code at a URL shortener.

But none of this worked, and after a day or so of playing with this a little, a hint was given on Friday night that told us “If you found Mary, you’ve gone too far.” So the whole poem might even be a red herring. This means I don’t have much at all to work with. Just the numbers. And the cover.

Saturday morning, I played a little looking for steganography (looking at the lowest bit, and also treating the three numbers in the phone number as an RGB triplet to search the image for), but gave up on that pretty quickly. Maybe I can get an IP address out of the numbers. I tried factoring the numbers but found nothing obvious. I tried treating it as a single number and converting that to a dotted-quad internet address. That didn’t work. I even tried dropping the first or last number to treat them like hex (0×69651321) but again, no luck.

Finally, I tried 69.65.13.21 (this made some sense, since one copy of the number was torn off leaving only the last digit behind), and found a website that looked promising: An unconfigured WordPress blog, but after several minutes of explorign I didn’t find anything useful there. Then I realized, wait, I haven’t tried 69.65.13.216 yet. Trying that got me “Server 1 online.” I then tried that on port 443, and got a certificate mismatch error — telling me that I was trying to connect to pastebin.com.

Alrighty, then! Pastebin! But what paste?

I tried searching for different strings from the signs on the cover, and for things like DBIR and Verizon, but had no luck. Finally, I hit paydirt with “half million personal” — and got a huge list of hashes. There were over 14,000 of them…but as I looked closely, I noticed that one of the hashes was short (the last digit had been dropped). Then I saw that a lot of them ended with the same numbers (which told me they were probably LANMAN hashes), and looking even further, saw there were a lot of full-on duplicates. After passing the list through a couple of awk and sort | uniq -c steps, I found that one hash, and one hash alone, was unique in the entire file.

imahintz@gmail.com,98B451441C75C9F0F3BD49EDF32EB4A4

It only took another minute to lookup that hash online, and found that the password was “PINTEREST.” Cool! So I dashed off to Pinterest and looked for the name associated with that hash, which was “imahintz” (which, obviously, would’ve been a good clue if I’d taken the time to look at all 14,000+ emails).

The Ima Hintz user had five pin boards: Crafts, Favorite Places, People, My Style, and Recipes. Right off, the Style board catches my attention because of a picture of Chuck Testa, subject of a recent viral Internet meme and mentioned directly in the DBIR. Most of the rest of them just look like silly pictures to help fill out the account. Looking at the activity history, the most recent items to be pinned were four people (Larry Wall, a soccer player, Q-Bert, and Lincoln), then Chuck Testa, something about Oxygen, a couple of recipes (Mojito foam and Cupcakes), and finally, an image of ASCII art spelling “Challenge.” So let’s look at that last one!

That takes me to a blog, where I see the Challenge image (ironically, not even ASCII at all but a .png image), and some DBIR logos, and a big present made out of base-64 looking code, complete with a ribbon and bow. Decoding the base-64 (which I note has only lowercase letters) gives me a big chunk of binary, which I assume must be the ciphertext. I tried a bunch of keys (variants of phrases associated with Chuck Testa, also stuff from other images on the Pinterest account, like Puddy’s Eight-Ball jacket, etc.), not really expecting it to be that easy. It wasn’t.

                                           ***   
                               ****       ** **  
                              **  ***   ***  *** 
                             ***    *** **  ***  
                               ***    ***  ***   
                                 ***   *  ***    
                                   *** * ***     
                                     ******       
8vvpojkjq3c8a7d0ryi5fghqc9wvi7zba0puzyk**az3tkq5jdof2ssdcca01r0epgxu2sgvb2uz
jx5l7xxm0a11i5nsyhjkor8xe9ae06k27sumhqi**8qhrb1x7kixt53p5etuktrj35b9brrbnvtc
c24njbtr2jz1zjkc785ns1of43i7abcbkylsunp**soekn22c8r5asmbxd6opnfp5xk113hrca3m
kbubf9t1clswoqqucq7lke9inokuz3l46eu1tgq**q4gk1en3t1qmp2gzmc679x03t9y5x709cq5
obmzdh35v0rkq6oyk67d4jsgo08rco5yoji90mv**fbs1ye1rzjkm75l02zyb7vi1mxt1rkr3ba2
d6gkr2mc5lrsipbeboggz2415q7b01o1khy0zn8**rhxlq33k40lsm0nttyr88oiqtz8r1qtnexr
4t688b1cm8q2d2id7jufvuzy6g48bbyej9grqdy**d8yb5wl8kqc9nbb6ldhzn0suj3br59u74ft
lf8c3ea675n31b6qwnmej5hwv48teo86056tw35**i7o7l64uoa2evkyk1yuprjfyjirhny5ubpv
bnhcwn5hwmp0kxcgbw5b2w4l6oaojpz182j7ywt**ampoqhfxsy9x71wxjvgdq1cy09z15z2lii0
rcobyczafy5ltupcavoipmcjxh6h9mj6ok6xdsj**v4atn4ips2xc2rzauv4e9i0hyo7ay4k18cx
ij2hid3mdfhd74qkbz06nk066w6scml2efuhgsp**mlh7h8i36u5he05aajk2p4939jf7x1gejmv
qmsicuyxcen6ieav2acr5bs947c1y759sbbq3ws**r7hig36yv5v93qqpx9pr6j9g3esiatg3hue
****************************************************************************
ltvm632gqf31bhykk0wokp6jmkn5idji62r6id1**f4ncrulceizzc23p95rs1sdby5hyrnkcvku
2ehd4wrr629xsvpmivr3rc0b37907e4emlbrnbe**i0iyuhrmull00poau4hip6tefqx4v93q2js
r5mgcndutkxlk24ytxuxtgbzlhplmemdm7cj2gj**vwahybu5safhha9thsnxmk0jf71jc3zityg
cqk22nw1otk2fvxvzk1lglybb3xldpmphqrep2a**qpdjbomyres6n4tun2lyjmzdvpxjjty36gk
2gg42qtiykehb46dqgvi37gyv41ddtd110oh3m3**ub559tyxcqbvns5c0ts2lsitkhwrhim9pt5
pi47v37gh2vl34x0257mdmbb9pijcxgxkvxfiwc**2qxrmwe4ypfatf095gvqv6j5snavdnpcjj6
jowfuky2xlagtg27lhg951j70esmd2coj649k56**aiikyzzitx1ryjpuxxhkdi2j0xswamim469
3z4ojtkh7dkoguwy5c4z47y1fdbayle2cjs9lv9**vj0h0oovwe3uoli3uypekb7aa9irfmhjuqr
u3j7m5giarcyd7b92rdv1ec0ov47bvqgm6228dp**jzz8jurl617zch0yz2ld0ft3r9k97g0lk2d
du8vdfu2wlop1qb2h9fwg5xdeod77aythvpvvyy**vqfeu679095is2ps6kfgehoerrv60ytanv0
wvnojkezih25kr1sn30cv4sifxjaxpgkmfohwdw**zjvtmpp4vs45fuds061rdcg4n6q3kpnhf8k
6bdq98gv0p372n4butt5gn7s63ek8jct5zkx49d**yj1ycg0knp0uvmpke6yio32sx89m2qnjeo6
v0uygrre88nz

Then I noticed that the cupcake recipe is called “Encryption Cupcake Recipe.” Cool! The recipe has little bits that can help, like -nosalt and “a pinch of OpenSSL” but not much more. And I’d already assumed the -nosalt based on the ciphertext I was working with. I also checked the original recipe that this one credited, and saw that they’d added caramelized bananas, but didn’t think that was significant.

All along, I’ve been keeping @wadebaker informed of my progress (he’s a member of the DBIR team, and seemed to be tweeting the most about the contest). I mentioned that I was thinking the key might be in one of the password hashes, and he told me “I think u prolly got all u needed from that step.” Because I was addled, or hungry, or just stupid, I read that as “Good idea, you have all you need to make that happen.” What he meant, I learned a couple hours and 99% of the passwords later, was “No, you’re done with that step, move on.” D’oh.

So I’m back to looking at “the gift.” Interestingly, it’s almost the same size and shape as the base-64 code that gave us the opening poem — a couple characters too narrow, and a line too short. It’s also all lowercase, which I belatedly realize would be next to impossible to force if you’re encoding a random binary file (which an AES ciphertext would closely resemble). No idea why I didn’t think of that before. So maybe it’s uuencoded, not base-64? No, that has the same problems. Maybe the whole thing is base-36? But how would you convert that back to 8-bit binary? You’d need, maybe, to have two-character pairs (essentially, base-676 digraphs) and as long as no digraph ever reached 512, that’d be a 9-bit value represented by each digraph. String enough of those together, divide into 8-bit chunks, and you’ve got output. Voila! Except…well…that’s a bit crazy, even for me.

After telling Wade all this (and admitting how far afield I’m drifting) he suggests that this step might be “more puzzle than crypto.” So, okay, regroup, and revisit the original poem. It mentioned slicing and chopping, twisting and turning — maybe this is a big transposition cipher, and I need to shift rows around and such. But that seems almost as complicated as my base-676 craziness, and I don’t think much about it. Well, let’s fall back to looking for something hidden behind the text, and look at the HTML source for the gift image.

Interestingly enough, it’s all broken up. There’s an 8, then a bunch of characters in a single SPAN tag, then another 8, then another SPAN of other characters, then another 8…. Not wanting to jump to conclusions, I painstakingly check every single row in the image and, sure enough, every single 8 is separated out from the other characters. There’s something special about the 8s. Which I should have noticed earlier — a bunch of the pictures on the Pinterest site had prominent 8s, the poem had an 8 in ‘w8ed’, and even a couple of the hints on twitter had used 8 (like “devest8″).

8..........8................................................................
......................8..................8..................................
.................8...............................8..........................
............................................................................
..........................8.................................................
......................................8.....................88.....8........
...88....8.................8..............8.....8...........................
..8.......................8...8.............................................
................................8...........................................
.........................................................................8..
..............................................8.............................
............................................................................
............................................................................
............................................................................
............................................................................
............................................................................
............................................................................
............................................................................
............................................................................
............................................................................
............................................................................
....................................8.......8...............................
..8.........................................................................
..........................................................................8.
.....8......................8.....................................8.........
........88..

Also, the report itself mentioned that they’ve been producing the DBIR for, wait for it, eight years. Another interesting thing, is that when I hide all the other characters (turning them just to dots), there’s a big multi-line gap about 2/3 of the way down without a single 8 in it. None of the other characters show this — they’ve all got more normal looking distributions. Again, clearly, there’s something special about the 8s. But what?

Crazy Eights

I tried resizing the array of characters, thinking that maybe it’s supposed to turn into a picture. Or maybe if I resize it to 8 rows, it’ll be like 8-bit-wide paper tape. Or maybe it’s Morse code. But ultimately, there’s just not enough information there. There are only 32 of the 8s, that’s just not enough to convey anything useful, at least not as bits. But perhaps it’s the spaces between the 8s that matter — and I count them out and convert them to letters, but again, this gives me nothing, even when I try various Caesar shifts on the output. So…Saturday ends with me having made some good progress, but still feeling quite stuck.

I get back at it first thing Sunday morning (after the kids have dragged me out of bed to investigate a robin that’s been attacking its reflection in our dining room window). The ribbon on the gift looks almost like axes on a graph, but I can’t think of how to use that. With nothing else to go on, I tried playing with some of the other images I’d seen — cupcake pictures, etc. — looking for more stego, using the tool they used last year. Then I get a note from Wade: “What does Mary live in?” I immediately think of the original base-64 text from the report cover, and instantly I know what the trick is: A grille cipher. And I realize that I’d, again, been shortsighted: removing the ribbon (as I thought the stars that made it up were just window-dressing) resulted in a gift image that was smaller than the base-64 text that produced the poem. But leaving it in place meant the gift was exactly the same size. Which absolutely should have been something I paid more attention to.

Fifteen minutes later, I’ve written a script to simulate the grille: it converted both the gift and base-64 text to long strings, and counted forward in the grille string. Whenever I encountered an ’8′ in the first, I output the corresponding character in the second.

Another way to imagine this is to simply layer lines one atop the other:

VGhhbmsgeW91IGZvciBwYXJ0aWNpcGF0aW5nIGluIHRoZSAyMDEyIFZlcml6b24gREJJUiBDb3Zl
8..........8................................................................
ciBDaGFsbGVuZ2UuCldlIGhvcGUgeW91IGVuam95IHRoaXMgY2hhbGxlbmdlIGFzIG11Y2ggYXMg
......................8..................8..................................

This gave me a base-64 string:

    V1hHWmxVaGplc204cVNVam1TbU92ZVJH

Which, when decoded, gave another base-64 string:

    WXGZlUhjesm8qSUjmSmOveRG

Just like it’s pretty much impossible to make a random binary encode to an all-lowercase base-64 text, it’s very unlikely that a random base-64 text will decode to another valid base-64 text. So I take this as an indicator that I’ve finished this stage successfully, and go make breakfast. While eating (“Daddy, why do you have your computer at the table?”) I look around the Pinterest page again for other ideas on keys.

Where’s the Key?

Two years, ago, the key was a phrase that you had to find on the web. Last year, they made it somewhat more explicit and had the key hidden as stego text inside an image. So this year, I was looking for something equally clear (and hopefully directly visible). I revisited the script I (unsuccessfully) used in 2010, and added things like “nope! Chuck Testa” (referred to in the DBIR text), “All signs point to ‘Yes!’” (from the page describing Puddy’s Eight-Ball jacket), and several other variants and other phrases and words. All with different uppercase and lowercase and punctuation permutations. None of them worked.

Then I realized I was just spinning my wheels (and was feeling stressed ’cause I just knew someone else must be about to beat me to it). So I stepped back and looked around a little more…and looked more closely at the cupcake recipe. The only thing that was changed from the original recipe was the addition of the bananas. I looked, again, very closely at the image of the torch on the banana slice, and saw nothing. I also looked closely, perhaps for the first time, at the picture of all the cupcakes, and noticed “-base64″ written next to one of the banana slices. Superimposed on another was “-rc4-40.” Aha! So now I know exactly what cipher to use (and it wasn’t one I’d been testing against). Updated my script, ran the keylist through again, but still, nothing.

Stepping back for a moment was so helpful that I did it again, and sat staring at Ima Hintz’ home page for a little bit. Wait — there’s an 8 I totally missed. It looks like a bumper sticker, with “Mark it 8, Dude.” on it. I opened up that pinboard, and that image was one of only a few with a caption: “Markitdude.” (was this a pun, to refer to the “marketing dudes” who probably end up paying for the contest prizes?) I added both of those to my list, ran it, and…success!

   **** DINGDINGDING ****

   Password: Markitdude
   Output: email 8trak 2dbir

At 11:40 am on Sunday, after half-hearted poking around on Thursday and Friday and a nearly all-day bender on Saturday, I’ve solved the puzzle.

I immediately sent off a DM to Wade, and followed up with an email to the dbir email address sprinkled throughout the DBIR text. Then I went to my mother-in-law’s house to help with some light fixtures (but I brought my laptop with me, just in case). And waited. And waited. Finally, about 3:00, I heard back — I’d won! Woohoo!

Too Long; Didn’t Read

(Yes, I know that’s supposed to go at the top, so you don’t have to read all the rest of this. Tough.)

  1. Find the base-64 text hidden on the front cover. Don’t bother decoding, the content is a red herring. But do add some newlines so it looks all nice and pretty.
  2. Convert the incomplete phone number (696) 513-216 to the IP address 69.65.13.216, and go there using HTTPS to get redirected to pastebin.com.
  3. Enter the text from the sign which had the phone numbers (“half million personal records”) to get a password dump.
  4. Realize that the dump is full of duplicates, but also includes a single unique hash.
  5. Crack that hash to get pointed to pinterest.com, and use the email address for that hash to get the Pinterest user’s ID.
  6. Find the Challenge picture on the Pinterest site and, clicking on it, find the ASCII “gift” image.
  7. Realize the importance of 8s (by viewing source on the gift image, or by noticing all the 8s in all the pictures, or by looking at the visual distribution of each character in the gift and seeing that 8 is “different” from all the rest).
  8. Realize that the gift, and the base-64 text from step 1, are exactly the same size and shape.
  9. Use the 8s as a grille cipher, and uncover the corresponding characters from the base-64 text.
  10. Decode that string to get another base-64 string. This is the final ciphertext.
  11. Find the “Encryption Cupcakes” recipe on the pinterest page and see the clues in the text and the picture: openssl, -nosalt, -base64, -rc4-40.
  12. Look around the pinterest site some more, and see the “Mark it 8, Dude.” picture, and realize that it’s only one of four pictures with a caption (another was the 3 Wolf Moon t-shirt from last year’s puzzle).
  13. Use that caption as the decryption key.
  14. Win.

For completness’ sake, here’s a command to perform the final decrypt (all one line):

echo 'WXGZlUhjesm8qSUjmSmOveRG' | openssl enc -d -rc4-40 -base64 
    -nosalt -pass pass:Markitdude

Conclusion

This was an excellent puzzle. It had lots of clear indicators of success, but also plenty of distractions. I spent some time searching for things like “wadebaker” and “pirogue” because of random, offhand tweets he’d made. There were lots of interesting looking comments around Figure 42. Chuck Testa satisfied the need for a meme, like last year’s puzzle. Not to mention the cryptic text in the initial red herring poem.

Ultimately, though, everything we needed to win was on some kind of page or document created or maintained by the DBIR team. Nothing came from any 3rd party page (no comments on YouTube videos, or in Amazon listings, or on the Puddy or Chuck Testa pages linked in Pinterest). All clearly marked, and very “conspicuous” (which was the twitter ID used for some of the hints, and the name of the user who posted the password dump). The big trick was simply noticing everything. And, as I’m sure was the case for many other players, I skipped right past most of the clues the first two or three or four times I looked.

It had a modern cipher (the RC4). It had a classic cipher (the grille), which was a little bit obscure, but I was actually thrilled to see it used. It wasn’t easy, but as usual, a large degree of the difficulty was simply My Own Fault, for missing things, or making stupid assumptions, or conveniently overlooking what should have been blazingly-bright red alarm lights that I was Doing It Wrong.

But as I completed each stage, the right answer was clear and hard to miss. The grille and original base-64 text being the same size. The 8s having a markedly different distribution. The base-64 text decoding to base-64. The final key being one of only four captions in the Pinterest account.

Bottom line: I absolutely loved this. Favorite part: The grille cipher, just because it’s a part of cryptographic history and I haven’t seen it used in a puzzle like this before (and it was used, I think, very well).

So, in the end, a big thanks to the DBIR team for a fantastic puzzle, an awesome prize (iPad!), and of course, thanks for the excellent Data Breach Investigation Report itself: for all the effort the whole team put into the collection and analysis of the data, and especially for making the report available to all the world for free.

Hopefully next year I won’t make as many mistakes.

Categories: Cryptography, Puzzles

Verifying a Detatched S/MIME Signature in Python

February 21, 2012 Leave a comment

I was recently experimenting some more with my iOS MDM server, and found that I needed to verify inbound signatures on the messages the clients send to the server. It took some doing, but eventually I found the right way to handle it at the command line.

I had to take the signature (in this case, provided as a base-64 string in the HTTP header), decode it, and save it to a file. Then I needed a copy of the public key for the certificate used to sign the message, and finally, I had to copy the text of the message itself to another file. Once all that was done, it was something like this:


openssl smime -verify -in -inform der -content -certfile -CAfile

This then spits out a copy of the text, and the message “Verification successful.” Very simple, though it took a while to get it exactly right. (I may have been using the wrong signer certificate for some time, though….)

So this is all well and good, but how do I do this programatically? In my server? Should be easy, right? Just find a good OpenSSL library for Python, and Bob’s your Uncle!

Turns out, that’s the hard part–finding a good OpenSSL library for Python. PyOpenSSL was abandoned for a while, but recently revived. The other library I found, M2Crypto, was a bit more arcane and also fairly dated. But in the end, I did figure out how to get M2Crypto to work. Here’s the code, in a nutshell:


from M2Crypto import SMIME, X509, BIO

raw_sig = ""
msg = """"""

sm_obj = SMIME.SMIME()
x509 = X509.load_cert('signer.crt') # public key cert used by the remote
# client when signing the message
sk = X509.X509_Stack()
sk.push(x509)
sm_obj.set_x509_stack(sk)

st = X509.X509_Store()
st.load_info('CA.crt') # Public cert for the CA which signed
# the above certificate
sm_obj.set_x509_store(st)

# re-wrap signature so that it fits base64 standards
cooked_sig = '\n'.join(raw_sig[pos:pos+76] for pos in xrange(0, len(raw_sig), 76))

# now, wrap the signature in a PKCS7 block
sig = """
-----BEGIN PKCS7-----
%s
-----END PKCS7-----
""" % cooked_sig

# and load it into an SMIME p7 object through the BIO I/O buffer:
buf = BIO.MemoryBuffer(sig)
p7 = SMIME.load_pkcs7_bio(buf)

# do the same for the message text
data_bio = BIO.MemoryBuffer(msg)

# finally, try to verify it:
try:
v = sm_obj.verify(p7, data_bio)
if v:
print "Client signature verified."
except:
print "*** INVALID CLIENT MESSAGE SIGNATURE ***"

This seemed to work just fine, though it did take a few tweaks to get exactly right. One thing that I found useful was to verify that I was at least getting the same message hash. Adding the following code to my test script (in the appropriate places), I could then see what it thought my message hashed to:


import binascii
from M2Crypto import EVP

md = EVP.MessageDigest('sha1')
md.update(msg)

print binascii.b2a_hex(md.digest())

Then, I’d look at the .der signature for the hash inside it:


openssl asn1parse -in sig.der -inform der

and look for the “HEX DUMP” string right after the “:messageDigest” header. If that matched what the script showed, then I knew I at least had the content properly processed, and any remaining problems were probably with the certificate. If they didn’t match, then I apparently hadn’t properly read the content in the first place, and no amount of fiddling with PKI would yield a positive result.

In the end, though it wasn’t nearly as simple as “verify(sig, text, ca)” I was still able to get it working reliably, and eventually added it to my server’s bag of tricks.

Categories: Cryptography, Programming

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.]

Follow

Get every new post delivered to your Inbox.