CONFidence CTF teaser 2017 Starblind Write up

Solved by 4rbit3r and HRJ.

I’ll have to admit, it was surprising to get a link to a website for a reverse engineering challenge. It was HRJ who found out that the website was running an encoding functionality using Javascript to encode our input. The input we give is supposed to be 27 characters long. These 27 characters are then inserted into an array and then the array is filled with some junk to extend it to a size of 64.

There are two major functions that perform the encoding ie xor and perm. The first one is pretty self explanatory. The second one takes a 512 size array as argument and does a lot of operations with our input.

These two functions are called alternatively with each function being called 256 times. So that means a total of 512 operations on our input after which the result is a 64 size array. This array is then converted to a hexadecimal string and then compared with a constant string. If they’re equal, you’ve got the flag.

The arguments passed to the xor and perm functions are given in the code itself. So all that we need to do is to create a function to reverse the effects of the perm function. After that, we can call the undo_perm and xor functions with the same arguments that are passed in the code with the only difference being that we call these functions in the reverse order.

So basically, if they’re calling

• xor(a)
• perm(b)
• xor(c)
• perm(d)

What we do is a

• undo_perm(d)
• xor(c)
• undo_perm(b)
• xor(a)

Now let’s dig deeper into the perm function.

let perm = function(imm) {
    let n = new Uint8Array(64);
    for (let i = 0; i &lt 512; i++) {
        const dst_bit = i % 8;
        const dst_byte = i / 8 | 0;
        const sign = Math.sgn(imm[i]);
        const idx = sign ? -imm[i] : imm[i];
        const src_bit = idx % 8;
        const src_byte = idx / 8 | 0;
        let b = (r[src_byte] >> src_bit) & 1;
        if (sign) {
            b ^= 1;
        }
        n[dst_byte] |= b << dst_bit;
    }
    r = n;
}

The argument passed to perm is the 512 size array of constants and r is the input that we give. We can see that all of the operations that the perm function does on our input is directly related to the value of the loop counter and the array passed as argument. What the function basically does is moving individual bits from the input array to the resultant array.

If we were to assume the input and resultant arrays as 2D arrays with each A_ij representing the j’th bit of the i’th character, the whole function can be simplified into one single line equation :

n[dst_byte][dst_bit] = r[src_byte][src_bit]

The variables dst_byte and dst_bit are directly dependent on the value of the loop counter. src_byte and src_bit are dependent on the value of imm[i] where imm is the constant array passed as input and i is the loop counter. So all we need to do here is to reverse this one equation.

I first converted the whole perm and xor functions into Python and then wrote the function for undo_perm. The annoying part was the next. I had to write 512 function calls. So I resorted to downloading the index.html and writing a parser function to get the array.

Now all that was left for me was to kick off my script with the expected string and wait for the flag to magically show up. Didn’t happen.

I spent a lot of time trying to find out what was wrong with the code. But it turned out that the problem was probably because I had chosen to write the script in Python and not Javascript.

HRJ then showed me a way to debug the original Javascript code so that I get a clear picture of what’s going on. That is when I noticed that the array of 512 constants that was passed to perm contained ‘-0’ in some places.

There is this one line of code in the perm function which checks if the imm[i] is negative or not. If negative, the bit @ r[src_byte][src_bit] is xor’ed with 1. In the original code, -0 is treated as negative.

My parser was converting the characters into corresponding integers. So effectively, ‘-0’ was converted to 0. And so the part where I check whether the number is negative or not returns False in my function and True in their code.

So all that was required was a quick tweak. Every time imm[i] was 0, check the original character array to check if the character is ‘-0’ or not. If the original character is indeed ‘-0’, then xor the bit with 1.

And well, needless to say, that was it. Just running the script gave us the flag.

In hindsight, I might have solved this challenge way sooner had I used Javascript instead of Python.

Anyway, here’s the script in Python

correct = "983bb35ed0a800fcc85d12806df9225364713be578ba67f65bc508b77f0c54878eda18a5eed50bac705bdc7db205623221e8ffe330483955a22216960754a122".decode('hex')

def xor(a,b):
        c = [0 for x in xrange(64)]
        for x in xrange(64):
                c[x] = (a[x] ^ b[x]) % 256
        return c

def reverse_perm(b,c,temp):
        a = [0 for x in xrange(64)]
        for x in xrange(512):
                src_bit = abs(b[x])%8
                src_byte = abs(b[x])/8
                dst_bit = x%8
                dst_byte = x/8
                flag = (c[dst_byte] >> dst_bit) & 1
                if b[x]<0:
                        flag ^= 1
                if b[x]==0 and "-0" in temp[x]:
                        flag ^=1
                a[src_byte] += (flag *(2**src_bit))
        return a

def parse_file():
        f = open("reverse","r")
        c = [ord(x) for x in correct]
        for x in xrange(512):
                line = f.readline()
                func = line[4:line.find("(")]
                rest = line[line.find("[")+1:line.find("]")].split(", ")
                temp = rest
                rest = [int(x) for x in rest]
                if func == "perm":
                        c = reverse_perm(rest,c,temp)
                elif func == "xor":
                        c = xor(c,rest)
                else:
                        print "Strange"
        return c
if __name__ == "__main__":
        d = parse_file()[:27]
        print ''.join(chr(x) for x in d)

And well, running that gave the flag.

$ python solve.py
DrgnS{Humank1ndEmpire0fAbh}
$