## Tuesday, June 4, 2013

### Sophos Puzzle 2013

So one of my friends sent me a link to the Sophos puzzle which was a cryptogram to be solved. The rules are below or you can go here:
So you can solve this year's AusSHIRT #sophospuzzle straight from the shirt, using nothing but pencil, paper and intellect. Of course, you can still throw some home-hacked scripts at the problem if you want: a little bit of brute force goes a long way, and you can leave your scripts running while you attend the conference parties.

How to get started

The puzzle is a cryptogram, which means that the letters on the cube have been scrambled using an encryption algorithm.

Encryption algorithms usually rely on a mixture of substitution, where one letter is changed into another, though not necessarily always into the same one, and transposition, where two letters are switched around, like an anagram.

The easy part in this puzzle is that the substitution always replaces each decrypted letter with the same encrypted letter.

And the letters in the answer appear in the same left-to-right, top-to-bottom order that they do on the cube.

The only transposition you need to worry about is to put the three faces in the right order, so there are only six possible combinations to worry about.

Usually, a straight letter-for-letter substitution is called a Caesar cipher.

The cipher gets its name because it was considered state-of-the-art back in 55BC, when J. Caesar first invaded Britain. He just shifted every letter two places along in the alphabet, writing C for A, D for B and so on. At the end, he wrapped round, so Y became A and Z turned into B.

Caesar ciphers are easy to solve because of repeated letters: the encrypted text shows the same bias (e.g. in English, that ETAOIN are more common than JKXQZ) as normal text.

So we've made this slightly harder than that, as follows:

Letters appearing more than once in the puzzle are all shifted by the same fixed amount (obviously, the shift is somewhere from 1 to 25). Each letter that appears just once in the puzzle is shifted by a different amount, with one letter shifted by 9, another by 8, and so on down to a shift of 1. By the way, the Sophos Shield icons are just for decoration - they don't count as letters in the puzzle.

How to get hints

Oh, and bear in mind that a dictionary attack probably wouldn't hurt, so you might like to start out by trying to guess at text that is likely to appear in the solution.

I solved it by first brute forcing the key space of 26 to find out what key shift the multiple letters were using. After finding that out I pen and papered it to find out the solution. I decided to script the ability to give every possible combination for the single letters which then could be sifted through to find the correct solution. Both the solution and code can be found after the jump or you can go here to read the nakedsec solution.

The solution is "SOPHOS SECURITY MADE SIMPLE". I found the letters with multiples key shift was 4 by brute forcing the key space and getting the results "HUQIRVMB SOPLOSSE GESIMPNE". I knew this was probably the right key shift because I saw what looked like. SOPHOS and SIMPLE. That left me with 7 letters left to solve for and I went to work with pencil and paper and solved it.

The python script I made gives every possible solution given the letter with multiples key space is 4. The output is put into a file. Below is the script which has two parts, the brute forcing of the letter with multiples key and the brute forcing of the single letters.

```import itertools

# FIND KEY FOR LETTERS THAT SHOW UP MULTIPLE TIMES
message = 'LYUMVZQF WSTPSWWI KIWMQTRI'
LETTERS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
for key in range(len(LETTERS)):
translated = ''
for symbol in message:
if symbol in LETTERS:
num = LETTERS.find(symbol)
num = num - key

if num < 0:
num = num + len(LETTERS)

translated = translated + LETTERS[num]

else:
translated = translated + symbol
print('Key #%s: %s' %(key, translated))
# KEY SHIFT = 4

# REPLACE SINGLE LETTERS WITH THERE PROPER SHIFTS
message = list('LYUMVZQF WSTPSWWI KIWMQTRI')
# CORRECT ANSWER ON LINE 178008
singleLetters = 'LYUVZFPKR'
# THE BELOW ORDER WILL PUT THE CORRECT ANSWER ON THE FIRST LINE OF THE OUTPUT FILE. THE CORRECT SOLUTION
# BUT ALL THE SHIFTS ARE CORRECT.
#singleLetters = 'ZVUYFRKPL'
LETTERS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

# GENERATE PERMUTATIONS OF THE SINGLE LETTERS
combos = itertools.permutations(singleLetters, 9)
f = open('workfile.txt', 'w')

# SHIFT EACH PERMUTATION
for combo in combos:
singleLetters = "".join(list(combo))
counter = 1
translated = ''
for symbol in singleLetters:
if symbol in LETTERS:
num = LETTERS.find(symbol)
num = num - counter
counter = counter + 1

if num < 0:
num = num + len(LETTERS)
translated = translated + LETTERS[num]

# SUBSTITUTE IN SINGLE LETTER CHANGES INTO THE ALREADY CHANGED MESSAGE WE GOT FROM DOING
# THE LETTERS THAT SHOW UP MULTIPLE TIMES SHIFT
tempMessage = list('LYUIVZMF SOPPOSSE KESIMPRE')
for index in range(9):
replaceIndex = message.index(singleLetters[index])
tempMessage[replaceIndex] = translated[index]
f.write("".join(tempMessage)+"\n")
```