Tuesday, April 9, 2013

2013 BSides ROC Crypto Challenge Write-Up


Members of the SUNY IT Network and Computer Security Club attended the Security BSides hacker conference in Rochester on April 6th. The BSidesROC event consisted of a number of security and computer related talks and games. One of the games at the conference was the Crypto Challenge, created by Darth Null (@DarthNull). The group was determined on solving the challenge and dedicated a good portion of the day attempting to decrypt the message. After the CTF Battleship was hacked, more members dedicated their time to the Crypto Challenge.

There were four pieces of the puzzle required to solve the riddle, a 27x27 “tableau” printed on a piece of paper located on each of the tables in the main hall, a 10x10 grid of characters printed on the event schedule and shown on the projector, a spreadsheet of 237 single-digit numbers taped on the wall in various locations around the event area, and another 10x10 battleship style game board printed on the Presentation posters hung around the event area. The following will outline the process taken to finally solve the riddle.

First, the projector and the conference schedule had a 10x10 grid with each cell containing a single letter. The projector labeled the grid as “Axis”; there was no title given for the grid on the BSides schedule (Fig. 1). Both 10x10 grids contained the same set of characters. This was the first piece of the puzzle necessary for obtaining the tableau key.

Fig 1. "Axis" character grid


This grid alone doesn’t really give any information by itself. And there was no discernable pattern to the text given in the cells. One of the members noticed an interesting image on one of the Presentation documents hanging on the wall. This  image is shown in Fig. 2.

Fig 2. Interesting diagram on the Presentations poster


The grid on the Presentation poster was what appeared to be a “Battleship” grid with hits and misse. It was also a 10x10 grid, which happened to match the size of the Axis grid shown above. The image from the poster has been re-created in Fig. 3, below.

Fig 3. Digital recreation of the image shown on Fig. 2


After assuming that these grids had something in common, we decided to map the “hits” on the ships to the letters on the other grid. These two grids have been combined together in Fig. 4 below. Note that the “hits” on the letters are shown in red.

Fig 4. Mapping the two grids


If we take the hits on the ships we get “MREASSYISEEK”, which is an anagram for “MISSES ARE KEY”. We assumed that this meant the shots that were shown on the board that did not hit a ship. So, we took the letters that did not hit a ship from the grid and we got “BOSSERDIC”, which is another anagram for “BSIDESROC”. Bingo, we have our key.

Now that we had the key we had to set up the tableau that was provided as part of the challenge. The tableau, labeled “Broh, do you even crypto?” was a grid separated into 9 blocks (in a 3x3 grid fashion) where each block was itself a 9x9 grid of letters. The tableau in its original form is shown in Fig. 5.

Fig 5. Original tableau layout


We noticed the string “SOOPERSEKRIT” going down the first column on the original grid. Darth Null informed us that this particular string was an example of the how to adjust the board layout if  “SOOPERSEKRIT” was the key.  Since we had our “BSIDESROC” key, we adjusted the board in a similar fashion. The board is adjusted by shifting each row in the tableau until the desired character is in the first column, then moving to the next row and doing the same until the key is shown down the first column. Since the original board had “SOOPERSEKRIT” down the first column only once, we modified our board in a similar fashion. This is shown in Fig. 6 as “Modified tableau - version 1”. We worked with this version of the board for a while without success, and we were later informed via a hint by Darth Null that the key should be repeated down the first column unlike in the example on the original board. We made the necessary adjustments and ended up with the tableau shown in Fig. 7.

Fig 6. Modified tableau- version 1


Fig 7. Final tableau layout



Now for the spreadsheet of numbers. This was posted on the wall and looked like an Excel-type spreadsheet. Each cell in the spreadsheet contained a single digit from 1-9. The spreadsheet was made up of 37 columns and 7 rows but the last row only had the first 15 cells filled in, giving a total of 237 1-digit cells.  We assumed that this was our cipher text, but we weren’t quite sure how to make it work. Another hint provided to us said that the final plaintext message was less than 80 characters and our calculations showed that 237 happened to be (3x79) so that verified our assumption that we had our ciphertext. The full list of all 237 digits is shown below, in the order given on the spreadsheet.

Cipher text:
844561197184312585915186981735259268157671728611367354752225878443358155879551297139633218482484217556657911456882665714359232739948713143697659824568783421973478884319326287389344646872435466961747455834131416553352693331174475726425756

By splitting the cipher text in to tuples of 3 digits we figured that this could be used to map out a specific character in the tableau. For example, the first 3 digits of the cipher text are 8,4,4 this could be interpreted as Block 8, Row 4, Column 4. This allowed us to map out any specific cell in the tableau, since there were 9 blocks and each block had 9 rows and 9 columns (Fig.8 & Fig.9).

We mapped our tableau into the following blocks:

Fig 8. Tableau block layout


And each (9x9) block was mapped as follows:

Fig 9. Row/Column layout



We split our cipher text into a group of mapping coordinates in the format (BLOCK,ROW,COLUMN) and ended up with the following:

(8,4,4) (5,6,1)(1,9,7) (1,8,4) (3,1,2) (5,8,5) (9,1,5)…

We attempted to map all of these coordinates out and nothing seemed to be working out and we weren’t getting anything but garbage. We were so close but we were missing one key component. Another hint from Darth Null gave us the last piece to the puzzle. He mentioned that the cipher text was transposed, so we had to do more work to get the correct coordinates.

Since we had 3x79 coordinates, we laid them out into three equal rows and read out the coordinates from each column. This is shown below:

8 4 4 5 6 1 1 971843125859151869817352592681576717286113673547522258...
9 7 1 3 9 6 3 321848248421755665791145688266571435923273994871314369...
3 4 7 8 8 8 4 319326287389344646872435466961747455834131416553352693...

New coordinates:
(8,9,3)(4,7,4)(4,1,7)(5,3,8)(6,9,8)(1,6,8)(1,3,4)…

After mapping out all of these new coordinates (again), we ended up with the following decrypted message:

NOWTELLBSIDESROCTHATTHEMAGICWORDSARESQUEAMISHOSTRICHANDYOUWINTHECRYPTOCHALLENGE

Final Message:
NOW TELL BSIDESROC THAT THE MAGIC WORDS ARE SQUEAMISH OSTRICH AND YOU WIN THE CRYPTO CHALLENGE



2 comments:

  1. So glad you enjoyed the puzzle. Not sure I'd've said "Darth Null informed us" so much...I mean, I tried giving hints, and useful ones at that...but they weren't *that* obvious, were they?

    I tried to pick the message length so there were only two ways to arrange the numbers -- 3x79 or 79x3 -- hoping that would help you find the transposition earlier. Not quite sure that worked... That, and the repeating of the key, were meant to be the "stumbling blocks" that you had to sort of work around. That's what I meant when I suggested you review assumptions -- the assumption that the key was only used once...

    I have to say, I was getting worried there at the end, that you might not quite make the final leap. Obviously, you did. :)

    ReplyDelete
    Replies
    1. I wondered how much I should mention the hints and I didn't want to convey the idea that we managed to completely solve it without them. Your hints generally mentioned things that we had already done and/or knew, so in reality I suppose that we used them more as validation and not so much as a means to figure out the next step.

      We did try the correct transposition of the 79x3 numbers early on, but with the wrong grid layout, so the output was all garbage.

      I suppose the main hint that really solidified everything was that the key repeated, so it all kinda fell into place after that point, it just took a while to manually map out each letter. After the 9th or 10th time everything on that damn grid started to blur together.

      In either case, this was the first attempt by the club at solving a challenge like this, and we're thrilled that we managed to do so. We have a more solid understanding of the different methods involved and how they work, so perhaps next time we won't have to keep you waiting too long.

      Thanks for the comment,
      -Mike

      Delete