I am freshly returning from Northsec, a large size cybersecurity Capture The Flag competition in my province - Québec, Canada - and while I spent an unreasonable amount of time on a cryptography challenge way above my skill level ("Olfactive Memory System") just because I saw it was written in Rust and I got excited, I still snuck in a solve of this fun challenge among my efforts.

(3 Points) Genetic System

Mr Wellington wants to ensure that he can easily repair his inner organs by generating stem cells at will. We’ve been severly warned to not do anything bad with this code, but we have to give it a try. To help generate genetic construction, we’ve been granted a copy of the advanced “game” needed to generate a 4-letters sequence and provide the expected value. It’s named the Stem Cell Generator advanced game, Boy/Girl edition. So for this, find a way to understand how to run that weird game, and then you’ll have to reverse engineer it. Let us know when you found the right answer.

Upon opening the .gba (Game Boy Advance - yes, Evie, I wrote it "Game Boy" and not "Gameboy", I remember!) file, we are met with this ultra-sophisticated UI, which demands an input of 4 letters:

The challenge window, showing the sequence AAAA

"The challenge is called Genetic System. Of course the code will be composed of AGCT. 4x4x4x4 combinations, for a total of 256, this will be easy to run trial and error on!" - blissfully unaware me

I flick the first letter.

The challenge window, showing the sequence BAAA

Well. 26x26x26x26 = 456 976 combinations. This will be fun.

Cracking open this program with a reverse engineering utility (in my case, Binary Ninja) reveals its inner workings... starting with this function, directing the user's ability to change the 4 letter sequence:

if (key_hit(0x20) != 0)
{
    cursor = (cursor - 1);
    if (cursor < 0)
    {
        cursor = 0;
    }
}
if (key_hit(0x10) != 0)
{
    cursor = (cursor + 1);
    if (cursor > 3)
    {
        cursor = 0;
    }
}

The left and right keys let us move the cursor across all four letters...

if (key_hit(0x40) != 0)
{
    *(uint8_t*)((cursor * 0xc) + 0x3000244) = ((int8_t)(((((uint32_t)*(uint8_t*)((cursor * 0xc) + 0x3000244)) + 1) << 0x18) >> 0x18));
    if (((uint32_t)*(uint8_t*)((cursor * 0xc) + 0x3000244)) > 0x5a)
    {
        *(uint8_t*)((cursor * 0xc) + 0x3000244) = 0x41;
    }
}
if (key_hit(0x80) != 0)
{
    *(uint8_t*)((cursor * 0xc) + 0x3000244) = ((int8_t)(((((uint32_t)*(uint8_t*)((cursor * 0xc) + 0x3000244)) - 1) << 0x18) >> 0x18));
    if (((uint32_t)*(uint8_t*)((cursor * 0xc) + 0x3000244)) <= 0x40)
    {
        *(uint8_t*)((cursor * 0xc) + 0x3000244) = 0x5a;
    }
}

As for the up and down keys, they are editing variables located at the memory address 50332228 (0x3000244), plus 12 (0xc) for each cursor shift. As for the nested if statements with 0x41 and 0x5a, they reset the counter back to A or Z if trying to find some mysterious 27th or 0th letter of the alphabet, respectively.

What are 0x41 and 0x5a? The codes for A and Z in hexadecimal, respectively.

Let us see what lives at those addresses:

03000244  char key_chars = 0x0
03000250  char data_3000250 = 0x0
0300025c  char data_300025c = 0x0
03000268  char data_3000268 = 0x0

Hmm, yes, data_300250, what a poetic way to say "second letter in the secret combination". Now, let us see what we need to print out the flag...

if (evaluation_routine() == 1) {
  sprintf(&var_38, "FLAG-%s%s%s%s", &var_15c);
}
while (true)
{
    tte_write("FAILURE");
}

We require a function named evaluation_routine to equal 1, or else, we enter an infinite loop where all our efforts to escape are rendered futile (until the big RESET button in my emulator is pressed, naturally).

That function is where the secret code is revealed to us... in a slightly indirect fashion.

if (((uint32_t)(key_chars & 0xf0)) != 0x40)
{
    r3 = 0;
}
else if (((uint32_t)(key_chars & 0xf)) != 5)
{
    r3 = 0;
}
else
{
    char r2_6 = data_3000250;
    if (((((uint32_t)r2_6) << 0x18) >> 0x18) < 0)
    {
        r3 = 0;
    }
    else if ((((uint32_t)r2_6) & 0x40) == 0)
    {
        r3 = 0;
    }
    else if ((((uint32_t)r2_6) & 0x20) != 0)
    {
        r3 = 0;
    }
    else if ((((uint32_t)r2_6) & 0x10) != 0)
    {
        r3 = 0;
    }
    else if ((((uint32_t)r2_6) & 8) != 0)
    {
        r3 = 0;
    }
    else if ((((uint32_t)r2_6) & 4) == 0)
    {
        r3 = 0;
    }
    else if ((((uint32_t)r2_6) & 2) == 0)
    {
        r3 = 0;
    }
    else if ((((uint32_t)r2_6) & 1) == 0)
    {
        r3 = 0;
    }
    else if ((((((uint32_t)r2_6) ^ ((uint32_t)data_300025c)) << 0x18) >> 0x18) != 0x16)
    {
        r3 = 0;
    }
    else
    {
        if ((((((uint32_t)(data_3000268 & 0xf0)) & 0x40) << 0x18) >> 0x18) != 0x40)
        {
            r3 = 0;
        }
        else
        {
            if (((uint32_t)(data_3000268 & 0xf)) == 0xb)
            {
                r3 = 1;
            }
            else
            {
                r3 = 0;
            }
        }
    }
}
return r3;

Wew. Good thing this is just a 4-letter code, or else, the Tentacular Mass of Writhing If Statements would grow as large as a star and would devour the universe as we know it.

We already know which variable corresponds to each letter in the combination (here is a reminder):

char key_chars // Letter 1
char data_3000250 // Letter 2
char data_300025c // Letter 3
char data_3000268 // Letter 4

We need to find the letters that will pass through all of those bitwise checks without ever tripping one, and landing on the dreaded r3 = 0 pitfalls, which will place us in the FAILURE eternal loop.

Understanding what the bitwise checks actually do is not required to solve the challenge - the 4 letter sequence can now be brute-forced by testing every single letter of the alphabet against each check.

Here is my quick Rust script to get the job done:

fn main() {
    for letter in b'A'..=b'Z' {
        let letter_32 = letter as u32;

        if (letter_32 & 0xf0) == 0x40 && (letter_32 & 0xf) == 5 {
            println!("Character '{}' meets conditions.", char::from_u32(letter_32).unwrap());
        }
    }

    for letter in b'A'..=b'Z' {
        let letter_32 = letter as u32;

        if ((letter_32 << 24) >> 24) >= 0 &&
           (letter_32 & 0x40)!= 0 &&
           (letter_32 & 0x20) == 0 &&
           (letter_32 & 0x10) == 0 &&
           (letter_32 & 8) == 0 &&
           (letter_32 & 4)!= 0 &&
           (letter_32 & 2)!= 0 &&
           (letter_32 & 1)!= 0 {
            println!("Character '{}' meets conditions.", char::from_u32(letter_32).unwrap());
        }        
    }

    for letter in b'A'..=b'Z' {
        let letter_32 = letter as u32;

        if (((b'G' as u32 ^ letter_32) << 0x18) >> 0x18) == 0x16{
            println!("Character '{}' meets conditions.", char::from_u32(letter_32).unwrap());
        }
    }

    
    for letter in b'A'..=b'Z' {
        let letter_32 = letter as u32;

        if ((((letter_32 & 0xf0) & 0x40) << 0x18) >> 0x18) == 0x40 && letter_32 & 0xf == 0xb{
            println!("Character '{}' meets conditions.", char::from_u32(letter_32).unwrap());
        }
    }
}

Note the b'A', converting from uppercase letters to their binary equivalents (an array of 8 unsigned 8-bit integers). Another amusing detail is the bitwise operation on 'G' in the third letter loop - indeed, the original code uses the variable tied to the second character (data_3000250) to check for the validity of the third character. As I was writing my code letter-by-letter, I was able to find out that the second loop always returns G as the only viable character.

For the curious, here is what is happening in the first loop:

  1. E, rendered in binary, is 01000101.
  2. 01000101 & 0xf fetches the last 4 bits, which becomes 00000101, which is equal to 5, or 00000101 in binary.
  3. 01000101 & 0xf0 only fetches the first 4 bits, which becomes 01000000, and this is indeed equal to 0x40, or 01000000 in binary.
  4. No other letter allows both of these checks to be true at once.
  5. All other loops do the same thing, with simply more numerous or varied checks.

And so, running this script returns the sequence: EGQK. Not much of a genetic code, now is it? There's guanine in there, sure, but what else? Ethanol? Quinine?? KETAMINE??? This Mr. Wellington's sure is a peculiar gentleman.

Regardless of any esoteric DNA composition, the code is indeed correct, and fetches us the flag!

The challenge window, showing the sequence EGQK and the revealed flag!

Technology Sprints and Marathons

I enjoyed my time at Northsec, but I have to say, the conditions are... dangerous. Over 16 hours of continued CTF solving on Saturday? Pizza served at 23:00? An waterfall of coffee perpetually flowing?

I think the CSGames were a little more reasonable in that aspect by granting 3 hour time limits after the initial revelation of each challenge. I don't know how much sleep the leading teams sacrificed, but closing challenges at 3:00 in the morning feels a bit like an encouragement of crunch culture.

Technology is a long and iterative process. Keeping a service secure is a matter of months of maintenance and investment in stable, robust protocols. Solutions cooked up in single day will crash and burn - even the so-called perfect ones, once you leave and the caretaking of your precious baby is entrusted to a successor with... less attachment to the guarantees of quality you pushed forwards.

Of course, it's a CTF. It's all in good fun. Work remains work, play remains play. Just don't make overwork a habit under the pressure of time...

Or else, once one can't take it anymore and is forced to quit, one will soon have time. Lots, lots of time.

If you enjoyed this writeup, feel free to contact me!

  • Discord: oneirical
  • Reddit: https://old.reddit.com/user/oneirical/
  • Zulip: https://rust-lang.zulipchat.com/#user/693959
  • Email: julien-robert@videotron.ca