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.