CTF Writeup - TUM CTF Teaser - whitebox crypto (Rev 20)

• Name - whitebox crypto
• Category - Reverse Engineering
• Points - 20
• Description - Do not panic, it's only XTEA! I wonder what the key was...
• Binary - Download here

According to the description we're required to find the key used by the 64-bit ELF binary to encrypt the input. We're also given the algorithm used: XTEA, eXtended Tiny Encryption Algorithm. The following is a C implementation of the encrypting part of the XTEA algorithm:

    void encipher (unsigned int num_rounds, uint32_t v[2], uint32_t const key[4]) {
        unsigned int i;
        uint32_t v0=v[0], v1=v[1], sum=0, delta=0x9E3779B9;
        for (i=0; i < num_rounds; i++) {
            v0 += (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + key[sum & 3]);
            sum += delta;
            v1 += (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + key[(sum>>11) & 3]);
        }
        v[0]=v0; v[1]=v1;
    }

One cycle of the XTEA algorithm consists of 2 Feistel rounds:

A few things to notice are 1) the key is used as is, i.e. it's not used to derive a longer key and 2) the key is split into 4 equal parts. Let's look at the enciphering function in the binary:

The function has been redacted as it contains 32 cycles. From the above C implementation and the Feistel-rounds image, we know that some constant delta is being added to the key at each cycle. Like the key, the delta is also constant. The fact that there are no instructions in the binary that add 2 constants together means that, the addition of delta and the key has been pre-computed and hard coded in the program. This leaves us with the following 4 potentially-interesting instructions:

xor eax, 7B707868h
xor r10d, 1B58EA2Eh
xor r9d, 0BA9AE30h
xor r12d, 9BD661DBh

The 1st time a part of the key is used, it is used as is since the sum is 0 at this point. The 2nd and 3rd time a part of the key is used, it is incremented by delta, the 4th and 5th by (delta * 2), and so on. With this in hand let's compute the original key.

      1) 0x7B707868 => {pxh

      2) 0x1B58EA2E - Delta => 0x1B58EA2E - 0x9E3779B9 => 0x7D217075 => }!pu

      3) 0x0BA9AE30 - Delta => 0x0BA9AE30 - 0x9E3779B9 => 0x6D723477 => mr4w

      4) 0x9BD661DB - (2 * Delta) => 0x0BA9AE30 - 0x3C6EF372 => 0x5F676E69 => _gni

Combining we get: hxp{w4rming_up!}