# zer0pts CTF 2023 - Unlimited Braid Works

## Overview

## Summary

This is a writeup for the “Unlimited Braid Works” challenge by mitsu at zer0pts CTF 2023. This challenge involved non-commutative group theory, and in particular braid groups. We were the first team to solve this challenge, which 6 teams solved in total.

Solved by: shalaamum

Writeup by: shalaamum

Writeup first published here.

## The braid group

We get to choose an `n`

, which has to be even and at least `16`

. There seems to be no reason to choose a larger `n`

, so the writeup is going to assume `n=16`

from now on. The remote than works with the braid group on n=16 strands `B_16`

, so let us first recall that this group is generated by `s_1, ..., s_15`

, where `s_i`

swaps strand `i`

and strand `i+1`

, by passing strand `i`

under strand `i+1`

. Note that we number the strands from `1`

to `16`

. The relations these generators satisfy are generated by `s_i * s_j = s_j * s_i`

for `i - j > 1`

(so generators commute with all other generators except the “immediate neighbors”) and `s_i * s_(i+1) * s_i = s_(i+1) * s_i * s_(i+1)`

for all `0 < i < 15`

.

## The problem

After we chose `n=16`

, the remote generates some elements `u`

, `al`

, and `br`

of `B_16`

randomly. `al`

is chosen so that it lies in `<s_1, .., s_6>`

, and `br`

is chosen so that it lies in `<s_10, ..., s_15>`

. The flag is encrypted by xoring with a hash obtained from an element `c`

of `B_16`

, which is defined as follows:

```
v = al * u * al^-1
c = br * v * br^-1
```

We get to know the ciphertext, and `u`

and `v`

, and additionally `w = br * u * br^-1`

, but not `c`

or `br`

.

## The solution

### Step 1

Let us unpack what `c`

is. In the following calculation, note that `br`

and `al`

commute, as each of `s_1, ..., s_6`

commutes with each of `s_10, ..., s_15`

. Thus we have:

```
c = br * v * br^-1
= br * al * u * al^-1 * br^-1
= al * br * u * br^-1 * al^-1
= al * w * al^-1
```

We know `w`

but not `al`

. The only access we have to `al`

is via knowing both `u`

and `v = al * u * al^-1`

. Perhaps we can deduce `al`

from this? But there is not reason to assume that `al`

is uniquely determined by this equation, for example we could always multiply `al`

on the right with some element that `u`

commutes with to get another solution. So suppose we found *some* element `a`

of `B_16`

, possibly different than `al`

, satisfying `v = a * u * a^-1`

. Does this imply that `c = a * w * a^-1`

? We can try to carry out the above calculation for `a`

instead of `al`

, and see that this will work as long as we assume that `a`

commutes with `br`

. In turn, this will be the case as long as `a`

is in `<s_1, ..., s_8>`

.

### Step 2

We are left to find `a`

in `<s_1, ..., s_8>`

so that `v = a * u * a^-1`

. The crucial idea now is to assume that `u`

lies in `<s_1, ..., s_8, s_10, ..., s_15>`

. Note that this is a reasonable assumption, `u`

is generated by

```
K = 32
u = random.choices(gs, k=K)
# u must be twisted
if not gs[n // 2 - 1] in u:
u[randint(0, K - 1)] = gs[n // 2 - 1]
```

so using `32`

random generators, so the chance that `s_9`

does not appear at least `(14/15)^30 ≈ 13%`

. The actual probability is slightly higher, due to one generator being replaced by `s_8`

(which is `gs[7]`

in the code) if it did not otherwise appear. The intention here might have been that it was `s_9`

that was supposed to be added to make `u`

“twisted”, but the vulnerability is in the off-by-one mistake of making it `s_8`

instead. As `u`

is generated randomly on each connection, we will thus expect to be able to solve the problem using roughly 10 retries if we have a solution under this assumption, which is acceptable.

Now with the assumption that `u`

lies in `H = <s_1, ..., s_8, s_10, ..., s_15>`

, and knowing that `v = al * u * al^-1`

, with `al`

also being an element of `H`

, we can conclude that `v`

is also on `H`

. Furthermore, as all elements of `s_1, ..., s_8`

commute with all elements of `s_10, ..., s_15`

, `H`

is isomorphic to a product `B_9 x B_7`

, with an isomorphism `f: H -> B_9 x B_7`

being given by mapping `s_i`

to `(s_i, 1)`

if `i < 9`

and to `(1, s_(i-9))`

otherwise. Let us write `f(v) = (v', v'')`

and similarly for `u`

and `al`

. Note that `al'' = 1`

. The relation `v = al * u * al^-1`

then implies `v' = al' * u' * al'^-1`

in `B_9`

and `v'' = 1 * u'' * 1^-1 = u''`

in `B_7`

.

Note that `f(a)`

for an `a`

of the form we are looking for is also of the form `(a', 1)`

. So we are trying to find an element `a'`

of `B_9`

so that `v' = a' * u' * a'^-1`

in `B_9`

and `v'' = 1 * u'' * 1^-1`

in `B_7`

. The latter is always satisfied, so our problem has been reduced to finding an element `a'`

of `B_9`

such that `v' = a' * u' * a'^-1`

. Luckily for us, Sage has a function solving this problem built in: the `conjugating_braid`

function.

## Attachments

The original challenge and my solution script.