Hack.lu CTF 2012: Mealtime (200 points)

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

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.

Permalink & comments

LSE Blog

Operating systems, computer security, languages theory, and even more!

Hack.lu CTF 2012: Mealtime (200 points)