Wednesday, April 29, 2015

BSides Rochester Crypto Challenge

I suppose it's time to recap this year's crypto challenge from the BSides Rochester conference. One of my main goals this year was to solve the crypto challenge for the third straight year. As usual, there were a handful of us working together throughout the day. I was a bit concerned since we got started pretty late, plus I was presenting so we all took a break for that hour. In the end, we managed to solve it just as closing ceremonies started and I have to say, this was probably my favorite of the challenges so far.

Before I begin, I want to acknowledge that I didn't do this alone. It was a group effort, and I want to acknowledge everyone that helped contribute to cracking the code. In no particular order, this includes Anthony Miller-Rhodes (@amillerrhodes), Mike Burke (@securechef), Matt Lapinski (@_the_colossus), Colin O'Brien (@InsanityBit), and Austin Karn (@SynthVerity).

Darth Null (@darthnull) threw out some new stuff at us, and somehow we managed to skip a step along the way using some creative thinking. This one gets a little weird, but that's probably my favorite part of the whole experience. Anthony (@amillerrhodes) came through in a big way with his Python-Fu to script up some of the more tedious aspects of the challenge which is a big reason why were were able to solve it in time.

So, without further ado, I give you this year's walkthrough:

After some initial confusion as to where the first clue resided, we were told that to look at the main BSides Rochester webpage, which is shown below.

Our adventure begins!

Clearly, we're being pointed toward the large red "V" on the right side of the page. Clicking on the image just opened the image in a separate tab, but there was nothing that immediately stood out here.
What secrets do you hold?

My first instinct was to determine whether there was any information appended to the file that would point us toward our next clue. Running 'strings' on the image yielded the following:
$ strings 2015-02.png
IHDR
bKGD
pHYs
tIME
IDATx
--snip--
bsidesroc.com/D0noV4n

Bingo! A URL was hidden within. Following the link brought us to this next page:


We have our next clue stating that a very important message awaits us, but in order to do that, we have to first find out how the Resistance has been communicating. We can see from the Communication Record at the bottom that there are 6 messages that we're going to need to locate to move forward. Great, but what now?

Next I checked out the webpage source code to see if there was anything that was hidden from the final markup, shown below.
Sneaky, sneaky
At the very bottom of the page was a link to a 5 pixel wide image with a name of drop.png. Maybe this was our next clue? The hidden image ended up being some sort of barcode.
What are you?
We first tried scanning this with our various barcode scanner/QR scanner apps. Nothing seemed to be working. Being wholly unfamiliar with bar codes, it was off to Google to find out exactly what type of barcode this was. Unsurprisingly there was a website all about barcode information: barcodefaq. After reviewing the options listed there, we decided that the barcode was a PDF-417 barcode and located an app on our phone that could properly scan it. The result was another URL:  bsidesroc.com/D0noV4n/1429963200.png

Following that link we received this beautiful gray pixel image:




Alright, so what next? This is only one of six required messages. Well the image name looked a little interesting to me, very similar to a Linux epoch time. But what time and date does it result in? The command line will help us here:

$ date -r 1429963200
Sat Apr 25 08:00:00 EDT 2015

So the result showed that it was today at 08:00:00 EDT. But wait, we saw that time once before, in the Communication Record back on the /D0noV4n/ page where we started!
Moving right along now
So this is where the first leap came in. If the first message matched up to the current date and the first time entry on the Communication Record, perhaps the rest of the messages could be similarly retrieved. First we calculated the epoch for the second message based by using the current date and the second time entry from the Communication Record.

$ date --date="Apr 25 08:15:00 2015" +%s
1429964100

Then we attempted to retrieve the second image from the same directory using the resulting string using the following URL: bsidesroc.com/D0noV4n/1429964100.png

Message 2 / 6

It worked! The next step was to retrieve the rest of the messages using the same process. The resulting epoch strings were:
1429965000, 1429977900, 1429978800, and 1429990625. Which resulted in the following images:
Message 3 / 6

Message 4 / 6

Message 5/6


Message 6 / 6
Clearly message 6 was was different from the rest, but we opted to try and solve the messages in the order in which they were sent. But what to do next? My initial thought was to pull the RGB values from the pixels, and convert to hex and see what happened. Each of the boxes was set to a repeating RGB value, which with Anthony's help we extracting using a fairly simple image processing script. I had to modify it a bit for my system since I still use Python 2.7.9 but it's essentially the same. By running the script and providing it an image file, the resulting hex will be output.


$ python image_to_hex.py ./1429963200.png 
cf 87 ba 22 1c 16 50
69 db 73 16 34 42 48
14 30 6a 30 e1 73 51
ab 26 35 00 63 42 6d
02 82 30 df 25 6e 40
34 12 6b 7b 73 46 1f

2c f1 0e 1d 55 15 47

For the rest of the images, the process was the same and resulted in the following:

Message 2:
c0 8e d9 df 25 78 0c
71 bc 82 64 19 40 05
de 0c 40 1e 58 0b ad
86 78 68 01 61 0b 4d
0f 3c c7 b6 c8 57 7c
12 68 7b a6 1c ae 45
46 5d 28 7f 7f ef 16

Message 3:
56 06 c6 ff a2 82 8c
1e aa ba a2 9d 97 0a
e6 37 c7 26 6c ca 90
33 14 ed 02 06 28 86
76 00 c9 b7 f5 c6 e4
8a b1 12 83 d5 92 c1
63 41 e3 98 4e df 46

Message 4:
a2 e1 91 18 c9 86 5a
e9 fe ee bb e2 67 96
ca 19 a5 6e 01 fa 51
e3 82 29 03 a2 8e 1a
93 32 d4 fd 65 b9 d5
86 ea bd fa be f0 32
a0 60 55 cf 57 8f ac

Message 5:
d9 9a 52 43 16 e4 00
07 3a 1d 7c 63 cb f0
cc 8d 73 c7 f7 19 63
ab 42 63 04 04 ee f6
6b 96 76 33 01 36 11
75 a0 0a a9 80 fe 30
de f8 8e 6b bf 65 36

Notice that the center block of each image increments. I've bolded it in the output above. Since this this is the case on all of the messages, we decided not to include it as part of the key or ciphertext. We hit our first block here for a bit trying to figure out how to decrypt the text with no discernable key. Back to the main Resistance Page to hunt for another clue.

One thing that we found interesting on the Resistance page was the red V at the top. It was different from the initial V that we found on the BSides homepage, it was more... pixelated. 

As it turned out, the image above was 7 "pixels" wide and 7 "pixels" tall, which matched directly with our gray blob images. Our first mistake where was assuming that the blocks in red were our key and the rest were the ciphertext (excluding the predictable middle block). The initial math seemed to workout too, 49 blocks - center block = 48, of those, 12 were red and 36 were white. Using that, Anthony came through again with another script that would extract the red blocks to create a key, and decrypt each ciphertext block with the next red block. By repeating the key three times this should work! But it didn't

Darth provided another clue which referenced that the puzzle had some influences from a PoC || GTFO article. Digging back through the archive, we came across PoC || GTFO 0x03 which contained an article which detailed how to create a PDF file that could also be a valid JPEG. Further research showed that this could also be done using a PNG and ZIP file. So we downloaded the above PNG, renamed it as a .ZIP and extracted it. Yes, really. Try it with the image above.

By unzipping the image file we get an extracted img.png which looks like this:

A bit garbled, no?

It was a bit garbled, but gave us the information we needed to decrypt each of the gray blob messages. By using the information that we can read, we can logically deduce the proper order of the ciphertext and key blocks. As a visual reference, I've reconstructed what the original image likely looked like.

That's better
Note that using this method, there were 32 blocks of ciphertext in the four colors shown above along with 16 blocks which made up the decryption key. Here we ended up scripting the decryption of the first 5 messages by extracting the key and ciphertext blocks, XORing them and outputting the resulting plaintext. Running this on the five encrypted message resulted in the following plaintext:

Plaintext 1:
HaveContactedLeaderOfResistance.

Plaintext 2:
NeedExtendedChanForImportantMesg

Plaintext 3:
PleaseReplyWithReqdMethodAndKeyX

Plaintext 4:
Cols:0541378629.Alpha:AI.RST.ONE

Plaintext 5:
Checkerboard.Extra 0x2e and 0x21

Progress! But we were running out of time. We had that odd sixth message which consisted all of numbers, and the information in the five messages above provided the final clue as to how to extract our important message. In the fifth message there is a reference to a Checkerboard Extra. We all hit Google to try and figure out how to handle this. We came across information relating to a "Straddle Checkerboard Cipher" which is located here. We were fairly certain this was the proper method, but since no one was familiar with it, it took some time to figure out how to properly configure our board. All the information we needed was in the five plaintext messages.

With a Checkerboard you first create the top column layout, which consists of the digits 0-9 and can be in any order. Decoded message 4 above shows that this order is 0541378629. The next step is to determine how the rest of the checkerboard should be laid out which requires a key to make it unpredictable. Message 4 again shows how the alpha key row is configured: AI.RST.ONE

If we lay out the first two rows, they'd look like this:

0541378629
AI.RST.ONE

But what about the rest? Well with checkerboard ciphers, the spots in that first alpha row that don't contain letters become row identifiers for the rest of the alphabet. In this case column 4 and 8 didn't contain any of our A-Z letters, so they would become the next two rows in our checkerboard. We then populated the rest of the board with our remaining letters.

  0541378629
  AI.RST.ONE
4:BCDFGHJKLM
8:PQUVWXYZ

But wait, there are still two spots available? The fifth plaintext message explains what to use there, ASCII 0x2e and 0x21 which are . and !, respectively. Our final checkerboard cipher is as follows:

  0541378629
  AI.RST.ONE
4:BCDFGHJKLM
8:PQUVWXYZ.!

This is where I started cursing Darth's name. The sixth message contained 209 digits which mapped to a plaintext letter using our checkerboard cipher. One by one (or two by two), we went through the decryption to get our plaintext. As an example, the first row of number in the sixth message was: 

7 942428298191886298274707

Decryption works as follows. If the digit matches a letter in the first column, then take the resulting plaintext letter. Our first digit is 7, which maps to the T plaintext letter. This is highlighted below for clarity.

  0541378629
  AI.RST.ONE
4:BCDFGHJKLM
8:PQUVWXYZ.!

7 942428298191886298274707

We then move to the next digit, 9. Again, this matches the first row, so we can take the resulting plaintext letter, E.


  0541378629
  AI.RST.ONE
4:BCDFGHJKLM
8:PQUVWXYZ.!

7 9 42428298191886298274707
T E

That means our final message begins with "TE". But we hit a snag on the next number, it's a 4 and there's nothing that maps to a 4 on the first row, it's empty! In this case we go to the second row labeled with the 4 and use the next digit from our ciphertext, in this case it's a 2. Our resulting plaintext is an "L". 


  0541378629
  AI.RST.ONE
4:BCDFGHJKLM
8:PQUVWXYZ.!


 7 9 42 428298191886298274707
 T E L  

The next ciphertext digit is again a 4 followed by a 2, so we'll end up with an "L" again.



  0541378629
  AI.RST.ONE
4:BCDFGHJKLM
8:PQUVWXYZ.!


 7 9 42 42 8298191886298274707
 T E L  L

The next ciphertext digit is an 8, so here we need to go to the third row, and match up to column 2. The plaintext here is "." which we interpreted as a space in the plaintext.


  0541378629
  AI.RST.ONE
4:BCDFGHJKLM
8:PQUVWXYZ.!

 7 9 42 42 82 98191886298274707
 T E L  L  .  

The process continues in this fashion until our final, super important message is revealed:

TELL EVERYONE THAT THE LEADER IS A RED LECTROID FROM PLANET TEN! ITS A COOKBOOK! SOYLENT GREEN! YOU MANIACS! YOU BLEW IT UP! ROSEBUD

We were very happy to win the challenge again. Many thanks to Darth for creating the puzzle. With any luck he'll travel up to Rochester next year. We're looking forward to it.

See you all next year!

No comments:

Post a Comment