Esoteric Languages in CTF: Recognising Code That Does Not Look Like Code

Introduction

You get a file. It contains a few hundred plus signs and angle brackets, or a page of song lyrics about a girl called Tommy, or a small PNG of coloured squares, or what looks like an empty text file that is 4KB on disk. There is no flag in it and strings tells you nothing.

All four are programs. The flag is what they print when you run them, and running them takes one command:

pip install brainfuck-interpreter    # or the 25-line one further down this page
 
# Brainfuck, Ook!, Whitespace, Malbolge, Befunge, Piet: all have public interpreters
python3 bf.py program.bf

In an esolang challenge the flag is the output, not the source. The entire task is identifying which language you are holding.

That last sentence is the whole guide, and it is worth stating plainly because people reliably do the harder thing instead. The instinct on seeing an unreadable block of symbols is to reverse it: work out what each character does, trace it by hand, decode it. That is real work and it is almost never necessary. Someone else wrote the interpreter years ago. The skill being tested is recognition, which takes about five seconds once you have seen each fingerprint once, and this guide is mostly a list of fingerprints.

I will admit to a soft spot here. Esoteric languages are one of the few places computing is openly having fun with itself, and a category that rewards knowing that Rockstar exists is a category I am happy to keep encountering. It is also useful practice, because the underlying skill, looking at a blob and asking what kind of thing it is before asking what it says, is the same one that saves you an hour on every forensics challenge you will ever open.

The fingerprint table

Every esolang that turns up in CTF has a visual signature, and most of them can be identified from a single screenful. This table is the reason the category is fast.

If nothing matches, the esolangs wiki catalogues well over a thousand of these, and its language list is searchable by the characters a language uses. That is where to go before deciding a file is encrypted rather than executable.

Brainfuck, properly

Brainfuck is the one worth actually learning, because it takes ten minutes and it turns up constantly, both by name and as the target of other encodings. The machine is a tape of bytes and a pointer. Eight instructions, and everything else in the file is a comment.

Here is a complete interpreter. It handles bracket matching up front rather than scanning at runtime, which is the difference between finishing instantly and appearing to hang on a program with nested loops.

def run(src, stdin=b""):
    src = [c for c in src if c in "><+-.,[]"]
    jump, stack = {}, []
    for i, c in enumerate(src):
        if c == "[":
            stack.append(i)
        elif c == "]":
            j = stack.pop()
            jump[i], jump[j] = j, i
    tape, p, pc, out, inp = bytearray(30000), 0, 0, bytearray(), iter(stdin)
    while pc < len(src):
        c = src[pc]
        if   c == ">": p += 1
        elif c == "<": p -= 1
        elif c == "+": tape[p] = (tape[p] + 1) & 0xff
        elif c == "-": tape[p] = (tape[p] - 1) & 0xff
        elif c == ".": out.append(tape[p])
        elif c == ",": tape[p] = next(inp, 0)
        elif c == "[" and not tape[p]: pc = jump[pc]
        elif c == "]" and tape[p]:     pc = jump[pc]
        pc += 1
    return bytes(out)

Three idioms cover most hand-written Brainfuck, and knowing them lets you skim a program rather than trace it. [-] zeroes the current cell. [->+<] moves a value one cell right, destroying the original. A long run of + followed by . is printing one literal character, which means a program that is nothing but runs of plus signs and dots is a constant string and you can read the flag off the counts without running anything.

Whitespace and invisible text

Whitespace uses exactly three characters: space, tab, and line feed. Everything else in the file is a comment, which means a valid Whitespace program can be hidden inside perfectly ordinary source code, and often is.

# Is this file actually empty, or full of invisible instructions?
wc -c mystery.txt          # a 'blank' file with real size is the tell
cat -A mystery.txt | head  # spaces stay, tabs show as ^I, newlines as $
 
# Which invisible characters, and how many of each?
python3 -c "
import collections,sys
d=open(sys.argv[1],'rb').read()
print(collections.Counter(c for c in d if c in b' \t\n\r'))" mystery.txt

The count is what tells you which problem you have. Three distinct whitespace bytes in a structured pattern is the Whitespace language, and it needs a real interpreter because it has a stack, arithmetic, and flow control. Two distinct characters is something simpler and more common: a binary encoding, where one character means zero and the other means one.

# Two symbols means binary. Decode on code points, not on bytes.
import collections, sys
 
text = open(sys.argv[1], encoding='utf-8').read()
blank = [c for c in text if c.isspace() or ord(c) in (0x200b, 0x200c, 0x200d, 0xfeff)]
counts = collections.Counter(blank)
print(counts.most_common(5))          # two symbols dominating = a one-bit channel
 
(zero, _), (one, _) = counts.most_common(2)
bits = ''.join('0' if c == zero else '1' for c in blank if c in (zero, one))
 
# You cannot know which symbol means zero, so print whichever polarity is readable.
for b in (bits, bits.translate(str.maketrans('01', '10'))):
    out = ''.join(chr(int(b[i:i+8], 2)) for i in range(0, len(b) - 7, 8))
    if out.isprintable():
        print(out)

WhitePages is this second case, and it is a good illustration of why the distinction matters: reaching for a Whitespace interpreter on it produces an error, and concluding the file is corrupt is a very easy mistake to make. Its two symbols are an ordinary space and U+2003, the em space, which is three bytes long in UTF-8. That is why the decoder above counts code points rather than bytes: a byte-level version splits every em space into three and returns nothing but null bytes. Unicode gives an author hundreds of code points that render as blank, all documented in the character database, so the modern version of this uses zero-width spaces rather than tabs. Same decode, different bytes. The document-carrier version of the trick is in document forensics.

Programs that read as prose

Rockstar, designed by Dylan Beattie in 2018, is a real programming language whose syntax is deliberately constrained to look like power ballad lyrics. Variables are common phrases, numbers are encoded as the letter counts of the words in a poetic literal, and the whole thing compiles and runs.

Tommy was a lovestruck ladykiller
Shout Tommy
 
# The parser takes the LENGTH of each word after the assignment and reads it
# as one decimal digit. Ten letters or more counts modulo 10.
#   a           1 letter   -> 1
#   lovestruck  10 letters -> 0
#   ladykiller  10 letters -> 0
# so Tommy is 100, and Shout prints it.
 
# The same rule, from the language's own documentation:
#   Papa was like a rolling stone   ->  1, 7, 5   ->  175
#   Scream like a banshee           ->  1, 7      ->  17

mus1c is exactly this. The challenge hands you what looks like a set of lyrics, and it is a Rockstar program that prints a series of numbers. Feed those numbers through an ASCII conversion and the flag appears. The two steps are worth separating: the language produces numbers, and turning numbers into text is your job, not the program's.

# Run the lyrics through a Rockstar interpreter, then:
python3 -c "
nums = [112, 105, 99, 111, 67, 84, 70]
print(''.join(chr(n) for n in nums))"

The ones you cannot read left to right

Two languages break the assumption that a program is a sequence, and both appear in CTFs precisely because that assumption is what makes them confusing.

Befunge lays code out on a two-dimensional grid, and the instruction pointer travels in a direction that the program itself changes: > sends it right, v down, < left, ^ up. Control flow is literally geometric, and the program can also modify its own grid while running. Reading one by hand means tracing a path around a maze. Running one takes a Befunge-93 interpreter and a second.

Piet, named after Piet Mondrian, is a language whose programs are images. Blocks of flat colour are the instructions, and the operation performed depends on the change in hue and lightness between the block you are leaving and the one you are entering. The practical trap is the codel size: if the image was scaled up, one logical pixel may be a 5 by 5 block, and the interpreter needs to be told.

# Befunge
befunge93 program.bf93
 
# Piet, with npiet. Try codel sizes until the output makes sense.
npiet -cs 1 program.png
npiet -cs 5 program.png
npiet -t -cs 1 program.png     # trace mode, when nothing comes out
 
# Is this image even a Piet program? Count distinct colours.
python3 -c "
from PIL import Image
im = Image.open('program.png').convert('RGB')
print(len(set(im.getdata())))"    # Piet uses 20 colours, so <= 20 is a strong hint

Obfuscated JavaScript is an esolang

JSFuck is not a separate language. It is ordinary JavaScript written using only the six characters []()!+, which is possible because JavaScript's type coercion rules let you build every digit, every letter, and eventually Function itself out of nothing but those symbols.

![]        -> false
!![]       -> true
+[]        -> 0
+!![]      -> 1
[]+[]      -> ""          (empty string)
[]+{}      -> "[object Object]"   <- now you have letters
 
# so this is a real, runnable program:
[+!![]]+[+[]]      ->  "10"

The reason it belongs in this guide is that people meet it and try to decode it as a cipher. It is not encoded, it is written. The safe way to read it is to hand it to a JavaScript engine but stop it before the final call: replace the outer Function(...)() invocation with a console.log of the string it built, and you get the original source rather than its effects.

// Never paste unknown JSFuck straight into a console on a page you care about.
// Print what it would run, instead of running it:
//   change   Function("...")()
//   to       console.log("...")
 
node --input-type=module -e 'console.log(eval(payload_without_final_call))'

The same principle covers jjencode, aaencode, and every packer that ends in an eval: find the sink, print instead of execute. That technique is the spine of JavaScript deobfuscation for CTF, which goes considerably deeper into it.

Writing for a strange machine

One family inverts the whole exercise. Instead of being handed a program in a strange language and asked what it prints, you are handed a strange machine and asked to write for it.

Core War, designed by A. K. Dewdney and published in 1984, is a game where two programs written in an assembly language called Redcode fight inside a shared circular memory running on a simulator called MARS. The winner is the program still executing when the other one dies. picoCTF's Ready Gladiator 0 asks for the least intuitive possible objective: lose every round, on purpose.

;redcode
DAT 0, 1
end
 
# DAT is the one instruction that kills the process that executes it,
# so a warrior consisting of only DAT dies on its first cycle.
printf ';redcode\nDAT 0, 1\nend\n' > lose.red
nc saturn.picoctf.net <PORT_FROM_INSTANCE> < lose.red

The lesson generalises past Core War. When a challenge gives you an instruction set you have never seen, read its documentation rather than reverse engineering its behaviour from examples. Redcode has a published standard, and so does every other machine that has ever appeared in a challenge. Reversing an interpreter is only necessary when the machine is genuinely custom, which is a different skill covered in reversing custom VMs. The plumbing for talking to the judge is in the netcat guide.

The method, in order

Five steps, and the order matters because each one is cheaper than the one after it.

Step five is where people stop too early. A program that prints 112 105 99 111 has done its job; the remaining work is one line of Python, or a paste into the recipe chain if the output turns out to have several layers. Multi-layer decoding as its own discipline is in CTF encodings explained.

picoCTF challenges

Bookmarklet is on the list because it teaches the same reflex as JSFuck: the code you were handed is meant to run somewhere, and running it somewhere you control is both safer and faster than reading it. The broader category ladder is in the general skills roadmap, and the decoding half of this work continues in CTF encodings.

Quick reference

# 1. What kind of thing is it?
file f && wc -c f && head -c 200 f | cat -A
 
# 2. How many distinct bytes? This names the language.
python3 -c "import collections,sys;
print(collections.Counter(open(sys.argv[1],'rb').read()).most_common(12))" f
 
#    8 printable symbols  ->  Brainfuck   (+-<>[].,)
#    3 tokens 'Ook'       ->  Ook!
#    3 whitespace bytes   ->  Whitespace
#    2 whitespace bytes   ->  a binary encoding, not a language
#    6 symbols []()!+     ->  JSFuck
#    <= 20 colours, PNG   ->  Piet
#    English that parses  ->  Rockstar / Shakespeare / Chef
 
# 3. Run it
python3 bf.py f            # the 25-line interpreter in this guide
npiet -cs 1 f.png          # try several codel sizes
befunge93 f.bf93
 
# 4. Convert the output
python3 -c "print(''.join(chr(n) for n in [112,105,99,111]))"
 
# When nothing matches: search the character set on esolangs.org

Related reading: CTF encodings for the layer after the program runs, JavaScript deobfuscation for JSFuck and its relatives, reversing custom VMs for when the machine is undocumented, document forensics for invisible characters in real documents, and Python for CTF for the scripting the last step always needs.

Sources and further reading

Esoteric languages are documented by their designers and by one very good community wiki. The interpreter above was written against the language reference and tested on the canonical Hello World program.

• The esolangs wiki is the reference for this entire category. Its individual language pages carry the specification, sample programs, and usually a list of implementations, which is exactly the three things you need in the order you need them.
• The Brainfuck page documents the eight instructions and, more usefully, the implementation differences around cell size and wrapping that cause most apparent failures. The Whitespace page covers its stack-based instruction encoding, which is worth a skim purely to see why a two-character file cannot be a Whitespace program.
• The Rockstar documentation on variables is where poetic number literals are specified: the parser "takes the length of each word and interprets it as a decimal digit", with ten letters or more counted modulo 10. That one rule is what lets you confirm a suspicious set of lyrics is a program before you go looking for an interpreter.
• David Morgan-Mar's Piet specification defines the twenty colours and the hue and lightness transition table. The codel-size problem is described there too, which saves the guessing game.
• Unicode Annex 44, the character database for the modern invisible-character version of the whitespace trick. The general categories and the list of code points with zero advance width are what make that channel possible in the first place.