Reverse Engineering
What is Reverse Engineering? Reverse engineering (RE) in computer science is the process of analyzing a compiled, binary application to understand its inner workings, logic, and structure without access to the original source code. In Capture The Flag (CTF) competitions, it involves breaking down software to uncover hidden flags, bypass licensing, or analyze malware, typically using tools like debuggers and disassemblers.
Sega Saturn
In this challenge, as we can see on the main page that there is a text and the flag which is actually a fake flag, the text is telling that “Sega Saturn should be able to Solve this”
After I checked the source code, I discovered an algorithm which is the implementation of LCG standard (Linear Congruential Generator).
17...
18function RNG(seed) {
19 return function() {
20 seed = (seed * 48271) % 2147483647;
21 return seed;
22 };
23}
24...And I also discovered an array named seq contains series of integers.
27...
28 const seq = [697438994, 112812148, 1601952528, 848567091, 1409540622, 719284623, 4183535244, 2852213902, 2109397207, 3611470734, 604567242, 1692610300, 2414225221, 1979551723, 3174382114, 425190723, 1060279654, 4283219352, 1099139615, 3427871953, 2056419824, 103242998, 2789231820, 97749902, 3832000502, 2437931514, 337329827, 1784389836, 1971115025, 2430188600, 420768160, 2890064672, 3927353914, 2033350795, 372941141, 2974609317, 1442092933, 2838369745, 3198352587, 230640255, 2641503210, 1721308159, 3764390994];
29...As we remember on the main page there is a hint, namely “Sega Saturn” which is indicated 32-bit architechture.
The Sega Saturn (セガサターン, Sega Satān) is a 32-bit video game console first released by Sega on November 22, 1994 in Japan, May 11, 1995 in North America, and July 8, 1995 in Europe. It was discontinued in 1998 in North America, Europe, and Australia, and in 2000 in Japan.
Source: Wikipedia
In computer science, signed 32-bit integer has range of data up to $2^{31} - 1$. we know that we need to find each elements of array seq for 32-bit data structure. In the source code before, I saw 1 line which is a little bit crucial.
38...
39 const big = (x << 24) | (rng() & 0xFFFFFF);
40...from this one line, I discovered:
- Bit 31-24 (MSB)
- x « 24 shifting encrypted characters to the leftmost 8-bit.
- Bit 23-0 (LSB)
- rng() & 0xFFFFFF will have an output from LCG, then conduct AND operation with 0xFFFFFF (equals to 24-bit), then placed in the rightmost 24-bit.
- Bitwise (|)
- then the two segments before are combined.
I have known that the creator of this challenge leaks the raw internal state in the lowest 24-bit (right side). From here i have an access to $S_{n+1}$ from 24-bit which has been leaked, then i need to find the $S_{n}$ (initial seed).
The LCG worked in 31-bit space before, but there is 24-bit leaked, it means 7-bit is missing (MSB from RNG state). So, i just need to do recovery state as many as 128 iterations.
How? so we need the reverse operation of modular multiplication, which is modular multiplicative inverse.
If $S_{n+1} \equiv (S_n \cdot a) \pmod{m}$, so $S_n \equiv (S_{n+1} \cdot a^{-1}) \pmod{m}$ which $a^{-1}$ is modular invers from 48271 to 2147483647.
With Python, we can calculate $a^{-1}$ using the following Python script:
10...
11MODULUS = 2147483647
12MULTIPLIER = 48271
13
14INVERSE_MULTIPLIER = pow(MULTIPLIER, -1, MODULUS)
15...To determine the initial seed, I’m using the following Python script:
1seq = [
2 697438994, 112812148, 1601952528, 848567091, 1409540622, 719284623, 4183535244,
3 2852213902, 2109397207, 3611470734, 604567242, 1692610300, 2414225221, 1979551723,
4 3174382114, 425190723, 1060279654, 4283219352, 1099139615, 3427871953, 2056419824,
5 103242998, 2789231820, 97749902, 3832000502, 2437931514, 337329827, 1784389836,
6 1971115025, 2430188600, 420768160, 2890064672, 3927353914, 2033350795, 372941141,
7 2974609317, 1442092933, 2838369745, 3198352587, 230640255, 2641503210, 1721308159,
8 3764390994
9]
10
11MODULUS = 2147483647
12MULTIPLIER = 48271
13
14INVERSE_MULTIPLIER = pow(MULTIPLIER, -1, MODULUS)
15
16leak_lsb = seq[0] & 0xFFFFFF
17recovered_seed = None
18
19for high_bits in range(128):
20 potential_state_curr = (high_bits << 24) | leak_lsb
21 if potential_state_curr >= MODULUS:
22 continue
23
24 s_prev_1 = (potential_state_curr * INVERSE_MULTIPLIER) % MODULUS
25 s_prev_2 = (s_prev_1 * INVERSE_MULTIPLIER) % MODULUS
26 seed_candidate = (s_prev_2 * INVERSE_MULTIPLIER) % MODULUS
27
28 test_state = seed_candidate
29 for _ in range(6):
30 test_state = (test_state * MULTIPLIER) % MODULUS
31
32 if (test_state & 0xFFFFFF) == (seq[1] & 0xFFFFFF):
33 recovered_seed = seed_candidate
34 break
35...After the seed has discovered (313374141), i conduct the decryption process using the following Python script:
35...
36def nibble_swap(byte_input):
37 return ((byte_input & 0x0F) << 4) | ((byte_input & 0xF0) >> 4)
38
39plaintext = ""
40current_rng_state = recovered_seed
41
42for packed_int in seq:
43 r1 = (current_rng_state * MULTIPLIER) % MODULUS
44 r2 = (r1 * MULTIPLIER) % MODULUS
45 r3 = (r2 * MULTIPLIER) % MODULUS
46 current_rng_state = r3
47
48 encrypted_byte = (packed_int >> 24) & 0xFF
49 encrypted_byte ^= (r2 & 0xFF)
50 encrypted_byte = nibble_swap(encrypted_byte)
51
52 adjustment = (r1 % 93) + 33
53 decrypted_char_code = (encrypted_byte - adjustment) % 256
54 plaintext += chr(decrypted_char_code)
55
56print(plaintext)cela@hugo:~$ python3 segasaturn.py
cyberwave{c4n_yoU_5olV3_th1s_l1f3_eQu4t10n}
Grogol
In this challenge I was asked to enter the right input.
cela@hugo:~$ nc 129.226.145.210 317
Input > abcdefg
abcdefg
Your input is inc0rr3ct!
After decompiling the main function (FUN_000103aa), I found that the program limits input to no more than 21 characters.
34...
35lVar6 = FUN_000120f6(auStack_1078,0x1000,PTR_DAT_00088590);
36if (lVar6 != 0) {
37 uVar7 = FUN_0001cc2a(auStack_1078);
38 if (uVar7 < 0x16) {
39...Then the program does not process the input as a whole, but breaks it down into a word (let’s say token) separated by space. the program takes the first token and stores it in an array pointer, then takes the next token.
37...
38 if (uVar7 < 0x16) {
39 pbVar8 = (byte *)FUN_0001d348(auStack_1078,&DAT_00057e98);
40 if (pbVar8 == (byte *)0x0) {
41 lVar6 = 0;
42 }
43 else {
44 ppbVar17 = local_3078;
45 lVar6 = 0;
46 do {
47 *ppbVar17 = pbVar8;
48 lVar6 = (long)((int)lVar6 + 1);
49 pbVar8 = (byte *)FUN_0001d348(0,&DAT_00057e98);
50 if (pbVar8 == (byte *)0x0) break;
51 ppbVar17 = ppbVar17 + 1;
52 } while (lVar6 != 0x3ff);
53 }
54...Each token found is calculated for its checksum value. so the program here initialises hash = 1, then performs XOR and Bit-Shift.
66...
67 if (*local_3078[0] != 0) {
68 uVar7 = 1;
69 pbVar8 = local_3078[0];
70 do {
71 pbVar19 = pbVar8 + (1 - (long)local_3078[0]);
72 *puVar16 = (long)uVar7 >> 1;
73 *(byte **)(gp + -0x7b8) = pbVar19;
74 bVar1 = *pbVar8;
75 pbVar8 = pbVar8 + 1;
76 uVar7 = (ulong)bVar1 ^ (long)uVar7 >> 1;
77 *puVar16 = uVar7;
78 } while (*pbVar8 != 0);
79...Then there is the checksum formula.
78...
79 if (((long)(int)(((uint)*local_3078[0] ^ (uint)pbVar19) << 4) & 0xffU | uVar7 & 0xf) = =
80 0x10) {
81...Here I used Gemini (im too lazy ehe) to map the checksum and found the final target, which was 31337.
| Conditions (Hex) | Ghidra Code | Operation |
|---|---|---|
| 0x11 | lVar10 = lVar10 + 3 | Add 3 |
| 0xf2 | lVar10 = lVar10 * 100 | Multiply by 100 |
| 0xce | lVar10 = lVar10 + 13 | Add 13 |
| 0x27 | lVar10 = lVar10 + 30 | Add 30 |
| 0x6a | lVar10 = lVar10 + 7 | Add 7 |
| 0x7a69 | if (stack == 0x7a69) | Final Target (31337) |
Our goal is to reach the number 31337. Here, we use the following logical calculation:
$((3 \times 100) + 13) \times 100 + 30 + 7 = 31337$
Then I used python to bruteforce the ASCII character to find some sort strings (1-2 chr) that matched the target checksum.
| |
So here we get the output:
| Token | Hex | Operation |
|---|---|---|
| cp | 0x11 | add_3 |
| dh | 0x6a | add_7 |
| md | 0xf2 | mul_100 |
| ni | 0xce | add_13 |
| po | 0x27 | add_30 |
Here we get the tokens that we have to input:
$((cp \times md) + ni) \times md + po + dh = 31337$
cela@hugo:~$ nc 129.226.145.210 317
Input > cp md ni md po dh
cp md ni md po dh
cyberwave{belajar_rev_di_google_aja}
KeygenMe
In this challenge I was asked to enter username and license key.
cela@hugo:~$ ./cyberwave_keygenme
Username: test
License Key: test
Access Denied!
After decompiling the main function (FUN_00101080), I found the variable local_128 for username input and the variable local_a8 for license key input.
28...
29printf("Username: ");
30pcVar7 = fgets((char *)local_128,0x80,stdin);
31...
32 printf("License key: ");
33 pcVar7 = fgets(local_a8,0x80,stdin);
34...And it was also found that the local_a8 input must be 19 characters long with the prefix “CW25” and a dash (-) check at a specific index, indicating that the format for the license key is:
CW25-xxxx-xxxx-xxxx
37...
38 if ((((((sVar8 - 1 < 0x20) && (sVar9 = strlen(local_a8),
39 sVar9 == 0x13
40 )) && (local_a4 == '-')) && ((local_a3[4] == '-' && (local_a3[9] == '-')))) && ((
41 local_a8[0] == 'C'
42 && ((
43 local_a8[1] == 'W'
44 && (
45 local_a8[2] == '2'
46 )))))) && (
47 local_a8[3] == '5'
48 )) {
49 uVar10 = 5;
50...Then, each of the three ‘XXXX’ is split into three parts and stored in their respective variables.
55...
56 local_162 = 0;
57 local_160 = (code *)((ulong)local_160 & 0xffffffffffff0000);
58 local_158[0] = 0;
59...The program here performs the first loop at local_128. The loop runs by reading each byte from local_128 (username).
62...
63 uVar6 = 0x31415926;
64 pbVar14 = local_128;
65 while( true ) {
66 bVar2 = *pbVar14;
67 pbVar14 = pbVar14 + 1;
68 if (bVar2 == 0) break;
69 uVar6 = (uint)bVar2 + uVar6 * 0x21;
70 uVar6 = (uVar6 * 0x80 | uVar6 >> 0x19) ^ uVar6;
71 }
72...In order for the program to print “Access Granted”, the input on local_a8 (license key) which is split into local_162, local_160, local_158 must meet the following conditions.
88...
89 if (((local_162 == (ushort)((ushort)uVar6 ^ (ushort)uVar11)) &&
90 ((ushort)local_160 ==
91 (ushort)(((ushort)(uVar6 << 0xb) | (ushort)(uVar6 >> 0x15)) ^ (ushort)(uVar11 >> 5)
92 ^ 0xbeef))) &&
93 (local_158[0] == (ushort)((ushort)uVar6 * 3 + (short)(uVar11 >> 9) ^ 0xc0de))) {
94 puts("Access Granted!");
95...Then I used this Python script to solve this challenge.
1def generate_key(username):
2 name_bytes = username.encode('ascii')
3 length = len(name_bytes)
4
5 uVar6_initial = 0x31415926
6 for b in name_bytes:
7 uVar6_initial = (b + uVar6_initial * 0x21) & 0xFFFFFFFF
8 uVar6_initial = ((uVar6_initial << 7 | uVar6_initial >> 25) & 0xFFFFFFFF) ^ uVar6_initial
9
10 uVar11 = 0xa53c9e17
11 uVar6 = 0xc0ffee25
12
13 for b in name_bytes:
14 uVar6 = (uVar6 * 0x101 + b) & 0xFFFFFFFF
15 uVar6 = ((uVar6 << 5 | uVar6 >> 27) & 0xFFFFFFFF) ^ 0xa5c3d2e1
16 uVar11 = (((uVar6 >> 3 ^ (b * 0x1f + uVar11) & 0xFFFFFFFF) * 0x11) + 0x3d) & 0xFFFFFFFF
17
18 uVar6 = ((length * 0x27d4eb2d) ^ uVar6) & 0xFFFFFFFF
19 uVar11 = ((uVar6 << 13 | uVar6 >> 19) & 0xFFFFFFFF) ^ uVar11
20
21 part1 = (uVar6 ^ uVar11) & 0xFFFF
22
23 rot_uVar6 = (uVar6 << 11 | uVar6 >> 21) & 0xFFFF
24 part2 = (rot_uVar6 ^ (uVar11 >> 5) ^ 0xbeef) & 0xFFFF
25
26 part3 = ((uVar6 * 3 + (uVar11 >> 9)) ^ 0xc0de) & 0xFFFF
27
28 return f"CW25-{part1:04X}-{part2:04X}-{part3:04X}"
29
30user = input("Enter Username: ")
31key = generate_key(user)
32print(f"License Key: {key}")So here we get the output:
cela@hugo:~$ python3 keygenme.py
Enter Username: cela
License Key: CW25-4FA0-A1AA-8D7A
Then I tried entering the same username and license key.
cela@hugo:~$ ./cyberwave_keygenme
Enter Username: cela
License Key: CW25-4FA0-A1AA-8D7A
Access Granted!
cyberwave{keygenme_easy_medium_2025}