This is a crazy challenge that drained my team's brains š¢ and we couldn't solve it in time of the CTF š After 2 days of trying to brainstorm, we have finally be able to crack the code, with a little bit of luck š
Since the intended solution will be provided by the author catto after the finals (18/12), which is over ONE MONTH AFTER from when I'm writing these lines (why it gotta take so long catto š š š), I decided to create my own writeup to explain our method of solving this problem š
Glitch in the matrix 2.0 - ISITDTU 2022 Quals - WriteupIntroductionTable of contentsChallengeDescriptionCodeAnalyzing stuffs...How to know the bits of password
?NotationsMatrix1.0Matrix2.0Probability hint Detecting password
Recover the remaining bits in password
Solve code
The server generates a securely random 64-bit hex string password that is kept secret. We as the clients have to guess the secret password to get the flag.
The server gives us hints about the password through the output of the encrypt(password)
, which is a function we can call as many times as we can, each time it seemingly produces a different output despite feeding the same input to the function.
This writeup provides a way to obtain the flag with 8 outputs of encrypt(password)
in a probability of about
āx#!/usr/bin/env python3
from secret import SECRET_BASIS
from secrets import token_hex
import random
import os
import copy
assert len(SECRET_BASIS) == len(SECRET_BASIS[0]) == 128
BASIS = copy.deepcopy(SECRET_BASIS)
def f(M: list[list[int]], C: list[int]) -> list[int]:
v = [0] * len(M[0])
for c, m in zip(C, M):
if c:
v = [x ^ y for x, y in zip(v, m)]
return v
def random_bits(n: int) -> list[int]:
return list(map(int, bin(random.getrandbits(n))[2:].rjust(n, "0")))
def encrypt(message: bytes) -> str:
global BASIS
random.shuffle(BASIS)
M = [b for c in message for b in map(int, "{:08b}".format(c))]
ct = []
for bit in M:
C = random_bits(64)
v = f(BASIS[:64], C) if bit else f(BASIS[64:], C)
ct.extend(v)
ct = "".join(map(str, ct))
return bytes([int(ct[i:i+8], 2) for i in range(0, len(ct), 8)]).hex()
def decrypt(ciphertext: str) -> bytes:
# TODO: implement this pls
pass
def action_prompt() -> int:
print('''============= MENU =============
1. Have a guess
2. Get ciphertext
3. Change password
4. Quit
================================\n''')
try:
option = int(input("Your option> "))
except:
return None
return option
def chall():
try:
password = token_hex(8)
while True:
option = action_prompt()
if option == 1:
user_password = input("Input your password (hex): ")
if user_password == password:
print(f"Is taking the red pill worth it? Here is the truth that you want: {os.environ['FLAG']}.")
else:
print("Guess you can't escape the matrix after all.")
break
elif option == 2:
print(f"Leaky ciphertext: {encrypt(bytes.fromhex(password))}")
elif option == 3:
print("Generating super secure password ...")
password = token_hex(8)
elif option == 4:
print("Maybe the truth is not that important, huh?")
break
else:
print("Invalid option.")
print("\n")
except:
print("An error occured!")
chall()
Let's first dissect everything in the source code to see what it does and how to make sense of the data given to us š If you've already known what to expect, you can hop onto the next section to see the discussion of the solution ā¤ļø
encrypt(message)
converts message
in hex form to its binary form M
as a list of 0 and 1s,
xxxxxxxxxx
def encrypt(message: bytes) -> str:
...
M = [b for c in message for b in map(int, "{:08b}".format(c))]
...
For each bit of M
, it generates a random 64-bit value C
(also a list of 0 and 1s),
xxxxxxxxxx
def random_bits(n: int) -> list[int]:
return list(map(int, bin(random.getrandbits(n))[2:].rjust(n, "0")))
def encrypt(message: bytes) -> str:
...
for bit in M:
C = random_bits(64)
...
calls f(C, [:64])
or f(C, BASIS[64:])
depending on the current bit of M
, appends the result of the call to the ct
variable.
xxxxxxxxxx
def encrypt(message: bytes) -> str:
global BASIS
...
ct = []
for bit in M:
C = random_bits(64)
ct = []
for bit in M:
C = random_bits(64)
v = f(BASIS[:64], C) if bit else f(BASIS[64:], C)
ct.extend(v)
BASIS
is a global variable, a 2-dimensional list with size 128x128 with unknown content whose rows are shuffled in every call to encrypt()
.
xxxxxxxxxx
assert len(SECRET_BASIS) == len(SECRET_BASIS[0]) == 128
BASIS = copy.deepcopy(SECRET_BASIS)
...
def encrypt(message: bytes) -> str:
global BASIS
random.shuffle(BASIS)
...
After loop, ct
is then converted to its hex form and returned to the user. From this code, it is safe to assume that the value of ct
is a list consisting of all 0s and 1s.
xxxxxxxxxx
def encrypt(message: bytes) -> str:
...
ct = []
for bit in M:
...
ct.extend(v)
ct = "".join(map(str, ct))
return bytes([int(ct[i:i+8], 2) for i in range(0, len(ct), 8)]).hex()
Also, it can be deduced from ct
and the type hints and operations of f()
, which is just bunch of repeated XORs of values in v
andM[i]
(M
is BASIS[:64]
or BASIS[64:]
), that BASIS
also consists of 128x128 values of 0s and 1s.
xxxxxxxxxx
def f(M: list[list[int]], C: list[int]) -> list[int]:
v = [0] * len(M[0])
for c, m in zip(C, M):
if c:
v = [x ^ y for x, y in zip(v, m)]
return v
All of these XORs and 2-dimensional arrays and lists of 0s and 1s seem to point everything into viewing those things as addition of matrices and vectors in
BASIS
as a 128x128 matrix in
As for f(M, C)
, there are two ways to view this function:
You can either view it as an operation that produces a 1xn vector v
by multipling a 1xm vector C
with an mxn matrix M
,
or as an operation that generates a linear combination of the rows in M
with coefficients on C
.
I'll choose to see it in the 2nd way because it helps when discussing the solution later š
encrypt(message)
randomizes C
and uses f(BASIS[...], C)
to produce random linear combinations of the first 64 rows of BASIS
or the last 64 rows of BASIS
depending on the current looping bit of M
or message
(0 - first 64, 1 - last 64). All of the resulting vectors are stored in ct
before converted into hex form and returned to the user.
ct
is a list of 64 different 128-dimensional vectors BASIS
or the first 64 rows of BASIS
. Each vector in ct
corresponds to a bit in password
.
Now we know how to view the encrypted password, let's discuss the solution!
password
?In order to get all the bits of password
, we must be able to classify which vector ct
belongs to which vector space. Is BASIS[:64]
(so BASIS[64:]
(so
We don't even have BASIS
, so if we know a particular vector is formed by a set of 64 rows in BASIS
, we can't even tell if that set positions at the top of the matrix or the bottom! The only bet for us is to know which bit is different from which bit by comparing the vector space that spans the corresponding vectors. If we've got the mapping of which bit is different from which bit, we can set one random bit to be 0 and let the mapping does the rest. This gives us the probability of finding the correct answer at
Before moving on, I think I should introduce some notations here to help discussing the next part.
Bit i of password
is
ct
, generated at a-th time we request to get encrypt(password)
.
BASIS
that generates
Based on the rule of this challenge, we can see that in an encrypt
operation:
BASIS[:64]
when BASIS[64:]
when Which leads to these properties:
In Glitch in the matrix 1.0, comparing BASIS[:64]
or BASIS[64:]
.
Because password
doesn't change every-time we call encrypt
and most importantly, BASIS
is not changed in the entire runtime of the program,
This means that we can request 64 encrypt
s to obtain BASIS[:64]
or BASIS[64:]
. In order to verify if
If the rank of this matrix is
In script, we fix password
with probability of
Glitch in the matrix 2.0 is the updated version where BASIS
is shuffled every-time we request a new encrypt(password)
. This means that the property that:
is generated from the same set of 64 vectors as where , or ,
is not correct this time around, which is very sad š. We also cannot refer to BASIS[:64]
and BASIS[64:]
as constants anymore.
After a while, a hint came out from the author:
And we still had no idea what the hell she is talking about until the end of the CTF ā¹ļø
...
And then, a thought comes to my mind:
While it's true that
proving that this is a very, very, very, very, very unlikely event.
This gives me an insight that the sets
This might be the "probability" thing catto was talking about! Also from this another idea is formed!
password
Let's say we generate encrypt(password)
And somehow, for a certain value of
This means that BASIS
except one/some row(s). The remaining row(s) of BASIS
would be present in the set of
And somehow, we can find a set of
So, this matrix
must have rank BASIS
.
If we change just one of
Here comes our mechanism to detect password
. In particular, if we randomize
However, in order for this to work, we need to make sure to choose
It turns out, if scenario 1. occurs more likely, scenario 2. will occur less likely and vice versa, so we need to balance
password
Remember the matrix password
. For every password
that
Then compares
With this information, we can recover password
with a probability of
This piece of code implements what I've just described above, with some small changes:
Constructs
Uses multiprocessing
to find the list
xxxxxxxxxx
from Crypto.Util.number import *
from tqdm import tqdm, trange
from pwn import remote, process
from sage.all import *
from multiprocessing import Process, Queue
import random, time
host = '34.132.73.130'
port = int(8003)
B = 64
N = 128
K = 8
targetRank = N-1
def convertToMatrix(input: bytes):
bits = ''
for byte in input:
bits += f'{byte:08b}'
bits = list(map(int, bits))
bits = [bits[i:i+128] for i in range(0, len(bits), 128)]
return Matrix(GF(2), bits)
class Solver:
# -------------------------------------- CONNECT --------------------------------------
def __init__(self) -> None:
self.io = remote(host, port)
def __del__(self):
self.io.close()
def request(self, data):
if isinstance(data, str):
data = data.encode()
elif not isinstance(data, bytes):
data = str(data).encode()
self.io.send_raw(data + b'\n')
def recvline(self):
return self.io.recvline().strip().decode()
# -------------------------------------- REQUEST --------------------------------------
def get(self, option):
self.io.recvuntil(b'option> ')
self.request(option)
def encrypt(self):
self.get(2)
return convertToMatrix(bytes.fromhex(self.recvline().split(': ')[-1]))
def submit(self, key):
self.get(1)
self.request(key)
def changePassword(self):
self.get(3)
# -------------------------------------- MAIN --------------------------------------
def execOneCore(self, U, Ntries, delta, retQueue, progBar):
choices = list(range(1, B))
for _ in range(Ntries):
random.shuffle(choices)
combination = choices[:N//K + int(N%K != 0) + delta]
P = block_matrix(
[[U[i]] for i in combination]
)
if P.rank() <= targetRank:
retQueue.put([
P.rank(), combination
])
break
if not retQueue.empty():
break
progBar.update()
def findBestComb(self, U, ncores=4, Ntries=100000, delta=2):
# Progress bars
progBars = []
for i in range(ncores):
progBar = tqdm(desc=f'#{i}', total=Ntries)
progBars.append(progBar)
# Hold return values of all cores
retQueue = Queue()
# Create new processes
futures = []
for _ in range(ncores):
futures.append(Process(
target=self.execOneCore,
args=(
U, Ntries, delta,
retQueue,
progBars[_],
)))
# Start all processes
for future in futures:
future.start()
# Wait for all process to finish :)
for future in futures:
future.join()
# Close all progress bars
for progBar in progBars:
progBar.close()
# Get answer!
if not retQueue.empty():
rank, comb = retQueue.get()
return rank, comb
return None, None
def main(self):
M = []
for i in range(K):
M.append(self.encrypt())
U = []
for i in range(B):
u = []
for j in range(K):
u.append([M[j][i, :]])
U.append(block_matrix(u))
print(f"[i] Find combination of vectors that forms a matrix with rank <= {targetRank}...")
rank, comb = self.findBestComb(U, Ntries=100000, delta=2)
if comb == None:
return False
print(f"[i] Best rank: {rank}")
print(f"[i] Best combination: {comb}")
# print(f"[i] Debug matrix:\n{block_matrix([[U[i]] for i in comb], subdivide=False)}")
# Deduce the password bits...
passwordbits = ''
for j in range(B):
if j in comb:
passwordbits += '0'
continue
P = block_matrix(
[[U[i]] for i in comb + [j]]
)
if P.rank() > rank:
passwordbits += '1'
else:
passwordbits += '0'
# Convert it to hex and send to server :)
password = bytes([int(passwordbits[i:i+8], 2) for i in range(0, len(passwordbits), 8)]).hex()
self.submit(password)
print('[i] Password is (maybe):', password)
print('[i] Password bits are (maybe):', passwordbits)
# Get answer from server, which is estimated to be successful at around 1/20...
answer = self.recvline()
print('server>', answer)
if 'Here is the truth that you want' in answer:
return True
return False
cnt = 0
while True:
cnt += 1
solver = Solver()
if solver.main():
break
print(f"[i] Solver took {cnt} times.")