Blackhat 2013 Sophos Puzzle

August 7th, 2013 by Strawp

Recently, Sophos like to mark attendance at a trade show by running a geeky puzzle competition and they’ve just done one for blackhat, which I actually managed to finish.

A hackable crossword puzzle

The puzzle started with a fairly straightforward crossword. Now, I’m terrible at crosswords, but fortunately this crossword had an answer checking function in its Javascript source code which contained hashes of the answers, using its own simple hashing function:

AnswerHash = new Array(81594, 21864, 31173, 82603, 59177, 71467, 9693, 97258, 
  92537, 49915, 30431, 16251, 59242, 66492, 67266, 96088, 2956, 97195, 73488, 
  73937, 38947, 81055);
...
// Returns a one-way hash for a word.
function HashWord(Word)
{
    var x = (Word.charCodeAt(0) * 719) % 1138;
    var Hash = 837;
    var i;
    for (i = 1; i <= Word.length; i++)
        Hash = (Hash * i + 5 + (Word.charCodeAt(i - 1) - 64) * x) % 98503;
    return Hash;
}

Porting this into PHP (my default scripting language) and using /usr/share/dict/words, it was pretty simple to solve a good number of the questions automatically. The hashing algorithm was prone to a lot of collisions, but narrowing down the possible words by length helped. I checked this worked properly against an easy clue: “How information starts its life”, which of course is “data”.

This technique gave me a nice spread of completed words across the board:

    • Decrement RCX and branch if not zero.: loop
    • The moves a pentester makes once he’s in.: lateral
    • Autonomous software (but not quite a virus).: agent
    • It’s not a lens, but it’s focused on you anyway.: prism
    • Vulnerabilities that really work.: exploits
    • How information starts its life.: data
    • On the Mac, it’s Option E.: acute
    • Where you set up the base pointer.: prolog
    • The guy who’ll win in the Apple-Samsung case.: attorney
    • What amateur cryptograms are always claimed to be.: airtight
    • Apple couldn’t bring themselves to call it Wi-Fi.: airport
    • Whitfield Diffie helped you share it.: secret
    • What the BlackHat trade show staff are really after.: leads

Then spotting a few more easy ones: “You’ll read it if you want to win the prize. [5,8]” is of courseNaked Security“, “What you do to your code when you’re in a hurry.” I got worryingly quickly: “Hack at it”. A few more required some googling: “He decrypted Hittite” is Hrozny. Curiously the last clue to get was “Why you are doing this puzzle”. “it’s fun” and “I’m bored” didn’t fit in, but I had enough letters that I could come up with possible combinations of words based on the words list and grep. You can do this with any crossword e.g. the first word “_H_E_” can be found with:

grep -i "^.h.e.$" /usr/share/dict/words

and the last word with

grep -i "^.r.n.e.$" /usr/share/dict/words

Despite the middle letter being “d” and “three” coming up in the first list, I still didn’t spot the answer (see, terrible at crosswords) so I combined the 26 possible first words with the 45 possible last words, creating a list of 1170 possible words, which I could then just run the hashing function against to reveal the right answer. This made me feel simultaneously cunning and stupid.

soln

The completed crossword

 

Moving on…

Counting in binary

As per the instructions on the competition page, this then gives you a string of 6 letters which form the password for the zip file containing the next stage, however you don’t know the case of each letter, which effectively means there are 2^6 possible passwords for the zip file. By considering an uppercase character as 1 and a lowercase character as 0, this is basically the same as counting from 0 to 64 in binary. e.g. if the possible letters were ABCDEF, you would first try abcdef, then abcdeF, abcdEf, abcdEF etc.

I wrote a simple script to create the word list and then ran “unzip -P [word] snodwen-message.zip” against each word. This gets you to the next stage.

Oh God, not FORTRAN

I hadn’t seen a line of FORTRAN for 12 blissful years until this point. The not-so-subtle reference to current affairs was a message as follows:

Dear Reader,

This is Teddy Snodwen speaking.

You don’t know me, and I don’t know you, but we may be able to help each other.

I have some private data I’ve encrypted, but I’m having some travel problems right now, with the result that I’m concerned about getting stuck in no-man’s land at some airport, unable to leave, or proceed, or get at my data.

So I have prepared a series of files from which anyone who’d like to help can extract a secret code that can be read out over the phone, or even just held up to the glass in the transit area for me to copy down.

When you’re ready, you’ll need a PDF file from here:

http://nakedsecurity.sophos.com/bh2013-sophospuzzle-the-snodwen-file

And you’ll need the password, a nine-digit number you can calculate with this simple algorithm, which I’ve written in my favourite programming language, MR-ISP.

It’s a rare dialect of FORTRAN:

P=1
DO 51 I=1,1000000000
P=1+1/P
51 CONTINUE
S=0
Q=1
DO 52 I=1,9
S=S*10
S=S+(INT(P*(10**Q)) MOD 10)
Q=Q*10
52 CONTINUE

I know you won’t so much as think of cracking the code until I give the signal, since gentlefolk don’t read other gentlefolks’ email.

And with that, I remain,

Yours sincerely,

Teddy Snodwen (Mr)

MR-ISP, eh? Subtle.

With some minor tweeks, that just about runs in FORTRAN, however unfortunately what you will very quickly notice is that the code is dealing with stupendously large numbers and a stupendously large precision number. The code is basically split into two parts:

Part 1: Iterate 1 billion times over the equation for phi to have that value to a very high degree of accuracy.
Part 2: Select digits from the decimal places of phi, in orders of magnitude increasing by 10. i.e. 1st decimal place, 10th, 100th, 1000th etc.

This doesn’t work in pretty much any programming language unless you use a library with which you can specify arbitrary precision of your numbers. So there are two ways of solving this:

  1. Find an arbitrary precision library for FORTRAN, get it to work with the above code, run the code
  2. Some other way which means I don’t have to touch any more FORTRAN or start looking for arbitrary precision libraries in another language

Obviously I chose #2. I can’t have been the first person on the internet to calculate phi to a ludicrous degree of accuracy. Indeed not. Someone had also written a program called y-cruncher which calculates famous constants to arbitrary precision and outputs them to a text file. Much nicer. I could then just pick out the digits by hand and come up with the 9 digit password for the PDF. Next.

Onion Skins Of Encryption

The Unlocked PDF has the URL and password for the next stage – another zip file. This contains a single text file – “e.9” – which contains Lua code. It’s clear from the first few characters that the code is an array of data encrypted using an XOR at some point:

k=11179023 o=bit32.bxor t=string.char f=math.floor c={
6501666,4735189,10824306,11719312,15507616,3654640,12739110
...
} function xit(n) local x=o(11994318,n) for i=1,24 do x=x*2 if x>=2^24 then x=o(x,25578747) end end return x end
function tit(n) return t(n%256)..t(f(n/256)%256)..t(f(n/65536)%256) end
p='' for i=1,#c do p=p..tit(o(k,c[i])) k=xit(k) end load(p)()

The code takes a very large array of integers, then iterates over them, XORing each integer against a key, then splitting the result into 3 bytes, adding that to a string and then creating a new key for the next iteration by shifting the old key one binary place to the left and then XORing that against a fixed number. Once all the iterations have finished the resulting string is loaded as Lua code and ran.

The first thing you would do once getting to this stage is to just run the code as is. You quickly find that:

  1. It takes ages
  2. It produces garbage

Clearly you need to change a few things. First of all, you don’t need to iterate over the entire array to find if it’s worked or not. Iterate over just 10 values by switching “#c” for “10” and switching “load(p)()” for “print(p)”. The next thing you have to do is make a few assumptions. What’s broken? The algorithm looks OK, so maybe the initial key isn’t right. To find a key for an XOR encrypted text is fairly easy if you know what the unencrypted text is for a part of the cypher text larger or equal to they key. The key is only 3 bytes long (only 3 characters), so this shouldn’t be too hard. I hadn’t used Lua before but to me, it looked like the last line “load(p)()” was treating “p” like a function and running it. Maybe the first line contains a function definition? I tried XORing the first 3 bytes of the cypher text against “fun” as in “function” using this code added to the end of e.9, replacing the normal decrypt loop:

function untit(test)
  return string.byte(test,1)+string.byte( test, 2 )*256+string.byte(test,3)*65536
end
test="fun"
v=untit(test)
k = o(c[1],v)
p = ''
for j=1,#c 
do 
	print( j.."/"..#c )
	p=p..tit(o(k,c[j])) 
	k=xit(k)
	if j>10 and not string.match( p, "function" ) then
	break
	end
end

This provides the reverse function of “tit”, “untit” and attempts to start the decryption by setting the initial key as the result of XORing the first 3 bytes with “fun”. If after 10 iterations the resulting string doesn’t contain “function” then the loop exits. If it does, then the decryption has worked and it continues to decrypt the rest of the array.

This didn’t work. The decrypted text clearly didn’t start with “fun”. So what then? The clue is the filename, “e.9”. The “e” is probably for “encryption” and the “9”? How about the 9th iteration? Suppose the file decrypts another selection of encrypted text? If it used the same algorithm that would mean the file started with “k=” and then a number between 0 and 9. Only 10 possible combinations of clear text for the first three bytes! I then took the above code and put it in a loop:

m = "k="
for i=0,9
do
  test = m..i
  v=untit(test)
  k = o(c[1],v)
  p = ''
  print( i )
  for j=1,#c 
  do 
    print( j.."/"..#c )
    p=p..tit(o(k,c[j])) 
    k=xit(k)
    if j>10 and not string.match( p, "bit32" ) then
      break
    end
  end
  if string.match( p, "bit32" ) then 
    print( test..": "..untit( k  ))
    print(p)
    file = io.open( "e.8", "w" )
    file:write(p)
    file:close()
  end
end

This attempts to decrypt using the known plaintext of “k=0”, “k=1” up to “k=9”. It then lets the algorithm carry on for 10 iterations and then tests to see if “bit32” has come out in the resulting string, as we know that this is also at the start of the code. If it has, it carries on decrypting the code and then writes it to file “e.8”.

As suspected, e.8 is basically the same, but slightly smaller. I could then just replace the array in my code with e.8’s, run it again and find e.7. Repeating this, you eventually get down to “e.1” and it stops working, suggesting that “e.0” doesn’t have the same code in it. We need a new known plaintext. Assuming e.0 was still Lua code, I tried a few things, eventually finding that it starts with “print”.

Extreme checksum

This is the final message:

print[[
In stage 1, you solved a crossword, extracted 24 characters 
from the completed grid, and used six of those characters to 
form a password.

Now take the remaining 18 characters and write them down in 
reverse alphabetic order (Z..A).

Then write a dollar sign.

In stage two, you calculated more than 400,000,000 decimal 
places of a certain transcendental number, and used nine of 
those digits to form a password.

Now write down the nine digits from decimal places 
100,000,001 to 100,000,009 inclusive.

Then write a dollar sign.

Now write four alphabetic characters (A-Z) of your choosing.

You should have a string of 33 characters. Ensure all letters 
are upper case.

Calculate the 512-bit SHA-3 hash of this string, print it as 
hexadecimal characters and use the first 20 as your answer.

Submit your answer as detailed here:

http://nakedsecurity.sophos.com/bh2013-final
]]

Fun! Basically, “You got this far, now prove again that you didn’t cheat”. If you were diligent in the early stages, you will have saved all your answers as you went along and this won’t take long. I took a screenshot of my crossword, thankfully but failed to save my digits of phi, so I had to do that bit again.

What’s with the last 4 characters? The puzzle author will check your hash against a rainbow table1 of 26^4 possible combinations to check you have the right answer, and presumably to restrict sharing of the hash.

Thanks to Paul Ducklin for the puzzle. It had a really nice difficulty curve that drew me in with an easy crossword and before too long I was writing in two programming languages I usually don’t touch.

[1] From the author:

“Less of a rainbow table and more of a list…only 26^4 options (about 0.5M).”

, however I consider anything I wouldn’t want to write by hand a rainbow table. Shopping list, you can do manually. Shopping rainbow table would be very expensive.

Comments are closed.