Problem Description
Pseudo-C decompilation makes us lazy. Analyze this ASM output from objdump.
Flag: CJ{%s} where %s is an accepted string
Author: farisv
Analysis
Assembly
We are given an assembly, presumably an output from objdump.
Copy 00000000000011c9 <check>:
11c9: endbr64
11cd: push rbp
11ce: mov rbp,rsp
11d1: sub rsp,0x20
11d5: mov QWORD PTR [rbp-0x18],rdi
11d9: mov rax,QWORD PTR [rbp-0x18]
11dd: mov rdi,rax
11e0: call 10a0 <strlen@plt>
11e5: mov DWORD PTR [rbp-0x4],eax
11e8: mov DWORD PTR [rbp-0x8],0x0
11ef: jmp 1226 <check+0x5d>
11f1: mov eax,DWORD PTR [rbp-0x8]
11f4: movsxd rdx,eax
11f7: mov rax,QWORD PTR [rbp-0x18]
11fb: add rax,rdx
11fe: movzx edx,BYTE PTR [rax]
1201: mov eax,DWORD PTR [rbp-0x4]
1204: sub eax,0x1
1207: sub eax,DWORD PTR [rbp-0x8]
120a: movsxd rcx,eax
120d: mov rax,QWORD PTR [rbp-0x18]
1211: add rax,rcx
1214: movzx eax,BYTE PTR [rax]
1217: cmp dl,al
1219: je 1222 <check+0x59>
121b: mov eax,0x0
1220: jmp 123c <check+0x73>
1222: add DWORD PTR [rbp-0x8],0x1
1226: mov eax,DWORD PTR [rbp-0x4]
1229: mov edx,eax
122b: shr edx,0x1f
122e: add eax,edx
1230: sar eax,1
1232: cmp DWORD PTR [rbp-0x8],eax
1235: jl 11f1 <check+0x28>
1237: mov eax,0x1
123c: leave
123d: ret
000000000000123e <main>:
123e: endbr64
1242: push rbp
1243: mov rbp,rsp
1246: add rsp,0xffffffffffffff80
124a: mov rax,QWORD PTR fs:0x28
1251:
1253: mov QWORD PTR [rbp-0x8],rax
1257: xor eax,eax
1259: lea rax,[rbp-0x70]
125d: mov rsi,rax
1260: lea rax,[rip+0xd9d] # 2004 <_IO_stdin_used+0x4>
1267: mov rdi,rax
126a: mov eax,0x0
126f: call 10d0 <__isoc99_scanf@plt>
1274: lea rax,[rbp-0x70]
1278: mov rdi,rax
127b: call 10a0 <strlen@plt>
1280: mov DWORD PTR [rbp-0x74],eax
1283: mov BYTE PTR [rbp-0x75],0x1
1287: cmp BYTE PTR [rbp-0x75],0x0
128b: je 12a4 <main+0x66>
128d: lea rax,[rbp-0x70]
1291: mov rdi,rax
1294: call 11c9 <check>
1299: test al,al
129b: je 12a4 <main+0x66>
129d: mov eax,0x1
12a2: jmp 12a9 <main+0x6b>
12a4: mov eax,0x0
12a9: mov BYTE PTR [rbp-0x75],al
12ac: and BYTE PTR [rbp-0x75],0x1
12b0: cmp BYTE PTR [rbp-0x75],0x0
12b4: je 12c3 <main+0x85>
12b6: cmp DWORD PTR [rbp-0x74],0x15
12ba: jne 12c3 <main+0x85>
12bc: mov eax,0x1
12c1: jmp 12c8 <main+0x8a>
12c3: mov eax,0x0
12c8: mov BYTE PTR [rbp-0x75],al
12cb: and BYTE PTR [rbp-0x75],0x1
12cf: cmp BYTE PTR [rbp-0x75],0x0
12d3: je 130a <main+0xcc>
12d5: cmp DWORD PTR [rbp-0x74],0x14
12d9: jle 130a <main+0xcc>
12db: movzx eax,BYTE PTR [rbp-0x70]
12df: cmp al,0x61
12e1: jne 130a <main+0xcc>
12e3: movzx eax,BYTE PTR [rbp-0x6e]
12e7: cmp al,0x61
12e9: jne 130a <main+0xcc>
12eb: movzx eax,BYTE PTR [rbp-0x6c]
12ef: cmp al,0x61
12f1: jne 130a <main+0xcc>
12f3: movzx eax,BYTE PTR [rbp-0x69]
12f7: cmp al,0x61
12f9: jne 130a <main+0xcc>
12fb: movzx eax,BYTE PTR [rbp-0x67]
12ff: cmp al,0x61
1301: jne 130a <main+0xcc>
1303: mov eax,0x1
1308: jmp 130f <main+0xd1>
130a: mov eax,0x0
130f: mov BYTE PTR [rbp-0x75],al
1312: and BYTE PTR [rbp-0x75],0x1
1316: cmp BYTE PTR [rbp-0x75],0x0
131a: je 133e <main+0x100>
131c: cmp DWORD PTR [rbp-0x74],0x3
1320: jle 133e <main+0x100>
1322: movzx eax,BYTE PTR [rbp-0x6f]
1326: movsx edx,al
1329: movzx eax,BYTE PTR [rbp-0x6d]
132d: movsx eax,al
1330: sub eax,0x1
1333: cmp edx,eax
1335: jne 133e <main+0x100>
1337: mov eax,0x1
133c: jmp 1343 <main+0x105>
133e: mov eax,0x0
1343: mov BYTE PTR [rbp-0x75],al
1346: and BYTE PTR [rbp-0x75],0x1
134a: cmp BYTE PTR [rbp-0x75],0x0
134e: je 1365 <main+0x127>
1350: cmp DWORD PTR [rbp-0x74],0x13
1354: jle 1365 <main+0x127>
1356: movzx eax,BYTE PTR [rbp-0x5d]
135a: cmp al,0x6d
135c: jne 1365 <main+0x127>
135e: mov eax,0x1
1363: jmp 136a <main+0x12c>
1365: mov eax,0x0
136a: mov BYTE PTR [rbp-0x75],al
136d: and BYTE PTR [rbp-0x75],0x1
1371: cmp BYTE PTR [rbp-0x75],0x0
1375: je 138c <main+0x14e>
1377: cmp DWORD PTR [rbp-0x74],0xf
137b: jle 138c <main+0x14e>
137d: movzx eax,BYTE PTR [rbp-0x61]
1381: cmp al,0x70
1383: jne 138c <main+0x14e>
1385: mov eax,0x1
138a: jmp 1391 <main+0x153>
138c: mov eax,0x0
1391: mov BYTE PTR [rbp-0x75],al
1394: and BYTE PTR [rbp-0x75],0x1
1398: cmp BYTE PTR [rbp-0x75],0x0
139c: je 13c0 <main+0x182>
139e: cmp DWORD PTR [rbp-0x74],0x6
13a2: jle 13c0 <main+0x182>
13a4: movzx eax,BYTE PTR [rbp-0x6a]
13a8: movsx edx,al
13ab: movzx eax,BYTE PTR [rbp-0x6b]
13af: movsx eax,al
13b2: sub eax,0x4
13b5: cmp edx,eax
13b7: jne 13c0 <main+0x182>
13b9: mov eax,0x1
13be: jmp 13c5 <main+0x187>
13c0: mov eax,0x0
13c5: mov BYTE PTR [rbp-0x75],al
13c8: and BYTE PTR [rbp-0x75],0x1
13cc: cmp BYTE PTR [rbp-0x75],0x0
13d0: je 13eb <main+0x1ad>
13d2: cmp DWORD PTR [rbp-0x74],0x11
13d6: jle 13eb <main+0x1ad>
13d8: movzx edx,BYTE PTR [rbp-0x68]
13dc: movzx eax,BYTE PTR [rbp-0x5f]
13e0: cmp dl,al
13e2: jne 13eb <main+0x1ad>
13e4: mov eax,0x1
13e9: jmp 13f0 <main+0x1b2>
13eb: mov eax,0x0
13f0: mov BYTE PTR [rbp-0x75],al
13f3: and BYTE PTR [rbp-0x75],0x1
13f7: cmp BYTE PTR [rbp-0x75],0x0
13fb: je 1412 <main+0x1d4>
13fd: cmp DWORD PTR [rbp-0x74],0xa
1401: jle 1412 <main+0x1d4>
1403: movzx eax,BYTE PTR [rbp-0x66]
1407: cmp al,0x63
1409: jne 1412 <main+0x1d4>
140b: mov eax,0x1
1410: jmp 1417 <main+0x1d9>
1412: mov eax,0x0
1417: mov BYTE PTR [rbp-0x75],al
141a: and BYTE PTR [rbp-0x75],0x1
141e: cmp BYTE PTR [rbp-0x75],0x0
1422: je 1441 <main+0x203>
1424: lea rax,[rbp-0x70]
1428: mov rsi,rax
142b: lea rax,[rip+0xbd5] # 2007 <_IO_stdin_used+0x7>
1432: mov rdi,rax
1435: mov eax,0x0
143a: call 10c0 <printf@plt>
143f: jmp 1450 <main+0x212>
1441: lea rax,[rip+0xbc7] # 200f <_IO_stdin_used+0xf>
1448: mov rdi,rax
144b: call 1090 <puts@plt>
1450: mov eax,0x0
1455: mov rdx,QWORD PTR [rbp-0x8]
1459: sub rdx,QWORD PTR fs:0x28
1460:
1462: je 1469 <main+0x22b>
1464: call 10b0 <__stack_chk_fail@plt>
1469: leave
146a: ret This is a really long assembly code. Although this is a reverse engineering challenge, manually analyzing the assembly line-by-line would be too naive considering how long and complicated it is. My approach here is to try and convert this assembly code *back* into binary, so that I can decompile it using tools such as Ghidra and look at the logic more clearly.
Because this is an output from objdump, there are some informations missing, such as the data segments. To retrieve those missing informations, I use the help of an AI. Well, at least I didn't use AI for the entirety of the challenge :)
Here's the "fixed" assembly.
Copy .intel_syntax noprefix
.section .note.GNU-stack,"",@progbits
.section .data
str_input: .string "%s" # Format string for scanf
str_correct: .string "Correct: %s\n" # Format string for correct output
str_wrong: .string "Wrong!" # Format string for wrong output
.section .text
.global main
.type check, @function
.type main, @function
check:
endbr64
push rbp
mov rbp,rsp
sub rsp,0x20
mov QWORD PTR [rbp-0x18],rdi
mov rax,QWORD PTR [rbp-0x18]
mov rdi,rax
call strlen@PLT
mov DWORD PTR [rbp-0x4],eax
mov DWORD PTR [rbp-0x8],0x0
jmp .L2
.L4:
mov eax,DWORD PTR [rbp-0x8]
movsxd rdx,eax
mov rax,QWORD PTR [rbp-0x18]
add rax,rdx
movzx edx,BYTE PTR [rax]
mov eax,DWORD PTR [rbp-0x4]
sub eax,0x1
sub eax,DWORD PTR [rbp-0x8]
movsxd rcx,eax
mov rax,QWORD PTR [rbp-0x18]
add rax,rcx
movzx eax,BYTE PTR [rax]
cmp dl,al
je .L3
mov eax,0x0
jmp .L5
.L3:
add DWORD PTR [rbp-0x8],0x1
.L2:
mov eax,DWORD PTR [rbp-0x4]
mov edx,eax
shr edx,0x1f
add eax,edx
sar eax,1
cmp DWORD PTR [rbp-0x8],eax
jl .L4
mov eax,0x1
.L5:
leave
ret
main:
endbr64
push rbp
mov rbp,rsp
sub rsp,0x80
mov rax,QWORD PTR fs:0x28
mov QWORD PTR [rbp-0x8],rax
xor eax,eax
lea rax,[rbp-0x70]
mov rsi,rax
lea rdi,str_input[rip]
mov eax,0x0
call __isoc99_scanf@PLT
lea rax,[rbp-0x70]
mov rdi,rax
call strlen@PLT
mov DWORD PTR [rbp-0x74],eax
mov BYTE PTR [rbp-0x75],0x1
cmp BYTE PTR [rbp-0x75],0x0
je .L7
lea rax,[rbp-0x70]
mov rdi,rax
call check
test al,al
je .L7
mov eax,0x1
jmp .L8
.L7:
mov eax,0x0
.L8:
mov BYTE PTR [rbp-0x75],al
and BYTE PTR [rbp-0x75],0x1
cmp BYTE PTR [rbp-0x75],0x0
je .L9
cmp DWORD PTR [rbp-0x74],0x15
jne .L9
mov eax,0x1
jmp .L10
.L9:
mov eax,0x0
.L10:
mov BYTE PTR [rbp-0x75],al
and BYTE PTR [rbp-0x75],0x1
cmp BYTE PTR [rbp-0x75],0x0
je .L11
cmp DWORD PTR [rbp-0x74],0x14
jle .L11
movzx eax,BYTE PTR [rbp-0x70]
cmp al,0x61
jne .L11
movzx eax,BYTE PTR [rbp-0x6e]
cmp al,0x61
jne .L11
movzx eax,BYTE PTR [rbp-0x6c]
cmp al,0x61
jne .L11
movzx eax,BYTE PTR [rbp-0x69]
cmp al,0x61
jne .L11
movzx eax,BYTE PTR [rbp-0x67]
cmp al,0x61
jne .L11
mov eax,0x1
jmp .L12
.L11:
mov eax,0x0
.L12:
mov BYTE PTR [rbp-0x75],al
and BYTE PTR [rbp-0x75],0x1
cmp BYTE PTR [rbp-0x75],0x0
je .L13
cmp DWORD PTR [rbp-0x74],0x3
jle .L13
movzx eax,BYTE PTR [rbp-0x6f]
movsx edx,al
movzx eax,BYTE PTR [rbp-0x6d]
movsx eax,al
sub eax,0x1
cmp edx,eax
jne .L13
mov eax,0x1
jmp .L14
.L13:
mov eax,0x0
.L14:
mov BYTE PTR [rbp-0x75],al
and BYTE PTR [rbp-0x75],0x1
cmp BYTE PTR [rbp-0x75],0x0
je .L15
cmp DWORD PTR [rbp-0x74],0x13
jle .L15
movzx eax,BYTE PTR [rbp-0x5d]
cmp al,0x6d
jne .L15
mov eax,0x1
jmp .L16
.L15:
mov eax,0x0
.L16:
mov BYTE PTR [rbp-0x75],al
and BYTE PTR [rbp-0x75],0x1
cmp BYTE PTR [rbp-0x75],0x0
je .L17
cmp DWORD PTR [rbp-0x74],0xf
jle .L17
movzx eax,BYTE PTR [rbp-0x61]
cmp al,0x70
jne .L17
mov eax,0x1
jmp .L18
.L17:
mov eax,0x0
.L18:
mov BYTE PTR [rbp-0x75],al
and BYTE PTR [rbp-0x75],0x1
cmp BYTE PTR [rbp-0x75],0x0
je .L19
cmp DWORD PTR [rbp-0x74],0x6
jle .L19
movzx eax,BYTE PTR [rbp-0x6a]
movsx edx,al
movzx eax,BYTE PTR [rbp-0x6b]
movsx eax,al
sub eax,0x4
cmp edx,eax
jne .L19
mov eax,0x1
jmp .L20
.L19:
mov eax,0x0
.L20:
mov BYTE PTR [rbp-0x75],al
and BYTE PTR [rbp-0x75],0x1
cmp BYTE PTR [rbp-0x75],0x0
je .L21
cmp DWORD PTR [rbp-0x74],0x11
jle .L21
movzx edx,BYTE PTR [rbp-0x68]
movzx eax,BYTE PTR [rbp-0x5f]
cmp dl,al
jne .L21
mov eax,0x1
jmp .L22
.L21:
mov eax,0x0
.L22:
mov BYTE PTR [rbp-0x75],al
and BYTE PTR [rbp-0x75],0x1
cmp BYTE PTR [rbp-0x75],0x0
je .L23
cmp DWORD PTR [rbp-0x74],0xa
jle .L23
movzx eax,BYTE PTR [rbp-0x66]
cmp al,0x63
jne .L23
mov eax,0x1
jmp .L24
.L23:
mov eax,0x0
.L24:
mov BYTE PTR [rbp-0x75],al
and BYTE PTR [rbp-0x75],0x1
cmp BYTE PTR [rbp-0x75],0x0
je .L25
lea rax,[rbp-0x70]
mov rsi,rax
lea rdi,str_correct[rip]
mov eax,0x0
call printf@PLT
jmp .L26
.L25:
lea rdi,str_wrong[rip]
call puts@PLT
.L26:
mov eax,0x0
mov rdx,QWORD PTR [rbp-0x8]
sub rdx,QWORD PTR fs:0x28
je .L28
call __stack_chk_fail@PLT
.L28:
leave
ret Recompilation
This assembly can be saved into a file with the .s file format (let's call it chall.s), then compiled into binary using gcc -no-pie chall.s chall. After successfully compiled, I decompiled it again using Ghidra to see how the assembly would look like in C.
Re-decompilation
Here are the decompilation results, only the important parts and with some modifications & annotations for ease.
check(str)
Copy size_t len;
int i;
len = strlen(str);
i = 0;
while( true ) {
if ((int)len / 2 <= i) {
return 1;
}
if (str[i] != str[((int)len + -1) - i]) break;
i = i + 1;
}
return 0; main()
Copy __isoc99_scanf(&str_input,&l_0);
sVar2 = strlen(&l_0);
len = (int)sVar2;
cVar1 = check(&l_0)
// the length must exactly be 21 & is a palindrome
if ((cVar1 == '\0') || (len != 0x15)) {
valid = false;
}
else {
valid = true;
}
// char [0], [2], [4], [7], [9] must be 'a'
if ((((valid) && (0x14 < len)) && (l_0 == 'a')) &&
(((l_2 == 'a' && (l_4 == 'a')) && ((l_7 == 'a' && (l_9 == 'a')))))) {
valid = true;
}
else {
valid = false;
}
// char [1] = char [3]-1 (-1 char(s) before char[3])
if (((valid) && (3 < len)) && ((int)l_1 == l_3 + -1)) {
valid = true;
}
else {
valid = false;
}
// char [19] must be 'm'
if (((valid) && (0x13 < len)) && (_19 == 'm')) {
valid = true;
}
else {
valid = false;
}
// char [15] must be 'p'
if (((valid) && (0xf < len)) && (l_15 == 'p')) {
valid = true;
}
else {
valid = false;
}
// char [6] = char [5]-4
if (((valid) && (6 < len)) && ((int)l_6 == l_5 + -4)) {
valid = true;
}
else {
valid = false;
}
// char [8] == [17]
if (((valid) && (0x11 < len)) && (l_8 == l_17)) {
valid = true;
}
else {
valid = false;
}
// char [10] must be 'c'
if (((valid) && (10 < len)) && (l_10 == 'c')) {
valid = true;
}
else {
valid = false;
}
if (valid) {
printf("Correct: %s\n",&l_0);
}
else {
puts("Wrong!");
} Solution Breakdown
Seeing the main function, the program's main flow is to validate a string inputted by the user with certain requirements. The program also uses a helper function check, which is a function to check whether a string given is a palindrome. Following the program flow one-by-one, we can construct an acceptable string.
Solution Construction
Check that the length must exactly be 21 & is a palindrome (using check)
Constructed string: _____________________
Check that characters in indices 0, 2, 4, 7, 9 must be 'a'. Because the string has to be a palindrome, we can also put 'a` from the reverse order.
Constructed string: a_a_a__a_a_a_a__a_a_a
Check that the character in index 19 must be 'm'. We can also put 'm' in index 1.
Constructed string: ama_a__a_a_a_a__a_ama
Check that the character in index 15 must be 'p'. We can also put 'p' in index 5.
Constructed string: ama_ap_a_a_a_a_pa_ama
Check that the character in index 10 must be 'c'. This is the middle of the string, so there are no palindrome reflections.
Constructed string: ama_ap_a_aca_a_pa_ama
Check that the character in index 6 is the character in index 5 minus 4. In other words, it is alphabetically 4 characters before the character in index 5. The character in index 5 is 'p', and four characters before 'p' is 'l' (L). We can put it on index 14 too.
Constructed string: ama_apla_aca_alpa_ama
Check that the character in index 1 is the character in index 3 minus 1. The character in index 3 is empty, but the character in index 1 is 'm', which means the character in index 3 must be 'n'. We can put it on index 17 too.
Constructed string: amanapla_aca_alpanama
Check that the character in index 8 is the same as the character in index 17.
Constructed string: amanaplanacanalpanama
Following those requirements, we can retrieve an accepted string: amanaplanacanalpanama.
Flag
CJ{amanaplanacanalpanama}