Young Cryptography — UIUCTF 2026

Description

No separate organizer prose was included in the supplied package. The challenge consisted of chal.py and the five-line out instance.

The source creates three random symmetric 64 x 64 nonnegative matrices. It publishes G, AG = my_prod(A, G), and GB = my_prod(G, B), then derives an AES-CBC key from the secret matrix AGB = my_prod(A, GB). The output also contains the ciphertext and IV.

The title is literal: the max/min recurrence in my_prod is Fomin's tropical RSK growth rule. Its boundary encodes a semistandard Young tableau, and matrix multiplication becomes multiplication in the plactic monoid.

Analysis

1. Splitting my_prod into a growth boundary and its inverse

The important detail in the source is this loop:

r = [z] * (n + 1)
for row in A + B:                 # list concatenation, not matrix addition
    s = [z]
    for j, x in enumerate(row, 1):
        s.append(f(r[j-1], r[j], s[-1], x))
    r = s

The function f is the tropical local rule. Processing a matrix produces a boundary

[ r=(\lambda^{(0)},\lambda^{(1)},\ldots,\lambda^{(N)}), ]

where every tuple is a partition/shape vector. The number of copies of symbol j in tableau row i is

[ r[j][i]-r[j-1][i]. ]

Thus the boundary-to-tableau conversion is only:

def tableau_from_boundary(r, n):
    P = [[] for _ in range(n)]
    for j in range(1, n + 1):
        for i in range(n):
            P[i] += [j] * (r[j][i] - r[j - 1][i])
    return [row for row in P if row]

The second half of my_prod sweeps the triangular growth diagram backwards. Given r, phase2(r) constructs the corresponding symmetric matrix. On valid boundaries these operations satisfy

[ \operatorname{phase1}(\operatorname{phase2}(r))=r. ]

Write P_X for the tableau obtained from matrix X. Since my_prod(X, Y) feeds every row of X and then every row of Y into the same RSK process,

[ P_{\operatorname{my_prod}(X,Y)}=P_X * P_Y, ]

where * is the associative plactic tableau product: row-insert the reading word of the right tableau into the left tableau. phase2 merely converts the resulting tableau boundary back to the matrix representation expected by the challenge.

2. Associativity reduces the key exchange to one division

Converting the three public matrices gives

[ P_{AG}=P_AP_G, \qquad P_{GB}=P_GP_B. ]

It is unnecessary to recover the organizer's exact P_A or P_B. Find any right quotient P_A' satisfying

[ P_A' * P_G=P_{AG}. ]

Then associativity gives

[ \begin{aligned} P_A' * P_{GB} &=P_A'(P_GP_B)\ &=(P_A'*P_G)P_B\ &=P_{AG}P_B\ &=(P_AP_G)P_B\ &=P_A(P_GP_B)\ &=P_{AGB}. \end{aligned} ]

This is precisely the promised plactic right-division problem q * b = c studied by Chris Monico in Division in the Plactic Monoid, Cryptology ePrint 2022/1684.

3. Content subtraction fixes the quotient's letters

Knuth relations change word order but preserve the multiplicity of every alphabet symbol. Therefore any solution of q * b = c must have

[ \operatorname{content}(q) =\operatorname{content}(c)-\operatorname{content}(b). ]

Here c is the reading word of P_AG and b is the reading word of P_G. The subtraction leaves exactly 256 quotient letters. The hard part is not choosing the letters, but finding an ordering whose insertion tableau product is P_AG.

4. Alphabet-by-alphabet projection and lifting

Trying random permutations over all 256 letters at once gives almost no useful guidance. Monico's scalable method solves a sequence of projected equations. For alphabet maximum s, delete every letter greater than s from q, b, and c, and solve

[ q_{\le s} * b_{\le s}=c_{\le s}. ]

The one-symbol equation is trivial. To lift a solution from s-1 to s:

1. add the required number of copies of symbol s, as determined by content subtraction;
2. project the known suffix and target to symbols at most s;
3. relocate letters within the candidate quotient until its product reaches the projected target;
4. retain the solved ordering and introduce the next symbol.

Each stage is much smaller and starts from a quotient already correct under the previous projection.

5. Tableau-row metric and non-increasing hill climb

Every product candidate is canonicalized to its RSK insertion tableau. The metric compares corresponding tableau rows from top to bottom. Within each row, it counts entries in the candidate row that cannot be paired with an equal entry in the target row; missing target rows contribute their full candidate length. Distance zero means the tableaux agree.

One proposal removes a randomly selected letter of the quotient word and reinserts it at another random position. This preserves the already-known content. The search accepts both improving and neutral moves:

Word candidate = relocate(quotient);
Word candidate_product = multiply(candidate, suffix);
int candidate_distance = distance_metric(candidate_product, target);

if (candidate_distance <= current_distance) {
    quotient = std::move(candidate);
    current_product = std::move(candidate_product);
    current_distance = candidate_distance;
}

Neutral acceptance is important because it lets the search move across metric plateaus. The implementation also retains Monico's escape mechanism: after a bounded number of nearby, nonproductive transitions, apply several random relocations starting from the best quotient seen globally. The real instance did not need that fallback.

The lifting loop in placdiv_metric.cpp is structurally:

// Content of q is forced by content(c) - content(b).
for (int x : target) ++count[x];
for (int x : suffix) --count[x];

quotient.assign(count[first], first);
for (int symbol = first + 1; symbol <= last; ++symbol) {
    quotient.insert(quotient.begin(), count[symbol], symbol);
    Word target_mod = filter_at_most(target, symbol);
    Word suffix_mod = filter_at_most(suffix, symbol);

    if (!find_permutation(quotient, target_mod, suffix_mod,
                          stage_budget))
        return false;
}
return multiply(quotient, suffix) == target;

The final equality is mandatory: the metric guides the probabilistic search, but exact tableau multiplication verifies the quotient.

6. Evidence from generated and real instances

test_placdiv_metric.py generated symmetric challenge-style instances and asserted both the known product and recovered quotient equations. The recorded metric_tests.log contains ten successful cases:

N=8:  4/4 verified
N=12: 4/4 verified
N=16: 2/2 verified

For the real N=64 data, deterministic PRNG seed 1 lifted through the full alphabet. The last two relevant lines of solve_metric.log are:

symbol=64 qlen=256 solved=1 proposals=630391 jumps=0
verified seed=1 proposals=630391 jumps=0

The result in p_a_metric_generated.txt is a 256-cell tableau with 26 rows, and solve_metric.py independently checks

assert product(p_a_prime, p_g) == p_ag

before using it.

7. Why direct reverse insertion was not the scalable route

A historically useful small-instance solver reversed RSK insertion by removing outer corners until it reached P_G. It is correct when given the insertion recording, but the public insertion tableau does not reveal which corner was added at each step. Searching those corner/removal orders worked on small tests and then became exponential; the real quotient has 256 cells.

Related reverse-corner and jeu-de-taquin experiments could invert a slide when its logged path was known, but choosing the missing paths again amounted to recovering the unknown recording tableau. Monico's metric-guided division avoids this combinatorial search entirely, so those experiments are historical validation rather than part of the final solve.

Solution

Reconstruct the shared matrix

After division, compute the shared tableau directly:

p_agb = product(p_a_prime, p_gb)

To feed it back to phase2, invert tableau_from_boundary. Boundary entry r[j][i] is the number of values at most j in tableau row i:

def tableau_boundary(tableau, alphabet_size):
    return [
        tuple(
            sum(value <= maximum for value in tableau[row])
            if row < len(tableau) else 0
            for row in range(alphabet_size)
        )
        for maximum in range(alphabet_size + 1)
    ]

boundary_agb = tableau_boundary(p_agb, 64)
agb = phase2(boundary_agb, 64)
assert phase1(agb, 64) == boundary_agb

This produces the same canonical matrix representation that my_prod(A, GB) would have produced.

Derive the key and decrypt

The challenge hashes Python's exact string representation of the matrix. A SHA-256 digest is 32 bytes, so the source's [:128] slice does not shorten it; the cipher therefore uses AES-256-CBC.

key = hashlib.sha256(str(agb).encode()).digest()
plaintext = AES.new(key, AES.MODE_CBC, iv).decrypt(ciphertext)
plaintext = unpad(plaintext, 16)

solve_metric.py performs the complete conversion, launches the C++ divider, verifies the quotient, reconstructs AGB, derives the digest, decrypts, and PKCS#7-unpads the plaintext.

Reproduction

From the challenge directory, install the one Python dependency, compile the metric divider, run its generated-instance tests, and solve the published instance:

$ python3 -m pip install pycryptodome
$ g++ -O3 -std=c++20 placdiv_metric.cpp -o placdiv_metric
$ python3 test_placdiv_metric.py | tee metric_tests.log
$ python3 solve_metric.py out
uiuctf{REDACTED}
quotient: <TASK_DIR>/p_a_metric_generated.txt
log: <TASK_DIR>/solve_metric.log

The default arguments used by solve_metric.py are seed 1 and a per-stage budget of 200000000; the successful run consumed only 630,391 total relocation proposals and made zero jumps. Re-running with those defaults also regenerates the quotient and real-instance evidence log.

Lessons Learned

• Recognizing the tropical RSK local rule turns an opaque matrix operation into a standard algebraic object with an associative product.
• For the shared secret, any verified quotient is as useful as the original private factor because associativity preserves the public product chain.
• Content subtraction removes the multiset search, while alphabet lifting and neutral metric moves make the remaining ordering problem practical.
• Always reconstruct the exact serialized object before hashing; here the key depends on Python's str() of the symmetric matrix, not directly on the tableau or quotient word.