FE-CTF 2023 - Brute force ahoy.

Published Oct 27, 2023

This is my write-up for the 2023 CTF qualifier held by the Danish Defence Intelligence Service: The UniPwnie Experience. This was an open CTF event, with the top 10 teams being invited to an in-person event.

In this write-up, I will focus on how I solved the “Login Level 3” challenge, a brute-force based challenge that was released early in the CTF.

The Challenge

When first opening the challenge page, you’re greeted by a simple login form with a username and password field. Attempting to log in, I was met with increasingly absurd password requirements — I’ve emulated it below, in case you want to join the fun:

Hoping against hope, I tried bypassing the validation and just submitting a password directly to the backend, but was met with a 403 Unauthorized. That would’ve been too easy anyway. Guess we’ll have to take another look at those password requirements.

Based on an earlier challenge in the same series, I assumed that the login system would accept arbitrary usernames. Presumably, the password would be the same: as long as it fulfilled the requirements, the login would go through and the flag be mine.

Initial thoughts and prayers

Cracking the password would probably involve brute-forcing it locally, trying out combinations of strings until one fulfilled all the password requirements.

With a bit of napkin math, it quickly became clear that this was somewhat infeasible to do naïvely. Although the password must be a palindrome, and we’d therefore only have to generate 5-10 characters to get the password to the required 10-20 characters, that still meant more than $95^{10} \approx 5.99 \cdot 10^{19}$ possible strings to go through (since the code only considered 95 different characters to be valid). Even if we could generate a billion strings a second, that’d take over 1897 years!

We’d therefore have to limit the brute-force space as much as possible, by trying to be a tiny bit smarter.

Although there are many ways to cut down on the required work, it seemed like the most promising was to focus on the “Base64 encoding must contain only lowercase letters” requirement.

Aside: Base64 encoding

Base64 is an encoding algorithm that takes arbitrary binary data (in our case this is the binary representation of our password) and turns it into a string consisting only of a subset of ASCII characters.

It does this by taking the input binary data and padding it with 0 until its length is dividable by 6. It then looks at each sextet of 6 bits in the binary data, and mapping them to one of $2^6 = 64$ pre-chosen ASCII characters.

Since we usually work with bytes of length 8, this creates a 3-to-4 compression ratio: 3 input bytes, totalling 24 bits, become 4 output ASCII characters. Since the reverse process should decode into a whole number of bytes, most implementations pad the encoding with = until its length is divisible by 4.

In our case, we want a password that only contains sextets ranging from 011010 (26) to 110011 (51), as those are the ones that are represented by lowercase letters a-z.

Back to our thoughts

With this in mind, we can conclude a few things:

1. The password’s length must be divisible by 3. If it was not, the Base64 encoding would be padded with the = character, which isn’t a lowercase letter. This means our palindrome length must be either 12, 15 or 18, as it must be between 10 or 20.

2. If the palindromic password is of length 12 or 18, its Base64-triplets would be well-aligned, with the first 2 or 3 of them in the first half of the palindrome, and the last 2 or 3 in the mirrored half. This means that the triplets would be mirrored too.

   Consider if such a password contained the character “1” (binary 00110001):

   • If it’s found in the first spot in a Base64-triplet in the first half of the password, then the first 6 bits of its binary value (001100) must map to a lowercase letter in Base64. Since the triplets are mirrored in the last half, its last 6 bits (110001) must also map to a lowercase letter.
     The same logic applies if it’s found in the last spot of a triplet in the first half of the password.
   • If it’s found in the center spot in a Base64-triplet, then the first 4 bits of its binary value (0011) must be the ending of at least one of the lowercase letter mappings, and the last 4 bits of its binary value (0001) must be the start of one.

   It turns out that, out of the 10 digit characters available, only “6”, “7”, “8” and “9” are valid under the above observation. If the password length is even, those are the only digits available to us.

   Since the sum of digits in the password must be 1, 8 or 27 (the only cube numbers we can sum to with our length of password), which we can only sum to by using an odd number of the valid digits, we can conclude that the length of the password must be 15.

3. As one of the requirements is to have 8 unique characters, and our password is a palindrome of length 15, the first half of the palindrome cannot have any duplicate characters.

4. Encoding characters are locked once every bit representing them has been covered by an input bit. When brute forcing our password we can use this to quickly discard any branches that encode into a character we don’t want.

Although not enough to get us all the way to our final password, this can be used to significantly lower the cost of brute forcing.

Limiting our search space

To use the above observations to cut down on our brute force work, we’ll slowly build up passwords one character at a time until we reach a length of 15. We’ll be careful to only use characters that maintain the lowercase-only Base64 encoding.

This means we’ll only have to check strings that at the very least encode to the right format, saving us the work of diving into any branches that start with e.g. “a” (as that’ll always encode into a Base64 string starting with “Y”).

We can implement it using simple bit-checking, filtering out any characters that would create a 6-bit group that doesn’t represent a lowercase letter in Base64:

// The ASCII characters we can use in our password are represented by char codes 32-126,
// and the sextets we want are in the range 26-51
const asciiCodes = [32..127];
const permittedBits = new Set([26..52].map(i => i.toBinary(wordLength=6)));
// Using this we can recursively generate all the passwords that encode to the wanted format
const generateStrings = (currentString, targetLength) => {
  if (targetLength <= 0) { return [currentString]; }
  return getAllowedCodes(currentString)
    .flatMap(code => {
      const candidateStr = currentString + char(code);
      // abort if it doesn't encode correctly
      const binary = candidateStr.toBinary(wordLength=8);
      for (let i = 0; i + 6 < binary.length; i += 6) {
        if (!permittedBits.has(binary[i..i+6])) { return []; }
      }
      // otherwise dive into this branch
      return generateStrings(candidateStr, targetLength - 1)
    });
};

Unfortunately, this still turned out to be slightly too slow to be reasonable. Clearly, there was still work to do.

To further limit the search space we can consider the requirement that the password must be a palindrome, similar to what we did to rule out even-length passwords.

Currently, we only check if the encoding works on the password as we build it up - but since we know that the password will eventually be reversed and added to itself to make a palindrome, we can also check that it encodes correctly in the reverse direction.

We don’t know what offset the latter half will be at, so we’ll simply test each of the three possible offsets and abort if none of them work:

// The ASCII characters we can use in our password are represented by char codes 32-126,
// and the sextets groups we want are in the range 26-51
const asciiCodes = [32..127];
const permittedBits = new Set([26..52].map(i => i.toBinary(wordLength=6)));
// Checks if the binary data encodes into only the sextets groups we want
const encodesCorrectly = (binary, offset) => {
  for (let i = offset; i + 6 < binary.length; i += 6) {
    if (!permittedBits.has(binary[i..i+6])) { return false; }
  }
  return true;
}
// Using this we can recursively generate all the passwords that encode to the wanted format
const generateStrings = (currentString, targetLength) => {
  if (targetLength <= 0) { return [currentString]; }
  return getAllowedCodes(currentString)
    .flatMap(code => {
      const candidateStr = currentString + char(code);
      // abort if it doesn't encode safely in the forwards direction
      const binary = candidateStr.toBinary(wordLength=8);
      if (!encodesCorrectly(binary, 0)) { return []; }
      // and if it doesn't encode in at least one of the possible offsets in the backwards direction
      const reverseBinary = candidateStr.reverse().toBinary(wordLength=8);
      if (![0,2,4].any(offset => encodesCorrectly(reverseBinary, offset))) {
        return [];
      }
      // otherwise dive into this branch
      return generateStrings(candidateStr, targetLength - 1);
    });
};

Brute-forcing

With the above code, we can limit our search space to be just small enough that we can test all possibilities in a reasonable time. Another improvement I ended up implementing was aborting any branch that included any of the disallowed words (only checking words of length 3 or below, for the sake of performance).

With these improvements, I was able to get a list of 36 valid passwords:

const fulfillsRequirements = str => { /* ... validation method from website */ };
const toPalindrome = str => {
  if (str.length % 2 === 0) {
    return str + str.reverse();
  }
  return str + str[0...str.length - 1].reverse();
}
const getValidPasswords = () => generateStrings("", 8).map(toPalindrome).filter(fulfillsRequirements);
getValidPasswords();
// ["o'knXjs8sjXnk'o", "o'sjXnk8knXjs'o", "o(knXjs8sjXnk(o", ...]

Trying to use one of them in the login form only passed the frontend validation, returning a 403 Forbidden from the backend. This was exactly the same error as would be given if we bypassed the client-side validation and submitted an invalid password.

Luckily this was easily solved by trying each of the valid passwords, which showed that the backend accepted exactly one of them:

const $form = document.querySelector("form");
getValidPasswords()
  .forEach(async (pass) => {
    const data = new FormData($form);
    data.set("password", pass);
    const resp = await fetch("/login", { method: "POST", body: data });
    if (resp.ok) { console.log("VALID:", pass); }
  });

Why the backend would accept arbitrary usernames, but only one password, is a mystery that isn’t meant to be solved ;)

Entering the successful password gave us the flag, earning us a few points for the leaderboard.