The challenge is written in https://www.uiua.org/, a fun stack based, array-oriented programming language. The source code is:
F ← -@\0 &sc
N ← ⧻F
[⍥(⍉↻1⍉.)] N . F
∵(⇌⬚0↙8⋯)
⍥(◿2+) N /∘
ⁿ↯N⇡8⍉⇌⍉×2
/+⍉
≍ 5_1_1_57_115_29_15_115_53_113_29_23_43_115_119_29_49_23_119_33_41_29_33_35_119_39_7_29_15_119_39_13_113_119_119_63
⍤"Sorry this wasn't the flag 😔"
:/+⍉◫7:/+↯9_4.⇌
≍ 844_662_647_745
⍤"So close but yet it's not the flag 😔"
≍ 512_464_506_521_571_546_543_589_607_619_650_601_632_650_647_605_547_552_584_595_531_554_549_576_567_532_560_576_525_548
⍤"You're soooo close 😔"
"Well done ! 🥳🚩"
It took me some time to understand what each operation was doing and I was able to compose the algorithm in 6 different steps.
At the start:
F ← -@\0 &sc
N ← ⧻F
Read the flag from stdin into F, and compute the length in N.
[⍥(⍉↻1⍉.)] N . F
Step 1 is creating a matrix with N+1 rows, and in each row (i) it rolls the
flag vector of (i):
def step1(flag, nl):
# [⍥(⍉↻1⍉.)] N . F
data = np.zeros((nl + 1, nl))
for i in range(nl + 1):
data[i,:] = np.roll(flag, i)
# print(data)
return data∵(⇌⬚0↙8⋯)
Step 2 converts the 2D matrix into a 3D matrix where each byte is converted to its binary form.
def step2(data: np.ndarray):
# ∵(⇌⬚0↙8⋯)
n, m = data.shape
new_data = np.zeros((n, m, 8))
for i in range(n):
for j in range(m):
bin_value = bin(int(data[i, j]))[2:].rjust(8, "0")
new_data[i, j, :] = np.array(list(map(int, bin_value)))
# print(new_data)
return new_data⍥(◿2+) N /∘
Step 3 performs an addition between the sub matrix of the 3D matrix -> 2D matrix, and apply a modulo 2 to each element in the matrix.
def step3(data: np.ndarray):
# ⍥(◿2+) N /∘
# Sum matrixes, and apply modulo 2
n, m, _ = data.shape
# Some hacks | i dont know why np.sum wasnt working
x = data[0] + data[1]
if n % 2 == 0:
for i in range(2, n, 2):
x += (data[i] + data[i+1])
else:
for i in range(2, n - 1, 2):
x += (data[i] + data[i+1])
x += data[-1]
for i in range(n - 1):
for j in range(8):
x[i, j] = int(x[i, j]) % 2
return xThese first 3 steps are creating a matrix that has in each row the binary value of this xor:
- Row: 0 -> x_1 xor x_2 xor ... xor x_n
- Row: 1 -> x_0 xor x_2 xor x_3 xor ... xor x_n
- Row: 2 -> x_0 xor x_1 xor x_3 xor ... xor x_n
- ...
- Row: n -> x_0 xor x_1 xor ... xor x_{n-1}
Where x_i are the bytes of the flag in position i that we give in input.
ⁿ↯N⇡8⍉⇌⍉×2
This step is just taking the matrix and raising each element to 2^j,
where j is the column number. Unfortunately, the 0 of the first column will become
1 regardless, because 2^0 = 1.
def step4(data: np.ndarray):
# raise to power of x
# print("\nBefore step 4")
# print(data.astype(int))
n, m = data.shape
for i in range(n):
for j in range(m):
data[i, j] = int(data[i, j]) * 2
data = data.transpose()
# reverse
data = np.flip(data, axis=0)
data = data.transpose()
x = np.zeros((n, 8))
for i in range(n):
for j in range(8):
x[i, j] = j
# power.. didnt find documentation xd
for i in range(n):
for j in range(8):
# if data[i,j] != 0:
data[i, j] = data[i, j] ** x[i, j]
data = data.astype(int)
return data/+⍉
This step is transposing the matrix, and summing over the columns.
def step5(data: np.ndarray):
data = data.transpose()
return np.sum(data, axis=0).astype(int)After this part the program is checking the values against an array of values.
:/+⍉◫7:/+↯9_4.⇌
This step is creating a matrix of 9x4 from the original flag, and summing the values over the columns. It compares the sum with an array. Additionally, it also create a sliding window from the flag and checking that the sum of the columns is equal to another array.
def step6(data: np.ndarray):
data = np.flip(data, axis=0)
n = len(data)
new_data = np.zeros((9, 4))
idx = 0
for i in range(9):
for j in range(4):
new_data[i, j] = data[idx]
idx += 1
idx %= n
new_data = np.sum(new_data, axis=0)
data = sliding_window_view(data, 7)
data = data.transpose()
data = np.sum(data, axis=0)
return data, new_dataIt is possible to reverse the step 5,4 because the sum is a sum between values of the form 2^i for i in range(7). The only thing that is not possible is to find the LSB bit, since it is impossible to distinguish the case between a 0 and a 1 in that case.
def reverse4_5(encrypted: np.ndarray):
n = len(encrypted)
data = np.zeros((8, n))
for j, enc in enumerate(encrypted):
bin_enc = list(map(int, bin(enc)[2:].rjust(8, "0")))
bin_enc.reverse()
for i, be in enumerate(bin_enc):
if be == 1:
data[i, j] = 2**i
data = data.transpose()
for i in range(n):
for j in range(8):
if data[i, j] != 0:
data[i, j] = 1
# print(data)
data = data.transpose()
data = np.flip(data, axis=0)
data = data.transpose().astype(int)
data[:,-1] = 0
return dataTo reverse the first three steps (that results in the xor) of the flag values
I've used z3, incorporating also the conditions after Step 6.
def reverse_3_2_1(data, trick=True):
n, m = data.shape
output = []
for i in range(n):
s = ""
for j in range(7):
s += str(data[i, j])
output.append(int(s, 2))
# print("\n".join(list(map(bin, output))))
# for o in output:
# print(chr((o << 1) | 1), end="")
# exit(0)
flag = [BitVec(f"x_{i}", 10) for i in range(n)]
s = Solver()
if not trick:
for i in range(n):
xor_expr = BitVecVal(0, 7)
for j in range(n):
if i != j:
xor_expr ^= Extract(7, 1, flag[j])
s.add(output[i] == xor_expr)
else:
for i in range(n):
s.add(Or(flag[i] == (output[i] << 1) | 1, flag[i] == (output[i] << 1) | 0))
vals = [844, 662, 647, 745][::-1]
for i in range(4):
s.add(vals[i] ==
flag[i]
+ flag[i+4]
+ flag[i+8]
+ flag[i+12]
+ flag[i+16]
+ flag[i+20]
+ flag[i+24]
+ flag[i+28]
+ flag[i+32]
)
last_check = [512, 464, 506, 521, 571, 546, 543, 589, 607, 619, 650, 601, 632, 650, 647, 605, 547, 552, 584, 595, 531, 554, 549, 576, 567, 532, 560, 576, 525, 548][::-1]
for i in range(35, 7, -1):
s.add(flag[i] + flag[i-1] + flag[i-2] + flag[i-3] + flag[i-4] + flag[i-5] + flag[i-6] == last_check[i-6])
if s.check() == sat:
m = s.model()
flag_str = ''.join(chr(m[flag[i]].as_long()) for i in range(n))
print(f"Flag: {flag_str}")
else:
print("rip")There is a trick here that we can perform. The first 5 steps are comparing the computed value against:
check1 = 5_1_1_57_115_29_15_115_53_113_29_23_43_115_119_29_49_23_119_33_41_29_33_35_119_39_7_29_15_119_39_13_113_119_119_63
and normally we could do the decryption process in this way:
def decrypt(check1):
reverse_3_2_1(reverse4_5(check1))
decrypt(check1)It is also possible to do:
data = encrypt(check1)
reverse4_5(data)
Because it will xor out all the flag values between each other and we will have
as output of reverse4_5 the 7 MSB of the flag. After this step it is possible
to guess the flag by evaluating the two options for each byte of the flag.
Both approaces are implemented in the function
import numpy as np
from numpy.lib.stride_tricks import sliding_window_view
from z3 import *
from copy import deepcopy
def step1(flag, nl):
# [⍥(⍉↻1⍉.)] N . F
data = np.zeros((nl + 1, nl))
for i in range(nl + 1):
data[i,:] = np.roll(flag, i)
# print(data)
return data
def reverse1(data):
return data[0, :]
def step2(data: np.ndarray):
# ∵(⇌⬚0↙8⋯)
n, m = data.shape
new_data = np.zeros((n, m, 8))
for i in range(n):
for j in range(m):
bin_value = bin(int(data[i, j]))[2:].rjust(8, "0")
new_data[i, j, :] = np.array(list(map(int, bin_value)))
# print(new_data)
return new_data
def reverse2(new_data: np.ndarray):
# Determine the original 2D array shape from the 3D array
n, m, _ = new_data.shape
# Initialize the original 2D array with zeros
original_data = np.zeros((n, m))
for i in range(n):
for j in range(m):
# Convert the 8-bit binary representation back to a decimal number
bin_value = ''.join(new_data[i, j, :].astype(int).astype(str))
original_data[i, j] = int(bin_value, 2)
return original_data
def step3(data: np.ndarray):
# ⍥(◿2+) N /∘
# Sum matrixes, and apply modulo 2
n, m, _ = data.shape
# Some hacks i dont know why np.sum wasnt working
# print(data)
# print("\nAFTER\n")
x = data[0] + data[1]
if n % 2 == 0:
for i in range(2, n, 2):
x += (data[i] + data[i+1])
else:
for i in range(2, n - 1, 2):
x += (data[i] + data[i+1])
x += data[-1]
for i in range(n - 1):
for j in range(8):
x[i, j] = int(x[i, j]) % 2
return x
def step4(data: np.ndarray):
# raise to power of x
# ⁿ↯N⇡8⍉⇌⍉×2
# print("\nBefore step 4")
# print(data.astype(int))
n, m = data.shape
for i in range(n):
for j in range(m):
data[i, j] = int(data[i, j]) * 2
data = data.transpose()
# reverse
data = np.flip(data, axis=0)
data = data.transpose()
x = np.zeros((n, 8))
for i in range(n):
for j in range(8):
x[i, j] = j
# power.. didnt find documentation xd
for i in range(n):
for j in range(8):
# if data[i,j] != 0:
data[i, j] = data[i, j] ** x[i, j]
data = data.astype(int)
# print("after step 4\n")
# print(data)
return data
def step5(data: np.ndarray):
# /+⍉
data = data.transpose()
# print("\n\ntranspose")
# print(data)
# print(data.shape)
return np.sum(data, axis=0).astype(int)
def step6(data: np.ndarray):
# :/+⍉◫7:/+↯9_4.⇌
data = np.flip(data, axis=0)
n = len(data)
new_data = np.zeros((9, 4))
idx = 0
for i in range(9):
for j in range(4):
new_data[i, j] = data[idx]
idx += 1
idx %= n
new_data = np.sum(new_data, axis=0)
data = sliding_window_view(data, 7)
data = data.transpose()
data = np.sum(data, axis=0)
return data, new_data
def encrypt(flag):
nl = len(flag)
data = step1(flag, nl)
data = step2(data)
data = step3(data)
# print(data)
# print("\nSTEP3 DONE")
data = step4(data)
# print("\n After step4")
# print(data)
data = step5(data)
return data
def crack(data, trick=True):
print("\n")
data = reverse4_5(data)
reverse_3_2_1(data, trick=trick)
def reverse4_5(encrypted: np.ndarray):
n = len(encrypted)
data = np.zeros((8, n))
for j, enc in enumerate(encrypted):
bin_enc = list(map(int, bin(enc)[2:].rjust(8, "0")))
bin_enc.reverse()
for i, be in enumerate(bin_enc):
if be == 1:
data[i, j] = 2**i
data = data.transpose()
for i in range(n):
for j in range(8):
if data[i, j] != 0:
data[i, j] = 1
# print(data)
data = data.transpose()
data = np.flip(data, axis=0)
data = data.transpose().astype(int)
data[:,-1] = 0
print(data)
return data
def reverse_3_2_1(data, trick=True):
n, m = data.shape
output = []
for i in range(n):
s = ""
for j in range(7):
s += str(data[i, j])
output.append(int(s, 2))
# print("\n".join(list(map(bin, output))))
# for o in output:
# print(chr((o << 1) | 1), end="")
# exit(0)
flag = [BitVec(f"x_{i}", 10) for i in range(n)]
s = Solver()
if not trick:
for i in range(n):
xor_expr = BitVecVal(0, 7)
for j in range(n):
if i != j:
xor_expr ^= Extract(7, 1, flag[j])
s.add(output[i] == xor_expr)
else:
for i in range(n):
s.add(Or(flag[i] == (output[i] << 1) | 1, flag[i] == (output[i] << 1) | 0))
vals = [844, 662, 647, 745][::-1]
for i in range(4):
s.add(vals[i] ==
flag[i]
+ flag[i+4]
+ flag[i+8]
+ flag[i+12]
+ flag[i+16]
+ flag[i+20]
+ flag[i+24]
+ flag[i+28]
+ flag[i+32]
)
last_check = [512, 464, 506, 521, 571, 546, 543, 589, 607, 619, 650, 601, 632, 650, 647, 605, 547, 552, 584, 595, 531, 554, 549, 576, 567, 532, 560, 576, 525, 548][::-1]
for i in range(35, 7, -1):
s.add(flag[i] + flag[i-1] + flag[i-2] + flag[i-3] + flag[i-4] + flag[i-5] + flag[i-6] == last_check[i-6])
if s.check() == sat:
m = s.model()
flag_str = ''.join(chr(m[flag[i]].as_long()) for i in range(n))
print(f"Flag: {flag_str}")
else:
print("rip")
def test_alg():
# Test imp
flag = b"GCC{abcdefghijklmnopqrstuvwxyz01234}"
flag = b"GCC{ab}"
for f in flag:
print(bin(f)[2:].rjust(8, "0"))
flag = np.frombuffer(flag, dtype=np.uint8)
print(flag)
print(len(flag))
print("\n")
nl = len(flag)
data = step1(flag, nl)
assert np.array_equal(reverse1(data), flag)
new_data = step2(data)
assert np.array_equal(reverse2(new_data), data)
def main():
first_check = np.array(
[
5, 1, 1, 57, 115, 29, 15, 115, 53, 113, 29, 23, 43, 115, 119, 29, 49, 23,
119, 33, 41, 29, 33, 35, 119, 39, 7, 29, 15, 119, 39, 13, 113, 119, 119, 63
]).astype(int)
crack(first_check, trick=False)
data = encrypt(first_check)
crack(data, trick=True)
if __name__ == "__main__":
main()