> For the complete documentation index, see [llms.txt](https://elijahchia.gitbook.io/ctf-blog/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://elijahchia.gitbook.io/ctf-blog/uiuctf-24/without-a-trace-crypto.md).

# Without a Trace (crypto)

Gone with the wind, can you find my flag?

{% file src="/files/IZPhmHlj4xZtqkemjxfs" %}

We are given the following Python code being run on the remote server:

```python
import numpy as np
from Crypto.Util.number import bytes_to_long
from itertools import permutations
from SECRET import FLAG

def inputs():
    print("[WAT] Define diag(u1, u2, u3. u4, u5)")
    M = [
        [0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0],
    ]
    for i in range(5):
        try:
            M[i][i] = int(input(f"[WAT] u{i + 1} = "))
        except:
            return None
    return M

def handler(signum, frame):
    raise Exception("[WAT] You're trying too hard, try something simpler")

def check(M):
    def sign(sigma):
        l = 0
        for i in range(5):
            for j in range(i + 1, 5):
                if sigma[i] > sigma[j]:
                    l += 1
        return (-1)**l

    res = 0
    for sigma in permutations([0,1,2,3,4]):
        curr = 1
        for i in range(5):
            curr *= M[sigma[i]][i]
        res += sign(sigma) * curr
    return res

def fun(M):
    f = [bytes_to_long(bytes(FLAG[5*i:5*(i+1)], 'utf-8')) for i in range(5)]
    F = [
        [0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0],
    ]
    for i in range(5):
        F[i][i] = f[i]

    try:
        R = np.matmul(F, M)
        return np.trace(R) # return sum along the diagonals

    except:
        print("[WAT] You're trying too hard, try something simpler")
        return None

def main():
    print("[WAT] Welcome")
    M = inputs() # generates a diagonal matrix with entries of our choice
    if M is None:
        print("[WAT] You tried something weird...")
        return
    elif check(M) == 0:
        print("[WAT] It's not going to be that easy...")
        return

    res = fun(M)
    if res == None:
        print("[WAT] You tried something weird...")
        return
    print(f"[WAT] Have fun: {res}")

if __name__ == "__main__":
    main()
```

`main()` first calls `inputs()`, which prompts us for inputs. Our input is then used as diagonal entries for a matrix M: `M[i][i] = int(input(f"[WAT] u{i + 1} = "))`

Then our matrix is checked using `check(M)`. If `check(M) == 0`, our inputs are rejected. Looking at `check()`, it is using a permutation algorithm to calculate the determinant of the matrix and returns it. Since our matrix is diagonal, its determinant is the product of the diagonal entries. Hence to pass the check, none of our inputs can be 0. 

After the check, the server prints `fun(M)`. The line 

```python
f = [bytes_to_long(bytes(FLAG[5*i:5*(i+1)], 'utf-8')) for i in range(5)]
```

first breaks the flag into 5 groups of 5 bytes each. Then, each group is converted to a long, giving us an array of 5 longs. Following this, we have:

```python
F = [
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
]
for i in range(5):
    F[i][i] = f[i]
```

which takes the longs in `f` and uses them as diagonal entries for `F`.

`fun()` then does 

```python
R = np.matmul(F, M)
return np.trace(R) # return sum along the diagonals
```

So it multiplies the 5x5 diagonal matrix `F` (representing the flag) with our given 5x5 diagonal matrix `M`, obtaining another 5x5 diagonal matrix `R`. Then we are given the sum of `R`'s diagonal entries.

$$
R\_{5\times5}=\begin{bmatrix}
f\_0 & 0 & 0 & 0 & 0\\
0 & f\_1 & 0 & 0 & 0\ 0 & 0 & f\_2 & 0 & 0 \ 0 & 0 & 0 & f\_3 & 0 \ 0 & 0 & 0 & 0 & f\_4
\end{bmatrix}\begin{bmatrix}
m\_0 & 0 & 0 & 0 & 0\\
0 & m\_1 & 0 & 0 & 0\ 0 & 0 & m\_2 & 0 & 0 \ 0 & 0 & 0 & m\_3 & 0 \ 0 & 0 & 0 & 0 & m\_4
\end{bmatrix}=\begin{bmatrix}
f\_0m\_0 & 0 & 0 & 0 & 0\\
0 & f\_1m\_1 & 0 & 0 & 0\ 0 & 0 & f\_2m\_2 & 0 & 0 \ 0 & 0 & 0 & f\_3m\_3 & 0 \ 0 & 0 & 0 & 0 & f\_4m\_4
\end{bmatrix}
$$

Therefore,

$$
res=f\_0m\_0+f\_1m\_1+f\_2m\_2+f\_3m\_3+f\_4m\_4
$$

Even if none of our $$m$$'s can be 0, we can still obtain the different values of $$f$$! In one connection we can set $$m\_0=2,m\_1=m\_2=m\_3=m\_4=1$$, which would give us $$res\_0=2f\_0+f\_1+f\_2+f\_3+f\_4$$ and in another connection we can set $$m\_0=m\_1=m\_2=m\_3=m\_4=1$$, giving us $$res\_1=f\_0+f\_1+f\_2+f\_3+f\_4$$. We can obtain $$f\_0$$ by calculating $$res\_0 - res\_1$$! And repeat this process to obtain $$f\_1,f\_2,f\_3$$ and $$f\_4$$. Then, we can use `long_to_bytes` from `Crypto.Util.number` to retrieve the bytes within each group.

```python
from pwn import *
from Crypto.Util.number import long_to_bytes

context.log_level = "debug"

arr = [1,1,1,1,1]

elems = []

for i in range(5):
    p = remote("without-a-trace.chal.uiuc.tf", 1337, ssl=True)
    new_arr = [1,1,1,1,1]
    new_arr[i] += 1
    for j in range(5):
        p.sendlineafter(b"= ", str(new_arr[j]).encode())
    res = p.recvline()
    res = int(res[16:-1].decode())
    p.close()
    p = remote("without-a-trace.chal.uiuc.tf", 1337, ssl=True)
    for j in range(5):
        p.sendlineafter(b"= ", str(arr[j]).encode())
    res2 = p.recvline()
    res2 = int(res2[16:-1].decode())
    p.close()
    elems.append(res - res2)

print(elems)
flag = b""
for x in elems:
    flag += long_to_bytes(x)

print(flag) # uiuctf{tr4c1ng_&&_mult5!}
```