Hic Sunt Dracones

Full solution below. Spoilers ahead.

Task description

You have been warned…

The original text also carried a dragon emoji.

What the handout does

The handout has Dockerfile, patch.py, chall.py and output.txt. There is no remote service, and the goal is to recover the flag from output.txt. The Dockerfile clones awnonbhowmik/Dragon-Crypto at commit 046ad8d and patch.py makes two changes to its Koblitz code: the modular square root becomes pow(n, (p+1)//4, p) (which needs p % 4 == 3, enforced in chall.py), and the prime p becomes a parameter instead of the hard-coded 751.

chall.py works in two steps:

1. Koblitz encoding. Each flag character m becomes a point (x_m, y_m) with x_m = 20*m + j, where j is in [1, 19] and is the smallest value for which x^3 + a*x + b is a quadratic residue mod p. The curve parameters a, b and the 256-bit prime p are random and secret.
2. Dragon “encryption”. The private key is (size, iterations, angle, a, b), with size a random 128-bit integer, iterations in [10, 14] and angle either 0 or 180. For each point, dragon_render moves a turtle to the point, turns it by angle, walks the dragon-curve turn sequence with step length size, and returns the end position.

The output is the end points written as X x1 X x2 X ... X Y y1 Y y2 Y ... Y, 78 of them.

The walk is a translation

A fixed sequence of forward moves and 90 degree turns always produces the same displacement, scaled by size and rotated by the turtle’s starting heading:

C_i = P_i + size * R(h_i) * v_iter

The secret curve parameters never touch this. The key effectively shrinks to the single integer size plus a tiny displacement vector.

The heading is never reset

chall.py swaps the real turtle for a HeadlessTurtle. goto() resets the position for each character, but the heading is not reset. dragon_render turns the turtle on every call and the walk leaves a net rotation behind, so the heading drifts from character to character and the displacement rotates in a fixed 4-cycle.

This shows up directly in the x column of output.txt. The first six values are:

1401,  +355856102978...857255985,  2282,  -355856102978...857251439,  1461,  +355856102978...857255122

The even-index points (0, 2, 4, …) all have small x, at most 2463 in absolute value, because their displacement is purely vertical, so their x is x_m exactly. The odd-index points carry a huge x of a constant magnitude whose sign alternates +, -, +, -. So the x displacement over the points is 0, +D, 0, -D repeating, with D the same for every odd point. That is the iterations = 14 pattern, whose unit 4-cycle (at size = 1) is (0, 128), (128, 0), (0, -128), (-128, 0) in x, giving D = 128 * size.

iter=10 angle=0   [(0, 32), (-32, 0), (0, -32), (32, 0)]
iter=14 angle=0   [(0, -128), (128, 0), (0, 128), (-128, 0)]
iter=14 angle=180 [(0, 128), (128, 0), (0, -128), (-128, 0)]

The even points already give characters with no key at all, since (x - 1) // 20 is the character code: 1401 gives F, 2282 gives r, 1461 gives I. Reading every even point this way spells out F.r.I.{.f.D.n.K.u.h.H.s.1._.n..., the even-indexed letters of the flag.

Recovering size from the known prefix

The odd points need size. The flag starts with FortID{, and its second character o is an odd point with x = x_o + D. Since x_o = 20*ord('o') + j with j in [1, 19], x_o is known to within 18, and D moves by 128 per unit of size, so only a handful of size values fit. Keeping every decoded x positive narrows it to a 15-integer window, and requiring (x - 1) mod 20 != 19 on all 78 points (the Koblitz invariant, since j never reaches 20) leaves 12 candidates:

x>0 alone bounds size to a 15-integer window
candidates passing x>0 and (x-1)%20 != 19 : 12
candidates whose plaintext starts with FortID{ : 1

The Koblitz constraint alone does not pin a single value; it is the FortID{ prefix that selects one of the 12. The recovered scalar is:

size = 278012580452280145225903631781209822295     # 128-bit, in [2^127, 2^128)
D    = 128 * size = 35585610297891858588915664867994857253760

A trimmed version of the solver reads output.txt, applies the 0, +D, 0, -D shift to the x column, and scans size:

DX = [0, 128, 0, -128]                      # iter=14, angle=0 (x components)
dx = [DX[i % 4] for i in range(N)]
# bound size from the first known char with a nonzero x shift, then test the window
for s in range(lo, hi + 1):
    xs = [X[k] - s * dx[k] for k in range(N)]
    if all(x > 0 and (x - 1) % 20 != 19 for x in xs):
        msg = "".join(chr((x - 1) // 20) for x in xs)
        if msg.startswith("FortID{"):
            print(s, msg)

angle only flips the vertical component, so it does not change the x-only decode. Decoding every point gives a 78 character string that starts FortID{1f_D0n_Knu7h... (length 78, sha256 df7e3d44612c), which matches the flag in the frontmatter.

The y coordinates confirm the displacement

The decode above uses only x, so the iterations = 14 displacement could in principle be a lucky fit. The y column settles it. Subtracting size * (−128, 0, 128, 0) (the y 4-cycle for angle = 0) from every point maps every repeated character to one and the same (x_m, y_m): the 15 underscores all collapse to (1901, 59867...826385), with zero disagreements across all 34 distinct characters, and every recovered y_m is a positive integer of at most 256 bits. That is exactly what a deterministic Koblitz encoding under one 256-bit curve produces. The angle = 180 sign pattern fails this check (it drives some y_m negative), so the data also pins angle = 0. None of this needed the cloned library; output.txt alone is enough.

Takeaways

The dragon walk is P -> P + k*v, an affine map with one unknown scalar. The secret curve parameters affect only y, and the Koblitz encoding leaves the character visible in x = 20*m + j, so the secret parts of the key protect nothing once the structure is known. The stateful turtle was the only extra obstacle: its drifting heading gave half the characters a zero x shift and the other half a clean +D / -D, and a known prefix settled the one real unknown. Encoding a message onto a curve is not encryption, and neither is moving the point along a geometric path; a real setting wants a vetted primitive such as AES-GCM or ECIES.