[Dicegang] Plane-or-Exchange

Introduction

I was quite busy so I rushed a bit on this post, I think I wrote this post just because i got motivated after “someone” posted Codex writeup. (hmmm i wonder who it is).

But yeah, This was a fun challenge so here’s the write up. Honestly, I don’t think this would get me 50 bucks but if i get it, i will happily use it to support the beer economy for Friendly Maltese Citizens. By buying a whole kattle.

TL;DR

I thought this protocol was just some broken Diffie Hellman but actually the public key is actually created by planar grid diagrams for knots. So A public key is formed by combining a public grid with a private grid and then scrambling them by grid diagram moves. The shared secret is derived from the normalized Alexander polynomial of another combined grid. The thing is this doesn’t really have anything that make this “solvable”, but how this challenge can be approached is by using normalized Alexander polynomial of the represented knot. which is also the quantity that is being hashed.

This polynomial shows these 2 information

1. Invariant under the knot preserving grid moves used by the scramble step
2. Multiplicative under connected sum

Because of these 2 facts, we can reconstruct the same shared polynomial from public data

aaaaaand, this is quite enough to derive the same keystream as Alice and Bob and get the flag

Grid Diagrams and Knots

Warning: Math ahead

Well to get started we first have to understand the math it uses, and lots of reading The challenge works with the combinatorial presentation of knots using grid diagrams. To understand Grid Homology, I would like to sugess y’all to read “Grid Homology for Knots and Links” since these definitions are coming from that book, and it’s a really good book.

To understand the code, we will map the challenge’s data structures directly to the formal definitions provided in that book.

The text after explains how this combinatorial object can be encoded as data

In the challenge script, a grid is represented exactly like this. In (x, o) the x and the o are arrays acting as the permutations $\sigma_{\mathbb{O}}$ and $\sigma_{\mathbb{X}}$

So now how does this grid represent a knot??? Well time to do some more reading.

And after this, the challenge checks that the diagram represents a single component knot, not a multi-component link and this condition is also, as you have guessed, it’s from the book lol.

The challenge’s validate(point) function makes us of this since it verifies the row/column uniqueness (Definition 3.1.1), and ensures the cycle decomposition of $\sigma_{\mathbb{X}} \cdot \sigma_{\mathbb{O}}^{-1}$. Which results in exactly $1$ cycle (Remark 3.1.2). This tells us that the grid represents a knot.

Scrambling & Cromwell’s Theorem

The protocal attempts to hide the private keys by “scrambling” the combined grids So what’s with the scrambling mathematically???

If you want to explicitly define the moves the challenge uses in the scramble function to prove they are mathematically valid “grid moves” it uses these

For row/column swaps we use commutations.

For shared square swaps we use switches.

For wrapping rows/columns around the edges we use cyclic permutation

If you think about it, all of these operations preserve the underlying knot type. Because the knot type is preserved, any topological invariant of the knot remains unchanged before and after scrambling. The scramble obscures the diagram but it doesn’t do anything to “obscure” the knot.

The Alexander Polynomial

To generate the shared secret, the challenge relies on calculate(G) and normalize(). What are these computing? Well time to bring out the book again, since it provides the exact formulas

First, the code builds a matrix based on winding numbers,

Then, it adjusts the determinant of this matrix

This function now moves to a known topological invariant

In the challenge code calculate(G) build the grid matrix $\mathbf{M}(\mathbb{G})$ and evaluates its determinant, and normalize() multiplies it by the missing sign $\epsilon(\mathbb{G})$ and Laurent monomial shift $(t^{-1/2} - t^{1/2})^{1-n} \cdot t^{a(\mathbb{G})}$

Thus, normalize(calculate(G)) is mathematically the same to evaluating the symmetrized Alexander polynomial $\Delta_K(t)$ of the knot!

Connected Sums

To mix the public and private grids, the protocol uses connect(g1, g2). From the code perspective, this takes two grids, places them diagonally adjacent, and links their ends to merge them into a single larger grid.

Topologically, this operation is exactly the connected sum, denoted $K_1 \# K_2$. It splices two knots together to form a new knot. Why is this not a bueno idea for cryptography? Because you can actually abuse this identity.

We can see that the invariant used to derive the shared secret is perfectly multiplicative over the protocol’s combination function. Which makes it vulnerable.

Summarization of the Challenge Script

Now since we know basic background of Grid Homology, it’s time to summarize the challenge script into clean knot topology.

Let $P$ be the public base knot, $A$ be Alice’s private knot, and $B$ be Bob’s private knot. Let $\Delta(K)$ denote the evaluation of the Alexander polynomial normalize(calculate(K)).

Alice’s public key $A_{\text{pub}}$ and Bob’s public key $B_{\text{pub}}$ are generated as

Because scrambling preserves the knot type (Theorem 3.1.9), and the Alexander polynomial is multiplicative (Theorem 2.4.6)

To compute the shared secret, Alice connects her private knot $A$ to Bob’s public knot $B_{\text{pub}}$ and extracts the polynomial

Bob does the equivalent on his side, which arrives at the exact same polynomial.

Formulating Our Solver

We intercept the public base grid $P$, and the two public keys $A_{\text{pub}}$ and $B_{\text{pub}}$. Since we know that the Alexander polynomials operate over standard polynomial multiplication, We can compute the shared secret purely from public data

and by substituting the underlying values

Dubbb we can now recover the polynomial Alice and Bob are hashing.

The Exploit Code

The script is quite simple if you understand the math. We can evaluate the polynomials using the challenge’s provided functions and do the polynomial division.

import ast
import hashlib
import sympy as sp
 
t = sp.Symbol('t')
 
def sweep(ap):
    l = len(ap)
    current_row = [0] * l
    matrix = []
    for pair in ap:
        c1, c2 = sorted(pair)
        diff = pair[1] - pair[0]
        s = 1 if diff > 0 else -1 if diff < 0 else 0
        for c in range(c1, c2):
            current_row[c] += s
        matrix.append(list(current_row))
    return matrix
 
def mine(point):
    x, o = point
    return sweep(list(zip(x, o)))
 
def poly_stuff(exp_rows):
    n = len(exp_rows)
    row_shifts = [max(r) for r in exp_rows]
    M = [[sp.Poly(t**(row_shifts[i] - exp_rows[i][j]), t, domain='ZZ')
          for j in range(n)] for i in range(n)]
 
    prev = sp.Poly(1, t, domain='ZZ')
    sign = 1
 
    for k in range(n - 1):
        piv = k
        while piv < n and M[piv][k].is_zero:
            piv += 1
        if piv == n:
            return sp.Poly(0, t, domain='ZZ')
        if piv != k:
            M[k], M[piv] = M[piv], M[k]
            sign *= -1
 
        pivot = M[k][k]
        for i in range(k + 1, n):
            for j in range(k + 1, n):
                num = pivot * M[i][j] - M[i][k] * M[k][j]
                if prev != 1:
                    q, r = num.div(prev)
                    assert r.is_zero
                    M[i][j] = q
                else:
                    M[i][j] = num
            M[i][k] = sp.Poly(0, t, domain='ZZ')
        prev = pivot
 
    det = M[n - 1][n - 1]
    if sign == -1:
        det = -det
    return det
 
def invariant(point):
    n = len(point[0])
    det = poly_stuff(mine(point))
    fac = sp.Poly((1 - t)**(n - 1), t, domain='ZZ')
    q, r = det.div(fac)
    assert r.is_zero
    poly = sp.Poly(q.as_expr().expand(), t, domain='ZZ')
    min_deg = min(m[0] for m in poly.monoms())
    if min_deg:
        poly = sp.Poly(poly.as_expr() / t**min_deg, t, domain='ZZ')
    if poly.nth(0) < 0:
        poly = -poly
    return sp.expand(poly.as_expr())
 
with open("public.txt") as f:
    lines = f.read().splitlines()
 
A = tuple(ast.literal_eval(lines[0].split(": ", 1)[1]))
B = tuple(ast.literal_eval(lines[1].split(": ", 1)[1]))
P = tuple(ast.literal_eval(lines[2].split(": ", 1)[1]))
ct = bytes.fromhex(lines[3].split(": ", 1)[1])
 
dA = sp.Poly(invariant(A), t, domain='ZZ')
dB = sp.Poly(invariant(B), t, domain='ZZ')
dP = sp.Poly(invariant(P), t, domain='ZZ')
 
shared_poly, rem = (dA * dB).div(dP)
assert rem.is_zero
 
shared_secret = hashlib.sha256(str(sp.expand(shared_poly.as_expr())).encode()).hexdigest()
 
key = bytes.fromhex(shared_secret)
while len(key) < len(ct):
    key += hashlib.sha256(key).digest()
 
pt = bytes(c ^ k for c, k in zip(ct, key))
print(pt.decode())

user@Baekseju:~/CTF/Dicegang/planar$ python3 solve.py
dice{plane_or_planar_my_w0rds_4r3_411_knotted_up}