Link to archived challenge

Category Difficulty Solves Author
reverse hard 10 Spaghetti

Description

Our forensics team ripped this firmware off a strange proprietary electronic device that was confiscated from a t3l0s member. Can you figure out what it does?

Players are given a file to download: kAjfehg-n.

Players are also given a single hint:

  1. The language that the file is written in is Uyjhmn n

Analysis

Uyjhmn n is an esoteric programming language (or “esolang” for short).
It is a programming language that was explicitly designed to be annoying to use:

Uyjhmn n was designed to annoy the user by combining verbose syntax with a terrible looking IDE that rushes the user. It was named after the gibberish that gets typed when you bang your head on the keyboard out of frustration.

Incidentally, that was also the method used to name this challenge.

Looking at the program from the challenge, we can identify 11 unique commands it uses:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

DECLARE THE NEW VARIABLE <variable>
OPEN THE VARIABLE <variable>
ASSIGN <const> TO THE OPEN VARIABLE
ADD <variable> TO THE OPEN VARIABLE
PRINT THE CHARACTER WITH THE ASCII VALUE <const>
PRINT THE OPEN VARIABLE'S CHARACTER
DEFINE THE NEW LABEL <label>
JUMP TO <label> IF <variable> IS EQUAL TO <variable>
JUMP TO <label> IF <variable> IS GREATER THAN <variable>
JUMP TO <label> IF <variable> IS LESS THAN <variable>
END THIS PROGRAM

Now, one could trace the program to determine what it would output, by hand.

But where’s the fun in that? What if there’s some subtle-yet-complex logic hidden in the middle of this mess?
Or, what if the next challenge decides to give us 20,000 instructions instead of just 200?

Solution

I wrote an interpreter!

When I playtested this challenge, I legitimately thought this was the intended solve.
Of course, I did go a little overboard and stayed up all night writing an actually-decent interpreter instead of slapping a Python script together and calling it a day.
But it actually revealed some bugs in the challenge, so I’d call it worth it.

This is where I’d tell you a bit about the process of writing the interpreter, and then show you the source code.
Except… I accidentally deleted it. Lesson learned: don’t rework git repos when you have a bunch of uncommitted files 🙃.

The Rewrite

After the competition, I wrote a new interpreter — this time with a proper parser library (nom).

I won’t get into the low-level details (you can read the code if you’re interested), but here’s a summary of what my program does:

  1. Load the program text and split it into lines.
  2. Parse each line as an instruction.
    Most invalid instructions cause “compile-time” errors, before the code starts executing.
  3. Collect label definitions.
    This is important because forward references are allowed (you can refer to a label that’s defined later in the file).
  4. Create the virtual machine.
    The VM state includes the currently-open variable, the names and values of all variables, and the instruction pointer.
  5. Execute program instructions.
    The VM starts execution at the first line, and increments the instruction pointer (IP) after most instructions (jump instructions can set the IP to the address of a label instead).
  6. Halt, or don’t.
    Program execution ends when the instruction pointer passes the last line of the program, or the END THIS PROGRAM instruction is encountered.

Conclusion

I don’t think writing an interpreter for this challenge is the necessarily the most efficient solve, but a simple one written in Python or a similar language could be a good choice.
I only solved this challenge with an interpreter written in Rust because it seemed fun and I wasn’t under any time constraints, but if I were competing I wouldn’t have spent as much time learning a new library (nom) or handling corner cases.