Welcome to Mark's blog for Capture The Flag (CTF) enthusiasts

Friday, July 1, 2022

CTF Writeup: STANDCON22 Royal Flag Formula

Short message from Mark:
Hello there, thanks for checking out this post. I'm trying out a new form of CTF writeup for the challenges I create. In these short CTF Creator Writeups, I'll be explaining how I put these challenges together, from my initial idea to a final package ready for deployment. In the process, you'll find out how to solve this challenge, and other similar ones too.

If you’re into making your own CTF challenges, please feel free to use some of the ideas from this post in your own creations. Let me know if you come up with something cool!

Quick stats
Name: Royal Colour Formula
Category: Programming
Difficulty: Hard
Link to challenge files, generators, and solutions: https://github.com/MarkB-NYP/ctf-challenge-archive/tree/main/Royal-Colour-Formula


   The final challenge shown to players during the CTF

Reconnaissance: Finding a unique challenge idea
While we were planning CTF challenges for STANDCON, I noticed a lack of programming challenges classified as 'hard'. I offered to try building one, and the organizers were kind enough to let me give it a shot. Full of excitement, I started brainstorming possible ideas for this challenge. 

Based on my experience in other CTFs, most programming challenges fall into two general categories: 
  1. Automating a tedious task (with a time limit to prevent manual solutions)
  2. Working with an obscure programming language (either a program purposely coded in a unintuitive way, or using an esoteric language)
With these two categories, it's usually pretty obvious what you need to do (for example, solve a math equation). The difficulty comes in the implementation: writing a program that works according to all the requirements.

For a bit of variety, I toyed around with the idea of a programming challenge where it would be trivially easy to code the solution. Instead, the hard part would be finding out what you were supposed to code.

Enumeration: Developing the challenge concept
I decided on one core programming concept to challenge: identifying and reversing an algorithm. Algorithm reversal sits quite close to the Cryptography or Reversing categories, so I added a few more constraints for myself. The challenge would:
  1. Not use a standard, modern cryptographic technique, or any fancy maths
  2. Not provide players with the generation/encryption source code
  3. Be solvable with any programming language the player was comfortable with

The next part was finding a concept that fit in with the CTF's overarching storyline. The whole STANDCON event had an Atlantis/underwater concept, which was really cool because all the challenges had related storylines. Some creators prefer to work on challenges on a purely technical level, then add a bit of design or references later on. I start with the story and theme, and get inspired by that.

I had a vision where each ruler of Atlantis would have their own set of special royal colours, that they put on their secret Atlantean submarines and stuff. Of course, the technologically-advanced race of Atlanteans wouldn't leave anything up to chance; They would have a formula to calculate the best colours for each ruler, based on whatever the previous ruler had used.

Of course, the Royal Colour Formula (the name had a nice ring to it) needed an initial 'seed' value. What colours did the first ruler of Atlantis use? Well, that first set of colours would be generated using the flag for this challenge, and using a set of later configurations, the player would have to reverse the formula and find the original set of colours (and the flag).

Exploit development: Building the final challenge materials
With the challenge concept in mind, I ran a few feasibility studies. These are small prototypes that I like to do first, to check if the technical aspects behind the challenge work. I played around with a few possible versions of the Royal Colour Formula. I could use the red, green and blue (RGB) values that make up each colour to store one character of the flag (hey, a Steganography technique!) 

In order to convert each set of colours into the next combination, I settled on a nice 'shifting' algorithm based on averages:
  1. Red value = Blue value of previous colour + Green Value of previous colour
  2. Green value = Blue value of previous colour + Red Value of previous colour
  3. Blue value = Red value of previous colour + Green Value of previous colour
Each colour would change independently (since the formula only mixes values within the same colour), but I hoped the overall impression would be bizarre enough to prevent players picking up on this immediately. Of course, RGB values only go from 0 to 255, so I added a few if-else checks that would keep the final values within the accepted range. Choosing the right checks so the colours all render correctly would be the final obstacle for players reversing the Royal Colour Formula.

An interesting side effect of this conversion algorithm is that there are only 24 possible combinations, after that the colours loop back to the first combination. A possible in-game explanation could be that the Atlantean scientists who first devised the algorithm believed after 24 kings or queens, no one would remember what the first set of colours was anyway.

Satisfied that the challenge would be solvable, I coded the final generation script, that would display the colour combinations in running order. Players would get the last four colour combinations to work with and examine. 


Output from the challenge generation script.

I decided against using a screenshot of the page, since sometimes images get compressed or look different depending on the display you're using. Hopefully, the challenge delivery method would also hint that the exact values of each colour were somehow crucial to the challenge. The message (or at least, the clue) was in the medium.

Another small touch I was careful to add was expressing the colours in the HTML as hex values, not RGB values. Hex (hexadecimal notation) was a lot more commonly used compared to RGB, and I was concerned that leaving the values as distinct, base-10 numbers would be too much of a giveaway. I wanted my challenge solvable, but not a walkover.

In the end, I copied the HTML elements to a new file and typed up a small, cute story about a professor (who appeared in another of my challenges from the same CTF). The organizers could either host the HTML page directly, or give it to participants as a download (what they did ultimately). You can see the final page here: https://markb-nyp.github.io/ctf-challenge-archive/Royal-Colour-Formula/distribute/Royal_Colour_Formula.html.

To test if the challenge was actually solvable, I reversed my generator code to create a solution in JavaScript, which I ran from Google Chrome's developer tools. This means that technically, the challenge can be solved entire from your web browser.

A 'push' to GitHub, approval from the organizers, and a month later, the challenge was live on the STANDCON CTF platform, ready to accept flags!


BONUS - Zero-day Discoveries: What happened during the actual CTF?
The organizers of STANDCON22 set up a special account for the challenge creators to access the CTF platform, which was great since I could have a look at how players were handling the challenges. The challenge had no solves for quite a long time. One one hand, I was starting to feel a little concerned that the challenge might be too difficult. On the other hand, I felt just a little bit satisfied, having achieved my target of a 'difficult programming challenge'.

Of course, the brilliant players at STANDCON22 were not to be denied one of the most valuable flags in the game. (STANDCON used dynamic scoring, where challenges with fewer solves were worth more points.) At the end of the competition, four teams managed to crack the formula and find the flag. Impressively, none of these teams bought any of the hints for this challenge.


The challenge, as seen on the CTF platform

Like I hoped, players used many different tools and paths to solve the challenge. The Team ManMode, for example, extracted the hex colour values and fed them into a custom Python script to solve the challenge, along with some trial-and-error to fix their algorithm. In many ways, it was the opposite of the steps I took to create the challenge.  


Thanks also to N0H4Ts for letting this challenge debut at STANDCON22. Find out more about them here: https://n0h4ts.com/.
at