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

```
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:

```
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):

```
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`

.