Google CTF 2024
Table of Contents
Google CTF 2024 #
Reverse #
not_obfuscate #
Description:
True story: I had planned on learning to write LLVM passes and use them for obfuscation for this year’s gCTF challenge.However, when I compiled this code with optimizations enabled, I decided I didn’t need to write an obfuscator. It’s a crackme, you know the drill. GL HF!
analysis #
After a quick check, I found the code flow is effortless:
First, it reads 32 chars from the console, then converts it from hex bytes. It saves these bytes as a rc4 key. So we know that it takes the 16-byte key from our input.
That key is just used for rc4 to decrypt a given buffer, a.k.a flag.
After that, it converts 16 bytes to an array, also a 4x4 matrix (the matrix is that thing I don’t think about when doing the challenge, so I got stuck while analyzing and guessing that thing).
So, here is the code flow of the challenge:
matrix_input = convert_fromhex()
matrix_temp = func(matrix_input,given_matrix_1)
...// a whole bunch of code with `matrix_temp`...
result = func(matrix_temp,given_matrix_2)
result = substitute(result) // like a AES subbyte
-> compare `result` with the given result [0x345,0x1,0x215...]
To be honest, I didn’t solve the challenge but after a quick check of the src, I can’t believe that the challenge flow is not hard at all, it’s about the math problem. So I decided to test it all.
Okay, just think, if we know that a 16-word array is a matrix, so do_something is probably an operation of the matrix, like add, multiply, inverse,…vv.
So I decided to test it, this one is the input matrix.
import numpy as np
def array_to_matrix(a:list):
return np.matrix([a[0:4],a[4:8],a[8:12],a[12:16]])
inp = [0x201, 0x201, 0x201, 0x201, 0x201, 0x201, 0x201, 0x201, 0x201, 0x201, 0x201, 0x201, 0x201, 0x201, 0x201, 0x201]
inp_matrix = array_to_matrix(inp)
buf1 = [0x49, 0x324, 0x7, 0x22, 0x24b, 0x210, 0x123, 0x17, 0x2b, 0x329, 0x21, 0x3, 0x241, 0x344, 0x330, 0x32a]
given_matrix_1 = array_to_matrix(buf1)
##test
result = inp_matrix+given_matrix_1
result = np.remainder(result,0x400)
print(result)
result = inp_matrix*given_matrix_1
result = np.remainder(result,0x400)
print(result)
Here’s result in python:
[[586 293 520 547]
[ 76 17 804 536]
[556 298 546 516]
[ 66 325 305 299]]
[[256 417 635 870]
[256 417 635 870]
[256 417 635 870]
[256 417 635 870]]
result in IDA:
[586, 293, 520, 547, 76, 17, 804, 536, 556, 298, 546, 516, 66, 325, 305, 299]
So, do_something seems like a matrix add operation. But when I take another add, it seems incorrect:
tmp1 = array_to_matrix([0x248, 0x10a, 0x323, 0x230, 0x125, 0x149, 0x206, 0x132, 0x217, 0x10b, 0x312, 0x220, 0x1a, 0x228, 0x46, 0x307])
tmp2 = array_to_matrix([0x308, 0x227, 0x133, 0x1, 0x120, 0x139, 0x205, 0x100, 0x145, 0x221, 0x29, 0x11a, 0x318, 0x13, 0x11a, 0x16])
print(np.remainder(tmp1,tmp2))
Result:
[[584 266 189 0]
[ 5 16 1 50]
[210 267 7 262]
[ 26 1 70 5]]
Result in IDA:
[323, 804, 6, 561, 581, 549, 11, 562, 780, 812, 827, 826, 805, 571, 259, 784]
Even add operation in a special way, I will explain in rns:
So the correct add is:
def add(a,b):
ret = 0
ret = ((a>>8) + (b>>8))%4
ret <<= 4
ret |= (((a>>4)&0xf)+((b>>4)&0xf))%5
ret <<= 4
ret |= ((a&0xf) + (b&0xf))%13
return ret
print([add(x,y) for x,y in zip(tmp1,tmp2)]) # [323, 804, 6, 561, 581, 549, 11, 562, 780, 812, 827, 826, 805, 571, 259, 784]
Then we know:
add(inp,matrix1)
...whole bunch of code...
add(inp,matrix2)
I found another matrix that I didn’t know while doing this challenge (it looked like an unknown xmmword, so I formatted and renamed it):
Do you think a whole bunch of code means just a simple operation? Yes, that’s it, the matrix multiplied with the other given matrix I found.
Testing
temp_matrix = inp_matrix+given_matrix_1
temp_matrix = np.remainder(temp_matrix,0x400)
after_shit = np.remainder(temp_matrix*another_matrix,0x400)
print(after_shit)
[[ 833 772 481 37]
[ 162 395 832 1005]
[ 708 856 200 72]
[ 651 559 943 164]]
Result in IDA:
Python>result = [idaapi.get_word(0x7FFDDB69FAA0 + i) for i in range(0,32,2)]
Python>print(result)
[584, 266, 803, 560, 293, 329, 518, 306, 535, 267, 786, 544, 26, 552, 70, 775]
It’s not working, am I missing something?
After a quick check, I found that another_matrix is used for later, and I see that just a simple xor operation but in the form of substitution.
def rns_xor_with_buf2(buf):
ret = [0]*16
for i in range(16):
num = buf[i] # decode before xor
a,b,c = num&0xf,(num>>4)&0xf,(num>>8)&0xf
d,e,f = buf2[i]&0xf,(buf2[i]>>4)&0xf,(buf2[i]>>8)&0xf
idx = 0x410 * ((5 * a + b)&0xff) + 0x104 * c + 4 * ((5 * d + e)&0xff) + f
ret[i] = given_words[idx]
return ret
I know it’s xor after checking the src code before it xor before it’s pack and decode the matrix. (matrix using a custom base in range 260, instead of 256)
Keep in mind this, the matrix uses rns, which is like another base.
rns #
Residue number system A residue numeral system (RNS) is a numeral system representing integers by their values modulo several pairwise coprime integers called the moduli. This representation is allowed by the Chinese remainder theorem, which asserts that, if M is the product of the moduli, there is, in an interval of length M, exactly one integer having any given set of modular values. The arithmetic of a residue numeral system is also called multi-modular arithmetic. https://en.wikipedia.org/wiki/Residue_number_system https://personal.utdallas.edu/~ivor/ce6305/m5p.pdf
conv_from_inp[i] = (hex_byte % 13u) | (16 * ((hex_byte % 5u) | (16 * hex_byte) & 0x30));
which means:
input_in_hex = [0x61,0x61,0x61,0x61,...] #'aaaaaaaaa'
matrix = rns(input_in_hex) #[rns(0x61),rns(0x61),rns(0x61),...]
#encode -> [0x12,0x12,......], in base 260
# and the `given_words` also known as `xor_table`
xor_table = [rns(byte_a^ byte_b
not
xor_table = [rns(byte_a) ^ rns(byte_b)]
That’s the reason why I got stuck for a long time…
So, we know the property of xor, then just xor again and we get the original buffer.
to_cmp = after_shit ^ another_matrix
=> after_shit = to_cmp ^ another_matrix
Just get the xor_table from binary, and then I use this function to operate xor.
I’ve tried this one but it didn’t work when I do it again, even if I patch these words into IDA and let it run, still got the wrong answer.
buf2 = [0x1a, 0x12c, 0x24c, 0x11c, 0x12a, 0x137, 0x210, 0x111, 0x242, 0x31b, 0x126, 0x327, 0x329, 0x20b, 0x3, 0x220]
# `another_buffer` a.k.a `buf2`
def rns_xor_with_buf2(buf):
ret = [0]*16
for i in range(16):
num = buf[i]
a,b,c = num&0xf,(num>>4)&0xf,(num>>8)&0xf
d,e,f = buf2[i]&0xf,(buf2[i]>>4)&0xf,(buf2[i]>>8)&0xf
idx = 0x410 * ((5 * a + b)&0xff) + 0x104 * c + 4 * ((5 * d + e)&0xff) + f
ret[i] = given_words[idx]
return ret
So I write another function to xor but just using brute foce, and it work:
def another_xor(buf):
res = []
for i in range(16):
res.append(brute(buf2[i],buf[i]))
return res
def brute(b2,to_cmp):
for hex_byte in range(256):
num = 0
num += hex_byte % 4
num <<= 4
num += hex_byte % 5
num <<= 4
num += hex_byte % 13
a,b,c = num&0xf,(num>>4)&0xf,(num>>8)&0xf
d,e,f = b2&0xf,(b2>>4)&0xf,(b2>>8)&0xf
idx = 0x410 * ((5 * a + b)&0xff) + 0x104 * c + 4 * ((5 * d + e)&0xff) + f
if given_words[idx] == to_cmp:
# print(hex(num),num)
return num
return None
def main():
#recover
recovered = another_xor(to_cmp_w)
print(recovered)
#test
tmp = rns_xor_with_buf2(recovered) # also check in IDA
print(tmp==to_cmp_w)
[771, 282, 38, 267, 39, 299, 819, 576, 770, 843, 529, 32, 837, 323, 315, 257]
True
Now, we have completed step 1, and here’s the flow we got:
tmp = (inp + matrix_1)
sus(tmp) #Whole bunch of Code
tmp = add(tmp,matrix_2)
tmp = xor(tmp, another_matrix)
if tmp == buf:
#we got it
and we have: matrix_1, matrix_2, another_matrix, and buf
Whole bunch of Code? #
The feeling…
RULE 35: It just a matrix operation
Before we reverse, I figure out how it is possible. I mean, How can a simple operation be a bunch of code?
Here’s a simple matrix multiply from programiz but I’m using built-in type: long double instead of int:
#include <iostream>
using namespace std;
int main()
{
long double a[10][10], b[10][10], mult[10][10];
int r1, c1, r2, c2, i, j, k;
cout << "Enter rows and columns for first matrix: ";
cin >> r1 >> c1;
cout << "Enter rows and columns for second matrix: ";
cin >> r2 >> c2;
while (c1!=r2)
{
cout << "Error! column of first matrix not equal to row of second.";
cout << "Enter rows and columns for first matrix: ";
cin >> r1 >> c1;
cout << "Enter rows and columns for second matrix: ";
cin >> r2 >> c2;
}
// Storing elements of first matrix.
cout << endl << "Enter elements of matrix 1:" << endl;
for(i = 0; i < r1; ++i)
for(j = 0; j < c1; ++j)
{
cout << "Enter element a" << i + 1 << j + 1 << " : ";
cin >> a[i][j];
}
// Storing elements of second matrix.
cout << endl << "Enter elements of matrix 2:" << endl;
for(i = 0; i < r2; ++i)
for(j = 0; j < c2; ++j)
{
cout << "Enter element b" << i + 1 << j + 1 << " : ";
cin >> b[i][j];
}
// Initializing elements of matrix mult to 0.
for(i = 0; i < r1; ++i)
for(j = 0; j < c2; ++j)
{
mult[i][j]=0;
}
// Multiplying matrix a and b and storing in array mult.
for(i = 0; i < r1; ++i)
for(j = 0; j < c2; ++j)
for(k = 0; k < c1; ++k)
{
mult[i][j] += a[i][k] * b[k][j];
}
// Displaying the multiplication of two matrix.
cout << endl << "Output Matrix: " << endl;
for(i = 0; i < r1; ++i)
for(j = 0; j < c2; ++j)
{
cout << " " << mult[i][j];
if(j == c2-1)
cout << endl;
}
return 0;
}
So, I compiled with Clang++ and see the different between without optimize and optimize flag enabled:
We easily see that optimization makes the code harder. Even if it is just a built-in type, the challenge is using a custom one, which is almost impossible.
It’s just a point of view from a reverser, here’s more about clang optimize:
https://www.incredibuild.com/blog/compiling-with-clang-optimization-flags https://news.ycombinator.com/item?id=28207207 https://www.reddit.com/r/C_Programming/comments/conavx/clangs_optimizer_is_ridiculously_smart_like/
In the challenge, we see it as SIMD:
https://ftp.cvut.cz/kernel/people/geoff/cell/ps3-linux-docs/CellProgrammingTutorial/BasicsOfSIMDProgramming.html https://www.codeproject.com/Articles/5298048/Using-SIMD-to-Optimize-x86-Assembly-Code-in-Array
We know that the code just doing some simple operations but is optimized.
After a day I figure out what is it. I finally found it just matrix multiply (as I guess) but it was difficult to find the multiplicand (matrix A)
So, to save time I decided to get it from src code (will be updated later).
Here is the complete flow:
A = Matrix_rns([208, 120, 107, 19, 138, 163, 11, 174, 217, 67, 60, 143, 13, 232, 181, 2],conv=True) # from source
B = Matrix_rns([0x49, 0x324, 0x7, 0x22, 0x24b, 0x210, 0x123, 0x17, 0x2b, 0x329, 0x21, 0x3, 0x241, 0x344, 0x330, 0x32a],ls=True) #from IDA
C = Matrix_rns([0x308, 0x227, 0x133, 0x1, 0x120, 0x139, 0x205, 0x100, 0x145, 0x221, 0x29, 0x11a, 0x318, 0x13, 0x11a, 0x16],ls=True)#from IDA
D = Matrix_rns([0x1a, 0x12c, 0x24c, 0x11c, 0x12a, 0x137, 0x210, 0x111, 0x242, 0x31b, 0x126, 0x327, 0x329, 0x20b, 0x3, 0x220],ls=True)#from IDA
#### THE FLOW
inp_matrix = Matrix_rns([0x201, 0x201, 0x201, 0x201, 0x201, 0x201, 0x201, 0x201, 0x201, 0x201, 0x201, 0x201, 0x201, 0x201, 0x201, 0x201],ls=True) # test input with 'aaaaaaaaaaaaaaaaaaaa'
temp = inp_matrix.add(B)
# print(temp.as_list())
temp = temp.mul(A)
# print(temp.as_list())
temp = temp.add(C)
# print(temp.as_list())
result = temp.xor(D)
And here’s the way that I operate xor to get the previous buffer before compare (expected_to_cmp):
from given_words import given_words,L
buf2 = [0x1a, 0x12c, 0x24c, 0x11c, 0x12a, 0x137, 0x210, 0x111, 0x242, 0x31b, 0x126, 0x327, 0x329, 0x20b, 0x3, 0x220]
buf1 = [0 for _ in range(16)]
aftershit = [0x143, 0x324, 0x6, 0x231, 0x245, 0x225, 0xb, 0x232, 0x30c, 0x32c, 0x33b, 0x33a, 0x325, 0x23b, 0x103, 0x310]
to_cmp_w = [0x346,1,0x215,0x4C,0x144,0x44,0x10C,0x301,0x125,0x30,0x309,0x31C,0x42,0x328,0x103,0x332]
assert len(to_cmp_w)==16
def get_index(value):
#rebuild from src
m = [13,5,4]
res = [0]*3
index = 0
for i in range(3):
res[2 - i] = (value >> (4 * i)) & 0xF
for i in range(3):
index += res[2-i]
if i+1 < 3:
index *= m[1-i]
# index &= 0xff
return index
def rns_xor_with_buf2(buf):
ret = [0]*16
for i in range(16):
num = buf[i]
a,b,c = num&0xf,(num>>4)&0xf,(num>>8)&0xf
d,e,f = buf2[i]&0xf,(buf2[i]>>4)&0xf,(buf2[i]>>8)&0xf
idx = 0x410 * ((5 * a + b)&0xff) + 0x104 * c + 4 * ((5 * d + e)&0xff) + f
ret[i] = given_words[idx]
return ret
def another_xor(buf):
res = []
for i in range(16):
res.append(brute(buf2[i],buf[i]))
return res
def brute(b2,to_cmp):
nums = []
for hex_byte in range(256):
num = 0
num += hex_byte % 4
num <<= 4
num += hex_byte % 5
num <<= 4
num += hex_byte % 13
a,b,c = num&0xf,(num>>4)&0xf,(num>>8)&0xf
d,e,f = b2&0xf,(b2>>4)&0xf,(b2>>8)&0xf
idx = 0x410 * ((5 * a + b)&0xff) + 0x104 * c + 4 * ((5 * d + e)&0xff) + f
if given_words[idx] == to_cmp:
# print(hex(num),num)
nums.append(num)
print(nums)
return nums[-1]
def main():
brute(buf2[4],324)
#recover
recovered = another_xor(to_cmp_w)
print(recovered)
#test
tmp = rns_xor_with_buf2(to_cmp_w)
print(tmp)
if __name__=='__main__':
main()
I tried both ways: brute and get xor table, which got me 2 different matrices.
[771, 282, 38, 267, 39, 299, 819, 576, 770, 843, 529, 32, 837, 323, 315, 257]
[771, 282, 38, 267, 76, 299, 819, 576, 770, 843, 529, 32, 837, 323, 315, 257]
I’ve reimplement the rns matrix in python, just need the matrix invert operation.
Here invert from @d4rk9n1ght in sagemath.
def convert_to_1mod(arr):
result = []
for i in arr:
a,b,c = i&0xf, (i>>4)&0xf, (i>>8)&0xf
res = crt([c,b,a], [4,5,13])
result.append(res)
return result
def convert_to_3mod(arr):
result = []
cp = [int(i) for i in arr]
for i in cp:
a,b,c = i %4, i%5, i%13
hehe = a
hehe <<= 4
hehe |= b
hehe <<= 4
hehe |= c
result.append(hehe)
return result
from sage.all import *
gl = GL(3, Zmod(4*5*13))
arr = [48, 3, 803, 838 ,568, 823, 795, 581 ,297, 802, 8, 816, 304, 43, 284, 546]
arr = convert_to_1mod(arr)
A = [arr[:4], arr[4:8], arr[8:12], arr[12:]]
A = Matrix(Zmod(4 * 5 * 13), A)
print(A.is_invertible())
inv_A = A.inverse()
print(A * inv_A)
# print(inv_A)
inv_A_arr = list(inv_A[0]) + list(inv_A[1]) + list(inv_A[2]) + list(inv_A[3])
# print(inv_A_arr)
final = convert_to_3mod(inv_A_arr)
print(final)
output
[811, 276, 795, 9, 295, 561, 306, 825, 295, 309, 842, 844, 580, 842, 279, 313]
Here’s script that recover the input:
A_inv = Matrix_rns([811, 276, 795, 9, 295, 561, 306, 825, 295, 309, 842, 844, 580, 842, 279, 313],ls = True)
print(A.mul(A_inv))
# aftershit = Matrix_rns([0x248, 0x10a, 0x323, 0x230, 0x125, 0x149, 0x206, 0x132, 0x217, 0x10b, 0x312, 0x220, 0x1a, 0x228, 0x46, 0x307],ls=True)
x = aftershit.mul(A_inv)
x = x.sub(B)
x = [x.decode(i) for i in x.as_list()]
print(bytes(x).hex())
output
[[273, 0, 0, 0], [0, 273, 0, 0], [0, 0, 273, 0], [0, 0, 0, 273]]
fcedd5ab42f188b49760fca0d51e6fb1
So, I finally found the correct input but still the wrong key for decryption. It is probably the problem from 2 matrices that I found above.
Also, I tried to brute force the byte in the matrix and got the result:
A_inv = Inverse(Matrix_rns([208, 120, 107, 19, 138, 163, 11, 174, 217, 67, 60, 143, 13, 232, 181, 2],conv=True).as_list())
A_inv = Matrix_rns(A_inv,ls = True)
print("A_inv: ",A_inv.matrix) ### A_inv is correct
enc_flag = b'\xe8M0a\x19\t\x8e\xac\x99\x8a\x8e:\x0f\xf1\xf6%w9t-h#\xc7{~\xa4\xcb\xbe\xee\xc7E\xff\x1c\x8f-m\xcb\xf5b'
for hex_byte in range(256):
num = 0
num += hex_byte % 4
num <<= 4
num += hex_byte % 5
num <<= 4
num += hex_byte % 13
aftershit.matrix[3][1] = num ## the wrong number is at matrix[3][1], I've test by each number of matrix.
x = aftershit.mul(A_inv)
x = x.sub(B)
x = [x.decode(i) for i in x.as_list()]
try:
#print(bytes(x).hex())
arc = ARC4(bytes(x))
flag = arc.decrypt(enc_flag)
if b'CTF' in flag or b'ctf' in flag:
print(flag)
except:
#print(x)
pass
output
A: [[48, 3, 803, 838], [568, 823, 795, 581], [297, 802, 8, 816], [304, 43, 284, 546]]
B: [[73, 804, 7, 34], [587, 528, 291, 23], [43, 809, 33, 3], [577, 836, 816, 810]]
C: [[776, 551, 307, 1], [288, 313, 517, 256], [325, 545, 41, 282], [792, 19, 282, 22]]
D: [[26, 300, 588, 284], [298, 311, 528, 273], [578, 795, 294, 807], [809, 523, 3, 544]]
A_inv: [[811, 276, 795, 9], [295, 561, 306, 825], [295, 309, 842, 844], [580, 842, 279, 313]]
b'Flag: ctf{I_pr0mize_its_jUsT_mAtriCeS}\x00'
Finally got flag: ctf{I_pr0mize_its_jUsT_mAtriCeS}
In my point, it’s the easiest challenge, and not interested at all, but at least, I know that I need to learn more, more, and more math. The new meta of Reverse. Also, I will update the remaining challenge later, pls enjoy.