Tokyo Westerns CTF 2020 - writeups.




[Rev] Reversing iS Amazing

It is a warmup chall, Given a rsa file, a 64 bit executable.
Decompiled the executable with ghidra.
undefined8 FUN_00100a6a(int param_1,long param_2)
{
int iVar1;
undefined8 uVar2;
size_t sVar3;
long lVar4;
undefined8 *puVar5;
undefined8 *puVar6;
long in_FS_OFFSET;
EVP_PKEY *local_b10;
rsa_st *local_b08;
BIO *local_b00;
undefined local_af8;
undefined local_af7;
undefined local_af6;
undefined local_af5;
undefined local_af4;
undefined local_af3;
undefined local_af2;
undefined local_af1;
undefined local_af0;
undefined local_aef;
undefined local_aee;
undefined local_aed;
undefined local_aec;
undefined local_aeb;
undefined local_aea;
undefined local_ae9;
undefined local_ae8;
undefined local_ae7;
undefined local_ae6;
undefined local_ae5;
undefined local_ae4;
undefined local_ae3;
undefined local_ae2;
undefined local_ae1;
undefined local_ae0;
undefined local_adf;
undefined local_ade;
undefined local_add;
undefined local_adc;
undefined local_adb;
undefined local_ada;
undefined local_ad9;
undefined local_ad8;
undefined local_ad7;
undefined local_ad6;
undefined local_ad5;
undefined local_ad4;
undefined local_ad3;
undefined local_ad2;
undefined local_ad1;
undefined local_ad0;
undefined local_acf;
undefined local_ace;
undefined local_acd;
undefined local_acc;
undefined local_acb;
undefined local_aca;
undefined local_ac9;
undefined local_ac8;
undefined local_ac7;
undefined local_ac6;
undefined local_ac5;
undefined local_ac4;
undefined local_ac3;
undefined local_ac2;
undefined local_ac1;
undefined local_ac0;
undefined local_abf;
undefined local_abe;
undefined local_abd;
undefined local_abc;
undefined local_abb;
undefined local_aba;
undefined local_ab9;
undefined local_ab8;
undefined local_ab7;
undefined local_ab6;
undefined local_ab5;
undefined local_ab4;
undefined local_ab3;
undefined local_ab2;
undefined local_ab1;
undefined local_ab0;
undefined local_aaf;
undefined local_aae;
undefined local_aad;
undefined local_aac;
undefined local_aab;
undefined local_aaa;
undefined local_aa9;
undefined local_aa8;
undefined local_aa7;
undefined local_aa6;
undefined local_aa5;
undefined local_aa4;
undefined local_aa3;
undefined local_aa2;
undefined local_aa1;
undefined local_aa0;
undefined local_a9f;
undefined local_a9e;
undefined local_a9d;
undefined local_a9c;
undefined local_a9b;
undefined local_a9a;
undefined local_a99;
undefined local_a98;
undefined local_a97;
undefined local_a96;
undefined local_a95;
undefined local_a94;
undefined local_a93;
undefined local_a92;
undefined local_a91;
undefined local_a90;
undefined local_a8f;
undefined local_a8e;
undefined local_a8d;
undefined local_a8c;
undefined local_a8b;
undefined local_a8a;
undefined local_a89;
undefined local_a88;
undefined local_a87;
undefined local_a86;
undefined local_a85;
undefined local_a84;
undefined local_a83;
undefined local_a82;
undefined local_a81;
undefined local_a80;
undefined local_a7f;
undefined local_a7e;
undefined local_a7d;
undefined local_a7c;
undefined local_a7b;
undefined local_a7a;
undefined local_a79;
undefined8 local_a78 [76];
uchar local_818 [1024];
uchar local_418 [1032];
long local_10;
local_10 = *(long *)(in_FS_OFFSET + 0x28);
local_af8 = 0x6f;
local_af7 = 0x86;
local_af6 = 0xe4;
local_af5 = 0x96;
local_af4 = 0x29;
local_af3 = 0xbe;
local_af2 = 0x8a;
local_af1 = 0x5e;
local_af0 = 0x21;
local_aef = 0xe2;
local_aee = 0xc0;
local_aed = 0xda;
local_aec = 0x25;
local_aeb = 0xb7;
local_aea = 0x95;
local_ae9 = 0xe0;
local_ae8 = 0x5f;
local_ae7 = 10;
local_ae6 = 0x6c;
local_ae5 = 0xe9;
local_ae4 = 0x44;
local_ae3 = 0xdb;
local_ae2 = 0x12;
local_ae1 = 0x4c;
local_ae0 = 0x3a;
local_adf = 0x6c;
local_ade = 0x14;
local_add = 0x87;
local_adc = 0xc6;
local_adb = 0x36;
local_ada = 0x6b;
local_ad9 = 0x6d;
local_ad8 = 0x95;
local_ad7 = 6;
local_ad6 = 0x1c;
local_ad5 = 0x2d;
local_ad4 = 0x11;
local_ad3 = 0x9e;
local_ad2 = 0xf8;
local_ad1 = 0x72;
local_ad0 = 0xcc;
local_acf = 0x9b;
local_ace = 0x74;
local_acd = 0x87;
local_acc = 0x73;
local_acb = 0xa7;
local_aca = 0x52;
local_ac9 = 0x72;
local_ac8 = 0xc;
local_ac7 = 0x5b;
local_ac6 = 0x92;
local_ac5 = 0x8d;
local_ac4 = 0x7c;
local_ac3 = 0xa9;
local_ac2 = 0x35;
local_ac1 = 0xeb;
local_ac0 = 0xc5;
local_abf = 0xd6;
local_abe = 0x1e;
local_abd = 0x1c;
local_abc = 0x9e;
local_abb = 0x7e;
local_aba = 0xd3;
local_ab9 = 0x6e;
local_ab8 = 0x43;
local_ab7 = 0x35;
local_ab6 = 0x93;
local_ab5 = 0xd0;
local_ab4 = 0x6c;
local_ab3 = 0x26;
local_ab2 = 0xb4;
local_ab1 = 0x95;
local_ab0 = 0xe5;
local_aaf = 0x99;
local_aae = 0x28;
local_aad = 99;
local_aac = 0x5e;
local_aab = 0xeb;
local_aaa = 0xad;
local_aa9 = 0x40;
local_aa8 = 0xce;
local_aa7 = 0x26;
local_aa6 = 0x67;
local_aa5 = 0xf7;
local_aa4 = 0x32;
local_aa3 = 0xb2;
local_aa2 = 3;
local_aa1 = 0xd;
local_aa0 = 0x30;
local_a9f = 0x24;
local_a9e = 0x93;
local_a9d = 0x84;
local_a9c = 0x3a;
local_a9b = 0x19;
local_a9a = 0xac;
local_a99 = 0x6f;
local_a98 = 0x11;
local_a97 = 0xbb;
local_a96 = 0xb;
local_a95 = 0x5b;
local_a94 = 0x41;
local_a93 = 0x8d;
local_a92 = 0x9d;
local_a91 = 0x49;
local_a90 = 0x1a;
local_a8f = 0xb1;
local_a8e = 0x21;
local_a8d = 0xd9;
local_a8c = 0x79;
local_a8b = 0x43;
local_a8a = 0xbc;
local_a89 = 0x83;
local_a88 = 0x1c;
local_a87 = 0x36;
local_a86 = 0x98;
local_a85 = 0xb9;
local_a84 = 0x5a;
local_a83 = 0x53;
local_a82 = 0xd9;
local_a81 = 0xf4;
local_a80 = 0xa3;
local_a7f = 0x99;
local_a7e = 0x34;
local_a7d = 0x67;
local_a7c = 0xa2;
local_a7b = 0x8b;
local_a7a = 0xce;
local_a79 = 6;
lVar4 = 0x4c;
puVar5 = &DAT_00101100;
puVar6 = local_a78;
while (lVar4 != 0) {
lVar4 = lVar4 + -1;
*puVar6 = *puVar5;
puVar5 = puVar5 + 1;
puVar6 = puVar6 + 1;
}
if (param_1 == 2) {
sVar3 = strlen(*(char **)(param_2 + 8));
memcpy(local_418,*(void **)(param_2 + 8),(long)(int)sVar3);
local_b08 = (rsa_st *)0x0;
local_b10 = (EVP_PKEY *)0x0;
local_b00 = (BIO *)0x0;
local_b00 = BIO_new_mem_buf(local_a78,0x260);
if (local_b00 == (BIO *)0x0) {
uVar2 = 1;
}
else {
local_b10 = d2i_PrivateKey_bio(local_b00,&local_b10);
if (local_b10 == (EVP_PKEY *)0x0) {
uVar2 = 1;
}
else {
local_b08 = EVP_PKEY_get1_RSA(local_b10);
if (local_b08 == (rsa_st *)0x0) {
uVar2 = 1;
}
else {
iVar1 = RSA_private_encrypt((int)sVar3,local_418,local_818,(RSA *)local_b08,1);
if (iVar1 < 0) {
uVar2 = 1;
}
else {
iVar1 = memcmp(local_818,&local_af8,(long)iVar1);
if (iVar1 == 0) {
puts("Correct!");
}
else {
puts("Incorrect!");
}
RSA_free((RSA *)local_b08);
EVP_PKEY_free(local_b10);
BIO_free_all(local_b00);
uVar2 = 0;
}
}
}
}
}
else {
printf("./rsa TWCTF{*****************************}");
uVar2 = 1;
}
if (local_10 != *(long *)(in_FS_OFFSET + 0x28)) {
/* WARNING: Subroutine does not return */
__stack_chk_fail();
}
return uVar2;
}
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
JavaScript
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).
#include <stdio.h>
#include <string.h>
#include <openssl/x509v3.h>
#include <openssl/objects.h>
#include <openssl/pem.h>
#include <openssl/evp.h>
int main(int argc, char const *argv[]) {
char chunk[609] = {48, 130, 2, 92, 2, 1, 0, 2, 129, 129, 0, 174, 104, 97, 212, 115, 166, 51, 49, 51, 194, 26, 94, 190, 245, 236, 144, 234, 133, 119, 234, 194, 219, 98, 115, 181, 41, 93, 194, 187, 58, 60, 209, 80, 187, 212, 212, 158, 238, 51, 221, 59, 48, 69, 60, 235, 190, 241, 31, 103, 228, 5, 92, 139, 156, 111, 58, 86, 186, 226, 186, 236, 154, 167, 208, 67, 237, 188, 39, 80, 70, 200, 64, 146, 46, 135, 182, 36, 227, 244, 195, 27, 214, 189, 173, 85, 164, 81, 100, 35, 16, 209, 108, 20, 253, 53, 168, 24, 161, 159, 171, 51, 20, 249, 62, 80, 52, 196, 60, 40, 182, 16, 210, 252, 144, 155, 151, 96, 213, 154, 19, 229, 62, 191, 56, 208, 82, 102, 125, 2, 3, 1, 0, 1, 2, 129, 128, 3, 126, 129, 223, 64, 197, 230, 166, 168, 179, 205, 213, 114, 27, 249, 54, 90, 12, 124, 127, 142, 145, 216, 162, 26, 210, 14, 87, 213, 106, 112, 71, 125, 71, 150, 23, 0, 108, 35, 75, 222, 96, 180, 50, 105, 66, 181, 15, 253, 3, 219, 123, 164, 44, 105, 42, 17, 12, 195, 120, 29, 63, 103, 247, 66, 188, 186, 56, 174, 204, 38, 219, 202, 129, 30, 73, 253, 250, 6, 189, 50, 131, 59, 158, 102, 30, 155, 139, 79, 245, 4, 94, 129, 218, 105, 219, 145, 126, 15, 150, 105, 161, 81, 147, 179, 80, 244, 132, 16, 216, 73, 36, 198, 176, 81, 43, 188, 122, 224, 38, 223, 66, 239, 187, 155, 87, 226, 221, 2, 65, 0, 217, 139, 131, 169, 246, 189, 148, 204, 239, 147, 52, 90, 53, 238, 139, 179, 78, 50, 65, 124, 198, 156, 42, 94, 240, 151, 194, 69, 61, 143, 104, 30, 52, 183, 176, 95, 175, 94, 158, 253, 65, 184, 238, 92, 139, 90, 202, 78, 183, 81, 122, 222, 87, 33, 55, 170, 64, 158, 35, 10, 81, 29, 237, 107, 2, 65, 0, 205, 60, 203, 57, 126, 206, 223, 159, 210, 200, 103, 157, 100, 134, 34, 211, 229, 188, 63, 10, 51, 50, 184, 224, 63, 220, 160, 127, 230, 166, 252, 135, 223, 78, 134, 128, 129, 58, 228, 224, 94, 225, 65, 26, 208, 244, 184, 194, 78, 0, 145, 154, 26, 240, 30, 56, 159, 202, 85, 226, 163, 45, 205, 183, 2, 65, 0, 129, 41, 123, 119, 235, 94, 174, 61, 107, 53, 12, 77, 79, 94, 29, 165, 205, 20, 187, 155, 24, 212, 217, 183, 90, 195, 207, 253, 138, 74, 93, 248, 41, 54, 178, 202, 108, 246, 18, 17, 173, 246, 221, 215, 38, 138, 54, 57, 188, 79, 237, 82, 155, 138, 198, 97, 24, 82, 139, 221, 113, 66, 2, 151, 2, 64, 18, 173, 81, 161, 45, 213, 13, 172, 177, 181, 227, 24, 3, 169, 225, 73, 127, 66, 158, 74, 3, 86, 190, 84, 73, 251, 125, 239, 165, 193, 212, 129, 88, 229, 0, 128, 121, 66, 46, 201, 236, 88, 123, 96, 65, 91, 195, 228, 138, 204, 170, 115, 103, 184, 42, 71, 228, 226, 184, 230, 35, 11, 108, 9, 2, 64, 62, 118, 100, 99, 212, 131, 176, 14, 98, 70, 184, 31, 13, 227, 48, 62, 233, 22, 64, 121, 143, 138, 119, 48, 102, 174, 37, 230, 195, 59, 117, 126, 171, 126, 255, 74, 9, 224, 56, 236, 182, 93, 235, 179, 133, 89, 192, 109, 85, 78, 168, 5, 195, 113, 239, 96, 24, 219, 43, 109, 204, 30, 146, 252};
BIO *key ;
EVP_PKEY *pkey;
RSA *rsakey;
unsigned char encrypted[4098]={ 111, 134, 228, 150, 41, 190, 138, 94, 33, 226, 192, 218, 37, 183, 149, 224, 95, 10, 108, 233, 68, 219, 18, 76, 58, 108, 20, 135, 198, 54, 107, 109, 149, 6, 28, 45, 17, 158, 248, 114, 204, 155, 116, 135, 115, 167, 82, 114, 12, 91, 146, 141, 124, 169, 53, 235, 197, 214, 30, 28, 158, 126, 211, 110, 67, 53, 147, 208, 108, 38, 180, 149, 229, 153, 40, 99, 94, 235, 173, 64, 206, 38, 103, 247, 50, 178, 3, 13, 48, 36, 147, 132, 58, 25, 172, 111, 17, 187, 11, 91, 65, 141, 157, 73, 26, 177, 33, 217, 121, 67, 188, 131, 28, 54, 152, 185, 90, 83, 217, 244, 163, 153, 52, 103, 162, 139, 206, 6 };
int enc_len = strlen(encrypted);
unsigned char decrypted[4098]={};
int dec_len;
key = BIO_new_mem_buf(chunk, 609);
if (key) {
pkey = d2i_PrivateKey_bio(key, &pkey);
if (pkey){
rsakey = EVP_PKEY_get1_RSA(pkey);
if (rsakey){
if(RSA_check_key(rsakey)) {
PEM_write_PrivateKey(stdout,pkey,NULL,NULL,0,0,NULL);
printf("\n[+] Trying to decrypt !...\n");
dec_len = RSA_public_decrypt(enc_len, encrypted, decrypted, rsakey, 1);
if(dec_len == -1) {
printf("[-] Failed to decrypt the data.\n");
} else {
printf("\n[+] Data decrypted\n");
printf("[+] Data Length = %d\n",dec_len);
printf("[+] Data = %s\n",decrypted);
}
RSA_free(rsakey);
EVP_PKEY_free(pkey);
BIO_free_all(key);
} else {
printf("[+] RSA key is invalid. :(\n");
}
} else {
printf("[-] Failed to RSA key from pkey\n");
}
} else {
printf("[-] Failed to load pkey from bio\n");
}
} else {
printf("[-] Failed to create key BIO\n");
}
return 0;
}
view raw rsa-reverse.c hosted with ❤ by GitHub
$ 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}
$ 
Python
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
using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Linq;
using System.Security.Cryptography;
using System.Text;
using System.Threading.Tasks;
namespace Core
{
// Token: 0x02000004 RID: 4
public static class Check
{
// Token: 0x06000007 RID: 7 RVA: 0x00002764 File Offset: 0x00000964
private static uint Func1(uint x, int n)
{
uint num = 1U;
for (int i = 0; i < n; i++)
{
num *= x;
}
return num;
}
// Token: 0x06000008 RID: 8 RVA: 0x00002784 File Offset: 0x00000984
private static uint Func2(List<uint> coefficients, uint x, int pos)
{
if (pos == -1)
{
return 0U;
}
uint num = coefficients[pos] * Check.Func1(x, pos);
return num + Check.Func2(coefficients, x, pos - 1);
}
// Token: 0x06000009 RID: 9 RVA: 0x000027B8 File Offset: 0x000009B8
private static uint Func3()
{
byte[] array = new byte[4];
using (RNGCryptoServiceProvider rngcryptoServiceProvider = new RNGCryptoServiceProvider())
{
rngcryptoServiceProvider.GetBytes(array);
}
return BitConverter.ToUInt32(array, 0);
}
// Token: 0x0600000A RID: 10 RVA: 0x000027FC File Offset: 0x000009FC
public static bool Func4(string flag)
{
ParallelOptions parallelOptions = new ParallelOptions
{
MaxDegreeOfParallelism = 4
};
byte[] bytes = Encoding.ASCII.GetBytes(flag);
int length = flag.Length;
if ((length & 3) != 0)
{
Array.Resize<byte>(ref bytes, length + (4 - (length & 3)));
}
for (int i = length; i < bytes.Length; i++)
{
bytes[i] = 0;
}
if (bytes.Length != Check.equations_arr.GetLength(0) * 4)
{
return false;
}
object lockObj = new object();
ConcurrentBag<bool> checkResults = new ConcurrentBag<bool>();
List<List<uint>> list = new List<List<uint>>();
for (int j = 0; j < Check.equations_arr.GetLength(0); j++)
{
List<uint> list2 = new List<uint>();
list2.Add(BitConverter.ToUInt32(bytes, j * 4));
for (int k = 0; k < Check.equations_arr.GetLength(1); k++)
{
list2.Add(Check.equations_arr[j, k]);
}
list.Add(list2);
}
Parallel.ForEach<List<uint>>(list, parallelOptions, delegate(List<uint> equation)
{
object lockObj = lockObj;
lock (lockObj)
{
uint num = Check.Func3();
for (int l = 0; l < 10000; l++)
{
num = Check.Func2(equation, num, equation.Count - 2);
}
checkResults.Add(num == equation[equation.Count - 1]);
}
});
return Enumerable.All<bool>(checkResults.ToArray(), (bool x) => x);
}
// Token: 0x04000001 RID: 1
private static readonly uint[,] equations_arr = new uint[,]
{
{
2921822136U,
1060277104U,
2035740900U,
823622198U,
210968592U,
3474619224U,
3252966626U,
1671622480U,
1174723606U,
3830387194U,
2514889364U,
3125636774U,
896423784U,
4164953836U,
2838119626U,
2523117444U,
1385864710U,
3157438448U,
132542958U,
4108218268U,
314662132U,
432653936U,
1147047258U,
1802950730U,
67411056U,
1207641174U,
1920298940U,
2947533900U,
3468512014U,
3485949926U,
3695085832U,
3903653528U
},
{
463101660U,
3469888460U,
2006842986U,
144738028U,
630007230U,
3440652086U,
2322916652U,
2227002010U,
1163469256U,
23859328U,
2322597530U,
3716255122U,
2876706098U,
713374856U,
2345958624U,
3496771192U,
1773957550U,
146382778U,
1141367704U,
1061893394U,
994321632U,
3407332344U,
2240786438U,
2218631702U,
2906647610U,
1919308420U,
2136654012U,
164975906U,
2834189362U,
3118478912U,
3258673870U,
3211411825U
},
{
2558729100U,
1170420958U,
2355877954U,
3593652986U,
2587766164U,
2271696650U,
1560549496U,
132089692U,
2893757564U,
3469624876U,
10109206U,
2948199026U,
4170042296U,
2717317064U,
4210960804U,
93756380U,
2006217436U,
2988057920U,
2251383150U,
226355976U,
579516546U,
3915017586U,
1273838010U,
2852178952U,
4272774672U,
1006507228U,
3595131622U,
1880597220U,
1230996622U,
2542910224U,
917668128U,
1612363977U
},
{
3637139654U,
2593663532U,
649194106U,
4275630476U,
2730487128U,
905133820U,
2868808700U,
1284610026U,
1051455306U,
272375560U,
1219428572U,
163965224U,
3899483864U,
309833108U,
1862243284U,
1919038730U,
3414916994U,
3134382762U,
2018925234U,
3467081876U,
4045123308U,
4244105094U,
4205568254U,
1793827648U,
257732384U,
2092183712U,
3517540150U,
2641565070U,
2181538960U,
2670634300U,
2070334778U,
1995308868U
},
{
561434200U,
2730097174U,
1499965472U,
760244614U,
1588114416U,
521516362U,
2963707630U,
1896166800U,
411250470U,
1601999958U,
2973942456U,
3027806424U,
1238337602U,
1380721280U,
122976200U,
788897864U,
3589391734U,
1987301254U,
1085198712U,
3553616586U,
1994354546U,
1684916442U,
2788234788U,
2641884090U,
612801768U,
1801824798U,
2019943314U,
3304068906U,
849354132U,
44941780U,
3473262708U,
1444837808U
},
{
921974086U,
404262832U,
1353817916U,
764855648U,
2290476820U,
2023815980U,
669786172U,
791841140U,
526348842U,
2979022342U,
3656325786U,
1276970440U,
2424614726U,
1190814714U,
2804417116U,
3654263826U,
3068580996U,
1908493640U,
3101330462U,
792198672U,
1772484794U,
4050408722U,
611660842U,
1610808360U,
431629552U,
2319897718U,
3255085210U,
1426503472U,
1630566802U,
4241881448U,
1606014350U,
636517450U
},
{
2906103140U,
1116553354U,
2279536366U,
3011561210U,
2641603848U,
1646150780U,
192124694U,
611421916U,
3416039786U,
4208848404U,
474397384U,
1491088256U,
3177553844U,
2042765300U,
1653674858U,
1365840538U,
1595225706U,
2705938552U,
3180386458U,
1723055560U,
2280421090U,
1241156010U,
3807390206U,
2595800854U,
2890507242U,
4068903400U,
3923234634U,
2613933834U,
3927909200U,
2149793556U,
3589302752U,
802516900U
},
{
171242408U,
1411016272U,
2890085382U,
624162464U,
3117870816U,
3388454296U,
3869111620U,
948964384U,
1670102044U,
3432346180U,
1670460686U,
3674313702U,
4108083090U,
915550832U,
4249135230U,
411447682U,
2915987712U,
3865207952U,
4017666788U,
275767786U,
2506858524U,
3488718446U,
1995975410U,
566166116U,
1590333384U,
329205954U,
3913164274U,
620615436U,
1464604756U,
269837028U,
963851056U,
2483789524U
},
{
4043184956U,
3569779124U,
3817645374U,
4281618348U,
4144074366U,
3776223584U,
2260112022U,
2417238210U,
4004384546U,
1196429850U,
1429697170U,
3075499898U,
2507660230U,
1342925724U,
3951341456U,
229184726U,
2762396986U,
1612961426U,
986238002U,
1228690306U,
3948701236U,
1378190546U,
3106898794U,
1894874158U,
1488049036U,
3718233910U,
1078939754U,
2355898312U,
2030934192U,
2879370894U,
3017715248U,
1647621107U
},
{
3849716376U,
3412391848U,
420800182U,
156925722U,
3602232204U,
2645326622U,
3864083570U,
1279782822U,
878821008U,
1906288878U,
1396282244U,
1641728726U,
2295751090U,
290937256U,
1958396986U,
2115100470U,
3706945590U,
2885002942U,
1935777480U,
1483762940U,
3589264430U,
3791465274U,
2553819596U,
2050180502U,
1381704584U,
4640270U,
628970046U,
774725214U,
2575508070U,
1330692832U,
1250987676U,
3756982724U
},
{
1460953346U,
1175847424U,
3477700838U,
3783709768U,
1064663570U,
3559971784U,
3802954664U,
2431960456U,
2198986400U,
859802318U,
3783810034U,
1110187920U,
4244034440U,
1796543058U,
902449590U,
160031782U,
3639253664U,
4255746326U,
3339514496U,
218988706U,
4085181614U,
2342973726U,
1391523108U,
1120970708U,
2639842372U,
156321138U,
1587974922U,
3686627774U,
1648124740U,
2095688044U,
293533614U,
3056924137U
},
{
1034259104U,
4077045412U,
789979418U,
961028604U,
2185949320U,
3457364068U,
3532291848U,
2206594748U,
3072062072U,
1796530288U,
1402389280U,
3478769990U,
196567236U,
3940435298U,
2237679842U,
668941406U,
170819894U,
1102049112U,
131349762U,
2512464482U,
4159048294U,
2186098090U,
123947608U,
1742064290U,
1711289746U,
1449132362U,
58078952U,
2976574968U,
1774398264U,
1532589156U,
4089484268U,
4041979478U
},
{
3681899832U,
4208608358U,
1951338724U,
3772673566U,
3160075610U,
1422174080U,
2431526454U,
529884656U,
2722748162U,
236192616U,
2684139926U,
697549902U,
3546454434U,
1921398338U,
1310272304U,
1691292498U,
4134700116U,
720619430U,
2592536546U,
2188997288U,
2461521148U,
455077540U,
1421274126U,
1052585740U,
2383754190U,
1567602170U,
3773864138U,
4036579298U,
2416620860U,
1931099884U,
2051263696U,
310763286U
},
{
1461705722U,
968835462U,
2563821358U,
576185928U,
1613137824U,
940353300U,
652295412U,
1135005196U,
3607866196U,
3307698550U,
3916080186U,
4052934590U,
3991167852U,
3799175976U,
3393348946U,
950814766U,
2174463160U,
2422320256U,
959545514U,
2820210140U,
4284041840U,
3082466322U,
1257510060U,
2676710840U,
127465314U,
3887977956U,
3218198116U,
957094088U,
1409365960U,
2217798938U,
277108032U,
2579736592U
},
{
3776055232U,
823459706U,
1913270776U,
1721511850U,
633354432U,
3901765934U,
2089017122U,
1103648570U,
3791238880U,
1686042442U,
1567720048U,
2924815412U,
1695861754U,
3641036796U,
1208391908U,
1593134050U,
1674288590U,
2322785248U,
2472109738U,
3572933674U,
3828029068U,
1641647380U,
4116180236U,
3884220004U,
3146594508U,
3587030908U,
3451856524U,
2965945264U,
162291656U,
2061732942U,
1551591510U,
4014200221U
},
{
3406794856U,
3181753846U,
2984888850U,
1748566984U,
1311737108U,
3415409722U,
2398926736U,
2006269026U,
3117725174U,
2901254050U,
2733703362U,
1595001962U,
106879068U,
3933136528U,
245096038U,
666024082U,
134803296U,
1657783988U,
3429228290U,
2120419114U,
2879013028U,
9653606U,
305704628U,
3793128986U,
369835124U,
2274924880U,
4233339440U,
2224753480U,
2427854922U,
1808326540U,
1833703938U,
2391461119U
},
{
1827597388U,
454565514U,
1282880792U,
561174442U,
3610484436U,
2327669348U,
765794442U,
3705161518U,
1715916192U,
292859360U,
183730846U,
3298097994U,
3535037218U,
2904849282U,
348832662U,
1856773750U,
3618335118U,
3017093112U,
3354956190U,
3208811970U,
897522204U,
2835584374U,
3097985334U,
2108903166U,
3230714490U,
2597789348U,
1597521406U,
1663858876U,
94923994U,
883872856U,
3230397040U,
3420763893U
},
{
4065160224U,
2129787468U,
3456903512U,
2860656238U,
2663588170U,
3224900102U,
2827778318U,
2685874320U,
2005737334U,
586304716U,
472376412U,
2938324550U,
3459137716U,
3422216092U,
3082124658U,
1173945064U,
842495374U,
2564495050U,
357433170U,
2050324102U,
1138367532U,
854845936U,
3054001576U,
2465772674U,
2305389082U,
3669610606U,
3527889292U,
3817664802U,
4238531160U,
1556372762U,
777986002U,
1126454981U
},
{
764733144U,
3965849612U,
1668893328U,
2104626056U,
1653642872U,
2883395356U,
3015268318U,
2322404760U,
1185726976U,
1607036694U,
3064704530U,
3639372768U,
1252489394U,
3950622630U,
3889240956U,
233990458U,
2393973872U,
3609439896U,
2108036182U,
152726882U,
3730671578U,
3038534682U,
3388044150U,
3128791454U,
2499312664U,
3396894570U,
2872225186U,
3048419004U,
2864782986U,
3169897264U,
2890258816U,
753842003U
},
{
2403595118U,
2093259638U,
2763900156U,
3772789760U,
3282639530U,
2884294140U,
3879894514U,
2512089226U,
318451120U,
2464691316U,
2179668204U,
795049786U,
326585310U,
1313213364U,
3437852224U,
4055872768U,
1224395344U,
1911910472U,
983774674U,
3804144712U,
3208317764U,
1534290234U,
3243577720U,
617743358U,
378252266U,
3612369740U,
1924240610U,
961715850U,
2058485164U,
1460892148U,
2613095898U,
73199927U
},
{
3093631524U,
2704600210U,
3519611266U,
5414320U,
3358912704U,
2462642760U,
3764896542U,
1253645320U,
4034052234U,
3137650284U,
4083324920U,
2667059126U,
436316958U,
497182460U,
404768030U,
1122443700U,
432434942U,
443290780U,
3487257114U,
2699955512U,
4250049274U,
3991832458U,
1037538700U,
3125332984U,
1533312690U,
1452437348U,
1283257518U,
3946567854U,
716640500U,
2417637998U,
3063327834U,
82885668U
},
{
1985108U,
1694522756U,
4205785758U,
333118606U,
2944637686U,
2196892858U,
4092971632U,
83374602U,
4049383084U,
2980843496U,
1801648602U,
2639009750U,
1944350566U,
3046229260U,
2662687100U,
2423732014U,
4179240348U,
1035280058U,
1015236846U,
3488976898U,
1530833166U,
3723596058U,
4125718292U,
1095267878U,
3635353922U,
2932904358U,
2764606674U,
45921060U,
3107074868U,
4198045636U,
1923836480U,
366302822U
}
};
}
}
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
Python
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
Python

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) ]
Python
Where x is final value, a32..a1 are coefficents. we can get constant in reverse. Boom:)
Lets calculate the constants for all 22 equations.
from Crypto.Util.number import long_to_bytes
def Equation(Coeffs, x, pos):
if pos == -1:
return 0
num = ( Coeffs[pos] * pow(x, pos, MAX) ) % MAX
return ( num + Equation(Coeffs, x, pos-1) ) % MAX
def Get_constant(List, X):
List = [0] + List
val = Equation(List, X, len(List)-2) % MAX
return (List[-1] - val) % MAX
MAX = 2**32
arr = [
[ 2921822136, 1060277104, 2035740900, 823622198, 210968592, 3474619224, 3252966626, 1671622480, 1174723606, 3830387194, 2514889364, 3125636774, 896423784, 4164953836, 2838119626, 2523117444, 1385864710, 3157438448, 132542958, 4108218268, 314662132, 432653936, 1147047258, 1802950730, 67411056, 1207641174, 1920298940, 2947533900, 3468512014, 3485949926, 3695085832, 3903653528 ],
[ 463101660, 3469888460, 2006842986, 144738028, 630007230, 3440652086, 2322916652, 2227002010, 1163469256, 23859328, 2322597530, 3716255122, 2876706098, 713374856, 2345958624, 3496771192, 1773957550, 146382778, 1141367704, 1061893394, 994321632, 3407332344, 2240786438, 2218631702, 2906647610, 1919308420, 2136654012, 164975906, 2834189362, 3118478912, 3258673870, 3211411825 ],
[ 2558729100, 1170420958, 2355877954, 3593652986, 2587766164, 2271696650, 1560549496, 132089692, 2893757564, 3469624876, 10109206, 2948199026, 4170042296, 2717317064, 4210960804, 93756380, 2006217436, 2988057920, 2251383150, 226355976, 579516546, 3915017586, 1273838010, 2852178952, 4272774672, 1006507228, 3595131622, 1880597220, 1230996622, 2542910224, 917668128, 1612363977 ],
[ 3637139654, 2593663532, 649194106, 4275630476, 2730487128, 905133820, 2868808700, 1284610026, 1051455306, 272375560, 1219428572, 163965224, 3899483864, 309833108, 1862243284, 1919038730, 3414916994, 3134382762, 2018925234, 3467081876, 4045123308, 4244105094, 4205568254, 1793827648, 257732384, 2092183712, 3517540150, 2641565070, 2181538960, 2670634300, 2070334778, 1995308868 ],
[ 561434200, 2730097174, 1499965472, 760244614, 1588114416, 521516362, 2963707630, 1896166800, 411250470, 1601999958, 2973942456, 3027806424, 1238337602, 1380721280, 122976200, 788897864, 3589391734, 1987301254, 1085198712, 3553616586, 1994354546, 1684916442, 2788234788, 2641884090, 612801768, 1801824798, 2019943314, 3304068906, 849354132, 44941780, 3473262708, 1444837808 ],
[ 921974086, 404262832, 1353817916, 764855648, 2290476820, 2023815980, 669786172, 791841140, 526348842, 2979022342, 3656325786, 1276970440, 2424614726, 1190814714, 2804417116, 3654263826, 3068580996, 1908493640, 3101330462, 792198672, 1772484794, 4050408722, 611660842, 1610808360, 431629552, 2319897718, 3255085210, 1426503472, 1630566802, 4241881448, 1606014350, 636517450 ],
[ 2906103140, 1116553354, 2279536366, 3011561210, 2641603848, 1646150780, 192124694, 611421916, 3416039786, 4208848404, 474397384, 1491088256, 3177553844, 2042765300, 1653674858, 1365840538, 1595225706, 2705938552, 3180386458, 1723055560, 2280421090, 1241156010, 3807390206, 2595800854, 2890507242, 4068903400, 3923234634, 2613933834, 3927909200, 2149793556, 3589302752, 802516900 ],
[ 171242408, 1411016272, 2890085382, 624162464, 3117870816, 3388454296, 3869111620, 948964384, 1670102044, 3432346180, 1670460686, 3674313702, 4108083090, 915550832, 4249135230, 411447682, 2915987712, 3865207952, 4017666788, 275767786, 2506858524, 3488718446, 1995975410, 566166116, 1590333384, 329205954, 3913164274, 620615436, 1464604756, 269837028, 963851056, 2483789524 ],
[ 4043184956, 3569779124, 3817645374, 4281618348, 4144074366, 3776223584, 2260112022, 2417238210, 4004384546, 1196429850, 1429697170, 3075499898, 2507660230, 1342925724, 3951341456, 229184726, 2762396986, 1612961426, 986238002, 1228690306, 3948701236, 1378190546, 3106898794, 1894874158, 1488049036, 3718233910, 1078939754, 2355898312, 2030934192, 2879370894, 3017715248, 1647621107 ],
[ 3849716376, 3412391848, 420800182, 156925722, 3602232204, 2645326622, 3864083570, 1279782822, 878821008, 1906288878, 1396282244, 1641728726, 2295751090, 290937256, 1958396986, 2115100470, 3706945590, 2885002942, 1935777480, 1483762940, 3589264430, 3791465274, 2553819596, 2050180502, 1381704584, 4640270, 628970046, 774725214, 2575508070, 1330692832, 1250987676, 3756982724 ],
[ 1460953346, 1175847424, 3477700838, 3783709768, 1064663570, 3559971784, 3802954664, 2431960456, 2198986400, 859802318, 3783810034, 1110187920, 4244034440, 1796543058, 902449590, 160031782, 3639253664, 4255746326, 3339514496, 218988706, 4085181614, 2342973726, 1391523108, 1120970708, 2639842372, 156321138, 1587974922, 3686627774, 1648124740, 2095688044, 293533614, 3056924137 ],
[ 1034259104, 4077045412, 789979418, 961028604, 2185949320, 3457364068, 3532291848, 2206594748, 3072062072, 1796530288, 1402389280, 3478769990, 196567236, 3940435298, 2237679842, 668941406, 170819894, 1102049112, 131349762, 2512464482, 4159048294, 2186098090, 123947608, 1742064290, 1711289746, 1449132362, 58078952, 2976574968, 1774398264, 1532589156, 4089484268, 4041979478 ],
[ 3681899832, 4208608358, 1951338724, 3772673566, 3160075610, 1422174080, 2431526454, 529884656, 2722748162, 236192616, 2684139926, 697549902, 3546454434, 1921398338, 1310272304, 1691292498, 4134700116, 720619430, 2592536546, 2188997288, 2461521148, 455077540, 1421274126, 1052585740, 2383754190, 1567602170, 3773864138, 4036579298, 2416620860, 1931099884, 2051263696, 310763286 ],
[ 1461705722, 968835462, 2563821358, 576185928, 1613137824, 940353300, 652295412, 1135005196, 3607866196, 3307698550, 3916080186, 4052934590, 3991167852, 3799175976, 3393348946, 950814766, 2174463160, 2422320256, 959545514, 2820210140, 4284041840, 3082466322, 1257510060, 2676710840, 127465314, 3887977956, 3218198116, 957094088, 1409365960, 2217798938, 277108032, 2579736592 ],
[ 3776055232, 823459706, 1913270776, 1721511850, 633354432, 3901765934, 2089017122, 1103648570, 3791238880, 1686042442, 1567720048, 2924815412, 1695861754, 3641036796, 1208391908, 1593134050, 1674288590, 2322785248, 2472109738, 3572933674, 3828029068, 1641647380, 4116180236, 3884220004, 3146594508, 3587030908, 3451856524, 2965945264, 162291656, 2061732942, 1551591510, 4014200221 ],
[ 3406794856, 3181753846, 2984888850, 1748566984, 1311737108, 3415409722, 2398926736, 2006269026, 3117725174, 2901254050, 2733703362, 1595001962, 106879068, 3933136528, 245096038, 666024082, 134803296, 1657783988, 3429228290, 2120419114, 2879013028, 9653606, 305704628, 3793128986, 369835124, 2274924880, 4233339440, 2224753480, 2427854922, 1808326540, 1833703938, 2391461119 ],
[ 1827597388, 454565514, 1282880792, 561174442, 3610484436, 2327669348, 765794442, 3705161518, 1715916192, 292859360, 183730846, 3298097994, 3535037218, 2904849282, 348832662, 1856773750, 3618335118, 3017093112, 3354956190, 3208811970, 897522204, 2835584374, 3097985334, 2108903166, 3230714490, 2597789348, 1597521406, 1663858876, 94923994, 883872856, 3230397040, 3420763893 ],
[ 4065160224, 2129787468, 3456903512, 2860656238, 2663588170, 3224900102, 2827778318, 2685874320, 2005737334, 586304716, 472376412, 2938324550, 3459137716, 3422216092, 3082124658, 1173945064, 842495374, 2564495050, 357433170, 2050324102, 1138367532, 854845936, 3054001576, 2465772674, 2305389082, 3669610606, 3527889292, 3817664802, 4238531160, 1556372762, 777986002, 1126454981 ],
[ 764733144, 3965849612, 1668893328, 2104626056, 1653642872, 2883395356, 3015268318, 2322404760, 1185726976, 1607036694, 3064704530, 3639372768, 1252489394, 3950622630, 3889240956, 233990458, 2393973872, 3609439896, 2108036182, 152726882, 3730671578, 3038534682, 3388044150, 3128791454, 2499312664, 3396894570, 2872225186, 3048419004, 2864782986, 3169897264, 2890258816, 753842003 ],
[ 2403595118, 2093259638, 2763900156, 3772789760, 3282639530, 2884294140, 3879894514, 2512089226, 318451120, 2464691316, 2179668204, 795049786, 326585310, 1313213364, 3437852224, 4055872768, 1224395344, 1911910472, 983774674, 3804144712, 3208317764, 1534290234, 3243577720, 617743358, 378252266, 3612369740, 1924240610, 961715850, 2058485164, 1460892148, 2613095898, 73199927 ],
[ 3093631524, 2704600210, 3519611266, 5414320, 3358912704, 2462642760, 3764896542, 1253645320, 4034052234, 3137650284, 4083324920, 2667059126, 436316958, 497182460, 404768030, 1122443700, 432434942, 443290780, 3487257114, 2699955512, 4250049274, 3991832458, 1037538700, 3125332984, 1533312690, 1452437348, 1283257518, 3946567854, 716640500, 2417637998, 3063327834, 82885668 ],
[ 1985108, 1694522756, 4205785758, 333118606, 2944637686, 2196892858, 4092971632, 83374602, 4049383084, 2980843496, 1801648602, 2639009750, 1944350566, 3046229260, 2662687100, 2423732014, 4179240348, 1035280058, 1015236846, 3488976898, 1530833166, 3723596058, 4125718292, 1095267878, 3635353922, 2932904358, 2764606674, 45921060, 3107074868, 4198045636, 1923836480, 366302822 ]
]
Str = ''
for List in arr:
X = List[-1]
Y = Get_constant(List, X)
Str += long_to_bytes(Y)[::-1].decode()
flag = "TWCTF{%s}"%Str
print("[+] Flag : ", flag)
Flag : TWCTF{Xm4r1n_15_4bl3_70_6en3r4t3_N471v3_C0d3_w17h_VS_3n73rpr153_bu7_17_c0n741n5_D07_N3t_B1n4ry}


Thanks for reading !...

Comments

Popular posts from this blog

Square CTF 2019 Writeup's

K3RN3L CTF 2021 Rev - `Recurso & Rasm ` writeups

Confidence CTF 2020 `Cat web` challenge writeup