Reverse - You Know The Rules And So Do I

Overview

I played LITCTF 2022 under my CryptoCTF team isanapap and we won the first place again xD. There are several high quality challenges and I would like to make a writeup on one challenge, namely You Know The Rules And So Do I in reverse category.

Attachment: You Know The Rules And So Do I

Challenge description and solve status:

Solves

Static Analysis

So we are given a binary main and a bmp file yougotrickrolledChallenge.bmp (rickrolled again).

% file main
main: ELF 64-bit LSB pie executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=2ed7f43e347752980af5e81aeceeb180a2657886, for GNU/Linux 3.2.0, not stripped

Great, it is unstripped. Now we can analyze the binary statically. I used IDA Pro and decompiled the code. The most important parts are main and alter which is called inside main.

int __cdecl main(int argc, const char **argv, const char **envp)
{
    int v3; // edx
    unsigned __int8 v5; // [rsp+3h] [rbp-21Dh] BYREF
    int i; // [rsp+4h] [rbp-21Ch]
    int j; // [rsp+8h] [rbp-218h]
    int k; // [rsp+Ch] [rbp-214h]
    int m; // [rsp+10h] [rbp-210h]
    int n; // [rsp+14h] [rbp-20Ch]
    int ii; // [rsp+18h] [rbp-208h]
    int v12; // [rsp+1Ch] [rbp-204h]
    int v13; // [rsp+20h] [rbp-200h]
    int v14; // [rsp+24h] [rbp-1FCh]
    int jj; // [rsp+28h] [rbp-1F8h]
    int kk; // [rsp+2Ch] [rbp-1F4h]
    int mm; // [rsp+30h] [rbp-1F0h]
    int nn; // [rsp+34h] [rbp-1ECh]
    FILE *stream; // [rsp+38h] [rbp-1E8h]
    FILE *v20; // [rsp+40h] [rbp-1E0h]
    FILE *v21; // [rsp+48h] [rbp-1D8h]
    char v22[400]; // [rsp+50h] [rbp-1D0h]
    char ptr[56]; // [rsp+1E0h] [rbp-40h] BYREF
    unsigned __int64 v24; // [rsp+218h] [rbp-8h]

    v24 = __readfsqword(0x28u);
    stream = fopen("flag.txt", "r");
    if ( !stream )
    {
        puts("Error: The flag file does not exist");
        exit(0);
    }
    if ( !fread(ptr, 0x32uLL, 1uLL, stream) )
    {
        puts("Error: The flag is too short");
        exit(0);
    }
    for ( i = 0; i <= 49; ++i )
    {
        for ( j = 0; j <= 7; ++j )
        v22[8 * i + j] = (((int)(unsigned __int8)ptr[i] >> (7 - j)) & 1) != 0;
    }
    v20 = fopen("yougotrickrolled.bmp", "r");
    v21 = fopen("yougotrickrolledChallenge.bmp", "w");
    for ( k = 0; k <= 137; ++k )
    {
        fread(&v5, 1uLL, 1uLL, v20);
        fputc(v5, v21);
    }
    for ( m = 0; m <= 799; ++m )
    {
        for ( n = 0; n <= 1199; ++n )
        {
        for ( ii = 0; ii <= 2; ++ii )
            fread(&grid[3600 * m + 3 * n + ii], 1uLL, 1uLL, v20);
        }
    }
    v12 = 0;
    v13 = 0;
    v14 = 0;
    for ( jj = 0; jj <= 399; ++jj )
    {
        alter(&grid[3600 * v12 + 3 * v13], v14, v22[jj]);
        v3 = v14 + 1;
        v14 = (v14 + 1) / 24;
        v14 = v3 - 24 * v14;
        if ( v22[jj] )
        ++v12;
        else
        ++v13;
    }
    for ( kk = 0; kk <= 799; ++kk )
    {
        for ( mm = 0; mm <= 1199; ++mm )
        {
        for ( nn = 0; nn <= 2; ++nn )
            fputc(grid[3600 * kk + 3 * mm + nn], v21);
        }
    }
    fclose(stream);
    fclose(v20);
    fclose(v21);
    return 0;
}

unsigned __int8 *__fastcall alter(unsigned __int8 *a1, int a2, unsigned __int8 a3)
{
    unsigned __int8 *result; // rax

    result = &a1[a2 / 8];
    *result ^= (a3 ^ ((((int)*result >> (a2 % 8)) & 1) != 0)) << (a2 % 8);
    return result;
}

I splitted main into 3 parts, and let’s deep dive into them.

Part 1

stream = fopen("flag.txt", "r");
if ( !stream )
{
    puts("Error: The flag file does not exist");
    exit(0);
}
if ( !fread(ptr, 0x32uLL, 1uLL, stream) )
{
    puts("Error: The flag is too short");
    exit(0);
}
for ( i = 0; i <= 49; ++i )
{
    for ( j = 0; j <= 7; ++j )
    v22[8 * i + j] = (((int)(unsigned __int8)ptr[i] >> (7 - j)) & 1) != 0;
}

This part is fairly easy to understand, as we read from flag.txt and store the flag in ptr. Then we iterate through the flag and convert each character to 8 bits and store in v22. (v22 is a bit array of size 8 * 50 = 400 bits)

Fun fact, the above code explanation is auto-generated by Copilot :)

Part 2

v20 = fopen("yougotrickrolled.bmp", "r");
v21 = fopen("yougotrickrolledChallenge.bmp", "w");
for ( k = 0; k <= 137; ++k )
{
    fread(&v5, 1uLL, 1uLL, v20);
    fputc(v5, v21);
}
for ( m = 0; m <= 799; ++m )
{
    for ( n = 0; n <= 1199; ++n )
    {
    for ( ii = 0; ii <= 2; ++ii )
        fread(&grid[3600 * m + 3 * n + ii], 1uLL, 1uLL, v20);
    }
}

In this part we just read from yougotrickrolled.bmp, store the pixels in grid and also write/copy to yougotrickrolledChallenge.bmp. Note that grid size is 3 * 800 * 1200, as image width is 1200, height is 800 and there are RGB channels. A fun fact not used in this challenge is that C parses bmp pixels in order of BGR, the reverse of Python Pillow.

Part 3

v12 = 0;
v13 = 0;
v14 = 0;
for ( jj = 0; jj <= 399; ++jj )
{
    alter(&grid[3600 * v12 + 3 * v13], v14, v22[jj]);
    v3 = v14 + 1;
    v14 = (v14 + 1) / 24;
    v14 = v3 - 24 * v14;
    if ( v22[jj] )
    ++v12;
    else
    ++v13;
}

This is the key part as it is where we alter the pixels in grid according to v22 bit array. We will need to determine if a given grid has been modified in order to reverse v22 array and thus get the flag.

My first idea was to feed alter some numbers and observe the output.

#include <stdio.h>
#include <stdint.h>

uint8_t alter(uint8_t a1, int a2, uint8_t a3) {
  uint8_t result;

  result = a1;
  result ^= (a3 ^ ((((int)result >> (a2 % 8)) & 1) != 0)) << (a2 % 8);
  return result;
}

int main()
{
    printf("%d\n", alter(209, 0, 0));
    printf("%d\n", alter(209, 0, 1));
    printf("%d\n", alter(208, 0, 0));
    printf("%d\n", alter(208, 0, 1));

    return 0;
}

Note that a2 can only take values from 0 to 23, and a3 is either 0 or 1. The output of this program is 208, 209, 208, 209 - so it seems that output is even number when a3 is 0 and odd number when a3 is 1. However this will not work if a2 is not 0. So checking if the pixel is even or odd is not going to work.

My solution to this is surprisingly simple. We are given the result of alter(&grid[3600 * v12 + 3 * v13], v14, v22[jj]), we know v14 and we need to get v22[jj]. We can brute force all possible combinations of grid and v22, where grid value is from 32 to 126 and v22 is 0 or 1. In the end it turns out that grid can have different values but v22 will always be fixed.

Note that in original alter, we have result = &a1[a2 / 8]; which means it is getting offset 0, 1, or 2 depending on a2 value which ranges from 0 to 23.

Solve script is attached below. I used a struct to store the image and auto-parsed the bmp file instead of hard-coding its header size, width, or height.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <stdint.h>

// image info with width, height and pixels
typedef struct {
    int w, h;
    unsigned char *px;
    unsigned char *head;
    int header; // header size
} image_t;

image_t parse_bmp(char* fname) {
    image_t x;

    FILE *tempfile = fopen(fname, "rb");
    if (!tempfile) {
        exit(1);
    }
    unsigned char* tmp = malloc(16 * sizeof(unsigned char));
    fread(tmp, sizeof(unsigned char), 16, tempfile);
    x.header = tmp[11] * 256 + tmp[10];
    fclose(tempfile);

    FILE *file = fopen(fname, "rb");
    x.head=malloc(x.header * sizeof(unsigned char));
    fread(x.head, sizeof(unsigned char), x.header, file);
    x.w = x.head[19] * 256 + x.head[18];
    x.h = x.head[23] * 256 + x.head[22];

    fseek(file, x.header, SEEK_SET);
    x.px = calloc(x.w * x.h * 3, sizeof(unsigned char));
    unsigned char *curr_pixel = calloc(1, sizeof(unsigned char));
    for(int i = 0; i < x.w * x.h * 3; i++) {
        fread(curr_pixel, 1, 1, file);
        x.px[i] = curr_pixel[0];
    }
    free(curr_pixel);
    fclose(file);
    return x;
}

unsigned char alter(unsigned char a1, int a2, unsigned char a3) {
  unsigned char result = a1;
  result ^= (a3 ^ ((((int)result >> (a2 % 8)) & 1) != 0)) << (a2 % 8);
  return result;
}

int main(int argc, char *argv[]) {
	image_t x = parse_bmp("yougotrickrolledChallenge.bmp");

    printf("Width: %d, Height: %d, Header: %d\n", x.w, x.h, x.header);

    int v3 = 0, v12 = 0, v13 = 0, v14 = 0;
    int flag[400];

    for (int jj = 0; jj <= 399; ++jj) {
        int curr = 0;
        if (v14 < 8) curr = x.px[3600 * v12 + 3 * v13 + 0];
        else if (v14 < 16) curr = x.px[3600 * v12 + 3 * v13 + 1];
        else curr = x.px[3600 * v12 + 3 * v13 + 2];
        // Brute force all combinations
        int cc[2]; cc[0] = 0; cc[1] = 0;
        for (int u = 1; u < 256; u++) {
            for (int v = 0; v <= 1; v++) {
                if (alter(u, v14, v) == curr) {
                    cc[v]++;
                }
            }
        }
        // cc will always be (2,0) or (0,2)!
        flag[jj] = (cc[0] > cc[1]) ? 0 : 1;

        v3 = v14 + 1;
        v14 = (v14 + 1) / 24;
        v14 = v3 - 24 * v14;
        if (flag[jj] == 1)
            ++v12;
        else
            ++v13;
    }

    for (int i = 0; i < 400; i+=8) {
        // binary to int
        int curr = 0;
        for (int j = 0; j < 8; j++) {
            curr = curr * 2 + flag[i+j];
        }
        printf("%c", curr);
    }

	return 0;
}

Exploit Code

This will give the flag LITCTF{h0n3stly_im_n0t_sur3_1f_rick_r0ll3d_mys3lf}.

Conclusion

This challenge is not really difficult, as the binary is unstripped and the code is not obfuscated. Probably some people are unfamiliar with bmp images or uncomfortable with using C/C++ for exploit. It is a nice challenge, probably my favourite in the CTF.

On a side note, I made a quite similar challenge in vsCTF less than a month ago, with a binary encrypting a bmp file. That challenge is more difficult since I stripped the binary plus used quite some obfuscation on pixel shift. If you want to have a try, check the challenge here!