Square CTF 2018 - C10: fixed point

Description

A handwritten note has been added to C10’s label.

If you are a Charvis then this is a simple application of Xkrith’s First and Sixth Theorems.  If you are not a Charvis then you should familiarize yourself with Xkrith’s works.  A primer can be found in Room 100034B.

Note: For the humans out there, this system is built on an oscillator. It’ll disable itself when you find the oscillator’s fixed point.

Good luck!

Solution

The Javascript code in the given HTML file applies the function below to our input x, and gives us the flag if and only if x is a fixed point (i.e. f(x) = x).

function f(x) {
  if ((x.substr(0, 2) == '🚀') && (x.slice(-2) == '🚀')) {
    return x.slice(2, -2);
  }
  if (x.substr(0, 2) == '👽') {
    return '🚀' + f(x.slice(2));
  }
  if (x.substr(0, 2) == '📡') {
    return f(x.slice(2)).match(/..|/g).reverse().join("");
  }
  if (x.substr(0, 2) == '🌗') {
    return f(x.slice(2)).repeat(5);
  }
  if (x.substr(0, 2) == '🌓') {
    var t = f(x.slice(2));
    return t.substr(0, t.length/2);
  }

  return "";
}

This function reads our input emoji by emoji interpreting each one of them as an instruction. Those instructions are pushed on the top of a stack. The final output of f is the result of applying all those instructions starting from the top of the stack, i.e. last in first out.

The mapping between emojis and instructions is the following:

• 👽 -> put 🚀 on the stack
• 📡 -> put reverse on the stack
• 🌗 -> put repeat(5) on the stack
• 🌓 -> put substr(0, t.length/2) on the stack
• 🚀x🚀 -> put x on the stack (exit case)
• default -> put '' on the stack (exit case)

We can do the following observations.

1. The only emoji that we can create is 🚀.
2. Following from 1. , the only way we have to “create” other emojis is trough the repeat(5) operation. Of course the emojis we want to “create” have to be in the argument of repeat(5).
3. From what above we conclude that the only acceptable exit case is 🚀x🚀, and that x has to include all the emojis we need to “create”.
4. 📡📡 corresponds to the unit operation.
5. 📡👽📡 translates to [reverse, 🚀 at beginning, reverse]. The result of those three instructions will be adding a 🚀 at the end of our current sequence.

Now we have enough information to start building our input!

Let’s define it to be x🚀x🚀, where x = y📡👽📡. This will translate into [..y.., reverse, 🚀 at beginning, reverse, x]. Remebering that we have to apply the instructions backwards (i.e. starting from the right), after applying the first four we will end up with the following situation:

• Partial output: x🚀
• Stack: [..y..] (i.e. the instructions encoded in y)

Thus, if we manage to have y such that its aggregation corresponds to repeat(2) we are done. In other words we want to find a uand vsuch that:

    1 * 5^u * 2^-v = 2

Unfortunately there is no integer solution to this equation, but we can overcome this limitation by generalizing what stated above. We can define our input to be x🚀 repeated n times (with x defined as before), so that, after applying the first four operations, the situation will be:

• Partial output: x🚀 repeated n-1 times
• Stack: [..y..] (i.e. the instructions encoded in y)

The equation to solve becomes:

    (n-1) * 5^u * 2^-v = n

Which hopefully has {n = 5, u = 1, v = 2} as a solution.

We obtain y=🌓🌓🌗, thus x=🌓🌓🌗📡👽📡. Now we repeat x🚀 five times and we are done!

🌓🌓🌗📡👽📡🚀🌓🌓🌗📡👽📡🚀🌓🌓🌗📡👽📡🚀🌓🌓🌗📡👽📡🚀🌓🌓🌗📡👽📡🚀

flag-2d4584368d09da2187f5

Bonus

Quines

The function f of this challenge is actually a quine. Quines are programs that print out their own source code.

Infinite solutions 📡📡

Since 📡📡 corresponds to the unit operation, there were an infinite number of solutions: one can add to his input as many couples of 📡 as he wants.

Beside this, there are many solutions to the equation presented above and {n = 5, u = 1, v = 2} is only one of them.