# 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="/files/CMHq7fKBMwfwnbWeERz7" %}

## 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="/files/HH8HHiasgnP2xa6RXUZ0" 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}
=================================================================
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://ctf.zeyu2001.com/2022/tisc-2022/level-2-leaky-matrices.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.