# Level 2 - Leaky Matrices

## Description

> Looks like PALINDROME implemented their own authentication protocol and cryptosystem to provide a secure handshake between any 2 services or devices. It does not look secure to us, can you take a look at what we have got?
>
> Try to fool their authentication service: nc chal00bq3ouweqtzva9xcobep6spl5m75fucey.ctf.sg 56765

{% file src="<https://3167364547-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MX1bWRlBzHpEPe1TYDD%2Fuploads%2FGKTRLOdUbPT8nGPtYTVl%2F2WKV_Whitepaper.pdf?alt=media&token=e78ed6b5-187e-48f5-9efe-eb39884e5de8>" %}

## Solution

This was a pretty straightforward crypto challenge where a weak authentication scheme allowed the leaking of the secret key through a challenge-response sequence. This relied on the following matrix multiplication in $$GF(2)$$.

<figure><img src="https://3167364547-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MX1bWRlBzHpEPe1TYDD%2Fuploads%2FcD20oyhW9zin16Jnd6Gt%2FScreenshot%202022-09-12%20at%201.36.22%20AM.png?alt=media&#x26;token=511bdfea-650b-45b2-bc8b-331675a3cc8d" alt=""><figcaption></figcaption></figure>

Importantly, this is equivalent to

$$
c\_1
\begin{bmatrix}
s\_{11} \\
s\_{21} \\
\vdots \\
s\_{n1}
\end{bmatrix}
\+
c\_2
\begin{bmatrix}
s\_{12} \\
s\_{22} \\
\vdots \\
s\_{n2}
\end{bmatrix}
\+
\cdots
c\_n
\begin{bmatrix}
s\_{1n} \\
s\_{2n} \\
\vdots \\
s\_{nn}
\end{bmatrix}
=============

\begin{bmatrix}
c\_{1}s\_{11} + c\_{2}s\_{12} + \cdots + c\_{n}s\_{1n} \\
c\_{1}s\_{21} + c\_{2}s\_{22} + \cdots + c\_{n}s\_{2n} \\
\vdots \\
c\_{1}s\_{n1} + c\_{2}s\_{n2} + \cdots + c\_{n}s\_{nn}
\end{bmatrix}
$$

​Since we control the challenge bits *c*, we could leak the result of each column by challenging the server. For example, setting $$c\_1=1, c\_{2 ... n}=0$$ gives us

$$
\begin{bmatrix} 	r\_1 \ 	r\_2 \ 	\vdots \ 	r\_n \end{bmatrix} = \begin{bmatrix} 	c\_{1}s\_{11} \ 	c\_{1}s\_{21} \ 	\vdots \ 	c\_{1}s\_{n1} \end{bmatrix}
$$

​and since we can do the same for all $$c\_{1...n}$$, we could reconstruct the response to any challenge by adding up the relevant column results.

The solution to this challenge is to simply probe the server with `00000001`, `00000010`, ... `10000000`, and when challenged, take the 1-bits and add up their corresponding probed values.

Since this happens in $$GF(2)$$, addition is the same as XOR (hence the use of XOR in the script).

```python
from pwn import *
import re

conn = remote("chal00bq3ouweqtzva9xcobep6spl5m75fucey.ctf.sg", 56765)

def solve():
    rows = []
    for i in range(8):
        conn.recvuntil(b"<-- ")
        binstr = "0" * (8 - i - 1) + "1" + "0" * (i)
        conn.send(binstr.encode() + b"\n")
        resp = conn.recvline().decode()
        match = re.search(r"--> (.*)\n", resp)
        
        rows.append(int(match.group(1), 2))
    
    for i in range(8):
        resp = conn.recvuntil(b"<-- ").decode()
        match = re.search(r"--> (.*)\n", resp)

        challenge = match.group(1)
        result = 0
        for j in range(8):
            if challenge[j] == "1":
                result ^= rows[7 - j]

        conn.send(bin(result)[2:].zfill(8).encode() + b"\n")
    
    conn.interactive()

solve()
```

This gives us the flag.

```
========================
All challenges passed :)
========================
=================================================================
Here is your flag: TISC{d0N7_R0lL_Ur_0wN_cRyp70_7a25ee4d777cc6e9}
=================================================================
```