FE-CTF 2023 - Brute force ahoy

This is my write-​up for the 2023 CTF qual­i­fier held by the Dan­ish De­fence In­tel­li­gence Ser­vice: The UniP­wnie Ex­pe­ri­ence. This was an open CTF event, with the top 10 teams being in­vited to an in-​person event.
In this write-​up, I will focus on how I solved the “Login Level 3” chal­lenge, a brute-​force based chal­lenge that was re­leased early in the CTF.

The Chal­lenge

When first open­ing the chal­lenge page I was greeted by a sim­ple login form with a user­name and pass­word field. At­tempt­ing to log in, I was met with in­creas­ingly ab­surd pass­word re­quire­ments, rang­ing from “pass­word must be at least 10 char­ac­ters long” to “sum of dig­its in pass­word must be a cube” - pre­sum­ably these would be the sub­ject of the chal­lenge.

Hop­ing against hope, I tried by­pass­ing the val­i­da­tion and just sub­mit­ting a pass­word di­rectly to the back­end - but was met with a 403 Unau­tho­rized. That would’ve been too easy any­way. Guess we’ll have to take an­other look at those pass­word re­quire­ments.

Open­ing the Chrome De­v­Tools quickly re­vealed a sin­gle JavaScript file con­tain­ing the rel­e­vant logic, nice and un­ob­scured, writ­ten in a submit han­dler on the login form. Read­ing the code we can quickly see that the pass­word re­quire­ments fall can be sum­ma­rized as:

1. Must con­sist of ASCII char­ac­ters, with each of the fol­low­ing groups rep­re­sented:
   • up­per­case let­ters,
   • low­er­case let­ters,
   • dig­its,
   • sym­bols,
   • and Roman nu­mer­als (CDILMVX).
2. There must be at least 8 unique char­ac­ters in the pass­word.
3. Must be be­tween 10 and 20 char­ac­ters long.
4. Must have an un­bro­ken se­quence of let­ters of at least length 5.
5. Can­not con­tain any of a long list of words (case in­sen­si­tive).
6. Must be a palin­drome.
7. Sum­ming up all the dig­its must give a cube num­ber (that is, its third root must be an in­te­ger).
8. When en­coded in Base64, the re­sult can­not con­tain any­thing but low­er­case let­ters.

There are no rules for the user­name, and no clues are given to its value. From an ear­lier chal­lenge in the same se­ries, I knew that the login sys­tem would ac­cept ar­bi­trary user­names. Pre­sum­ably, the pass­word would be the same: as long as it ful­filled the re­quire­ments, the login would go through and the flag be mine.

So I guess all that’s left to do is find a pass­word that ful­fills all the re­quire­ments. How hard can that be?

Ini­tial thoughts and prayers

Crack­ing the pass­word would most likely in­volve brute-​forcing it lo­cally, try­ing out com­bi­na­tions of strings until one ful­filled all the rules.
With a bit of nap­kin math, it quickly be­came clear that this was some­what in­fea­si­ble to do naïvely. Al­though the pass­word must be a palin­drome, and we’d there­fore only have to gen­er­ate 5-10 char­ac­ters to get the pass­word to the re­quired 10-20 char­ac­ter re­quire­ment, that still meant more than $95^{10} \approx 5.99 \cdot 10^{19}$ pos­si­bil­i­ties if using the 95 char­ac­ters the code con­sid­ered ASCII.
Even if I could try a bil­lion com­bi­na­tions a sec­ond, that’d still take over 1897 years.

I’d there­fore have to limit the avail­able pos­si­bil­i­ties as much as pos­si­ble, in a way that could be im­ple­mented as early as pos­si­ble in the brute force process. Al­though there are many ways to cut down on the re­quired work, it seemed like the most promis­ing way was to focus on the “must en­code to purely low­er­case let­ters in Base64” re­quire­ment.
This was what I im­me­di­ately jumped on.

Aside: Base64 en­cod­ing

Base64 is an en­cod­ing al­go­rithm that takes ar­bi­trary bi­nary data (in our case this is the bi­nary rep­re­sen­ta­tion of our pass­word) and turns it into a string con­sist­ing only of a sub­set of ASCII char­ac­ters.

It does this by split­ting up the bi­nary data into groups of 6 bits each (and padding with 0 if it doesn’t split nicely). Each of these sex­tets can be rep­re­sented by one of $2^6 = 64$ pre-​chosen ASCII char­ac­ters. In our case, we want a pass­word that only con­tains sex­tets rang­ing from 011010 (26) to 110011 (51), as those are the ones that are rep­re­sented by low­er­case let­ters a-z.

Most com­mon im­ple­men­ta­tions of Base64 out­put padded re­sults, ap­pend­ing = to the en­coded out­put until its length is di­vis­i­ble by 4: this en­sures that the Base64 rep­re­sen­ta­tion rep­re­sents a whole num­ber of our usual 8-bit bytes.

Back to our thoughts

With this in mind, we can con­clude a few things:

1. The pass­word’s length must be di­vis­i­ble by 3. If it was not, the Base64 en­cod­ing would be padded with the = char­ac­ter, which isn’t a low­er­case let­ter.
2. Since the sum of all dig­its must be 27, an un­even num­ber, the palin­drome must be of un­even length. Com­bined with know­ing the length must be di­vis­i­ble by 3, and be be­tween 10 and 20, this means that we know the pass­word to be of length 15.
3. En­cod­ing char­ac­ters are locked once every bit rep­re­sent­ing them has been cov­ered by an input bit. When brute forc­ing our pass­word we can use this to quickly dis­card any branches that en­code into a char­ac­ter we don’t want.
4. As one of the re­quire­ments is to have 8 unique char­ac­ters, and our pass­word is a palin­drome of length 15, the first half of the palin­drome can­not have any du­pli­cate char­ac­ters.

Al­though not enough to get us all the way to our final pass­word, this can be used to sig­nif­i­cantly lower the cost of brute forc­ing.

Lim­it­ing our search space

To use the above ob­ser­va­tions to cut down on our brute force work, we’ll slowly build up pass­words one char­ac­ter at a time until we reach a length of 15. We’ll be care­ful to only use char­ac­ters that main­tain the lowercase-​only Base64 en­cod­ing.
This means we’ll only have to check strings that at the very least en­code to the right for­mat, sav­ing us the work of div­ing into any branches that start with e.g. a (as that’ll al­ways en­code into a Base64 string start­ing with Y).

We can im­ple­ment it using sim­ple bit-​checking, fil­ter­ing out any char­ac­ters that would cre­ate a 6-bit group that doesn’t rep­re­sent a low­er­case let­ter 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)
    });
};

Un­for­tu­nately, this still turned out to be slightly too slow to be rea­son­able. Clearly, there was still work to do.

To fur­ther limit the search space we can con­sider the re­quire­ment that the pass­word must be a palin­drome.
Cur­rently, we only check if the en­cod­ing works on the pass­word as we build it up - but since we know that the pass­word will even­tu­ally be re­versed and added to it­self to make a palin­drome, we can also check that it en­codes cor­rectly in the re­verse di­rec­tion.

We don’t know what off­set the lat­ter half will be at, so we’ll sim­ply test each of the three pos­si­ble off­sets 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 pos­si­bil­i­ties in a rea­son­able time. An­other im­prove­ment I ended up im­ple­ment­ing was abort­ing any branch that in­cluded any of the dis­al­lowed words (only check­ing words of length 3 or below, for the sake of per­for­mance).

With these im­prove­ments, I was able to get a list of 36 valid pass­words:

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", ...]

Try­ing to use one of them in the login form only passed the fron­tend val­i­da­tion, re­turn­ing a 403 For­bid­den from the back­end. This was ex­actly the same error as would be given if we by­passed the client-​side val­i­da­tion and sub­mit­ted an in­valid pass­word.

Luck­ily this was eas­ily solved by try­ing each of the valid pass­words, which showed that the back­end ac­cepted ex­actly 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 back­end would ac­cept ar­bi­trary user­names, but only one pass­word, is a mys­tery that isn’t meant to be solved ;)

En­ter­ing the suc­cess­ful pass­word gave us the flag, earn­ing us a few points for the leader­board.