Rank Metric Analysis: Decoding Gabidulin Codes

Challenge Description

The challenge implements a cryptosystem based on rank-metric codes. We are provided with a warp matrix and a bolt vector, which represent a message encoded using a Gabidulin code with added noise.

every piece of the cipher lies open on the table. compose them correctly and the flag is yours.

Initial Analysis

The script operates over the finite field $GF(2^{43})$. The core of the cryptosystem is the generation of the bolt vector: $$bolt = secret \times warp + frays$$

Where the warp matrix is defined as: $$warp = knot \times loom \times shuttle^{-1}$$

By substituting warp into the equation and multiplying by shuttle on the right, we can transform the problem into a standard decoding task: $$bolt \times shuttle = (secret \times knot) \times loom + (frays \times shuttle)$$

Let:

• $y = bolt \times shuttle$ (Received codeword)
• $s’ = secret \times knot$ (Encoded message)
• $e = frays \times shuttle$ (Rank error)

Step 1 — Error Rank Analysis

The vulnerability lies in the construction of the error $e$. In rank-metric codes, we care about the dimension of the space spanned by the vector’s components over the base field $F_2$.

• frays is a vector whose components are $F_2$-linear combinations of 5 random elements.
• shuttle entries are $F_2$-linear combinations of 3 fibers.

This construction ensures the rank weight of $e$ over $F_2$ is at most $15$ ($5 \times 3$). Since the code parameters are $N=40$ and $K=8$, the maximum correctable error rank is $\lfloor (N-K)/2 \rfloor = 16$. Our error rank of 15 is perfectly within the decoding radius.

Step 2 — Welch-Berlekamp Decoding

To recover $s’$, we solve the Welch-Berlekamp linearized system. We search for a linearized locator polynomial $\Lambda(x) = \sum \lambda_i x^{2^i}$ of degree $2^{15}$ and an evaluator polynomial $N(x) = \sum n_i x^{2^i}$ of degree $2^{22}$ such that: $$\Lambda(y_i) = N(pegs_i)$$

This gives us 40 linear equations over $GF(2^{43})$. Solving this system allows us to find the coefficients of $s’$, recover the secret, and decrypt the AES-GCM vault.

Step 3 — Solution Script

Below is the complete SageMath script to solve the challenge:

#!/usr/bin/env sage
import json
from hashlib import sha256
from Crypto.Cipher import AES

# 1. Setup Field
MODPOLY = x**43 + x**21 + x**3 + x + 1
Fqm.<a> = GF(2**43, modulus=MODPOLY)

# Insert your output.json content here
json_data = """
{"spec": {"q": 2, "m": 43, "n": 40, "k": 8, "frays": 5, "modulus": [1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]}, "warp": [[4820033983943, 3886433294703, 6344648985341, 5029663425957, 4278872949636, 1886501098329, 6517333673856, 744985653293, 4685225925969, 7527265655773, 5797149818984, 2249910547654, 7130359247040, 6763716050692, 5622946406663, 934704329918, 2825136281240, 6387429694088, 3084833813201, 8597944873139, 7661104867289, 8129635528105, 1609945886570, 2037199388020, 5285108466268, 5588115518122, 756986324643, 5403933923854, 7054329407064, 7824021981841, 8782913635329, 1803903809912, 6264223609721, 8125344969457, 2231183922582, 3718570214274, 4345627095093, 3006719699077, 6090699607113, 6263179468824], [7647432443808, 942727080218, 6905154357359, 2612755691740, 131798514174, 8139332720728, 101843790029, 6419290969786, 1504540422389, 3328484492477, 2044864494460, 1755999693410, 7937952467688, 7937263595709, 4663206174803, 3540622918704, 6704618604781, 7057495468978, 4101063051350, 8380872769701, 2581217769400, 2538807570018, 8194106363856, 1181821309212, 3517586665665, 7243345359133, 7898605761877, 6807129910923, 6161164435355, 5358291218859, 7737616469690, 8324937371734, 8492378085556, 5192762235436, 383723605921, 7650762438902, 3541690705642, 8314983753435, 5389235295939, 5724594679346], [7887649295180, 8003753405741, 585204743873, 3632065853366, 2491206383601, 7149740818664, 4529572182257, 6671126714792, 7711776729514, 7920978009321, 4666475297791, 8006236599975, 1970367661726, 6786252141954, 3457661409427, 3748741016284, 5710086240363, 5090631418460, 6861894988600, 2549555980537, 1551405225091, 8031964973191, 2409034389319, 7818561082572, 380221251801, 448065783567, 8401373125718, 3573289802001, 7949429789406, 230779670992, 4656121986400, 8531947493824, 8523391585934, 7463818358452, 6211414984928, 1029625371988, 2173949294984, 7147488886740, 888512345067, 8649367652348], [3222904540009, 5527024080168, 3739038158830, 2918862861187, 8135523205301, 2810831109210, 5462248129028, 6239141783139, 1631846712152, 1173609529745, 7142408373644, 54117216081, 8490756236787, 6041611318980, 6304553761968, 4546139661733, 5783746664950, 2072210943852, 5688311135412, 7253310451550, 872562634032, 2490472757217, 2375872484012, 8526033968504, 3397202260666, 3985694272590, 1280869487138, 1824306261499, 3834143667550, 7958084174596, 1524498788955, 234486032030, 1530617992792, 275355625000, 7472478566145, 490329218179, 3266494965252, 5059988761850, 7374008354310, 4033114534448], [8219133966790, 1128030076717, 2482568412062, 5309031373860, 7097925474836, 8055037594053, 7905647287777, 2463423660115, 5588278445571, 8789559826009, 7822347974561, 1743342193889, 3291625431928, 7278451441510, 1636531339130, 7958403729656, 2235068696625, 6223033446095, 1101508675532, 4527935679723, 255250552843, 8163736013764, 4372109807937, 6034718772485, 2662241540423, 2340930838068, 740285758000, 1551839447605, 4290951470993, 5052644564517, 2182085828002, 3922136259176, 8794531337691, 5937676341070, 2878893983407, 8359757677855, 6536128217808, 2472175560479, 170519482703, 6782929267355], [5905339265123, 1264637242577, 7552071076782, 1637871088045, 7539942646471, 4582365662428, 7886584020227, 2952430091871, 1852391815802, 4990621816340, 1227611078195, 3003726778839, 2198620785572, 3005394473090, 1623488780096, 4952348200668, 3384244682974, 71106966914, 6991204265329, 8768876729062, 7366823276432, 1590377481968, 5718296784100, 3130464209010, 1202131966608, 2736429573127, 6123079624821, 2465283094385, 2804759716168, 4700674706858, 2519577605092, 2994254047961, 3130195938628, 6685774819562, 1199563270417, 3860234977512, 6800422318521, 3596082427200, 1275823501104, 1596241150164], [324974138794, 1764269650482, 4501496620575, 2352072528404, 10263649018, 3573344128694, 2520795309155, 8041746036269, 2567373143334, 1512726376957, 4761858974364, 7907029992970, 518214377589, 5906692918855, 1953841535713, 1654336910606, 5175567350310, 8493222505502, 2668042776741, 4520470733735, 938700144710, 3880865238911, 8309433649705, 7794851881269, 2804466029964, 6783631418734, 1324587564381, 3372100721326, 942411416362, 4166470890615, 6522692479031, 3972204753664, 2008288125129, 3106612623852, 939612035182, 4826853542801, 1365397420986, 4976869938452, 2569476547676, 2674389724675], [3596716035820, 7006129877678, 6430421891525, 6961391306599, 4458396212120, 3054104714708, 7093608313979, 3912669340308, 5197756429276, 3003064630968, 8643943351731, 5308385958335, 1668284944098, 5444380371180, 1050375593917, 2110608001309, 5300789985665, 5247108463714, 3376658084018, 3561249924918, 7967549350222, 6695369987159, 3673851490861, 8770155626253, 5326300351858, 1731359604061, 6189841423049, 1004829090041, 3434465038045, 2382392544199, 5141718259687, 4275146819540, 7729758827953, 2049893619279, 3727264903283, 1422544367675, 7621742399833, 667714945111, 624015880901, 1883656053175]], "bolt": [3624227407303, 4076167997695, 7480514299563, 100033909671, 7228383907896, 779131029518, 7973795938606, 1317848457334, 2071590418399, 2560748735750, 1064179444971, 4034788895157, 1351286000997, 7612119578188, 4220222689948, 1719873483774, 4667843717057, 1208496490888, 3905642704652, 2381116451732, 287300313057, 230774446962, 7500413731414, 2674290858803, 5242421167493, 8434226445495, 4924164326716, 7001309349573, 8280243156923, 943727967175, 5400838397479, 5477894612500, 8465823179906, 4458465551102, 7539691873305, 8751524040480, 8477854685216, 6588879892878, 1386244970068, 8291255373157], "loom": {"pegs": [6505045119309, 7001686519486, 8528597091489, 2525985830163, 385359326443, 7481030866777, 3839339589276, 2709499061832, 1294546481121, 1917948264068, 382825251389, 5105110300510, 2748692978677, 2817194753499, 2906596192653, 6760332047453, 8214796241837, 964782457593, 2604552414220, 2944087245440, 1140553545660, 1962559469984, 7406678599133, 3544503835297, 7583529012815, 3332057137358, 8177403280504, 766647210851, 5335850521347, 4982566676774, 5104657220149, 4634298452103, 133148591996, 5118492356446, 4767018317850, 2282560260776, 1496394386628, 3338101440599, 6542898670668, 3418705936068], "knot": [[5395287977024, 2940684484418, 5471194022213, 2898138286855, 2629621563660, 1169014426994, 1100901508611, 1279322357121], [7618276070096, 572612859019, 4736945551313, 6260724109373, 5876790942896, 8554604395329, 3921496119592, 193578844799], [988799377074, 541460271645, 4626464187164, 457172367248, 5944428406930, 650626556396, 3164413173463, 5849631356634], [1376561814634, 8237728503306, 567573098301, 4511357200133, 8004864604982, 780814188256, 230567275194, 4303884314594], [8109062924848, 1448116806479, 6105692210731, 2262287626247, 4492598034529, 2173638795282, 3468568298718, 4838634505371], [6244441201686, 134757251097, 1290560477518, 7360377973994, 3452062792539, 3280062355091, 5635513323251, 8122738537952], [1191148021159, 3782751829532, 3147080482955, 4478238110771, 4853760973756, 367098802151, 8197066967011, 1745456602445], [8099693524418, 2661903136153, 8116212957925, 6854946468509, 297962018675, 4279678295350, 1294546862963, 7895969466565]], "shuttle": [[1092637349182, 6425760483776, 5662837382398, 6425760483776, 6361596456302, 73846596782, 6425760483776, 1092637349182, 6361596456302, 6361596456302, 5662837382398, 1027971182992, 5735038629968, 6425760483776, 5735038629968, 5662837382398, 6425760483776, 5735038629968, 0, 5735038629968, 5662837382398, 5662837382398, 6361596456302, 1027971182992, 6361596456302, 1027971182992, 1092637349182, 1027971182992, 73846596782, 5735038629968, 5662837382398, 5662837382398, 6425760483776, 5662837382398, 1027971182992, 0, 1092637349182, 1027971182992, 6425760483776, 6425760483776], [1092637349182, 5735038629968, 1027971182992, 1027971182992, 73846596782, 73846596782, 0, 6425760483776, 5735038629968, 1092637349182, 0, 73846596782, 1092637349182, 1027971182992, 1092637349182, 5662837382398, 6425760483776, 73846596782, 6361596456302, 6425760483776, 6361596456302, 0, 5735038629968, 0, 1027971182992, 0, 5735038629968, 5662837382398, 1027971182992, 6425760483776, 5735038629968, 6361596456302, 1027971182992, 6361596456302, 1027971182992, 5662837382398, 5662837382398, 5662837382398, 0, 1027971182992], [5662837382398, 1092637349182, 6361596456302, 5735038629968, 5735038629968, 1092637349182, 0, 5662837382398, 1027971182992, 0, 73846596782, 1092637349182, 6361596456302, 1092637349182, 0, 73846596782, 5662837382398, 6425760483776, 5735038629968, 0, 5735038629968, 0, 0, 6361596456302, 6361596456302, 0, 0, 1027971182992, 0, 6425760483776, 1027971182992, 5735038629968, 73846596782, 1027971182992, 0, 6425760483776, 1027971182992, 1092637349182, 6425760483776, 5662837382398], [0, 6425760483776, 1027971182992, 5735038629968, 5735038629968, 5735038629968, 6361596456302, 5735038629968, 6425760483776, 0, 1092637349182, 1027971182992, 1027971182992, 6361596456302, 1092637349182, 5662837382398, 6361596456302, 5662837382398, 73846596782, 6361596456302, 1027971182992, 73846596782, 73846596782, 5735038629968, 1027971182992, 73846596782, 1092637349182, 5662837382398, 6361596456302, 6425760483776, 6361596456302, 6361596456302, 0, 0, 5735038629968, 73846596782, 0, 1027971182992, 1027971182992, 73846596782], [6361596456302, 73846596782, 5662837382398, 5662837382398, 1027971182992, 5662837382398, 73846596782, 0, 6361596456302, 1092637349182, 6425760483776, 5662837382398, 1092637349182, 1027971182992, 1027971182992, 0, 1027971182992, 1092637349182, 73846596782, 1027971182992, 6425760483776, 1092637349182, 6425760483776, 5735038629968, 1092637349182, 6425760483776, 0, 5662837382398, 1027971182992, 0, 6361596456302, 1092637349182, 1092637349182, 6361596456302, 5662837382398, 6361596456302, 1027971182992, 1027971182992, 5735038629968, 1092637349182], [6361596456302, 73846596782, 1027971182992, 5662837382398, 5735038629968, 0, 6425760483776, 0, 6425760483776, 5662837382398, 73846596782, 6425760483776, 0, 5735038629968, 1027971182992, 6361596456302, 6425760483776, 5735038629968, 73846596782, 1092637349182, 6361596456302, 6361596456302, 1027971182992, 6425760483776, 5662837382398, 1027971182992, 5662837382398, 0, 1027971182992, 6425760483776, 5735038629968, 6425760483776, 6361596456302, 6361596456302, 73846596782, 5735038629968, 0, 1027971182992, 6361596456302, 1092637349182], [5662837382398, 5662837382398, 6361596456302, 1092637349182, 6425760483776, 5735038629968, 0, 5662837382398, 6425760483776, 6361596456302, 1027971182992, 0, 5662837382398, 0, 6425760483776, 5662837382398, 73846596782, 0, 5735038629968, 0, 1027971182992, 5735038629968, 6361596456302, 0, 6425760483776, 5735038629968, 1092637349182, 0, 0, 5662837382398, 6361596456302, 5662837382398, 5735038629968, 1092637349182, 6425760483776, 0, 0, 0, 6361596456302, 1092637349182], [73846596782, 1092637349182, 6361596456302, 1027971182992, 73846596782, 0, 1027971182992, 73846596782, 5735038629968, 0, 5735038629968, 5735038629968, 1027971182992, 5735038629968, 5662837382398, 5662837382398, 0, 5735038629968, 6361596456302, 1092637349182, 6425760483776, 73846596782, 6361596456302, 6425760483776, 1027971182992, 73846596782, 73846596782, 0, 6425760483776, 0, 1027971182992, 6425760483776, 1027971182992, 5735038629968, 1027971182992, 0, 6361596456302, 1027971182992, 0, 5735038629968], [73846596782, 1027971182992, 0, 6361596456302, 5735038629968, 5662837382398, 5735038629968, 73846596782, 6361596456302, 73846596782, 73846596782, 1027971182992, 1027971182992, 6425760483776, 73846596782, 73846596782, 0, 0, 1027971182992, 6425760483776, 0, 6425760483776, 73846596782, 6361596456302, 5662837382398, 1092637349182, 5662837382398, 6425760483776, 6425760483776, 0, 1092637349182, 1027971182992, 1092637349182, 0, 5662837382398, 5662837382398, 0, 1092637349182, 73846596782, 1092637349182], [5662837382398, 6425760483776, 6425760483776, 0, 1027971182992, 1027971182992, 5662837382398, 0, 73846596782, 5662837382398, 6361596456302, 1027971182992, 5735038629968, 1027971182992, 5735038629968, 1092637349182, 1092637349182, 5662837382398, 73846596782, 6425760483776, 0, 5735038629968, 6425760483776, 1092637349182, 6425760483776, 5735038629968, 5735038629968, 0, 6361596456302, 5735038629968, 1092637349182, 5662837382398, 6425760483776, 5735038629968, 6361596456302, 0, 5735038629968, 1092637349182, 73846596782, 6425760483776], [6425760483776, 5662837382398, 1027971182992, 6361596456302, 0, 6425760483776, 0, 1092637349182, 6361596456302, 6361596456302, 5662837382398, 1027971182992, 6361596456302, 5735038629968, 1092637349182, 6361596456302, 5662837382398, 73846596782, 6425760483776, 73846596782, 5662837382398, 5735038629968, 73846596782, 5662837382398, 6425760483776, 6361596456302, 1027971182992, 5735038629968, 0, 0, 6425760483776, 73846596782, 6361596456302, 1027971182992, 6361596456302, 0, 6425760483776, 73846596782, 5662837382398, 5735038629968], [1092637349182, 5735038629968, 73846596782, 5662837382398, 5735038629968, 0, 1092637349182, 0, 1027971182992, 1027971182992, 1092637349182, 5662837382398, 1092637349182, 1092637349182, 0, 6361596456302, 5662837382398, 73846596782, 1092637349182, 1092637349182, 1027971182992, 1092637349182, 6361596456302, 6425760483776, 1027971182992, 1027971182992, 1027971182992, 73846596782, 73846596782, 1027971182992, 0, 0, 5662837382398, 0, 0, 73846596782, 1092637349182, 6361596456302, 1092637349182, 1027971182992], [1092637349182, 5735038629968, 6361596456302, 5662837382398, 1027971182992, 1092637349182, 1092637349182, 1027971182992, 6361596456302, 5735038629968, 6361596456302, 0, 5662837382398, 0, 5735038629968, 1092637349182, 5735038629968, 73846596782, 73846596782, 6425760483776, 5735038629968, 1092637349182, 1027971182992, 6361596456302, 0, 5735038629968, 1092637349182, 6425760483776, 5662837382398, 73846596782, 1027971182992, 73846596782, 5735038629968, 5735038629968, 5662837382398, 0, 6361596456302, 73846596782, 6361596456302, 1092637349182], [0, 0, 1027971182992, 1092637349182, 0, 73846596782, 1027971182992, 73846596782, 5662837382398, 1092637349182, 6425760483776, 5662837382398, 6425760483776, 73846596782, 5735038629968, 6361596456302, 0, 5662837382398, 73846596782, 1092637349182, 73846596782, 5735038629968, 0, 5662837382398, 5662837382398, 1092637349182, 1092637349182, 73846596782, 1092637349182, 6361596456302, 1092637349182, 0, 1092637349182, 6361596456302, 5735038629968, 1027971182992, 5662837382398, 73846596782, 6425760483776, 5735038629968], [5735038629968, 1092637349182, 5662837382398, 1092637349182, 5662837382398, 6425760483776, 6361596456302, 1092637349182, 0, 73846596782, 5735038629968, 6425760483776, 73846596782, 0, 5735038629968, 1027971182992, 5735038629968, 0, 5735038629968, 1092637349182, 1027971182992, 5735038629968, 6425760483776, 73846596782, 1027971182992, 1027971182992, 5735038629968, 73846596782, 1027971182992, 73846596782, 0, 6425760483776, 6361596456302, 5735038629968, 0, 5662837382398, 6425760483776, 0, 6361596456302, 0], [5662837382398, 6425760483776, 73846596782, 6425760483776, 0, 73846596782, 6361596456302, 6425760483776, 5735038629968, 73846596782, 1092637349182, 73846596782, 6425760483776, 1092637349182, 6425760483776, 5662837382398, 1092637349182, 73846596782, 1027971182992, 73846596782, 5662837382398, 0, 6425760483776, 1027971182992, 5662837382398, 5735038629968, 6425760483776, 1092637349182, 6361596456302, 73846596782, 6425760483776, 6425760483776, 5735038629968, 5735038629968, 5735038629968, 6425760483776, 5662837382398, 73846596782, 0, 73846596782], [73846596782, 5735038629968, 6361596456302, 5662837382398, 5662837382398, 1027971182992, 5735038629968, 6361596456302, 1092637349182, 6425760483776, 0, 5735038629968, 1092637349182, 1027971182992, 1027971182992, 0, 0, 73846596782, 0, 5735038629968, 1092637349182, 5735038629968, 1092637349182, 0, 1027971182992, 6425760483776, 73846596782, 1027971182992, 0, 6361596456302, 5662837382398, 1027971182992, 6361596456302, 1027971182992, 1027971182992, 6361596456302, 1027971182992, 5735038629968, 73846596782, 5735038629968], [5662837382398, 6425760483776, 6425760483776, 1092637349182, 6361596456302, 6361596456302, 5735038629968, 6425760483776, 5662837382398, 5662837382398, 5735038629968, 5662837382398, 6425760483776, 5735038629968, 6425760483776, 1027971182992, 5662837382398, 73846596782, 6425760483776, 73846596782, 6425760483776, 1027971182992, 0, 5662837382398, 1092637349182, 73846596782, 5735038629968, 73846596782, 5662837382398, 1027971182992, 6425760483776, 1027971182992, 6361596456302, 6361596456302, 1092637349182, 6361596456302, 1092637349182, 5662837382398, 6361596456302, 5735038629968], [1092637349182, 5735038629968, 0, 5735038629968, 6361596456302, 73846596782, 5662837382398, 6425760483776, 1027971182992, 1092637349182, 0, 5662837382398, 1092637349182, 6425760483776, 1027971182992, 5662837382398, 73846596782, 6361596456302, 73846596782, 6425760483776, 1092637349182, 5662837382398, 5662837382398, 0, 1027971182992, 6361596456302, 5662837382398, 73846596782, 73846596782, 5735038629968, 5735038629968, 1027971182992, 5735038629968, 73846596782, 73846596782, 6425760483776, 73846596782, 1092637349182, 1027971182992, 5662837382398], [6361596456302, 73846596782, 0, 0, 5662837382398, 73846596782, 5735038629968, 5735038629968, 5662837382398, 1092637349182, 5662837382398, 5662837382398, 73846596782, 5662837382398, 5662837382398, 1092637349182, 1092637349182, 1027971182992, 0, 73846596782, 0, 73846596782, 5662837382398, 1092637349182, 5735038629968, 5735038629968, 5662837382398, 6425760483776, 6425760483776, 1027971182992, 0, 1027971182992, 1027971182992, 6425760483776, 1027971182992, 6361596456302, 5735038629968, 73846596782, 6425760483776, 73846596782], [0, 1092637349182, 6361596456302, 5662837382398, 1092637349182, 6425760483776, 5735038629968, 5735038629968, 5662837382398, 6425760483776, 1092637349182, 1027971182992, 1027971182992, 6361596456302, 6425760483776, 6425760483776, 5662837382398, 5662837382398, 1092637349182, 0, 0, 73846596782, 5662837382398, 5735038629968, 1027971182992, 6361596456302, 1027971182992, 5735038629968, 5662837382398, 1092637349182, 5735038629968, 5735038629968, 6361596456302, 6361596456302, 73846596782, 5662837382398, 0, 6425760483776, 1092637349182, 1027971182992], [1092637349182, 1092637349182, 6361596456302, 1092637349182, 6425760483776, 6361596456302, 73846596782, 5735038629968, 0, 5735038629968, 5735038629968, 6361596456302, 5662837382398, 1092637349182, 6361596456302, 0, 73846596782, 1027971182992, 73846596782, 1092637349182, 73846596782, 5662837382398, 1092637349182, 5662837382398, 0, 0, 6361596456302, 1092637349182, 0, 6361596456302, 1092637349182, 6361596456302, 0, 1092637349182, 73846596782, 6361596456302, 6361596456302, 73846596782, 6361596456302, 73846596782], [0, 1092637349182, 1027971182992, 73846596782, 0, 0, 5735038629968, 1027971182992, 1092637349182, 5735038629968, 73846596782, 0, 73846596782, 73846596782, 1092637349182, 73846596782, 1092637349182, 6361596456302, 1092637349182, 6361596456302, 6361596456302, 5735038629968, 1027971182992, 1092637349182, 73846596782, 6361596456302, 0, 5662837382398, 6425760483776, 73846596782, 1027971182992, 6425760483776, 6425760483776, 5662837382398, 5735038629968, 1027971182992, 5735038629968, 6425760483776, 73846596782, 73846596782], [6425760483776, 1027971182992, 73846596782, 5662837382398, 6425760483776, 5735038629968, 0, 6361596456302, 5662837382398, 73846596782, 1027971182992, 5735038629968, 73846596782, 1092637349182, 0, 0, 5662837382398, 1027971182992, 6361596456302, 5662837382398, 73846596782, 6361596456302, 1027971182992, 1027971182992, 6425760483776, 0, 5662837382398, 6425760483776, 1027971182992, 5735038629968, 73846596782, 6361596456302, 5662837382398, 1092637349182, 6361596456302, 6361596456302, 1027971182992, 5735038629968, 0, 6361596456302], [1027971182992, 73846596782, 1092637349182, 6425760483776, 6425760483776, 6425760483776, 6361596456302, 1027971182992, 6361596456302, 6361596456302, 5735038629968, 6361596456302, 5662837382398, 1092637349182, 5735038629968, 73846596782, 1027971182992, 0, 6425760483776, 1092637349182, 5662837382398, 5735038629968, 73846596782, 5735038629968, 6361596456302, 5662837382398, 0, 0, 73846596782, 0, 1027971182992, 5735038629968, 73846596782, 5662837382398, 73846596782, 1027971182992, 1092637349182, 6425760483776, 0, 5662837382398], [0, 1027971182992, 73846596782, 1027971182992, 5662837382398, 6361596456302, 6425760483776, 1092637349182, 5662837382398, 1092637349182, 1092637349182, 1027971182992, 0, 6425760483776, 73846596782, 5662837382398, 6425760483776, 0, 6425760483776, 73846596782, 5735038629968, 5662837382398, 1027971182992, 5662837382398, 1092637349182, 1027971182992, 1092637349182, 6425760483776, 1027971182992, 6361596456302, 73846596782, 6361596456302, 1092637349182, 1027971182992, 0, 1027971182992, 0, 5662837382398, 1027971182992, 5662837382398], [6425760483776, 1027971182992, 6361596456302, 5662837382398, 5662837382398, 1027971182992, 5735038629968, 5662837382398, 5735038629968, 5662837382398, 5662837382398, 73846596782, 1027971182992, 73846596782, 6425760483776, 73846596782, 5735038629968, 1027971182992, 73846596782, 6361596456302, 0, 1092637349182, 6361596456302, 6425760483776, 0, 6425760483776, 5662837382398, 6361596456302, 1027971182992, 73846596782, 6425760483776, 6361596456302, 1027971182992, 0, 1092637349182, 5735038629968, 73846596782, 1092637349182, 73846596782, 0], [73846596782, 1027971182992, 5735038629968, 5662837382398, 1092637349182, 6425760483776, 1092637349182, 1092637349182, 5662837382398, 73846596782, 73846596782, 5735038629968, 73846596782, 73846596782, 5735038629968, 1027971182992, 6361596456302, 73846596782, 0, 1092637349182, 5662837382398, 1027971182992, 6361596456302, 73846596782, 6425760483776, 0, 6425760483776, 5662837382398, 1092637349182, 0, 5735038629968, 73846596782, 5662837382398, 0, 5735038629968, 1092637349182, 5662837382398, 1092637349182, 1092637349182, 5662837382398], [1092637349182, 6425760483776, 1092637349182, 0, 5662837382398, 0, 5735038629968, 5735038629968, 1027971182992, 6361596456302, 6361596456302, 1027971182992, 6361596456302, 73846596782, 73846596782, 73846596782, 0, 5735038629968, 73846596782, 5735038629968, 6425760483776, 5735038629968, 5662837382398, 1027971182992, 5735038629968, 1092637349182, 0, 1092637349182, 1027971182992, 5735038629968, 0, 73846596782, 0, 73846596782, 6425760483776, 73846596782, 5662837382398, 5662837382398, 6425760483776, 1092637349182], [6361596456302, 1027971182992, 6425760483776, 1092637349182, 5662837382398, 73846596782, 5735038629968, 6425760483776, 5735038629968, 6361596456302, 73846596782, 1092637349182, 5735038629968, 6361596456302, 1027971182992, 6425760483776, 5735038629968, 5735038629968, 0, 73846596782, 5662837382398, 1027971182992, 1092637349182, 5735038629968, 5735038629968, 6425760483776, 1027971182992, 5735038629968, 73846596782, 73846596782, 1092637349182, 5662837382398, 5735038629968, 1027971182992, 6361596456302, 5662837382398, 6425760483776, 6425760483776, 1092637349182, 1092637349182], [1092637349182, 0, 6425760483776, 1027971182992, 5735038629968, 5662837382398, 6425760483776, 5662837382398, 5735038629968, 1092637349182, 6425760483776, 0, 5662837382398, 6361596456302, 6425760483776, 6425760483776, 1027971182992, 5735038629968, 6361596456302, 5662837382398, 1027971182992, 73846596782, 6425760483776, 5735038629968, 6361596456302, 5662837382398, 6425760483776, 1027971182992, 6361596456302, 0, 5735038629968, 5662837382398, 0, 1027971182992, 5735038629968, 1092637349182, 6425760483776, 6361596456302, 0, 6425760483776], [5735038629968, 0, 5662837382398, 5662837382398, 6425760483776, 5662837382398, 5735038629968, 1092637349182, 1092637349182, 6361596456302, 1027971182992, 5662837382398, 6361596456302, 0, 6425760483776, 0, 1092637349182, 5662837382398, 73846596782, 1027971182992, 1092637349182, 1027971182992, 6425760483776, 5735038629968, 6361596456302, 0, 1092637349182, 5735038629968, 73846596782, 1092637349182, 5662837382398, 6361596456302, 5662837382398, 5735038629968, 6425760483776, 6361596456302, 1092637349182, 0, 6425760483776, 0], [6425760483776, 5662837382398, 1092637349182, 6361596456302, 6425760483776, 1092637349182, 5735038629968, 6425760483776, 1027971182992, 6425760483776, 0, 6425760483776, 6425760483776, 6425760483776, 6425760483776, 1027971182992, 1027971182992, 0, 1027971182992, 5735038629968, 5662837382398, 1027971182992, 0, 6361596456302, 6361596456302, 5735038629968, 1027971182992, 73846596782, 73846596782, 1092637349182, 1092637349182, 5735038629968, 5735038629968, 1027971182992, 0, 5662837382398, 6425760483776, 5662837382398, 73846596782, 1027971182992], [5735038629968, 1027971182992, 6425760483776, 1027971182992, 0, 0, 1092637349182, 5662837382398, 1027971182992, 73846596782, 1092637349182, 0, 1027971182992, 6425760483776, 5735038629968, 73846596782, 0, 5662837382398, 5735038629968, 0, 1092637349182, 6425760483776, 1092637349182, 1027971182992, 1027971182992, 0, 73846596782, 5735038629968, 1027971182992, 5735038629968, 6425760483776, 6361596456302, 6425760483776, 5735038629968, 0, 1027971182992, 5662837382398, 6361596456302, 5735038629968, 5662837382398], [1092637349182, 6361596456302, 0, 0, 5735038629968, 6425760483776, 0, 0, 6425760483776, 6361596456302, 6361596456302, 5735038629968, 1092637349182, 73846596782, 5662837382398, 1092637349182, 5735038629968, 5735038629968, 5662837382398, 1092637349182, 73846596782, 6361596456302, 5662837382398, 73846596782, 6425760483776, 5735038629968, 5735038629968, 73846596782, 0, 6425760483776, 0, 5662837382398, 6425760483776, 6361596456302, 73846596782, 6361596456302, 1027971182992, 0, 5662837382398, 5662837382398], [1027971182992, 1027971182992, 5662837382398, 1027971182992, 6361596456302, 1092637349182, 6425760483776, 5735038629968, 5662837382398, 5662837382398, 1027971182992, 1027971182992, 1092637349182, 73846596782, 5735038629968, 6425760483776, 0, 0, 6425760483776, 5662837382398, 6361596456302, 6425760483776, 6425760483776, 6361596456302, 5735038629968, 0, 5735038629968, 1027971182992, 6361596456302, 0, 6425760483776, 1027971182992, 5662837382398, 73846596782, 6361596456302, 5662837382398, 0, 5735038629968, 1092637349182, 6361596456302], [5735038629968, 1027971182992, 1092637349182, 6425760483776, 6361596456302, 73846596782, 6425760483776, 1092637349182, 0, 0, 5662837382398, 5662837382398, 6425760483776, 5735038629968, 73846596782, 1027971182992, 0, 5662837382398, 6361596456302, 5735038629968, 0, 6361596456302, 5662837382398, 73846596782, 1027971182992, 5735038629968, 1027971182992, 6361596456302, 5735038629968, 6425760483776, 5662837382398, 5662837382398, 1092637349182, 5662837382398, 73846596782, 1027971182992, 6361596456302, 1027971182992, 1092637349182, 73846596782], [6425760483776, 6425760483776, 1092637349182, 6425760483776, 6425760483776, 6425760483776, 6361596456302, 6361596456302, 5662837382398, 1092637349182, 1027971182992, 1092637349182, 0, 6425760483776, 1027971182992, 0, 0, 1027971182992, 1092637349182, 5662837382398, 5735038629968, 1027971182992, 6425760483776, 5735038629968, 73846596782, 6361596456302, 5662837382398, 5662837382398, 0, 5662837382398, 1092637349182, 73846596782, 6425760483776, 6361596456302, 6425760483776, 5735038629968, 6361596456302, 5735038629968, 6361596456302, 1027971182992], [5662837382398, 5735038629968, 5662837382398, 0, 1092637349182, 0, 6425760483776, 6425760483776, 0, 73846596782, 73846596782, 6425760483776, 5662837382398, 0, 1027971182992, 6361596456302, 5662837382398, 0, 6361596456302, 1092637349182, 6425760483776, 5662837382398, 5735038629968, 5662837382398, 1092637349182, 1027971182992, 6425760483776, 1092637349182, 6425760483776, 5735038629968, 6361596456302, 5735038629968, 6361596456302, 1092637349182, 6361596456302, 73846596782, 6425760483776, 6361596456302, 1027971182992, 5735038629968], [1092637349182, 0, 1027971182992, 1027971182992, 1027971182992, 1027971182992, 0, 6361596456302, 1092637349182, 73846596782, 1092637349182, 1027971182992, 1092637349182, 6425760483776, 1092637349182, 73846596782, 0, 73846596782, 5735038629968, 1092637349182, 1027971182992, 5735038629968, 6425760483776, 1092637349182, 0, 73846596782, 1027971182992, 5735038629968, 1092637349182, 0, 73846596782, 1092637349182, 73846596782, 73846596782, 73846596782, 1092637349182, 6425760483776, 1027971182992, 73846596782, 6425760483776]], "fibers": [5662837382398, 5735038629968, 1027971182992]}, "vault": {"iv": "d3dcc925729b88c117b38875", "body": "373763cb2c22b30d4e9357aeb13f73ac5477c1dca635a0811d9d1db7e5d1556d9166942fe8ad7d46b61531250ebf9bedb5a1bb22793a76cf7bf7f31c67b4c0f89c1342de4ce3", "tag": "990157e7b5bf7035882c0e9047fb4055"}}"""

handout = json.loads(json_data)

def unpack(val):
    return sum(Fqm.gen()**i * ((val >> i) & 1) for i in range(43))

def pack(v):
    cs = list(v.polynomial()) if v else []
    cs = [int(c) for c in cs] + [0] * (43 - len(cs))
    val = 0
    for i, c in enumerate(cs): val |= c << i
    return int(val)

# Parse components
pegs = [unpack(v) for v in handout['loom']['pegs']]
shuttle_mat = Matrix(Fqm, 40, 40, [[unpack(v) for v in row] for row in handout['loom']['shuttle']])
knot_mat = Matrix(Fqm, 8, 8, [[unpack(v) for v in row] for row in handout['loom']['knot']])
bolt_vec = vector(Fqm, [unpack(v) for v in handout['bolt']])

# Transform to y = s'G + e
y = bolt_vec * shuttle_mat

# Solve Welch-Berlekamp system
rows = []
for i in range(40):
    row = [y[i]**(2**j) for j in range(16)] + [pegs[i]**(2**j) for j in range(23)]
    rows.append(row)

M_sys = Matrix(Fqm, rows)
vec = M_sys.right_kernel().basis()[0]
lambdas, ns = vec[:16], vec[16:]

# Normalize
while lambdas[0] == 0:
    lambdas = [v**(2**42) for v in lambdas[1:]] + [0]
    ns = [v**(2**42) for v in ns[1:]] + [0]

# Recover s_prime coefficients
s_prime = []
for j in range(8):
    val = ns[j]
    for i in range(1, j + 1):
        if i < len(lambdas): val -= lambdas[i] * (s_prime[j-i]**(2**i))
    s_prime.append(val / lambdas[0])

# Final decryption
s_vec = vector(Fqm, s_prime) * knot_mat.inverse()
secret_bytes = b''.join(pack(v).to_bytes(6, 'big') for v in s_vec)
wrap_key = sha256(secret_bytes).digest()[:16]

iv = bytes.fromhex(handout['vault']['iv'])
body = bytes.fromhex(handout['vault']['body'])
tag = bytes.fromhex(handout['vault']['tag'])

cipher = AES.new(wrap_key, AES.MODE_GCM, nonce=iv)
flag = cipher.decrypt_and_verify(body, tag)
print(f"Flag: {flag.decode()}")

Flag

UMDCTF{l01dr34u_l4mbda3_brick5_th3_w34v3_but_th3_trapd00r_unsp00ls_1t}