Tokyo Westerns CTF 2020 - writeups.

[*]-challenges
    [+] (Rev - 126 pts) Reversing iS Amazing
    [+] (Rev - 224 pts) Tamarin

Our Team Invaders ended up at 21th position
in `Tokyo Westerns CTF 2020` conducted by `TokyoWesterns team`.

[Rev] Reversing iS Amazing

It is a warmup chall, Given a rsa file, a 64 bit executable.
Decompiled the executable with ghidra. As the binary is dynamically linked, we still have the external library function calls.

BIO_new_mem_buf
d2i_PrivateKey_bio
EVP_PKEY_get1_RSA
RSA_private_encrypt

Those are openssl library API calls, by going through the documentation and code.
in the binary it has an EVP key, Cipher text.
The binary is creating a RSA private key from EVP Key , then encrypting our input and checking with cipher text.
Dumped the EVP Key, Cipher text from the binary. Written a decrypting code with same api calls (as we have private key).

$ gcc rsa-reverse.c -o rev -lssl -lcrypto
$ ./rev 
-----BEGIN PRIVATE KEY-----
MIICdgIBADANBgkqhkiG9w0BAQEFAASCAmAwggJcAgEAAoGBAK5oYdRzpjMxM8Ia
Xr717JDqhXfqwttic7UpXcK7OjzRULvU1J7uM907MEU8677xH2fkBVyLnG86Vrri
uuyap9BD7bwnUEbIQJIuh7Yk4/TDG9a9rVWkUWQjENFsFP01qBihn6szFPk+UDTE
PCi2ENL8kJuXYNWaE+U+vzjQUmZ9AgMBAAECgYADfoHfQMXmpqizzdVyG/k2Wgx8
f46R2KIa0g5X1WpwR31HlhcAbCNL3mC0MmlCtQ/9A9t7pCxpKhEMw3gdP2f3Qry6
OK7MJtvKgR5J/foGvTKDO55mHpuLT/UEXoHaaduRfg+WaaFRk7NQ9IQQ2EkkxrBR
K7x64CbfQu+7m1fi3QJBANmLg6n2vZTM75M0WjXui7NOMkF8xpwqXvCXwkU9j2ge
NLewX69env1BuO5ci1rKTrdRet5XITeqQJ4jClEd7WsCQQDNPMs5fs7fn9LIZ51k
hiLT5bw/CjMyuOA/3KB/5qb8h99OhoCBOuTgXuFBGtD0uMJOAJGaGvAeOJ/KVeKj
Lc23AkEAgSl7d+terj1rNQxNT14dpc0Uu5sY1Nm3WsPP/YpKXfgpNrLKbPYSEa32
3dcmijY5vE/tUpuKxmEYUovdcUIClwJAEq1RoS3VDayxteMYA6nhSX9CnkoDVr5U
Sft976XB1IFY5QCAeUIuyexYe2BBW8Pkisyqc2e4Kkfk4rjmIwtsCQJAPnZkY9SD
sA5iRrgfDeMwPukWQHmPincwZq4l5sM7dX6rfv9KCeA47LZd67OFWcBtVU6oBcNx
72AY2yttzB6S/A==
-----END PRIVATE KEY-----

[+] Trying to decrypt !...

[+] Data decrypted
[+] Data Length = 28
[+] Data = TWCTF{Rivest_Shamir_Adleman}
$ 

Flag : TWCTF{Rivest_Shamir_Adleman}

---

[Rev] Tamarin

Given an apk file. by unpacking it going through files found libmonodroid_bundle_app.so(lib file).
a Xamarin/Monodroid application bundle from which we can unbundle it get DLL files.
which i have learned from past `Alles 2020 CTF` Secret Notes chall , I tried a lot, sadly didn't solved it, due to lack of knowledge on this concept.

Used the tool : https://github.com/tjg1/mono_unbundle
Unpacked , and found a Tamarin.dll file. Used dnSpy to decompile and see the dll file
The code is small. The length is due to 22*32 array of uint 32 numbers.
The code has 4 functions namely, Func1, Func2, Func3, Func4.
Func1 is simply power function. pow(base, exp); Used in Func2
Func2 is a Polynomial equation evaluator by recursion. Solve(Coefficients, X_value, pos)
Func3 is random number generator function
Func4 is the flag checking function, where it uses Func2, Func3

Func4 function (Some Math part TLDR;)

from basics checks, we can know the length of input string 88 (4**22), 22 is length of 2D Array(22 x 32) namely equations_arr.
The 22 * 32 Array is nothing but coefficents of 22 equations.
For each iteration it uses one array from equations_arr and a uint number by combining 4 bytes from our input .

For each iteration

That number constructed from 4 bytes of input is used as the Constant for the equation taken from equations_arr.

f(x) = a32(x**32) + a31(x**31) . . . . . . . . . . + a1(x) + Constant

That constant is our input and a32..a1 are coefficeients given in equation_arr along with final value
Then

x = Func3() # a random number
for i in range(10000):
	x = f(x)  # a32(x**32) + a31(x**31) . . . . . . . . . . + a1(x) + Constant
x == final_value # final check

At first I cant understand how can it manage to get the final value, in spite of random `X` value and only with the correct constant.
To check it, I written identical code in python and testing it on sample values.
The results are surprising as everytime it merging to same value, eventhough with different X value.

Checked how it is happening
And found that, in those 10,000 iterations, it is coming to a fixed point. `x == f(x)`. so the next iterations cant even effect it.
It keeps on repeat that value.

I didn't get why this(coming to fixed point) is happening, it may be something with the modular math. as we have uint (32 bits) which simply means (% 2**32).
Note : But just by assuming all those `22 final values` are also fixed points ` x = f(x) `.
Now we have everything

a32(x**32) + a31(x**31) . . . . . . . . . . + a1(x) + Constant = x
Constant = x - [ a32(x**32) + a31(x**31) . . . . . . . . . . + a1(x) ]

Where x is final value, a32..a1 are coefficents. we can get constant in reverse. Boom:)
Lets calculate the constants for all 22 equations. Flag : TWCTF{Xm4r1n_15_4bl3_70_6en3r4t3_N471v3_C0d3_w17h_VS_3n73rpr153_bu7_17_c0n741n5_D07_N3t_B1n4ry}

Thanks for reading !...