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
2WKV_Whitepaper.pdf
2MB
PDF
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)GF(2)GF(2)
.
Importantly, this is equivalent to
c1[s11s21⋮sn1]+c2[s12s22⋮sn2]+⋯cn[s1ns2n⋮snn]=[c1s11+c2s12+⋯+cns1nc1s21+c2s22+⋯+cns2n⋮c1sn1+c2sn2+⋯+cnsnn]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}c1​⎣⎡​s11​s21​⋮sn1​​⎦⎤​+c2​⎣⎡​s12​s22​⋮sn2​​⎦⎤​+⋯cn​⎣⎡​s1n​s2n​⋮snn​​⎦⎤​=⎣⎡​c1​s11​+c2​s12​+⋯+cn​s1n​c1​s21​+c2​s22​+⋯+cn​s2n​⋮c1​sn1​+c2​sn2​+⋯+cn​snn​​⎦⎤​
​Since we control the challenge bits c, we could leak the result of each column by challenging the server. For example, setting c1=1,c2...n=0c_1=1, c_{2 ... n}=0c1​=1,c2...n​=0
 gives us
[r1r2⋮rn]=[c1s11c1s21⋮c1sn1]\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}⎣⎡​r1​r2​⋮rn​​⎦⎤​=⎣⎡​c1​s11​c1​s21​⋮c1​sn1​​⎦⎤​
​and since we can do the same for all c1...nc_{1...n}c1...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)GF(2)GF(2)
, addition is the same as XOR (hence the use of XOR in the script).
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}
=================================================================
Level 1 - Slay The Dragon
Level 3 - PATIENT0
Last modified 8mo ago