pbctf2020 Hyper Bitstreams I write-up

This challenge gives statically compiled x64 ELF binary which implements dynamic linking by itself. And there are a lot of anti reversing like self modifying, code obfuscation.

description

Heading to binary

This binary does not strip symbol information.

symbol

There are functions for resolving dynamic symbol like _dl_resolve, dl_find, _dynlink. From this, we can assume that this binary implements dynamic linking by itself.

And the main function is too simple.

main

It just compares argv[1] with encoded flag. So I thought there are hidden routine at constructor. But this challenge was not compiled using common compiler like gcc, clang, so I analyzed _start routine.

start

Most of code’s are not disassembled and IDA does not create _start as function. It means this binary was obfuscated.

As you can see, _start calls only sub_401001 function and exits. But sub_401001 function has only jmp rax.

obf

So calling sub_401001 is same with calling rax. _start assigns byte_404387 to rax and it means byte_404387 is executable instructions.

Let’s disassemble.

obf2

It assigns 0x33 at fs segment selector. 0x33 is the value of cs segment selector so it means this binary can access code segment via fs segment selector. Maybe it will be apear again later.

And next, it calls 0x40439F via sub_401001. After some tracing, I noticed that this binary has a lot of branches like jmp rax.

For binaries with a lot of branches like this one, dynamic analysis is more helpful.

Dynamic analysis

After some debugging, I found out this binary appends write permission to code section via mprotect. So obviously this binary will do self modifying.

With a little more debugging, it’ll run bitstream function which seems important.

bitstream

This function does simply call callback function with argument as bit of first argument. Calling callback runs in while loop until callback returns 0. And at this time, the callback was passed to function mod.

mod

There are a lot of calling sub_401001, and switch cases. I just traced this function and finally catched what the function does.

First, this function uses instruction operand as variable like loop count, sum, switch case number.

For example, in simple, it looks like this.

call $+5
pop r12
loop:
mov al, 4
test al, al
jz loop_end
call do_something
dec byte ptr cs:[r12+0xf]
jmp loop
loop_end:
ret

When pop r12 executed, r12 has current code address because call $+5 means calling following instruction.

And the main point is dec byte ptr cs:[r12+0xf]. r12+0xf points second operand of mov al, 4. So when this instruction executed, mov al, 4 instruction changes to mov al, 3.

So that loop runs 4 times. Really interesting technique.

Second, this function has instruction polyglot.

Let see below two pictures. This instructions are the difference between when branch was taken or not.

When branch was taken.

poly1

When branch was not taken.

poly2

It was implemented to execute add instruction if branch was taken and execute shl instruction if not.

In my opinion, this is why fs segment selector setted to 0x33 :p

Okay, so this is what mod function and does.

collect 4 bit from bitstream.
set collected 4 bit value (0~15) as loop count
in while loop:
3-1. read 1 bit
3-2. if bit is 0, do shl 1 for the given specific address.
3-3. if bit is 1, do add 1 for the given specific address.
increase 1 given specific address.
if bitstream ends, return.

Going back to the point of debugging, the mod function finally does rewriting code section.

Analyzing new code

newcode1

Newly written code is more clear. When I tried to do decompile, positive sp value has been found error was occured. But fixing SP value at 0x401102 to -0x8 can fix it.

newdeccode1

The functions which called in this is not static function. When I enter into the function, it was similar to plt. So the first time I call this function, dl resolving is performed.

plt

Anyway, this function does check some condition about input.

input length must be 86.
input must be in the flag format (pbctf{}).
input starts with mod and ends with 0401.

If this condition all satisfied, the binary does rewriting code section again.

func2

The next function checks again about input.

find the last underbar (_) at the end.
decode the string to hex after _. (e.g. 4142 -> AB)
call bitstream function with arguments as decoded value and mod function.
compare bitstream function result with :3 awesome.
if same, rewriting again.

Okay, our input after _ is in the form of a hex and the result of mod function should be :3 awesome.

We already analyzed the mod function, so let’s write the code.

target = bytearray(":3 awesome")
bitstream = ''

for c in target:
    cur = bin(c)[2:]
    cur_stream = ''
    for i in range(len(cur)):
        bit = cur[i]
        if bit == '0':
            cur_stream += '0'
        else:
            cur_stream += '01'
    bitstream = '0' + (bin(len(cur_stream) - 1)[2:].zfill(4) + cur_stream)[::-1] + bitstream

bitstream = '0' * (8 - len(bitstream) % 8) + bitstream
res = []
while bitstream:
    bit = bitstream[-8:]
    res.append(int(bit, 2))
    bitstream = bitstream[:-8]

print ''.join([hex(i)[2:].zfill(2) for i in res]) + '0401'

Now I got value a992549409a48246a52a456a15354a552ba552240401. From here, there are many ways to construct the hex value, so multiple flags can appear.

The author’s hex value was 8d4a1a45050245414ba56a8a3454d452aa86526a8a0401.

Below is third rewrited function.

func3

It exchanges first 8 bytes of input to 0x320471336C4B6F01.

And calling bitstream again, but callback is not function mod. This callback just xors the value before underbar of input with my original first 8 bytes.

And not in the decompiled code, but if you look at the code in disassembled code, it checks if the first 8 bytes are 0x6D73415F333C5F49.

It means our first 8 bytes must be 0x6D73415F333C5F49 ^ 0x320471336C4B6F01 == 0x5F77306F5F773048 ("H0w_l0w_").

I think it was fake that first function checked if it started with pbctf{mod.

Okay, only the last one is left.

func4

Last rewrited code simply adds the next index value in order of input and call sub_401110 with argument as getData function output.

func5

As you can see, sub_401110 seems matrix multiplication.

Matrix is getData function’s output and vector is our input which added as index order.

After that, binary calls main function. So the value compared from main is output of matrix multiplication.

Decrypt the flag

We have original matrix so we can recovery original vector.

Ask to sage what the original was.

mat = [0x66a49, 0xa8f1d, 0xcc652, 0x67309, 0xf7c14, 0x9e0f1, 0x930d4, 0x8a1dd, 0x4ad6d, 0xb643, 0xfcdfe, 0x33c88, 0xb592a, 0xd9c5e, 0x7b6e5, 0x7f2b9, 0xeb8f, 0x6f9e1, 0x68869, 0x3c99c, 0x30668, 0xaa073, 0x92ff5, 0x15d16, 0x30b09, 0xcbbf8, 0x204fd, 0xad2ef, 0x55d1a, 0x25a04, 0xaffee, 0x95dc1, 0x34e11, 0x7ca3c, 0x3a5a, 0x5a3fa, 0xef962, 0xd388e, 0x9da51, 0x74d42, 0x8cc88, 0x3657e, 0xf359c, 0xe4610, 0x18c63, 0xb9284, 0x7af0e, 0xc23f4, 0xe0282, 0xc2d56, 0xfdee0, 0xbc077, 0xd1990, 0xbc14e, 0x363ce, 0xe9efc, 0x1ee44, 0x9386f, 0x3b11, 0xc4cc1, 0xe6809, 0x639f1, 0x2176, 0x88cef, 0x31159, 0x413d5, 0x9dfea, 0x7ad3f, 0x4e28f, 0xac7da, 0xa5705, 0x7a2f, 0x7c4de, 0xb8986, 0x1694d, 0x15e56, 0x1f9e6, 0x3add5, 0x92862, 0xc518c, 0x555c1, 0x80527, 0x4336f, 0xa13db, 0x92d03, 0x43941, 0xd6e7, 0xf8ad6, 0x636c, 0x930b8, 0xbd697, 0x977a5, 0x73e12, 0x81652, 0xc8faa, 0xc3378, 0x19a924, 0x2a3c74, 0x331948, 0x19cc24, 0x3df050, 0x2783c4, 0x24c350, 0x228774, 0x12b5b4, 0x2d90c, 0x3f37f8, 0xcf220, 0x2d64a8, 0x367178, 0x1edb94, 0x1fcae4, 0x3ae3c, 0x1be784, 0x1a21a4, 0xf2670, 0xc19a0, 0x2a81cc, 0x24bfd4, 0x57458, 0x1c29, 0x149b0, 0x5c4e3, 0xffa06, 0x46e32, 0x32deb, 0xdfbdf, 0xabc38, 0x25825, 0x89ef6, 0x1faa1, 0xca68d, 0xfeed6, 0x77cec, 0x9ddb1, 0x19551, 0x71646, 0x51852, 0xe94f, 0xfc5e, 0x3b70d, 0xaf20, 0x23f53, 0xffdff, 0x61526, 0x76dcb, 0x1b0fc, 0x46107, 0xbb6a2, 0xad701, 0x2c8ad, 0xa3ce0, 0xa1c7c, 0xfb7e8, 0x3aa90, 0xc139f, 0xe36b8, 0x73980, 0xf1235, 0x6ed0d, 0xec3dc, 0x58636, 0x3f02f, 0xbfbe0, 0xa6248, 0xbf080, 0xb4343, 0x19b21, 0xbe40e, 0xa2f9d, 0x5df61, 0x7b7cc, 0xb790d, 0x20910, 0x5c011, 0x685ee, 0xc9582, 0x9eff8, 0x280d4, 0x7c16e, 0xc46f1, 0xca5ba, 0x39c89, 0xe0c7, 0x5ee64, 0xee672, 0xed0dc, 0xab645, 0xfd85a, 0x40629, 0x59c9e, 0xe68b1, 0x2262f, 0xece1d, 0xfc7a3, 0x48f27, 0x2b82d, 0x9d87f, 0x67f24, 0x55708, 0x959f9, 0xe57b5, 0x2b1eb, 0x831b6, 0x55308, 0x85a22, 0xebb67, 0x2bf67, 0x34c58, 0x5f7dd, 0xdc402, 0x38291, 0x59cd5, 0xf0f26, 0x46792, 0x9aa95, 0xede5d, 0x793a, 0x6d2ed, 0x72313, 0xc96e0, 0xcfae6, 0x3b5e, 0xbfe26, 0x3c5d5, 0xfef2a, 0x7af1c, 0x90175, 0x7f3df, 0x23010, 0x82b64, 0xcaebb, 0x7339, 0xe70c4, 0x51822, 0x42da5, 0x6d022, 0x811a, 0x545c0, 0x6ec9f, 0x10983, 0x3e6d5, 0xbd79b, 0xc9ea6, 0x6faf0, 0x5fd21, 0x10c94, 0xc0bd5, 0x38367, 0xacc6a, 0x2c8fd, 0xdd2aa, 0x38831, 0x74249, 0x758d0, 0x77e2c, 0x247b7, 0xd0619, 0x173ee, 0xf9c9b, 0x764f0, 0xa5b4f, 0xbd432, 0xbd7b8, 0x69369, 0xa9b76, 0x4f1aa, 0xf5b47, 0x2baaa, 0x83475, 0x62915, 0xc9f2a, 0x41ff0, 0xa09a0, 0x542ad, 0xa0366, 0x937f3, 0xce61e, 0xaa132, 0x65c19, 0x8db75, 0x5ca68, 0x41479, 0xadd9a, 0x5fb79, 0xc3bbc, 0xe0026, 0xace2b, 0xdf5d7, 0xef1a, 0x32256, 0xedd3b, 0xb4dcf, 0xee19, 0x18dde, 0xbdd55, 0xd749f, 0xd801c, 0x11a47, 0x51e35, 0x80ce7, 0x13a2d, 0x6a62e, 0xec85e, 0xebf1e, 0xe81ca, 0xe370c, 0x3a967, 0x2d127, 0xb975e, 0xa5be4, 0x178b4, 0xfff2935b, 0xfff53b65, 0xfff5d37c, 0xfff51a95, 0xfffa3a7e, 0xfff883ba, 0xfff4966e, 0xfff11a9a, 0xfff5ff93, 0xfff316d3, 0xfff3499d, 0xfff7c79e, 0xfff81ee6, 0xfff20000, 0xfff6925c, 0xfff662d1, 0xfff74ef9, 0xfff8b25b, 0xffffa4da, 0xfff807d8, 0xfff43b06, 0xfff1aceb, 0xfff28b4d, 0xfff8126e, 0x86646, 0xc4ca3, 0x1c476, 0x3fa3d, 0x728cf, 0x23b71, 0x9dc9, 0xcad0e, 0x685a0, 0x18c37, 0x128ce, 0x87a4, 0x5330c, 0x4f2fc, 0x31b9, 0x42d8a, 0x3b93e, 0x7e69c, 0xb0c64, 0x9aa15, 0x5fc29, 0xaa442, 0x6675d, 0xbb84e, 0xfffcec14, 0xffc9767c, 0xffdfc2bc, 0xffc75818, 0xffee1f48, 0xffe9742c, 0xffd11ab0, 0xffe26020, 0xffd7dc2c, 0xffef29b8, 0xffc25a04, 0xfffbc56c, 0xfff68f30, 0xfffcc258, 0xfff7b3d8, 0xfff408fc, 0xfffa3d64, 0xffd3320c, 0xffca8c5c, 0xfff9c51c, 0xffe88fec, 0xffe97ba8, 0xffe6fed0, 0xffdaf700, 0x7733a, 0xc95f7, 0xca691, 0x3cf59, 0x31d9b, 0x95a9a, 0x990dd, 0x408ae, 0x4b2e3, 0x4adc1, 0xa5738, 0xafb09, 0xbe494, 0x5cb0a, 0xabdd5, 0xc6c6, 0xe4497, 0x3eb57, 0x80e0b, 0x4114d, 0xaecde, 0x28386, 0x22e8a, 0x5ba89, 0x992e9, 0xe5f30, 0x94e93, 0xe095f, 0xaadee, 0xca282, 0xc3254, 0x121ab, 0x333b, 0x4bc5b, 0xe1976, 0x41180, 0x155cb, 0x21b44, 0xe30f5, 0xdf0c2, 0x78f9d, 0xe9b1b, 0x54ddf, 0x2e8f1, 0x8d72c, 0x12171, 0xf2e8a, 0xbf14f, 0x2e9bd, 0xac10a, 0xa676, 0x5f4bb, 0xf8d22, 0x2abd9, 0xf88e7, 0xab788, 0x19aa5, 0x32dee, 0x72253, 0x2b4fe, 0x581b1, 0xdd4e5, 0x4b8a6, 0xc93bc, 0xacb97, 0x9316c, 0x81f8d, 0x73dc8, 0xe3b11, 0xec52d, 0xb7675, 0x7c310, 0x688ac, 0xe438f, 0xef1b2, 0xa82ae, 0xb17e7, 0xc0899, 0x64d7d, 0x89b55, 0x59717, 0xa4ee5, 0xce8ee, 0xe97fd, 0xf1a7d, 0x187d5, 0xf2ac2, 0x76ff0, 0xc42e2, 0x89f7e, 0xc48cf, 0xd45c9, 0xab0ce, 0x2b851, 0xda03a, 0x7d024, 0x12a87, 0xd721, 0x4ba39, 0x59d5f, 0x1e46b, 0xc46a4, 0xd8d7e, 0x934ac, 0x4fc, 0xca0a, 0xf5171, 0x2201c, 0x4a1aa, 0x71d7b, 0x53070, 0x1eb15, 0x33368, 0x6c54b, 0x11c21, 0x36fc8, 0xafdec, 0x6ce66, 0xc88df, 0x12d36, 0xfff8a4ae, 0xfff98bde, 0xffe12b3e, 0xfff379cc, 0xfffb0812, 0xffedeace, 0xfffefbd0, 0xffeaabe4, 0xfff62744, 0xfff784e2, 0xfff6fb84, 0xffe624d6, 0xfff99522, 0xffe77db4, 0xfffc1fdc, 0xfffc2f12, 0xffe77d18, 0xfff00590, 0xffe79210, 0xffed16ec, 0xffe01454, 0xfff8eea6, 0xffee24e6, 0xfffbb744, 0xfff9e9ee, 0xffe68810, 0xfffbf606, 0xffea5a22, 0xfff545cc, 0xfffb4bf8, 0xffea0024, 0xffed447e, 0xfff963de, 0xfff06b88, 0xffff8b4c, 0xfff4b80c, 0xffe20d3c, 0xffe58ee4, 0xffec4b5e, 0xfff1657c, 0xffee66f0, 0xfff93504, 0xffe194c8, 0xffe373e0, 0xfffce73a, 0xffe8daf8, 0xfff0a1e4, 0xffe7b818, 0x3ada9, 0x33a11, 0xf6a61, 0x6431a, 0x27bf7, 0x90a99, 0x8218, 0xaaa0e, 0x4ec5e, 0x43d8f, 0x4823e, 0xced95, 0x3356f, 0xc4126, 0x1f012, 0x1e877, 0xc4174, 0x7fd38, 0xc36f8, 0x9748a, 0xff5d6, 0x388ad, 0x8ed8d, 0x2245e, 0x7c4de, 0xb8986, 0x1694d, 0x15e56, 0x1f9e6, 0x3add5, 0x92862, 0xc518c, 0x555c1, 0x80527, 0x4336f, 0xa13db, 0x92d03, 0x43941, 0xd6e7, 0xf8ad6, 0x636c, 0x930b8, 0xbd697, 0x977a5, 0x73e12, 0x81652, 0xc8faa, 0xc3378, 0xc5191, 0xf3db5, 0xab2e4, 0xafccf, 0x5854e, 0xa380c, 0xf355f, 0x799a3, 0xe63d5, 0x56eb6, 0x1c6e1, 0xdc0b5, 0x30591, 0x60808, 0xc5a1a, 0xa7997, 0xb2496, 0xe3930, 0x5ec62, 0x2089d, 0x704ad, 0xed91, 0x66c89, 0xe19a8, 0xffff7333, 0xfff98f90, 0xffe32791, 0xffb01de2, 0xffe9d906, 0xfff01a69, 0xffba14a5, 0xffca52e8, 0xfff44747, 0xffd4e532, 0xfff61adb, 0xffc0bf3f, 0xffb055d2, 0xffda8f64, 0xffceab8b, 0xfff8156b, 0xffdc90a2, 0xffe68666, 0xfffb7175, 0xfffb122a, 0xffed6cbf, 0xfffc9460, 0xfff4c361, 0xffb00a05, 0xfffdecfa, 0xfff83256, 0xffe850ca, 0xffe6c2b4, 0xfff20a20, 0xfff405be, 0xfffde6d8, 0xffe7e856, 0xfff8f932, 0xffea672c, 0xfffa6e06, 0xffe45aac, 0xfff8ef9e, 0xfff17b6e, 0xfff14e60, 0xfff103a8, 0xfffb7092, 0xffe5f3ce, 0xfffd1824, 0xffe0c6ca, 0xfff13620, 0xffeb4962, 0xffe8579c, 0xffe85090, 0xc3024, 0xe8b47, 0x486f4, 0x49e68, 0x7902d, 0xa6466, 0xdce65, 0xba4b6, 0xdbb2b, 0x7fb2c, 0xfd965, 0x8f2fc, 0x3e99a, 0x63eb3, 0xb9647, 0x3eb67, 0x59c6b, 0x6e25d, 0x3697b, 0xd4f7d, 0xc0642, 0x943a, 0x932fc, 0x6d1df, 0xd6ca5, 0xac49b, 0xa2c84, 0xae56b, 0x5c582, 0x77c46, 0xb6992, 0xee566, 0xa006d, 0xce92d, 0xcb663, 0x83862, 0x7e11a, 0xe0000, 0x96da4, 0x99d2f, 0x8b107, 0x74da5, 0x5b26, 0x7f828, 0xbc4fa, 0xe5315, 0xd74b3, 0x7ed92, 0xc4fb, 0xda261, 0x80f51, 0xe29fa, 0x4782e, 0x5a2f5, 0xbb954, 0x767f8, 0xa08f5, 0x43592, 0xf697f, 0x10ea5, 0x25c34, 0xcf6a, 0x2130a, 0x2fdc1, 0x170a7, 0xb337d, 0xd5ce9, 0x18eb9, 0x5dc05, 0x5a116, 0x6404c, 0x94240, 0xc4705, 0xb7a29, 0x2c64f, 0x7cc62, 0x9e252, 0x61489, 0x993ba, 0xc8f9b, 0xc2f46, 0x12691, 0xb2dc4, 0xfed78, 0xafabd, 0xd484c, 0x1e48d, 0x58963, 0x9e92d, 0x785b3, 0x4f06c, 0xcd93f, 0x71149, 0xb44b4, 0x933fa, 0x50ae2] # getData output
v = [0x1b95f6bf, 0x18f211ff, 0x79151f2, 0xbc6c18e, 0x6e57dafc, 0xab169a9, 0x602ed53, 0x157f6311, 0x1941e3b1, 0xc3082ee, 0x1775a1cc, 0x159139bf, 0xca073d5, 0xe7815098, 0xd65bbaa, 0x999da948, 0x43b26ac, 0x2086eb8d, 0x1a03c9a2, 0x1026dbd5, 0x10cce155, 0xfcfa3266, 0xce1bdc02, 0x182e6cd, 0xbc6c18e, 0xb1ba5b6, 0xca88efb3, 0xd114bc68, 0x11edf430, 0x187eaf68, 0x199895ae, 0xa389b7c]    # encrypted flag
A = []
for i in range(32):
    A.append(mat[i*24:i*24+24])
A = Matrix(Zmod(2^32), A)
ans = A.solve_right(vector(v))
print [i.lift() & 0xff for i in ans]

All you have to do is reverse calculation of ans.

ans = [39, 4, 59, 58, 111, 131, 127, 145, 149, 125, 125, 136, 136, 116, 113, 149, 133, 119, 65, 89, 138, 111, 120, 96]
for i in range(len(ans) - 2, -1, -1):
    ans[i] -= ans[i + 1] & 0xff

k = bytearray("H0w_l0w_")
for i in range(len(ans)):
    ans[i] ^= k[i % len(k)]
    
print ''.join(chr(i) for i in list(k) + ans)

Finally got flag, the input before underbar was H0w_l0w_l3vel_c4n_y0u_r3ally_go?.

flag: pbctf{H0w_l0w_l3vel_c4n_y0u_r3ally_go?_8d4a1a45050245414ba56a8a3454d452aa86526a8a0401}

December 8, 2020 · CTF