Date: June 12, 2023 rank: 1 team: ProjectSekai
It’s the first writeup since joining the ProjectSekai. I joined the second day after CCE (local ctf organized by NIS). I took some reversing and smart contracts.
NOW ( 11 solve )
1
2
3
4
5
6
7
8
__int64 __fastcall main(int a1, char **a2, char **a3)
{
puts("Obtaining flag...");
flip(dec);
recursive(recursive_first, dec);
puts("Here is the...wait, where did it go-");
return 0LL;
}
It just flip dec (hexadecimal string) and call recursive function. ( I changed the names while analyzing )
1
2
3
4
5
6
7
8
9
for ( i = 0; ; ++i )
{
result = *(i + a1);
if ( !result )
break;
v3 = to_num(*(i + a1));
*(i + a1) = to_hex((15 - v3));
}
return result;
to_num → 0 to ‘0’, to_hex → ‘0’ to 0
the flip function flip all numbers of dec. recursive_first and dec is global variable and looks like this : 780c ... 69
hexademical string.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
if ( strlen(a2) != 1 || *a2 != '1' )
{
if ( is_even(a2) ) // even
{
div_2(a2);
sub_171E(a1, a1);
recursive(a1, a2);
}
else // odd
{
v2 = to_num(*a2);
*a2 = to_hex(v2 - 1);
*dest = 0LL;
v5 = 0LL;
memset(v6, 0, sizeof(v6));
v7 = 0;
v8 = 0;
strcpy(dest, a1);
recursive(a1, a2);
sub_171E(a1, dest);
}
}
recursive function, when a2 is 1, the recursive function end. a2 is used like counter, it is divided into two cases
1
2
3
4
5
6
7
8
9
10
11
if is_even(a2):
sub_1932(a2);
sub_171E(a1,a1);
recursive(a1,a2);
else:
v2 = to_num(*a2);
*a2 = to_hex(v2 - 1);
memset(dest, 0, sizeof(dest));
strcpy(dest, a1);
recursive(a1, a2);
sub_171E(a1, dest);
let’s see sub_1932 first
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
size_t __fastcall sub_1932(const char *a1)
{
char carry; // [rsp+17h] [rbp-19h]
int i; // [rsp+18h] [rbp-18h]
int v4; // [rsp+1Ch] [rbp-14h]
carry = 0;
for ( i = strlen(a1) - 1; i >= 0; --i )
{
v4 = to_num(a1[i]);
if ( carry )
{
carry = 0;
v4 += 0x10;
}
a1[i] = to_hex(v4 / 2);
if ( (v4 & 1) != 0 )
carry = 1;
}
return replace_0_to_NULL(a1);
}
it seem’s to implement divide operation on string representations of numbers.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
unsigned __int64 __fastcall sub_171E(char *a1, char *a2)
{
int i; // [rsp+14h] [rbp-488Ch]
int j; // [rsp+18h] [rbp-4888h]
int v5; // [rsp+1Ch] [rbp-4884h]
char a1_mul[2176]; // [rsp+20h] [rbp-4880h] BYREF
char v7; // [rsp+8A0h] [rbp-4000h] BYREF
__int64 v8; // [rsp+38A0h] [rbp-1000h] BYREF
char v9[8]; // [rsp+4080h] [rbp-820h] BYREF
__int64 v10; // [rsp+4088h] [rbp-818h]
char v11[1008]; // [rsp+4090h] [rbp-810h] BYREF
int v12; // [rsp+4480h] [rbp-420h]
__int16 v13; // [rsp+4484h] [rbp-41Ch]
char *src; // [rsp+4490h] [rbp-410h] BYREF
__int64 v15; // [rsp+4498h] [rbp-408h]
char v16[1008]; // [rsp+44A0h] [rbp-400h] BYREF
int v17; // [rsp+4890h] [rbp-10h]
__int16 v18; // [rsp+4894h] [rbp-Ch]
unsigned __int64 v19; // [rsp+4898h] [rbp-8h]
while ( &v8 != &v7 )
;
v19 = __readfsqword(0x28u);
*v9 = '0';
v10 = 0LL;
memset(v11, 0, sizeof(v11));
v12 = 0;
v13 = 0;
src = '0';
v15 = 0LL;
memset(v16, 0, sizeof(v16));
v17 = 0;
v18 = 0;
for ( i = 0; i <= 15; ++i )
{
strcpy(&a1_mul[1030 * i], &src); // a1*0, a1*1, a1*2 ... a1*15
sub_15BA(&src, a1);
}
for ( j = 0; a2[j]; ++j )
{
v5 = to_num(a2[j]);
strcpy(&src, &a1_mul[1030 * v5]);
if ( j )
sub_1502(&src, j);
sub_15BA(v9, &src);
}
strcpy(a1, v9);
return v19 - __readfsqword(0x28u);
}
in sub_171E, there are two functions, sub_15BA, sub_1502.
sub_15BA → implemented plus operation on string numbers. but subtract if larger than 780c…20a69.
sub_1502 → shift left by second argument. If greater than 780c…20a69, subtract that much.
so sub_171E works like this
1
2
3
4
5
a1_mul -> [ a1*0, a1*1, a1*2, a1*3 ... a1*15 ]
v9 += a1_mul[a2[j]]
v9 += a1_mul[a2[j+1]] << 4
v9 += a1_mul[a2[j+2]] << 8
...
It’s multiply operation on string number. and the result isn’t greater then 780c…20a69. so that function is modular operation.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
if ( strlen(a2) != 1 || *a2 != '1' )
{
if ( is_even(a2) ) // even
{
a2/=2
a1 = a1 * a1 % M
recursive(a1, a2);
}
else // odd
{
a2-=1
backup = a1
recursive(a1, a2);
a1 = a1 * backup % M
}
}
back to recursive funcion. How to turn a recursive function into a loop?
If a2 is even, it updates a1 immediately but if not, it saves a1 and multiply by updated a1. I solved in this way
- if a2 is odd, store the pair a2 and a1. if not, just update the a1.
- starting with the smallest a2 stored, update the a1
solve code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
modulo = "780c9276bf474a488e56d5ec3a4827b8cffeca20cfb3dc5f53b25bc6b4d61152de663e13613222d8b1425a4e3329ac9b302586a0a097e74058466d070fba734ceedde9ef151611e937f249cb4f70e303efc2a96a0b586757a2bb517019aecc9a2cf2bbf6ffc0b496276a2366d2d0131d2829829a100a37e0da3a755aa6ab372430a3c0a666a7a502098a98315684a1c92c53cbafe3d4fbedfc671e1265fbd668c7f399a2371f0c2ad0b16c56ee0478290c34da9cbb8ba6bfc1409c57f5ef1cfaa7517cfe02674479f2f4ec5d1d090f1efa3b04a9d9df178a94c277d8b32a6bf030efe2a7e746c055684bc308c8e5776f0fdf88b52155c149b6810cade8c52f83998f111c773e91e887ce5b2ef1db10ecbc3a5e4aca6a75d426d7334799ebd7cd688fc75de08f7555e791b5e8634a7cdbb1e118ea2e61e287b332f00cf4cafff1b2fa7484aa2eebfb785df0e39dcac7bddb2a085d7bc845c52489202cb48b0e5efcd1ff538df61b6f93578858316fc51be6e5e0eb77fab23b5f94afca48a817f94145c3e66f62a8852e8cbc5de197cf03a7ebf20c6137d9404260b1600e913c946a987d9fd25d98dffc7d0f2b534cee3482789d06191fa10133fda862337cf4e000586f188bcab5d05b8e40726040e7c5aa762b789ed09ff5c0faf39e9e18821cd020f1ca7b16a993219a2172a1af5a78b798ae1522f2f6bfc6657db3b6620a69"
a1 = "72feecd39ab2b416966c16b6cfa3b55ce50ffa5d02dbca44d56377be2d8f00e8f8df5548651b1ea37ffe37b9937a0673b1d5756f057625f76c82a6e9daa180baaef543e3bac57c95326e65315831d76b766d354495a2e233d76bfe80b404c0d254ecdc4107704966d1cd959bb26802a7d505250710047497b5dfde45bd9164700d5d3dfa40900fbaa02ae1a047eaac262d1069211fe0b39d86516dde1fe3144120bcbecf6a0c8a50d068cff5b55a1187765bfefc288f5c511ff217c2f435f2ff4524b513d8625aa87239f287423febb8ada47b0f6aaeac71be7355b4e9b12c20de815a052108edc78325b3b3a993ee4612efd17a30626d375f0669adb2632222c5a922cef0a515d848877b2f440f38b3554decd8fda0327995df2a64a426088389495caf89a540a69d2c048d46a29d9d90a560deb1859898398d46a3fe8070d07a34e1da5f8108c2f0a1012e76f422c09a6847cf9b16653c77bca3e3939e14dc01a2757b32ff0ccf0ab62d28c8266c8e1f47e7e25a444e48ffd4f0288e158a9404947786a11e869b6fdc3204b9fc433ba28ac77775ff4b51b1df668154d32e30b01a0ff5968f9bb7b4f5bc772ffc4b1c5af1859dae67552e077f650842c60f4fe1929468f5a701b66bdd9d01c1ce22496c49091f225a26987e3e0f2d7a7f27ab20fd3448450794835477786f6b9a97bf4d4091c9b261d75d62120138b3104f76"
a2 = "e7787d3f8c184210c0f99dc6ea823ab6334e2d9ae8acaa00d94eed4ef44e68ad76343fea24e2ccfb4ae358a7101e85ae23a3df24149748677b4f7b062a55ad726539dd51844efda612c38edd194d6c6b5117b569bce7a9cbc4b4bc3f73eab892b1795ca60e485aebe900fcdef242c2344d407e9d06b05e77db8c27c37552bd902a4a520f79f3e1a5e9fd3f182f5e16e117bbdbfe3225a45ce956181cc16f166a58abcbe345543709d1703acc8a27d9eaadcf1d67544ce45ce83985d1c5e45cc3a89f46faa80876f906aa444b7a520a9f1d1eec068c559b35b92f062cbae2e5bcc279c3ff93460ea04649696067854b3dd699e92992a8b883e0f4d291bbe79417d5defe75baa3c9de6cef7279d4cb19d1f40eedf90928165f3d4be915e206cdeb732f1fda3c3fd88ca089719cb3ef38c6040602625e466765c47637185605bece27a0640f42d29e78aa233735402c795b8401b70e72fae7e9bb24696b41844e24f3b197a277cf603aa25127028023de12044efa4b020202e2acdb5612e990556599d4c0f9fc37404dcf5d4ab07dc4ba8b0d0e03420a08db3e0a85faa77d2538ba11f64269e7ae049cc83e45780c0ed9f7c101dcf8dac55b5edc04a00a806f496beee6f33680eab37da22061573f8c933226b1a8e3af754ceba20c42786e78a6a30c19e46f5a7e12ce989a67ab84c79a8f3c571e32af64d031bf3b2c65538b4a19"
a1 = int(a1[::-1],16)
a2 = int(a2[::-1],16)
modulo = int(modulo[::-1],16)
a2 = 0x10**1024 - a2 - 1 # flip
def modular_mul(a1,a2):
return (a1*a2)%modulo
ll = {}
while a2 != 1:
if a2&1==1:
ll[a2] = a1
a2-=1
else:
a2//=2
a1 = modular_mul(a1,a1)
keys = sorted(ll.keys())
for k in keys:
a1 = modular_mul(a1,ll[k])
print(bytes.fromhex(hex(a1)[2:]))
SEE{bTw_NOW_1s_riv3st_sH4m1r_Adl3m4n_cAEs4r_sh1Fted_tw3ntY_tWO}
Murky SEEPass (14 solve)
replaced with pictures
XD