HackTM - Babybear
Babybear was a simple reversing challenge, and I solved it the hard way by reversing the whole thing.
user@KARCH ~/ctf/bear % ./baby_bear
(c).-.(c) █ █ █ █
/ ._. \ █ █ █ █
__\( Y )/__ █ ███ ███ ███ █ █ ███ ███ ███ █ ██
(_.-/'-'\-._) █ █ █ █ █ █ █ ██ █ █ █████ █ █ ██
|| X || █ █ █ █ █ █ █ █ █ █ █ █ █ █
_.' `-' '._ █ ███ ███ ███ █ ███ ███ ███ █
(.-./`-'\.-.) █
`-' `-' █ Baby bear says: 1110111010010001101111100110000001110000000110
What do you say? AAAAAAAA
1111001100110011001100110011001101000101010101
Baby bear is thinking...
"Someone's been eating my porridge and they ate it all up!" cried the Baby bear.
There is some translation function, which translates input into a sequence of 1s and 0s. The challenge is to find some input which leads to the same sequence as the one babybear got. Bruteforcing is not an option because we neet to proove against the remote server and the secret is a 16Byte value from urandom.
Unpacking
The whole thing is UPX packed, however it would not unpack by using the default UPX tool. So I just started the packed executable in radare2, continued until the text input appears, and took a memory snapshot of the unpacked region. (which is a valid ELF file for itself as well)
[0x004005dd]> dm
0x0000000000400000 - 0x0000000000401000 * usr 4K s r-x /home/user/ctf/bear/baby_bear /home/user/ctf/bear/baby_bear ; map.home_user_ctf_bear_baby_bear.r_x
0x0000000000600000 - 0x0000000000601000 - usr 4K s rwx /home/user/ctf/bear/baby_bear /home/user/ctf/bear/baby_bear ; map.home_user_ctf_bear_baby_bear.rwx
0x0000000000601000 - 0x0000000000602000 - usr 4K s rwx unk0 unk0 ; map.unk0.rwx
0x00007ffc88b21000 - 0x00007ffc88b43000 - usr 136K s rwx [stack] [stack] ; map.stack_.rwx
0x00007ffc88bcd000 - 0x00007ffc88bd0000 - usr 12K s r-- [vvar] [vvar] ; map.vvar_.r
0x00007ffc88bd0000 - 0x00007ffc88bd1000 - usr 4K s r-x [vdso] [vdso] ; map.vdso_.r_x
[0x004005dd]> s 0x0000000000600000
[0x00600000]> dmd
Dumped 4096 byte(s) into 0x00600000-0x00601000-rwx.dmp
[0x00600000]>
We can now continue working with the unpacked version.
Reversing
Initially my first thought was to just bruteforce byte by byte, as the input seemed to be transformed linear (i.e. leaving the first byte the same leads to the same start of the output sequence). But as the challenge was network based I was afraid of hitting a timeout before I could obain some result. So I started reversing the translation function. As the binary seemed to be handwritten in assembly this was a little painful.
Basically what it does is creating a binary representation of the input bytes in memory. Then it traverses some Graph, where each node consumes one bit of the input. Depending on the input the next node is choosen, and sometimes value(s) are omitted (“1” or “0”, leading to the output sequence). After 46 omitted values the translation function returns.
So what I did was placing brakepoints on all cmpsb byte [rsi], byte ptr [rdi], scasb al, byte [rdi] and lodsb al, byte [rsi] instructions, as well as on the output function. Those are my nodes. Then I took pen and paper and traced the graph for a known input until I reconstructed the whole graph. This was some kind of a sisiphus work and I got mad on every new node, but it must have been worse for the challenge author to construct this task in plain ASM :D
Then, I implemented the graph in Python so I could perform a fast translation. Based on this I did a simple bruteforce search, even had to limitate the amount of states kept to 10 to avoid a combinatorial explosion.
import string
class Graph:
def __init__(self, data):
self.path = []
self.data = data[:]
self.length = 0x2e
def finished(self):
return self.length <= 0 or not self.data
def emit(self, value):
self.path.append(value)
self.length -= 1
def x366(self, x):
if x:
self.emit(1)
return self.x34d
self.emit(0)
return self.x3de
def x34d(self, x):
if x:
return self.x457
return self.x40b
def x457(self, x):
if x:
self.emit(0)
return self.x3b0
return self.x37e
def x40b(self, x):
if x:
self.emit(1)
self.emit(0)
return self.x3b0
self.emit(1)
return self.x37e
def x3de(self, x):
if x:
self.emit(0)
return self.x379
return self.x3e9
def x3e9(self, x):
if x:
return self.x37e
self.emit(0)
return self.x470
def x470(self, x):
if x:
self.emit(1)
return self.x482
return self.x44c
def x44c(self, x):
if x:
self.emit(0)
return self.x3c4
return self.x3c7
def x482(self, x):
if x:
self.emit(0)
return self.x3c4
return self.x44c
def x3c4(self, x):
if x:
return self.x3c7
return self.x366
def x3c7(self, x):
if x:
self.emit(1)
return self.x366
self.emit(1)
return self.x11b
def x11b(self, x):
if x:
return self.x366
self.emit(0)
return self.x470
def x39c(self, x):
if x:
self.emit(0)
return self.x3b0
self.emit(1)
return self.x482
def x3b0(self, x):
if x:
self.emit(0)
return self.x3c4
return self.x366
def x37e(self, x):
if x:
return self.x39c
self.emit(1)
return self.x482
def x379(self, x):
if x:
return self.x40b
return self.x37e
def traverse(self):
current = self.x366
while not self.finished():
current = current(self.data.pop(0))
return self.path
def tobin(key):
res = ''
for c in key:
res += '{:08b}'.format(ord(c))[::-1]
return [1 if c == '1' else 0 for c in res]
def arrstartswith(arr, pre):
return arr[:len(pre)] == pre
result = [1 if x == '1' else 0 for x in '0010111111001000100111101111111011000100100100']
states = ['']
for _ in range(12):
newstates = []
for state in states:
newstates += [state + x for x in string.letters]
states = filter(lambda x: arrstartswith(result, Graph(tobin(x)).traverse()), newstates)[:10]
print(states)