sugar free candies

2 minutes to read

We are given the Python source code to encrypt the flag:

from Crypto.Util.number import bytes_to_long

FLAG = open("flag.txt", "rb").read()

step = len(FLAG) // 3
candies = [bytes_to_long(FLAG[i:i+step]) for i in range(0, len(FLAG), step)]  

cnd1, cnd2, cnd3 = candies

with open('output.txt', 'w') as f:
    f.write(f'v1 = {cnd1**3 + cnd3**2 + cnd2}\n')
    f.write(f'v2 = {cnd2**3 + cnd1**2 + cnd3}\n')
    f.write(f'v3 = {cnd3**3 + cnd2**2 + cnd1}\n')
    f.write(f'v4 = {cnd1 + cnd2 + cnd3}\n')

And this is the output of the script:

v1 = 1181239096013650837744125294978177790419553719590172794906535790528758829840751110126012179328061375399196613652870424327167341710919767887891371258453  
v2 = 2710472017687233737830986182523923794327361982506952801148259340657557362009893794103841036477555389231149721438246037558380601526471290201500759382599
v3 = 3448392481703214771250575110613977019995990789986191254013989726393898522179975576074870115491914882384518345287960772371387233225699632815814340359065
v4 = 396216122131701300135834622026808509913659513306193

Source code analysis

In math terms, the script splits the flag in three parts and translates them to integers $\mathrm{cnd}_1$, $\mathrm{cnd}_2$ and $\mathrm{cnd}_3$. Then, it computes for values $v_1$, $v_2$, $v_3$ and $v_4$ as follows:

$$ \begin{cases} v_1 = (\mathrm{cnd}_1)^3 + (\mathrm{cnd}_3)^2 + \mathrm{cnd}_2 \\ v_2 = (\mathrm{cnd}_2)^3 + (\mathrm{cnd}_1)^2 + \mathrm{cnd}_3 \\ v_3 = (\mathrm{cnd}_3)^3 + (\mathrm{cnd}_2)^2 + \mathrm{cnd}_1 \\ v_4 = \mathrm{cnd}_1 + \mathrm{cnd}_2 + \mathrm{cnd}_3 \end{cases} $$

Solution

The objective is to find the values of $\mathrm{cnd}_1$, $\mathrm{cnd}_2$ and $\mathrm{cnd}_3$. In other words, we need to solve the previous system of equations. Given the fact that we have 3 unknowns and 4 equations, it must be possible. Also, we know that there exists a solution, because the values $v_1$, $v_2$, $v_3$ and $v_4$ are built from the flag.

We could take paper and pen and try to solve this by hand using symbolic math. However, we can use a computer program to solve this way faster. In SageMath, we can use solve as follows:

$ sage -q
sage: v1 = 1181239096013650837744125294978177790419553719590172794906535790528758829840751110126012179328061375399196613652870424327167341710919767887891371258453  
....: v2 = 2710472017687233737830986182523923794327361982506952801148259340657557362009893794103841036477555389231149721438246037558380601526471290201500759382599
....: v3 = 3448392481703214771250575110613977019995990789986191254013989726393898522179975576074870115491914882384518345287960772371387233225699632815814340359065
....: v4 = 396216122131701300135834622026808509913659513306193
sage: 
sage: cnd1, cnd2, cnd3 = var('cnd1, cnd2, cnd3')
sage: 
sage: sol = solve([
....:     v1 == cnd1 ** 3 + cnd3 ** 2 + cnd2,
....:     v2 == cnd2 ** 3 + cnd1 ** 2 + cnd3,
....:     v3 == cnd3 ** 3 + cnd2 ** 2 + cnd1,
....:     v4 == cnd1 + cnd2 + cnd3
....: ], cnd1, cnd2, cnd3, solution_dict=True)
sage: sol
[{cnd1: 105709155715849064931516800270848071425751222546035,
  cnd2: 139427457951053646347891878266599404989598900055137,
  cnd3: 151079508464798588856425943489361033498309390705021}]

And there we have the solution to the system of equations.

Flag

At this point, we can transform each value to bytes and join everything together:

sage: b''.join(bytes.fromhex(hex(v)[2:]) for v in sol[0].values())  
b'HTB{solving_equations_for_parts_of_the_flag_over_the_integers!}'