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.
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
0x66 alignment bytes and the
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
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
0x66 from the end is the eighteenth-to-last byte. However, there are ten contiguous
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
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) b = Byte(i+pair) # swap t = a a = b b = t # apply PatchByte(i+pair, a) PatchByte(i+pair, 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)
After running the above script, here is the final function epilogue:
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.