Flash CTF - Ways To Lie
Ways To Lie Writeup
Overview
The handout is a single file of emoji and there is no service to talk to. The emoji are base100, an encoding with no key, and peeling it off leaves a string of musical symbols. Those symbols are a substitution over hex nibbles, two per plaintext byte. The fixed SkillBit{ prefix hands over more than half the alphabet, and the way the author laid the alphabet out gives up the rest, apart from one symbol that only the English settles.
Reconnaissance
The handout is flag.txt, and it is not text in any useful sense:
$ head -c 80 dist/flag.txt
📙💐💥📙💐💣📙💐💦📧💔👻💢📙💐💦📧💔👻💘
The codepoints matter more than the pictures. Dumping them shows a tight cluster:
$ python3 -c "
t = open('dist/flag.txt', encoding='utf-8').read().strip()
print(len(t), 'codepoints')
print([hex(ord(c)) for c in t[:6]])
print(min(ord(c) for c in t) - 0x1F3F7, max(ord(c) for c in t) - 0x1F3F7)"
404 codepoints
['0x1f4d9', '0x1f490', '0x1f4a5', '0x1f4d9', '0x1f490', '0x1f4a3']
132 240Every codepoint lands between U+1F3F7 + 132 and U+1F3F7 + 240. A file whose characters all sit inside a 256-wide window anchored at U+1F3F7 is base100 and nothing else.
Exploitation
Subtracting the base and reading the result as UTF-8 produces the second layer:
$ python3 -c "
notes = bytes((ord(c) - 0x1F3F7) & 0xFF for c in open('dist/flag.txt', encoding='utf-8').read().strip()).decode()
print(notes)"
♮♬♯𝄫♯𝄡♯𝄐♯𝄐♭♫♯𝄡𝄞♭𝄞𝄫♬♭♯𝄑♬♩♯𝄒♬𝄡♮𝄓♬♪♬♩♬♩♮𝄓♮𝄞♬♭𝄞𝄡♬♮♮𝄓♬𝄞♬♩♮𝄓♭𝄐♬♪♬♬♮𝄓♮𝄡♬♩𝄞♮♮𝄓♬♭♯♬𝄞♭𝄞♮♬♭♯𝄐♯𝄐𝄞𝄡♮𝄓♭♯♬♩𝄞♮♯𝄒♯♭♮𝄓♬𝄞♯𝄢♬♬♮𝄓♬𝄞𝄞♫𝄞♮♬𝄞♯𝄢𝄞𝄑Counting what is actually in there settles the question of what kind of cipher this is:
$ python3 -c "
notes = bytes((ord(c) - 0x1F3F7) & 0xFF for c in open('dist/flag.txt', encoding='utf-8').read().strip()).decode()
print(len(notes), 'symbols,', len(set(notes)), 'distinct')
for s in sorted(set(notes), key=ord): print(f' {s} U+{ord(s):04X} x{notes.count(s)}')"
120 symbols, 15 distinct
♩ U+2669 x6
♪ U+266A x2
♫ U+266B x2
♬ U+266C x24
♭ U+266D x10
♮ U+266E x17
♯ U+266F x15
𝄐 U+1D110 x5
𝄑 U+1D111 x2
𝄒 U+1D112 x2
𝄓 U+1D113 x9
𝄞 U+1D11E x16
𝄡 U+1D121 x6
𝄢 U+1D122 x2
𝄫 U+1D12B x2Fifteen distinct symbols across 120 positions. A flag of a plausible length is around 60 characters, and 120 is exactly twice that,so each symbol is half a byte. Fifteen rather than sixteen just means one nibble value never occurs in this particular plaintext.
The prefix is free plaintext. SkillBit{ is 536b696c6c4269747b in hex, so the first eighteen symbols spell out eighteen nibbles whose values are already known:
$ python3 -c "
notes = bytes((ord(c) - 0x1F3F7) & 0xFF for c in open('dist/flag.txt', encoding='utf-8').read().strip()).decode()
m = {}
for sym, nib in zip(notes, 'SkillBit{'.encode().hex()): m.setdefault(sym, nib)
for sym, nib in sorted(m.items(), key=lambda kv: kv[1]): print(f' {sym} = {nib}')
out = ''
for i in range(0, len(notes), 2):
hi, lo = m.get(notes[i]), m.get(notes[i+1])
out += chr(int(hi+lo, 16)) if hi and lo else '?'
print(out)"
♫ = 2
♬ = 3
♭ = 4
♮ = 5
♯ = 6
𝄞 = 7
𝄡 = 9
𝄫 = b
𝄐 = c
SkillBit{4???9?????W4y5?7??L?3?Y?u?4ctu4lly?F?u?d?7?3?7ru7??Nine symbols for one guess, and most of the flag is already readable. Filling the rest by hand from the leetspeak would work, though the codepoint column from earlier makes it faster. The first seven symbols are U+2669 through U+266F, seven consecutive codepoints, and the crib assigned them 2, 3, 4, 5 and 6 in that order. An author who builds an alphabet by walking a Unicode block leaves consecutive codepoints holding consecutive values, so the same run gives up 0 and 1. The U+1D110 run has 𝄐 = c sitting at its head, and the pair at U+1D121 has 𝄡 = 9, so walking both the same way fills the rest:
$ python3 -c "
notes = bytes((ord(c) - 0x1F3F7) & 0xFF for c in open('dist/flag.txt', encoding='utf-8').read().strip()).decode()
m = {}
for sym, nib in zip(notes, 'SkillBit{'.encode().hex()): m.setdefault(sym, nib)
alpha = sorted(set(notes), key=ord)
for _ in range(len(alpha)):
for a, b in zip(alpha, alpha[1:]):
if ord(b) - ord(a) != 1: continue
if a in m and b not in m: m[b] = f'{int(m[a],16)+1:x}'
elif b in m and a not in m: m[a] = f'{int(m[b],16)-1:x}'
print('mapped', len(m), 'of', len(alpha))
out = ''
for i in range(0, len(notes), 2):
hi, lo = m.get(notes[i]), m.get(notes[i+1])
out += chr(int(hi+lo, 16)) if hi and lo else '?'
print(out)
print('left over:', [s for s in alpha if s not in m])"
mapped 15 of 15
SkillBit{4m0n9_100_W4y5_70_L13_Y0u_4ctu4lly_F0und_7j3_7ru7j}
left over: []Nothing is left over and the result is flag shaped, but it is not the right text. 7j3 and 7ru7j want to be 7h3 and 7ru7h, so one symbol came out wrong. The runs are not equally trustworthy. U+2669 to U+266F holds five crib symbols that step by one all the way across, which proves the block was walked in order before anything is read off it. The U+1D110 run and the U+1D121 pair hold one crib symbol each, so both are extrapolation from a single point. U+1D110 happens to be in order. U+1D121 is not: the author placed 𝄢 at U+1D122 ahead of 𝄡 at U+1D121 in nibble order, so the step that reads 𝄢 = a should read 𝄢 = 8. The plaintext is the only thing that catches it, because j is a legal flag character and nothing about the decode looks broken.
The sixteenth symbol, 𝄪 at U+1D12A, never shows up. Nibble a does not occur anywhere in this plaintext, which is why the alphabet came back fifteen wide.
Getting the Flag
With all fifteen symbols placed, the alphabet runs through the nibbles in codepoint order apart from that one swapped pair, with a skipped, so the decode collapses to one command:
$ python3 -c "notes = bytes((ord(c) - 0x1F3F7) & 0xFF for c in open('dist/flag.txt', encoding='utf-8').read().strip()).decode()m = dict(zip('♩♪♫♬♭♮♯𝄞𝄢𝄡𝄫𝄐𝄑𝄒𝄓', '0123456789bcdef'))print(bytes.fromhex(''.join(m[s] for s in notes)).decode())"SkillBit{4m0n9_100_W4y5_70_L13_Y0u_4ctu4lly_F0und_7h3_7ru7h} runs the same chain end to end and derives the mapping from the artifact, so it never needs the author's codec. It also refuses to walk a run that holds a single crib symbol, which leaves 𝄑, 𝄒, 𝄓 and 𝄢 to a short brute force: the flag charset cuts that to eighteen candidates and the English bigrams pick the one that reads. The codec itself lives at
writeup/solve.pychal/music_layer.py if you want to check the recovered alphabet against the original.
Solve Script
#!/usr/bin/env python3
"""Solver for Ways To Lie.
This is a static challenge with no service behind it, so the house -u/--url,
-k, -x and -s solver flags do not apply. The handout is the only input, so the
CLI takes a path instead and defaults to dist/flag.txt relative to the
challenge root.
Run from the challenge root:
~/pyenv/bin/python writeup/solve.py
Nothing here imports chal/music_layer.py. Recovering the note alphabet from the
artifact is the challenge, so the solver rebuilds it from a known-plaintext
crib, the codepoint layout of the alphabet, and frequency analysis.
"""
import argparse
import itertools
import re
import sys
# base100 lays one emoji codepoint over every input byte, starting at U+1F3F7.
BASE100_OFFSET = 0x1F3F7
# Every byte of the plaintext is a flag character, which prunes the search hard.
FLAG_CHARSET = set("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789_{}")
# Known plaintext. Every SkillBit flag opens with this, and nine ASCII bytes
# spell out eighteen nibbles of the stream.
CRIB = "SkillBit{"
FLAG_RE = re.compile(r"SkillBit\{.*?\}")
# Leetspeak substitutions, so the recovered body can be scored as English.
LEET = str.maketrans("4013579", "aoiesgt")
# The forty most common English bigrams, most frequent first. Used to pick the
# readable plaintext out of the handful the charset filter leaves behind.
COMMON_BIGRAMS = (
"th he in er an re on at en nd ti es or te of ed is it al ar "
"st to nt ng se ha as ou io le ve co me de hi ri ro ic ne ea"
)
# Most common bigram gets the highest weight, least common gets 1.
BIGRAM_WEIGHT = {b: i for i, b in enumerate(reversed(COMMON_BIGRAMS.split()), 1)}
def load_artifact(path):
"""Read the handout as text. base100 output is UTF-8 emoji, not raw bytes."""
with open(path, encoding="utf-8") as fh:
return fh.read().strip()
def base100_decode(text):
"""Undo the outer layer: every emoji is one byte at a fixed offset.
The result is still text, because the inner layer is a string of musical
symbols rather than binary.
"""
data = bytes((ord(ch) - BASE100_OFFSET) & 0xFF for ch in text)
return data.decode("utf-8")
def distinct_symbols(symbols):
"""Symbols in order of first appearance.
A long ciphertext over an alphabet this small cannot be a character-level
cipher. Two symbols per plaintext byte is the giveaway that each symbol
carries one hex nibble.
"""
seen = []
for symbol in symbols:
if symbol not in seen:
seen.append(symbol)
return seen
def crib_mapping(symbols):
"""Map symbols to nibbles using the known SkillBit{ prefix.
The first len(CRIB) * 2 symbols are the hex of the crib, so reading them
off in order hands over more than half the alphabet for free.
"""
mapping = {}
for symbol, nibble in zip(symbols, CRIB.encode().hex()):
if mapping.setdefault(symbol, nibble) != nibble:
raise ValueError(f"crib conflict on {symbol!r}")
return mapping
def codepoint_runs(alphabet):
"""Split the alphabet into maximal runs of consecutive codepoints."""
runs = []
for symbol in sorted(alphabet, key=ord):
if runs and ord(symbol) - ord(runs[-1][-1]) == 1:
runs[-1].append(symbol)
else:
runs.append([symbol])
return runs
def extend_along_codepoint_runs(alphabet, pinned):
"""Fill in symbols that share a run of consecutive codepoints with the crib.
The author picked the alphabet by walking blocks of musical characters, so
a run of consecutive codepoints usually carries consecutive nibbles.
Usually is the catch, because one pair in this alphabet is out of order. A
run holding two or more crib anchors proves its own step, since the anchors
have to agree before anything is propagated. A run holding a single anchor
is an extrapolation, and a wrong nibble there still decodes to legal flag
characters, so nothing downstream would catch it. Those runs are left to
the brute force instead.
"""
mapping = dict(pinned)
for run in codepoint_runs(alphabet):
anchors = [symbol for symbol in run if symbol in pinned]
if len(anchors) < 2:
continue
steps = itertools.pairwise(anchors)
if any(
ord(high) - ord(low) != int(pinned[high], 16) - int(pinned[low], 16)
for low, high in steps
):
continue
base, base_nibble = anchors[0], int(pinned[anchors[0]], 16)
for symbol in run:
value = base_nibble + ord(symbol) - ord(base)
if 0 <= value < 16:
mapping[symbol] = f"{value:x}"
return mapping
def candidate_flags(symbols, alphabet, mapping):
"""Brute force the leftover symbols and keep the flag-shaped results.
Only a handful of symbols and nibbles survive the steps above, so the
search is a few permutations rather than a real cryptanalysis. Several
assignments decode to legal flag characters, which is why the English
score below gets the last word.
"""
unknown = [s for s in alphabet if s not in mapping]
unused = [f"{n:x}" for n in range(16) if f"{n:x}" not in mapping.values()]
found = []
for guess in itertools.permutations(unused, len(unknown)):
candidate = dict(mapping, **dict(zip(unknown, guess)))
try:
plaintext = bytes.fromhex("".join(candidate[s] for s in symbols)).decode(
"ascii"
)
except (KeyError, ValueError, UnicodeDecodeError):
continue
if set(plaintext) <= FLAG_CHARSET and FLAG_RE.fullmatch(plaintext):
found.append(plaintext)
return found
def english_score(flag):
"""Rank a candidate by how much English its body contains once de-leeted.
The remaining candidates differ in one or two letters, and the wrong ones
break words like "the" and "truth". Weighting by bigram rank separates them.
Dropping everything that is not a letter matters as much as the de-leeting,
because the word separator is itself one of the unknown symbols: a candidate
that turns it into a letter has to carry the bigrams that letter creates,
while a real separator drops out and leaves the words touching.
"""
body = flag[len(CRIB) : -1].lower().translate(LEET)
letters = "".join(ch for ch in body if ch.isalpha())
return sum(
BIGRAM_WEIGHT.get(letters[i : i + 2], 0) for i in range(len(letters) - 1)
)
def main():
parser = argparse.ArgumentParser(description="Solve Ways To Lie from the handout.")
parser.add_argument(
"path",
nargs="?",
default="dist/flag.txt",
help="path to the handout (default: dist/flag.txt)",
)
args = parser.parse_args()
artifact = load_artifact(args.path)
print(f"[*] handout: {len(artifact)} codepoints")
symbols = base100_decode(artifact)
alphabet = distinct_symbols(symbols)
print(f"[*] base100 decode: {len(symbols)} symbols, {len(alphabet)} distinct")
print(f"[*] alphabet: {' '.join(sorted(alphabet, key=ord))}")
mapping = crib_mapping(symbols)
print(f"[*] crib '{CRIB}' pins {len(mapping)} symbols")
mapping = extend_along_codepoint_runs(alphabet, mapping)
print(f"[*] codepoint runs extend that to {len(mapping)} symbols")
candidates = candidate_flags(symbols, alphabet, mapping)
if not candidates:
sys.exit("[!] no assignment produced flag-shaped plaintext")
print(f"[*] {len(candidates)} candidates survive the flag charset")
flag = max(candidates, key=english_score)
print(f"[+] {flag}")
if __name__ == "__main__":
main()