Monday, 26 October 2015

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!}

Sunday, 25 October 2015

CTF Writeup - TUM CTF Teaser - selftest (Rev 10)

  • Name - selftest
  • Category - Reverse Engineering
  • Points - 10
  • Description - Baby's 1st
  • Binary - Download here

This 64-bit ELF was the easiest of the RE lot. The binary is given to us but to get the flag we need to netcat, suggesting that the key is not embedded in the binary itself. Let's connect to it and try our luck:

Command Prompt
C:\>ncat 1060 some_random_stuff :( C:\>

No surprises there. Let's look at it under IDA.

It's easy to see where we need to end up to manage to get the flag. Also, this confirms that the key is not in the binary. The following is the beginning of the program:

The first block tells us that our input is interpreted as hex and is ORed with RSI, which is 0x8000000000000000. The second block takes this number and creates a character-count map of it. For example let's say we input c0ffee, this is then ORed with 0x8000000000000000, which results in 0x8000000000c0ffee, giving us the following character-count map:

With this pinned out, we take a look at the validation routine.

The validation loop operates on the character-count map in reverse order and does the following:
  1. If the byte read is 0x00, jump to the next one.
  2. If the byte read is not 0x00 and is equal to the character it represents, jump to the next one.
  3. If the byte read is not 0x00 and is NOT equal to the character it represents, FAIL.

Simply put, an input string is valid if the occurrences of its bytes are equal to the bytes themselves. Keep in mind that OR 0x8000000000000000 might mess up the string. This means that the following are all valid strings:
  • 8888888 (There's 7 of them because RSI starts with 0x8000000000000000)
  • 18888888
  • 13338888888

Trying the first one out:

Command Prompt
C:\>ncat 1060 8888888 hxp{g00d_m0rning_r3v3r53r5} :) C:\>