This challenge taught me a lot about a few different things. The challenge files consist of an executable and some SDL libraries. Running the executable shows us this:

You can enter text up until a certain length and then the program says ‘Nope’. My initial idea was to start by finding the input handling code and seeing what happens there, but that would’ve been too easy. Running through that with a debugger didn’t give any clues just yet, so I decided to start mapping the executable using Binary Ninja.

Exploring

Looking through the strings in the executable, some interesting ones came up, that started with #version 430 at 0x49a403:

#version 430
in vec3 vert_xyz;
in vec2 vert_uv;

out vec2 frag_uv;

void main() {

  frag_uv = vert_uv;
  
  // Rescale the scene so it's in pixels.
  
  gl_Position = vec4(
    (vert_xyz.x / 1280.0) * 2.0 - 1.0,
    -((vert_xyz.y / 720.0) * 2.0 - 1.0),
    vert_xyz.z / 1024.0,
    1.0
  );
}

And another one at 0x49a53e:

#version 430
in vec3 vert_xyz;
in vec2 vert_uv;

out vec2 frag_uv;

void main() {

  frag_uv = vert_uv;
  
  // Rescale the scene so it\'s in pixels.
  
  gl_Position = vec4(
    (vert_xyz.x / 1280.0) * 2.0 - 1.0,
    -((vert_xyz.y / 720.0) * 2.0 - 1.0),
    vert_xyz.z / 1024.0,
    1.0
  );
}

A quick Google search turned up that this is GLSL: the OpenGL Shader Language. In the executable, these are loaded with glCreateProgram() and glCompileShader(). The program calls glCompileShader() once, in a sub at 0x401770, which we’ll call moon_compileshader. A string reference saying glCompileShader: %s in this sub confirms this. What got me curious is that we’ve found two shaders in the strings, but moon_compileshader is actually called 3 times:

The third time is in a function we’ll call moon_mysteryshader. This function seems to decode some constant in steps and save it into a std::basic_string. I let x64dbg run through the function and sure enough, another piece of shader code shows up:

Extracting this and adding a bit of formatting gives me this:

#version 430
layout(local_size_x = 8, local_size_y = 8) in;
layout(std430, binding = 0) buffer shaderExchangeProtocol
{
    uint state[64];
    uint hash[64];
    uint password[32];
};

vec3 calc(uint p)
{
    float r = radians(p);
    float c = cos(r);
    float s = sin(r);
    mat3 m = mat3(c, -s, 0.0, s, c, 0.0, 0.0, 0.0, 1.0);
    vec3 pt = vec3(1024.0, 0.0, 0.0);
    vec3 res = m * pt;
    res += vec3(2048.0, 2048.0, 0.0);
    return res;
}

uint extend(uint e)
{
    uint i;
    uint r = e ^ 0x5f208c26;
    for (i = 15; i < 31; i += 3)
    {
        uint f = e << i;
        r ^= f;
    }
    return r;
}

uint hash_alpha(uint p)
{
    vec3 res = calc(p);
    return extend(uint(res[0]));
}

uint hash_beta(uint p)
{
    vec3 res = calc(p);
    return extend(uint(res[1]));
}

void main()
{
    uint idx = gl_GlobalInvocationID.x + gl_GlobalInvocationID.y * 8;
    uint final;
    if (state[idx] != 1)
    {
        return;
    }
    if ((idx & 1) == 0)
    {
        final = hash_alpha(password[idx / 2]);
    }
    else
    {
        final = hash_beta(password[idx / 2]);
    }
    uint i;
    for (i = 0; i < 32; i += 6)
    {
        final ^= idx << i;
    }
    uint h = 0x5a;
    for (i = 0; i < 32; i++)
    {
        uint p = password[i];
        uint r = (i * 3) & 7;
        p = (p << r) | (p >> (8 - r));
        p &= 0xff;
        h ^= p;
    }
    final ^= (h | (h << 8) | (h << 16) | (h << 24));
    hash[idx] = final;
    state[idx] = 2;
    memoryBarrierShared();
}

I have no experience with OpenGL shaders, but the syntax seems pretty straight forward and C-like. This is a hashing function that is called in several steps. The ‘state’ array keeps track of which steps have been executed. The function calc() does some basic pre-calculations using trigonometric functions and matrix/vector calculations, then for each character two 32-bit values are calculated (alpha and beta) which are added to the hash.

Input verification

But we need to find out what it is being checked against. At 0x401bf0 there is a function that runs the shader program, lets call that moon_generatehash. Finally, in moon_main a string is constructed and then a memcmp() is called. This verification code looks like this (in Binary Ninja medium IL):

Modifying rax after the memcmp() call in a debugger indeed seems to validate the password! It also shows the password is validated against a 512 byte hash string which is found in the executable at 0x49f138. This is the hash we’ll need to reverse to get the password.

Breaking the hashing algorithm

At first glance, it seems the algorithm cannot be bruteforced easely because at some point, the entire password is used:

    uint h = 0x5a;
    for (i = 0; i < 32; i++)
    {
        uint p = password[i];
        uint r = (i * 3) & 7;
        p = (p << r) | (p >> (8 - r));
        p &= 0xff;
        h ^= p;
    }

Bruteforcing every possible character for the entire password would take a huge amount of time. However, the result of this loop is the same throughout every hashed character in the password. We could simply bruteforce h first along with the first character in the password, which would take 256² steps at most. That’s doable! After that, we can simply crack the hash by trying each possible character and comparing the resulting hash in groups of 2 32-bit integers.

I copied the hashing algorithm into C# and wrote some simple bruteforcing code. It cracks the password from the hash found in the program in less than a second. You can find the code on Github