Herbarium

A Goppa code over GF(43^2) hid five messages behind burst errors and a 78-million-step time-lock. I recovered the hidden support signs with a linear system, decoded exactly at the interleaved bound, then ground the delay with chunked modular exponentiation.

The challenge

The handout was a tarball with two files: the reference implementation and one instance. Five message rows had been encoded with a scrambled Goppa generator, damaged in the same 105 columns, and the flag was sealed with a key derived from the original messages plus a sequential squaring delay. Getting the messages back was the whole game.

Recon

I extracted the tarball into work/ so the originals stay untouched:

tar xzf herbarium-dist.tar.gz -C work
ls work

challenge.py
instance.json

The challenge description read:

The conservators stored every specimen together with its mirror image, then kept one flower from each pair. They insist the choice of side cannot matter.

Five archive rows were damaged in exactly the same 105 columns. Each damaged symbol is otherwise independent. The archive key was derived from the original five message rows.

challenge.py implements everything: a QuadraticField with u^2 = 2, Goppa polynomial g(X) = gamma(X)^(q-1), parity expansion from GF(43^2) down to GF(43), nullspace plus scramble_rows for the public generator, and derive_delay_base / evaluate_delay / derive_archive_key / open_flag for the lock.

I wrote payloads/01_recon.py to survey the instance and ran it from the challenge directory:

python3 payloads/01_recon.py

It prints and saves recon/recon.txt:

instance 0e3ed46bebe0ed54ced3f052
dimensions {'ell': 5, 'k': 71, 'n': 320, 'r': 126, 't': 105}
field {'basis': 'u^2=delta', 'delta': 2, 'q': 43}
goppa {'description': 'g(X)=gamma(X)^(q-1)', 'exponent': 42, 'gamma': [3, 0, 0, 1]}
delay 78266000 squarings, 4096-bit modulus
generator rank 71 (expected 71)
pairs 320, b min 1 max 21
num b>21 0
num b<=21 320
G*real^T zero? True nonzero 0
G*imag^T (all-plus) zero? False nonzero 8714

What I took from that: n = 320, k = 71, ell = 5 rows, t = 105 shared error columns, extension redundancy r = 126. Gamma is X^3 + 3, so deg g = 3 * 42 = 126, matching r. The generator is full rank. Every support pair [a, b] has b in 1..21, i.e. the canonical half — each pair stands for {a + b*u, a - b*u} with the sign withheld. And the last two lines already hint at the sign attack: the real parity rows are orthogonal to the generator for arbitrary signs, the imaginary rows are not.

I also confirmed the obvious bound arithmetic: single-row unique decoding handles about r/2 = 63 errors, far below 105. But interleaved decoding with ell = 5 reaches r * ell / (ell+1) = 126 * 5 / 6 = 105. Exactly the stated damage count. That told me the intended solver before I wrote any of it.

The side-choice confusion

The flavour text says the choice of side cannot matter. I first read that as per-pair invariance — any combination of signs gives the same code. I tested it directly by building the expanded parity for all-plus, all-minus, and random signs:

plus pivots len 249
minus pivots len 249
rand pivots len 249

plus==minus? True
plus==rand? False

Same rank, different row spaces. Global conjugation fixes the code; mixed per-pair flips do not. So the sentence means something narrower. The math that replaced it: for one column, the two candidate parity columns are conjugates. Real parts agree, imaginary parts flip sign. That single observation turns sign recovery into linear algebra instead of a 2^320 search.

Recovering the hidden signs

Write the extension parity as H[i,j] = alpha_j^i / g(alpha_j) with g(alpha) = gamma(alpha)^(q-1). Expand each entry a + b*u into a real row carrying a and an imaginary row carrying b. The real matrix does not depend on the sign choices at all. The imaginary matrix for the all-plus choice, call it M, gets multiplied column-wise by the unknown signs: column j of the true imaginary matrix is s_j * M[:,j] with s_j = ±1.

A codeword c over GF(43) satisfies the parity checks in both halves. For the true signs and every generator row G[p] and imag row i:

sum_j G[p][j] * M[i][j] * s_j = 0

That is homogeneous linear in s: 71 * 126 = 8946 equations, 320 unknowns over GF(43). payloads/02_sign_matrix.py builds it:

python3 payloads/02_sign_matrix.py

saved loot/sign_system.npy shape (8946, 320)

(The .npy is a scratch intermediate; it regenerates in seconds and is not kept.)

payloads/02_sign_kernel.sage solves it:

sage payloads/02_sign_kernel.sage

matrix 8946x320 rank 319
null dim 1
saved loot/signs.json head [1, 1, -1, -1, 1, -1, 1, 1, 1, -1]

Rank 319, kernel dimension 1, every entry 1 or 42 (-1 mod 43). That vector is the sign pattern up to a global flip, and the flip does not change the code. I verified the recovered signs make the full expanded parity orthogonal to the generator, for both the vector and its negation.

Syndromes

With signs known the support is concrete: alpha_j = a_j + s_j * b_j * u. The Goppa multiplier is y_j = 1/g(alpha_j), and column j of the extension parity is alpha_j^i * y_j.

payloads/03_syndromes.py builds all of it with the integer field arithmetic from work/challenge.py and saves machine-readable intermediates:

python3 payloads/03_syndromes.py

saved support/ys/syndromes to loot (r=126, n=320, ell=5)

Outputs in loot/: support.json, ys.json, syndromes_comps.json (each extension element as an [a, b] pair). Syndromes are S[i,l] = sum_j H[i,j] * R[l][j] for the five received rows. Since every codeword is in the kernel, each syndrome equals the syndrome of that row's error vector.

The locator at the bound

Let the shared error columns be E, |E| = t = 105, and the locator Lambda(x) = prod_{j in E}(x - alpha_j) = x^t + c_{t-1} x^{t-1} + ... + c_0. For row l, syndrome i is S[i,l] = sum_{j in E} y_j e_{l,j} alpha_j^i. Multiplying Lambda(alpha_j) = 0 through by y_j e_{l,j} alpha_j^{i-t} and summing gives the recurrence, for every row and every i >= t:

S[i,l] + sum_k c_k * S[i-t+k,l] = 0

There are r - t = 21 usable values of i per row and 5 rows: 105 equations for the 105 unknown coefficients. payloads/04_locator.sage sets that system up over GF(43)[x]/(x^2-2) and solves it:

sage payloads/04_locator.sage

A 105x105 rank 105
solved head ['22*u + 37', '17*u + 17', '17*u + 16']

Full rank, unique solution. It saves loot/locator_coeffs.txt.

payloads/05_roots.sage evaluates the locator at every support point:

sage payloads/05_roots.sage

Lambda degree 105
num roots 105 head [1, 3, 5, 7, 11, 12, 13, 18, 21, 22]

105 roots out of 320 candidates:

[1, 3, 5, 7, 11, 12, 13, 18, 21, 22, 23, 24, 30, 31, 32, 36, 37, 38, 41, 43, 44, 48, 50, 54, 57, 59, 65, 66, 67, 74, 77, 86, 87, 88, 91, 96, 101, 102, 105, 109, 113, 116, 117, 120, 123, 124, 126, 129, 131, 132, 134, 135, 137, 140, 141, 143, 146, 150, 152, 156, 162, 163, 166, 170, 172, 173, 178, 181, 182, 188, 191, 194, 199, 209, 212, 215, 222, 225, 233, 236, 238, 244, 245, 247, 248, 258, 261, 265, 267, 268, 269, 275, 284, 286, 287, 288, 295, 296, 297, 300, 301, 303, 308, 309, 313]

A random degree-105 polynomial over an 1849-element field hits roughly 18 of 320 points. Hitting 105 is the signal the locator is right. It saves loot/error_positions.json.

The divide-by-y bug

payloads/06_errors.sage solves for magnitudes with Bt[i,k] = alpha_{E_k}^i * y_{E_k} and Bt * e = s. My first version then divided the solution by y. Every value came back with a nonzero u part:

row 0 pos 1 not in base field: 27*u + 35

I assumed the instance was at fault. It was not. I built a synthetic case — random messages, the same code parameters, the same 105-column burst shape with fresh random base-field errors — and the locator still matched perfectly while the values were wrong in exactly the same way:

match? True
row 0 bad count 104

Positions right, values wrong, same signature. Writing the equation out showed the mistake: Bt already contains y, so the solution e is the base-field error itself. Dividing again was the bug. Checking e directly gave clean base-field values, so the fix was deleting the division and asserting u-coefficient zero plus full r = 126 verification per row:

sage payloads/06_errors.sage

t=105 r=126 ell=5
Bt rank 105
row 0 mismatch? False bad 0 sample [38, 21, 22, 20, 37, 39, 17, 40, 2, 31]
row 1 mismatch? False bad 0 sample [13, 32, 41, 33, 42, 37, 19, 30, 10, 33]
row 2 mismatch? False bad 0 sample [15, 1, 5, 42, 36, 5, 41, 2, 24, 23]
row 3 mismatch? False bad 0 sample [8, 39, 40, 22, 10, 34, 17, 37, 2, 26]
row 4 mismatch? False bad 0 sample [14, 3, 33, 10, 41, 7, 17, 12, 3, 27]

It saves loot/errors_real.json (ell x n over GF(43)). The lesson I kept: build the synthetic test before touching the real instance, not after an hour of staring.

Messages

Error subtraction is plain modular arithmetic, then M * G = C for the message rows. The generator's first 71 columns are independent here, so payloads/07_messages.py solves each row against those pivot columns and re-encodes to check:

python3 payloads/07_messages.py

pivots 71 head [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
saved messages loot/messages.json, re-encode OK

Outputs: loot/codewords.json, loot/pivots.json, loot/messages.json. The re-encode assertion is the gate — it passed, so the five recovered rows are exactly the rows the archive key was derived from.

The delay

The base derives quickly from the messages:

base=0x6101f69b1e9d314d22a51673963ccb0eecb25a417dc29bad5b2d1cc03c...

Then 78,266,000 sequential squarings mod a 4096-bit modulus. A pure-Python loop benchmarked near 125 us per square, about 160 minutes. A gmpy2 loop did 10k squares in 0.175 s. The identity that makes it manageable: v -> v^(2^1M) is exactly 1M squarings, and gmpy2.powmod does those 1M squarings in C. So payloads/08_delay.py works in 78 chunks of 1M plus a 266000 remainder, with a JSON checkpoint per chunk:

python3 payloads/08_delay.py 2>&1 | tee evidence/delay.log

Early progress looked like:

chunk 1/78 done=1000000/78266000 chunk_time=15.6s rate=64297 sq/s ETA=20.0min

About 16 s per chunk, roughly 24 minutes wall clock. The tail of evidence/delay.log:

chunk 78/78 done=78000000/78266000 chunk_time=16.9s rate=59178 sq/s ETA=0.1min total_elapsed=24.0min
doing remainder 266000 via powmod
done delay output 0x907b62db1ed959817e7a5e984b6538f22706ead27fc5b18be3625e35ba6760724aacfff79a428c...
key c43da48069a5b2e8928f6d4956a265b489ee9cbfd5773f7fc7f620cd79eb2eb8
flag b'07CTF{r00t5_wh0_d035n_l0ve_THEM?!}'
saved flag

The script derives the key with derive_archive_key and opens with open_flag, saving loot/flag.txt and loot/delay_output.txt. The checkpoint at loot/delay_ckpt.json means an interrupted run resumes instead of restarting.

Full exploit chain

Every command runs from the challenge directory. Python steps use work/challenge.py; sage steps build GF(43)[x]/(x^2-2) to match its u^2 = 2.

python3 payloads/01_recon.py
python3 payloads/02_sign_matrix.py
sage payloads/02_sign_kernel.sage
python3 payloads/03_syndromes.py
sage payloads/04_locator.sage
sage payloads/05_roots.sage
sage payloads/06_errors.sage
python3 payloads/07_messages.py
python3 payloads/08_delay.py 2>&1 | tee evidence/delay.log

The moving parts, compressed: signs from G * imag(s)^T = 0 (8946x320, kernel dim 1); syndromes S = H * R^T; locator from the 105x105 recurrence at the r*ell/(ell+1) bound; positions as locator roots (105 of 320); magnitudes from Bt * e = s with no extra division, verified over all 126 rows; messages from pivot columns with re-encode check; delay by chunked powmod with checkpoints; key and flag by the reference derive_archive_key / open_flag.

No browser work applied here, so there are no screenshots. This was a pure coding and number-crunching task.

Flag

07CTF{r00t5_wh0_d035n_l0ve_THEM?!}

What I would do differently

I would build the synthetic test first. The locator logic was right on the first try; the magnitude bug cost the most time and a known-answer test caught it in one run. I would also stop over-reading flavour text: the parity check said global invariance holds and per-pair does not within minutes, and the sign system fell straight out of that. The prose pointed at the property; only the matrix said which one.