Cairn

The brief

One step at a time. Do not look back.

• RULES.md, 3.7 KB
• challenge.json, 7.5 KB

In short

Cairn hides an AES key at the end of a walk of 1,048,576 steps through the supersingular isogeny graph over a 256 bit field. Each step depends on the last, so speed is the only way through. The lab built a fast, self checking root finder and finished the walk in 1,418 seconds.

A walk with its rules written out

Cairn ships its own rules. Start at j = 1728 on the supersingular isogeny graph over a 256 bit field, take 1,048,576 steps, and hash the final point into an AES key.

Every step hashes the one before

Each step hashes the current point and its number. One byte picks a degree, 2, 3, 5 or 7, another picks a root of a modular polynomial. The next step needs that root, so the walk cannot be split or skipped.

One power sorts the roots 32 ways

Every step means finding all roots of a polynomial of degree up to 8 over a 256 bit field. Since p squared minus 1 is 32 times an odd number, one exponentiation sorts the roots into 32 classes at once, not the usual two.

Checked against a slow twin

Before the long run, the lab built a slow, independent reference. The first 60 states matched it byte for byte, and every step checks itself: as many roots as the degree, each a true zero, none repeated.

1,048,576 steps in 1,418 seconds

The full walk ran at 1.35 milliseconds a step. Degrees 2, 3, 5 and 7 each came up about 262,000 times, exactly what an even hash gives.

The tag verifies

The last point, hashed with the word IsogenyLabyrinth, is the AES-256-GCM key. The tag verifies, which proves every one of the million steps was right, and the plaintext is the flag.

The insight

The hash chain leaves no mathematical shortcut, only speed. A root finder that splits 32 ways in one power turned a million steps into 24 minutes.

The flag

hiCTF{w41k_th3_sup3rs1n9u14r_l46yr1ntH}