Thursday, July 6, 2017

Google CTF Quals 2017 - Moon

This writeup is for the reversing challenge "Moon" we solved during 2017 Google CTF Quals. This writeup and 3 others were also submitted to the Google CTF Writeup Competition.

Dealing with GLEW

A big problem we noticed early on was the use of GL3W, which generates code to lazily load all OpenGL functions at runtime--at all places where an OpenGL function was used we would simply see a call to some offset in the data section. Unfortunately we couldn't find a script to re-symbolize function calls, but we plan to make one soon-ish :)

We can see the huge routine which calls LoadLibrary on every OpenGL function, at sub_4032c0.

Instead of symbolizing (by hand) all of the symbols, we only bothered to load ones which had valid XREFs to them, saving a bit of time.

Running the Program

Unfortunately all the RPI-sold computers from our year are not yet reported to support OpenGL 4.3, so first and foremost we had to patch the OpenGL verification check from 4.3 to 4.2. Surprisingly, this "just worked" despite the code making use of Compute Shaders which I had thought to be introduced in OpenGL 4.3.

The program simply opens up a window, and asks for a password. After we've entered 32 characters, the program either responds "good" (presumably), or "Nope".

When we XREF the string Nope, we see that it is used when constructing the texture to be printed for this SDL event loop iteration. Not too far from "Nope" do we find "Good", and we notice that "Good" is only selected if a particular global variable is set. We trace this back to the following code in main:

We want should_compute here to be 2, meaning the memcmp succeeded. Buf2 is the following string:


So, once our input is hashed, it must match the above value. The hashing of our input seems to occur at sub_401BF0, and through windbg we can confirm that our input is the first argument, and the hash is written out to the second argument. Nothing much happens here, however, though we do see references to glUseProgram and glDispatchCompute, as seen below:

Although we can see the fragment and vertex shaders in clear view in the strings, we can't see any reference to the compute shader glsl source. We assume it's encrypted somehow, so we break on glCompileShader and wait until the glsl compute shader is decrypted. This is a wild guess, as the shader could have been precompiled somehow but we punt on this.

The dumped source is as follows, after adding the proper formatting:

Reversing the Compute Shader

We note a few properties of the hashing function below:

  1. The h variable is constant for all iterations of this compute shader. It is dependent only on the password.
  2.  The only place in which the index, idx affects final is where we compute final ^= idx << i in a loop. This is completely reversible.
  3. Other than these 2 conditions, final is completely dependent on the current character.

Our goal here is to exploit these characteristics to find an idx-independent and password-independent hash for each character. This would allow us to brute force the password character by character. We can find the h of the real password like so:

hash_C  = reverse_idx(final_C) ⊕ hash_h
hash_C' = reverse_idx(final_C) ⊕ hash_h'

Here, hash_C is the value of the first index corresponding to the 'C' character in 'CTF' (we're assuming the password starts thus because of the flag format), for the real password, or the password we'd like to find. hash_C' is the value of the same index in our dummy string, say CTF{AAAAAAAAAAAAAAAAAAAAAAAAAAAA which also has a 'C' at the same index. hash_h represents the h value used to xor with the output of the hash function for the real password, and likewise hash_h' is this value of h for our dummy password.

Note that final_C is the same for both the real and the dummy password; it's passed out of the hash function. The reverse_idx function removes final_C's dependence on idx, reproduced below:

reverse_idx(final,idx) = final ⊕ (idx<<0) 
                               ⊕ (idx<<6) 
                               ⊕ ... 
                               ⊕ (idx<<26)

Finally, to compute hash_h, we simply need to perform the following:
hash_h = hash_C' ⊕ hash_C ⊕ hash_h'

Although it took a lot of work, we now have h of the target password, since we know hash_C', hash_C, and hash_h'. With this, we can figure out the hash value of every character in the password, independent of the character's index, and brute force them character by character.

Brute Forcing the Password

Unfortunately we were unable to replicate this algorithm forwards in C++, for some unknown reasons (probably something to do with the calc function). Since we were running out of time, we opted instead to compute a lexicon of characters up front with the debugger. We then took the hash of each character and made them idx-independent, as well as un-xor'd their h terms, like so:

Now, all we need to do is take Buf2's characters and render them also idx-independent, un-xor them with the known h for this password (which turns out to be 0x6f6f6f6f, computed in the previous section) and then match each hash with the known values in our lexicon, as below:

The resulting flag is: CTF{OpenGLMoonMoonG0esT0TheMoon}