• Hack.lu CTF 2012: Mealtime (200 points)

Written by Pierre Bourdon
October 25, 2012 at 11:00

 ``` 1 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 several `cnf_*` 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` and `dw2`: `615f7a6e 645f6572`.

Repeating this technique on the three remaining 64 bits blocks gives us the following key: `--delicious_brainz_are_delicious`.