PHDays CTF Quals 2014 Write-up: "miXer"

The description of the task is that the program has been stuck “in a blender.”  Upon opening the program in IDA Pro, it is clear the bytes have been modified, since there are nonsensical instructions and a large block of undecipherable bytes.

Nonsensical bytes in miXer.elf

It is clear the binary has been messed with, and from both the description and name of the task, we hypothesize that bytes have only been shuffled around, not otherwise modified (via encryption, XOR, etc.).  This hypothesis is further strengthened by examining the end of the shuffled function: the epilogue is visible here from the 0x90 and 0x66 alignment bytes and the 0xc3 (ret) instruction.

The shuffled epilogue

Since we now have a solid basis on our assumption of a permutation cipher, we must determine the effective block size used.  The function range is from 0x0804845c to 0x08048830, or 980 bytes.  If an evenly divisible block size was used, and if we assume that the challenge is not impossibly complex, we assume this limits the block size to one of 5, 7, 10, 14, 20, or 28.  By again examining the function epilogue, we note that 0xc3 is the twentieth-to-last shuffled byte, and the furthest 0x90 or 0x66 from the end is the eighteenth-to-last byte.  However, there are ten contiguous 0x90/0x66 bytes at the end of the range, meaning that the window size must be at least ten if the eighteenth-to-last byte will also fall into place after the 0xc3.

I used IDAPython and the PatchByte function to permute bytes to figure out the cipher.  I initially assumed the block size was 14 or 20 and spent a long time trying to get it to work by attempting to make a standard gcc function prologue at 0x0804845c.  Since there are several versions of this prologue, it also took trial and error to determine which was in use here.  I eventually determined this was not possible and another block size must have been used.  In the end, a permutation with the block size of 10 turned out to be correct.  Here is the final script to patch the program in IDA:

# Standard gcc prologue:
#   55 89 e5 57 56 53 83 e4 f0...
# Standard gcc epilogue:
#   8d 65 f4 5b 5e 5f 5d c3

swap_pairs = [
    (0,3),
    (1,9),
    (2,5),
    (3,4),
    (4,8),
    (5,6),
    (6,9),
    (7,8),
    (8,9)
]

#window_size = 0x14  Nope!
#window_size = 0x0e  Nope!
window_size = 0x0a

def swap(p):
    for i in range(0x804845c, 0x8048830, window_size):
        for pair in p:
            # get values
            a = Byte(i+pair[0])
            b = Byte(i+pair[1])

            # swap
            t = a
            a = b
            b = t

            # apply
            PatchByte(i+pair[0], a)
            PatchByte(i+pair[1], b)
    return


def reset():
    for i in range(0x804845c, 0x8048830):
        PatchByte(i, GetOriginalByte(i))
    MakeUnknown(0x804845c, 0x8048830-0x804845c, DOUNK_SIMPLE)
    return

reset()
swap(swap_pairs)
MakeUnknown(0x804845c, 0x8048830-0x804845c, DOUNK_SIMPLE)
MakeCode(0x804845c)

miXer.py

After running the above script, here is the final function epilogue:

After fixing the shuffled bytes

Patching the program on disk is simple since the offsets within the ELF are similar to the virtual addresses in IDA; only some small modifications are needed to our script.  The new ELF then runs perfectly, giving the flag.

Flag: y0ur.f1rst.fl4g