Baby Bear

Framework

baby_bear challenge was classified as reversing challenge. The file was given and was 64-bit x86-64 statically linked file.
In order to get the flag, it was needed to connect a remote session and challenge the remote session baby_bear process. Runnning readelf on the baby_bear file find two sections, one of them is UPX0 and the other is bss. After we’ve extracted the UPX section is was found that this is a wrong analyze of readelf and not a real UPX-packed executable. No libc is linked. All communication etc. is done via direct syscalls.

First Look

At the beginning, the process opened /dev/urandom and read 0x10 bytes. Afterward it takes those bytes and convert them to a bit stream.
At the end of the initialization state the start procedure jumps to the next part of the program.
The next part is a number of small assembly snippets, each of which implements a different obfuscated check for whether the next bit in the input stream is zero of one, and performs some operations as a result. Operations can include writing a bit to the output stream, and jumping to another snippet. There are a lot of different snippets, which jump to each other, and it is not clear what the overall algorithm is.

running the baby_bear file result is

$ ./baby_bear

and wait for user input.

Deeper inspection

The only real function is the one at at 0x4000B0.
This function write an input byte of 0 or 1 to the output stream, and if the number of bytes written to the output is 0x2E, it stops the ‘calculation’ process, and starts the input and checking process.
It asks the user for some input bytes, then runs the same calculation process it ran on
the random bytes on the input.
If the output of the two algorithms are the same (0x2E bytes) the flag is retrieved.
All the code snippets can read bits from the input stream, do some calculations and call another snippet or call the write to memory function.

Solving

In the call/jump flow we assume no function is returned. So we reversed all the code snippet and translate them to python, where any jump or call converted to call the correlated snippet function.
After we got a python script which emulate the same output as the algorithm as the baby_bear binary, we built a table of all the inputs bitstreams which are less than 8 bits and call to the start of the algorithm in the 2nd time. Because this algorithm is deterministic and consume each bit only once, we were able to concatenate multiple bitstreams from the input in order to get the requested output.
Now we just had to split the bitstream baby_bear wrote and find in our table. and pack it back to a 19 bytes stream and write it to the remote baby_bear process stdin.