DEFCON Quals 2018: "pssecure" writeup
In this task, we’re given a core dump of an x86-64 ELF file that has crashed due to a SIGSEGV. Our job is to investigate on the reason of the SIGSEGV and reconstruct the actual program flow calculating a flag.
The reason of the segfault is quite obvious, as gdb tells us:
RAX 0x555555554e9a ◂— inc dword ptr [rax]
RBX 0x555555554e9d ◂— leave
RCX 0x7fffffffec70 ◂— 0x6c69665f73696874 ('this_fil')
RDX 0x7fffffffec94 ◂— 0xdc7ab200791dc20e
RDI 0x7fffffffec70 ◂— 0x6c69665f73696874 ('this_fil')
RSI 0x7fffffffec90 ◂— 0x791dc20eefa46567
R8 0x7ffff7fd7740 ◂— 0x7ffff7fd7740
R9 0x13
R10 0x7ffff7fd7740 ◂— 0x7ffff7fd7740
R11 0x246
R12 0x5555555549d0 ◂— xor ebp, ebp
R13 0x7fffffffed90 ◂— 0x5
R14 0x0
R15 0x0
RBP 0x7fffffffecb0 —▸ 0x5555555552d0 ◂— push r15
RSP 0x7fffffffec38 —▸ 0x5555555552aa ◂— mov eax, 0
RIP 0x555555554e9a ◂— inc dword ptr [rax]
[────────────────────────DISASM───────────────────────────]
► 0x555555554e9a inc dword ptr [rax]
Currently, rax points to non-writable memory within the program’s executable segment causing the inc instruction to fail. Clearly, the execution flow should not end up here.
Cleanup work for IDA
Fortunately, IDA supports coredumps, and so we can start our analysis right away. After a bit of digging, we recognize the main function of the program at address 0x555555554FF7. Interestingly, Hex-Rays refuses to decompile the function, as the stack frame is not cleaned up properly at the (alleged) function end. Furthermore, the pointers of imported glibc functions in the GOT section point to invalid memory. Nevertheless, common sense lets us reconstruct them by statically looking at the function call sequences, the parameters and the contents of the strtab:
/tmp/askjaneaboutthewhale/ps-sec
/tmp/askjaneaboutthewhale/ps-sec
/tmp/askjaneaboutthewhale/ps-sec
/lib/x86_64-linux-gnu/libdl-2.26.so
/lib/x86_64-linux-gnu/libdl-2.26.so
/lib/x86_64-linux-gnu/libc-2.26.so
/lib/x86_64-linux-gnu/libc-2.26.so
/lib/x86_64-linux-gnu/libcrypto.so.1.0.0
/lib/x86_64-linux-gnu/libcrypto.so.1.0.0
/lib/x86_64-linux-gnu/ld-2.26.so
/lib/x86_64-linux-gnu/ld-2.26.so
/lib/x86_64-linux-gnu/ld-2.26.so
ELF
/lib64/ld-linux-x86-64.so.2
GNU
GNU
!V4
libcrypto.so.1.0.0
_ITM_deregisterTMCloneTable
__gmon_start__
_ITM_registerTMCloneTable
MD5
libc.so.6
strcpy
exit
sprintf
fopen
strncpy
__stack_chk_fail
fgets
strlen
fseek
fclose
malloc
fwrite
atoi
__cxa_finalize
strcmp
__libc_start_main
OPENSSL_1.0.0
GLIBC_2.4
GLIBC_2.2.5
Thusly, after cleaning up the binary and declaring function arguments to IDA and Hex-Rays, the PLT looks like the following
load:00005555555548C0 printf proc near ; CODE XREF: load_noise+8Fp
load:00005555555548C0 ; get_alignment+31p
load:00005555555548C0 ; get_alignment+6Bp
load:00005555555548C0 ; get_alignment+A3p
load:00005555555548C0 ; get_alignment+D7p
load:00005555555548C0 ; calculate_flag+68p
load:00005555555548C0 ; calculate_flag+B0p
load:00005555555548C0 ; main+2Bp
load:00005555555548C0 ; main+42p
load:00005555555548C0 ; main+76p
load:00005555555548C0 ; main+291p
load:00005555555548C0 000 jmp cs:qword_555555755F58
load:00005555555548C0 printf endp
load:00005555555548C0
load:00005555555548C6
load:00005555555548C6 ; =============== S U B R O U T I N E =======================================
load:00005555555548C6
load:00005555555548C6
load:00005555555548C6 sub_5555555548C6 proc near
load:00005555555548C6
load:00005555555548C6 ; FUNCTION CHUNK AT load:00005555555548B0 SIZE 0000000C BYTES
load:00005555555548C6
load:00005555555548C6 000 push 0
load:00005555555548CB 008 jmp loc_5555555548B0
load:00005555555548CB sub_5555555548C6 endp
load:00005555555548CB
load:00005555555548D0
load:00005555555548D0 ; =============== S U B R O U T I N E =======================================
load:00005555555548D0
load:00005555555548D0 ; Attributes: thunk
load:00005555555548D0
load:00005555555548D0 ; int __fastcall fseek(void *file, void *a2, int a3)
load:00005555555548D0 fseek proc near ; CODE XREF: load_noise+49p
load:00005555555548D0 000 jmp cs:qword_555555755F60
load:00005555555548D0 fseek endp
load:00005555555548D0
load:00005555555548D6
load:00005555555548D6 ; =============== S U B R O U T I N E =======================================
load:00005555555548D6
load:00005555555548D6
load:00005555555548D6 sub_5555555548D6 proc near
load:00005555555548D6 000 push 1
load:00005555555548DB 008 jmp loc_5555555548B0
load:00005555555548DB sub_5555555548D6 endp
load:00005555555548DB
load:00005555555548E0
load:00005555555548E0 ; =============== S U B R O U T I N E =======================================
load:00005555555548E0
load:00005555555548E0 ; Attributes: noreturn thunk
load:00005555555548E0
load:00005555555548E0 exit proc near ; CODE XREF: main+4Cp
load:00005555555548E0 ; main+80p
load:00005555555548E0 000 jmp cs:qword_555555755F68
load:00005555555548E0 exit endp
load:00005555555548E0
load:00005555555548E6
load:00005555555548E6 ; =============== S U B R O U T I N E =======================================
load:00005555555548E6
load:00005555555548E6
load:00005555555548E6 sub_5555555548E6 proc near
load:00005555555548E6 000 push 2
load:00005555555548EB 008 jmp loc_5555555548B0
load:00005555555548EB sub_5555555548E6 endp
load:00005555555548EB
load:00005555555548F0
load:00005555555548F0 ; =============== S U B R O U T I N E =======================================
load:00005555555548F0
load:00005555555548F0 ; Attributes: thunk
load:00005555555548F0
load:00005555555548F0 ; int __fastcall MD5(void *a1, void *a2, void *a3)
load:00005555555548F0 MD5 proc near ; CODE XREF: MD5_hexlify+4Cp
load:00005555555548F0 000 jmp cs:qword_555555755F70
load:00005555555548F0 MD5 endp
load:00005555555548F0
load:00005555555548F6
load:00005555555548F6 ; =============== S U B R O U T I N E =======================================
load:00005555555548F6
load:00005555555548F6
load:00005555555548F6 sub_5555555548F6 proc near
load:00005555555548F6 000 push 3
load:00005555555548FB 008 jmp loc_5555555548B0
load:00005555555548FB sub_5555555548F6 endp
load:00005555555548FB
load:0000555555554900
load:0000555555554900 ; =============== S U B R O U T I N E =======================================
load:0000555555554900
load:0000555555554900 ; Attributes: thunk
load:0000555555554900
load:0000555555554900 ; void *__fastcall malloc(_QWORD)
load:0000555555554900 malloc proc near ; CODE XREF: load_noise+53p
load:0000555555554900 000 jmp cs:qword_555555755F78
load:0000555555554900 malloc endp
load:0000555555554900
load:0000555555554906
load:0000555555554906 ; =============== S U B R O U T I N E =======================================
load:0000555555554906
load:0000555555554906
load:0000555555554906 sub_555555554906 proc near
load:0000555555554906 000 push 4
load:000055555555490B 008 jmp loc_5555555548B0
load:000055555555490B sub_555555554906 endp
load:000055555555490B
load:0000555555554910
load:0000555555554910 ; =============== S U B R O U T I N E =======================================
load:0000555555554910
load:0000555555554910 ; Attributes: thunk
load:0000555555554910
load:0000555555554910 ; FILE *__fastcall fopen(const char *name, const char *mode)
load:0000555555554910 fopen proc near ; CODE XREF: load_noise+22p
load:0000555555554910 ; calculate_flag+CBp
load:0000555555554910 000 jmp cs:qword_555555755F80
load:0000555555554910 fopen endp
load:0000555555554910
load:0000555555554916
load:0000555555554916 ; =============== S U B R O U T I N E =======================================
load:0000555555554916
load:0000555555554916
load:0000555555554916 sub_555555554916 proc near
load:0000555555554916 000 push 5
load:000055555555491B 008 jmp loc_5555555548B0
load:000055555555491B sub_555555554916 endp
load:000055555555491B
load:0000555555554920
load:0000555555554920 ; =============== S U B R O U T I N E =======================================
load:0000555555554920
load:0000555555554920 ; Attributes: thunk
load:0000555555554920
load:0000555555554920 ; char *__cdecl fgets(char *s, int size, FILE *stream)
load:0000555555554920 fgets proc near ; CODE XREF: load_noise+72p
load:0000555555554920 000 jmp cs:qword_555555755F88
load:0000555555554920 fgets endp
load:0000555555554920
load:0000555555554926
load:0000555555554926 ; =============== S U B R O U T I N E =======================================
load:0000555555554926
load:0000555555554926
load:0000555555554926 sub_555555554926 proc near
load:0000555555554926 000 push 6
load:000055555555492B 008 jmp loc_5555555548B0
load:000055555555492B sub_555555554926 endp
load:000055555555492B
load:0000555555554930
load:0000555555554930 ; =============== S U B R O U T I N E =======================================
load:0000555555554930
load:0000555555554930 ; Attributes: thunk
load:0000555555554930
load:0000555555554930 ; size_t __fastcall strlen(_QWORD)
load:0000555555554930 strlen proc near ; CODE XREF: MD5_hexlify+36p
load:0000555555554930 ; calculate_flag+F8p
load:0000555555554930 ; main+5Fp
load:0000555555554930 ; main+F6p
load:0000555555554930 ; main+137p
load:0000555555554930 000 jmp cs:qword_555555755F90
load:0000555555554930 strlen endp
load:0000555555554930
load:0000555555554936
load:0000555555554936 ; =============== S U B R O U T I N E =======================================
load:0000555555554936
load:0000555555554936
load:0000555555554936 sub_555555554936 proc near
load:0000555555554936 000 push 7
load:000055555555493B 008 jmp loc_5555555548B0
load:000055555555493B sub_555555554936 endp
load:000055555555493B
load:0000555555554940
load:0000555555554940 ; =============== S U B R O U T I N E =======================================
load:0000555555554940
load:0000555555554940 ; Attributes: thunk
load:0000555555554940
load:0000555555554940 ; int sprintf(char *str, const char *format, ...)
load:0000555555554940 sprintf proc near ; CODE XREF: MD5_hexlify+87p
load:0000555555554940 ; eat_cpu+B2p
load:0000555555554940 000 jmp cs:qword_555555755F98
load:0000555555554940 sprintf endp
load:0000555555554940
load:0000555555554946
load:0000555555554946 ; =============== S U B R O U T I N E =======================================
load:0000555555554946
load:0000555555554946
load:0000555555554946 sub_555555554946 proc near
load:0000555555554946 000 push 8
load:000055555555494B 008 jmp loc_5555555548B0
load:000055555555494B sub_555555554946 endp
load:000055555555494B
load:0000555555554950
load:0000555555554950 ; =============== S U B R O U T I N E =======================================
load:0000555555554950
load:0000555555554950 ; Attributes: thunk
load:0000555555554950
load:0000555555554950 ; unsigned __int8 *__cdecl atoi(void *a1)
load:0000555555554950 atoi proc near ; CODE XREF: main+A1p
load:0000555555554950 ; main+B7p
load:0000555555554950 000 jmp cs:qword_555555755FA0
load:0000555555554950 atoi endp
load:0000555555554950
load:0000555555554956
load:0000555555554956 ; =============== S U B R O U T I N E =======================================
load:0000555555554956
load:0000555555554956
load:0000555555554956 sub_555555554956 proc near
load:0000555555554956 000 push 9
load:000055555555495B 008 jmp loc_5555555548B0
load:000055555555495B sub_555555554956 endp
load:000055555555495B
load:0000555555554960
load:0000555555554960 ; =============== S U B R O U T I N E =======================================
load:0000555555554960
load:0000555555554960 ; Attributes: noreturn thunk
load:0000555555554960
load:0000555555554960 stack_chk_fail proc near ; CODE XREF: MD5_hexlify+A6p
load:0000555555554960 ; eat_cpu+ECp
load:0000555555554960 ; calculate_flag+151p
load:0000555555554960 ; main+2C7p
load:0000555555554960 000 jmp cs:qword_555555755FA8
load:0000555555554960 stack_chk_fail endp
load:0000555555554960
load:0000555555554966
load:0000555555554966 ; =============== S U B R O U T I N E =======================================
load:0000555555554966
load:0000555555554966
load:0000555555554966 sub_555555554966 proc near
load:0000555555554966 000 push 0Ah
load:000055555555496B 008 jmp loc_5555555548B0
load:000055555555496B sub_555555554966 endp
load:000055555555496B
load:0000555555554970
load:0000555555554970 ; =============== S U B R O U T I N E =======================================
load:0000555555554970
load:0000555555554970 ; Attributes: thunk
load:0000555555554970
load:0000555555554970 ; char *__fastcall strstr(const char *haystack, const char *needle)
load:0000555555554970 strstr proc near ; CODE XREF: calculate_flag+94p
load:0000555555554970 000 jmp cs:qword_555555755FB0
load:0000555555554970 strstr endp
load:0000555555554970
load:0000555555554976
load:0000555555554976 ; =============== S U B R O U T I N E =======================================
load:0000555555554976
load:0000555555554976
load:0000555555554976 sub_555555554976 proc near
load:0000555555554976 000 push 0Bh
load:000055555555497B 008 jmp loc_5555555548B0
load:000055555555497B sub_555555554976 endp
load:000055555555497B
load:0000555555554980
load:0000555555554980 ; =============== S U B R O U T I N E =======================================
load:0000555555554980
load:0000555555554980 ; Attributes: thunk
load:0000555555554980
load:0000555555554980 ; void *__cdecl strcpy(void *a1, char *a2)
load:0000555555554980 strcpy proc near ; CODE XREF: main+207p
load:0000555555554980 000 jmp cs:qword_555555755FB8
load:0000555555554980 strcpy endp
load:0000555555554980
load:0000555555554986
load:0000555555554986 ; =============== S U B R O U T I N E =======================================
load:0000555555554986
load:0000555555554986
load:0000555555554986 sub_555555554986 proc near
load:0000555555554986 000 push 0Ch
load:000055555555498B 008 jmp loc_5555555548B0
load:000055555555498B sub_555555554986 endp
load:000055555555498B
load:0000555555554990
load:0000555555554990 ; =============== S U B R O U T I N E =======================================
load:0000555555554990
load:0000555555554990 ; Attributes: thunk
load:0000555555554990
load:0000555555554990 ; void __fastcall fclose(void *a1)
load:0000555555554990 fclose proc near ; CODE XREF: calculate_flag+13Cp
load:0000555555554990 000 jmp cs:qword_555555755FC0
load:0000555555554990 fclose endp
load:0000555555554990
load:0000555555554996
load:0000555555554996 ; =============== S U B R O U T I N E =======================================
load:0000555555554996
load:0000555555554996
load:0000555555554996 sub_555555554996 proc near
load:0000555555554996 000 push 0Dh
load:000055555555499B 008 jmp loc_5555555548B0
load:000055555555499B sub_555555554996 endp
load:000055555555499B
load:00005555555549A0
load:00005555555549A0 ; =============== S U B R O U T I N E =======================================
load:00005555555549A0
load:00005555555549A0 ; Attributes: thunk
load:00005555555549A0
load:00005555555549A0 ; void __fastcall strncat(void *a1, void *a2, int a3)
load:00005555555549A0 strncat proc near ; CODE XREF: eat_cpu+D7p
load:00005555555549A0 000 jmp cs:qword_555555755FC8
load:00005555555549A0 strncat endp
load:00005555555549A0
load:00005555555549A6
load:00005555555549A6 ; =============== S U B R O U T I N E =======================================
load:00005555555549A6
load:00005555555549A6
load:00005555555549A6 sub_5555555549A6 proc near
load:00005555555549A6 000 push 0Eh
load:00005555555549AB 008 jmp loc_5555555548B0
load:00005555555549AB sub_5555555549A6 endp
load:00005555555549AB
load:00005555555549B0
load:00005555555549B0 ; =============== S U B R O U T I N E =======================================
load:00005555555549B0
load:00005555555549B0 ; Attributes: thunk
load:00005555555549B0
load:00005555555549B0 fwrite proc near ; CODE XREF: calculate_flag+ECp
load:00005555555549B0 ; calculate_flag+113p
load:00005555555549B0 ; calculate_flag+130p
load:00005555555549B0 000 jmp cs:qword_555555755FD0
load:00005555555549B0 fwrite endp
load:00005555555549B0
load:00005555555549B6
load:00005555555549B6 ; =============== S U B R O U T I N E =======================================
load:00005555555549B6
load:00005555555549B6
load:00005555555549B6 sub_5555555549B6 proc near
load:00005555555549B6 000 push 0Fh
load:00005555555549BB 008 jmp loc_5555555548B0
load:00005555555549BB sub_5555555549B6 endp
load:00005555555549BB
load:00005555555549C0
load:00005555555549C0 ; =============== S U B R O U T I N E =======================================
load:00005555555549C0
load:00005555555549C0 ; Attributes: thunk
load:00005555555549C0
load:00005555555549C0 sub_5555555549C0 proc near ; CODE XREF: sub_555555554A90+1Ep
load:00005555555549C0 000 jmp cs:qword_555555755FF8
load:00005555555549C0 sub_5555555549C0 endp
load:00005555555549C0
load:00005555555549C0 ; ---------------------------------------------------------------------------
Linear Congruential Generator and Related Shenanigans
Okay, great. Now we can start looking into the binary in more detail. All relevant functions apart from main can be fed into Hex-Rays and are rather concise:
// virtual address 0x555555554ADA
unsigned int __fastcall lcg(unsigned int *a1)
{
*a1 = 214013 * *a1 + 2531011;
return (*a1 >> 16) & 0x7FFF;
}
// virtual address 0x555555554B0A
signed __int64 __fastcall jump_forward_lcg(unsigned int *lcgstate)
{
__int64 v1; // rdx@1
signed __int64 result; // rax@1
__int64 vars0; // [sp+8h] [bp+0h]@0
v1 = (unsigned __int8)lcg(lcgstate);
result = vars0 + 8;
*(_QWORD *)(vars0 + 8) += v1;
return result;
}
// virtual address 0x555555554B3B
void __fastcall load_noise(__int64 vault, unsigned int *state0, __int64 state1)
{
FILE *fp; // ST28_8@1
unsigned int v5; // eax@1
fp = fopen((const char *)vault, mode);
v5 = lcg(state0);
fseek(fp, (void *)(signed int)v5, 0);
magic_flag_contents = (char *)malloc(130LL);
fgets(magic_flag_contents, 128, fp);
jump_forward_lcg((unsigned int *)state1);
printf("The noise has been loaded\n", 128LL);
}
What we can see here is that load_noise, the first function not from the standard library called by main reads in 128 bytes from a file vault.txt specified on the command line and stores it into a malloced buffer of size 130. The lcg function is a Linear Congruential Generator with 32 bit internal state producing 15-bit pseudo random numbers (hence the challenge name pseudo secure) which is then used as a seek offset within the vault file. Fortunately, the core dump contains the heap and therefore the contents of the magic_flag_contents buffer. We also found the FILE struct corresponding to vault.txt on the heap, including the first 4096 bytes of its content. From this we learned that the LCG must have returned 0, as the seek offset observable from the FILE struct is currently 128, meaning it was a 0 prior to the fgets.
The function jump_forward_lcg is delicate: It changes the value of the saved return address on the stack by adding a 8-bit value obtained from the LCG earlier. This sounds already a bit awkward and might be related to the SIGSEGV we saw earlier.
Even worse, the initial LCG state is obtained from argv[1] and argv[2], which unfortunately have been censored to XXXXXXXXXX and therefore removed from the coredump. We therefore are a bit stuck because we cannot follow the control flow when leaving the function load_noise as an arbitrary, unknown offset has been added to the return pointer. Darn.
Reversing the Control Flow
Following the control flow from the entry point of the binary seems to be a dead end for now. Hence we started looking at the current program state in the coredump. Here, we notice that the address contained on the top of the stack points to 0x0x5555555552aa: An instruction directly behind an indirect call. The code sequence around the indirect call looks like follows:
load:0000555555555241 078 call lcg
load:0000555555555246 078 mov ecx, eax
load:0000555555555248 078 mov edx, 7E07E07Fh
load:000055555555524D 078 mov eax, ecx
load:000055555555524F 078 imul edx
load:0000555555555251 078 sar edx, 5
load:0000555555555254 078 mov eax, ecx
load:0000555555555256 078 sar eax, 1Fh
load:0000555555555259 078 sub edx, eax
load:000055555555525B 078 mov eax, edx
load:000055555555525D 078 mov edx, eax
load:000055555555525F 078 shl edx, 6
load:0000555555555262 078 add edx, eax
load:0000555555555264 078 mov eax, ecx
load:0000555555555266 078 sub eax, edx
load:0000555555555268 078 cdqe
load:000055555555526A 078 lea rdx, [rax+1Ch]
load:000055555555526E 078 lea rax, alignment_and_noise
load:0000555555555275 078 add rax, rdx
load:0000555555555278 078 mov [rbp+var_48], rax
load:000055555555527C 078 lea rdi, aHoldYourBreath ; "Hold your breath..\n"
load:0000555555555283 078 mov eax, 0
load:0000555555555288 078 call printf
load:000055555555528D 078 lea rax, [rbp+flagfile]
load:0000555555555291 078 lea rdx, [rax+24h]
load:0000555555555295 078 lea rax, [rbp+flagfile]
load:0000555555555299 078 lea rsi, [rax+20h]
load:000055555555529D 078 lea rcx, [rbp+flagfile]
load:00005555555552A1 078 mov rax, [rbp+var_48]
load:00005555555552A5 078 mov rdi, rcx
load:00005555555552A8 078 call rax
load:00005555555552AA
load:00005555555552AA loc_5555555552AA: ; DATA XREF: load:00007FFFFFFFEC38
load:00005555555552AA 078 mov eax, 0
This is very interesting. What we can see here is that the LCG output is added to a function pointer (which we named alignment_and_noise). Even though Hex-Rays is not available, this is about the equivalent functionality of the assembly piece above:
addr = (char *)alignment_and_noise + (int)lcg(&state0) % 65 + 0x1C;
printf("Hold your breath..\n");
((void (*)(char *, unsigned int *, int *))addr)(flagfile, &state0, &state1);
Assuming that the LCG output was wrong, we might very well end up at a wrong address and crash the program. The alignment_and_noise function is at address 0x555555554E51, the program crashed at 0x555555554e9a. Subtracting the two values yields 0x49. Even more importantly, the internal state of the LCG (state0) is passed as an argument to the function, which means that in the core dump, at the time of the crash, the second and third parameter (rsi and rdx) must hold the current internal states of the LCG!
A quick calculation confirms this hypothesis. From gdb we obtain
pwndbg> x/1xw $rsi
0x7fffffffec90: 0xefa46567
pwndbg> x/1xw $rdx
0x7fffffffec94: 0x791dc20e
where the jump distance depends on the value returned by the LCG’s last invocation (0xefa46567 >> 16 & 0x7fff = 0x6fa4) modulo 65 plus 0x1c. And indeed 0x6fa % 65 + 0x1c = 0x49!
Explaining the Crash
This means we’ve successfully reconstructed the (wrong) jump target from the LCG state. Copying the LCG implementation into a python script and doing a 32 bit brute force search also tells us that the state preceding the current LCG state was 0x00745874 (as 214013 * 0x00745874 + 2531011 & 0xffffffff = 0xefa46567, the current value of state0). This value immediately looks suspicious for the trained eye of a reverse engineer: It’s printable ASCII with a NULL termination reading tXt\x00. A quick view into the disassembly prior to the LCG invocation tells us that the code performs roughly the following steps:
strcpy(flagfile, argv[4])
char *tmp = &flagfile[strlen(flagfile)];
*(int *)tmp = 'tXt.';
tmp[4] = 0;
The value of argv[4] is this_file_will_contain_the_flag, according to gdb, and, looking further up in the code to find the stack setup, we can see that the flagfile buf is only 32 bytes in length, and is directly followed by state0. So the program crash occurred because the poor user entered a file name not small enough to fit into the buffer. Then the program forcefully appended ".txt\x00" to the output file name, effectively overwriting the value of state0 leading to the LCG output being wrong eventually causing the program to crash. Phew.
Understanding the Flag Generation Function
Well. Now we know better. But this is terrible, as we now don’t know the actual internal state of the LCG prior to being overwritten. Poking around in the dump in IDA we finally find the function which looked as if it should be the correct target of the indirect jump: At address 0x555555554E9F we find a function that first zeroes out some array on the stack and then calls printf("This may take a while..\n");. We quickly rewrote this function (and all the called subfunctions) in C:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <openssl/md5.h>
unsigned char flag[0x100] =
{
0x0B, 0x7A, 0x64, 0x33, 0x42, 0xE0, 0x9C, 0x1D, 0xCC, 0x2E,
0x68, 0xCB, 0x23, 0x46, 0x66, 0xB8, 0x15, 0xAE, 0x77, 0xC3,
0x63, 0xE5, 0x51, 0x70, 0xA5, 0x0D, 0xE1, 0xF6, 0xE5, 0xC1,
0x32, 0xF3, 0xF9, 0xB7, 0x7F, 0x35, 0xF3, 0xD0, 0x5A, 0x96,
0xFB, 0x34, 0x46, 0x14, 0x76, 0x63, 0x53, 0x5C, 0x4B, 0x7C,
0xA8, 0x7F, 0x24, 0xDA, 0xB5, 0xC4, 0x63, 0x25, 0xF3, 0xAA,
0x12, 0xCA, 0x43, 0x63, 0xE1, 0x2B, 0x8E, 0x1A, 0x3E, 0xDB,
0xC6, 0xDA, 0x49, 0x64, 0x76, 0x16, 0x66, 0xC6, 0x37, 0x91,
0xBE, 0x91, 0xF4, 0xA3, 0x2C, 0xC0, 0xD8, 0xCC, 0xF3, 0x2A,
0xFC, 0xB2, 0xDC, 0x17, 0x57, 0xA0, 0x38, 0xEF, 0x5A, 0x3F,
0x5E, 0x63, 0xB2, 0x59, 0xB8, 0x13, 0x9C, 0x2F, 0x23, 0xA3,
0x59, 0xF4, 0x13, 0x97, 0x39, 0xCF, 0xBC, 0xA9, 0x15, 0xC5,
0x07, 0x7E, 0x83, 0x43, 0x72, 0xDA, 0x0C, 0x7A, 0x60, 0xB5,
0xA9, 0x64, 0x2E, 0x2C, 0xF9, 0x9F, 0x6A, 0x56, 0xAD, 0xC8,
0x36, 0x82, 0x18, 0xA1, 0xCE, 0x2C, 0x86, 0x4A, 0x8F, 0xFB,
0xAA, 0x8B, 0xD8, 0x70, 0xAF, 0xED, 0x82, 0x42, 0x40, 0xF9,
0x42, 0x9D, 0x88, 0x81, 0x83, 0x30, 0x97, 0x7B, 0x47, 0xCD,
0xA8, 0x9B, 0xEF, 0x40, 0x6E, 0x53, 0x2B, 0xC7, 0x61, 0x64
};
unsigned int lcg(unsigned int *state)
{
*state = 214013 * *state + 2531011;
return (*state >> 16) & 0x7FFF;
}
void MD5_hexlify(unsigned char *in, char *out)
{
size_t len = 0;
unsigned int i = 0;
unsigned char md[0x10] = { 0 };
MD5(in, strlen(in), md);
for (i = 0; i <= 15; i++)
sprintf(&out[2 * i], "%02x", md[i]);
}
void eat_cpu(char *res, unsigned int *s0)
{
unsigned int i = 0;
unsigned char hash[0x30] = { 0 };
flag[127] = 0;
printf("%d\n", strlen(flag));
MD5_hexlify(flag, hash);
for (i = 0; i <= 99999999; ++i) {
MD5_hexlify(hash, hash);
sprintf(&hash[0x20], "-%.8x", lcg(s0));
}
strncat(res, hash, 0x63);
}
int main(int argc, char **argv)
{
char result[0x100] = { 0 };
if (argc != 2) {
puts("Missing argument.");
return -1;
}
unsigned int s0 = strtoul(argv[1], NULL, 0);
eat_cpu(result, &s0);
printf("Flag:{");
printf("%s", result);
printf("}\n");
fflush(stdout);
}
This seems to invoke the MD5 hash function and the LCG with state0 one houndred million times, and encloses the result with Flag:{ and }. (btw, OOO, why this inconsistency? Wouldn’t this have been trivial to change to OOO{ }?)
So our task now becomes clear: Reconstruct the overwritten state0 variable, and do it precisely (even on 2018 hardware the hashing takes about 2 minutes).
Reconstructing the LCG State
The LCG has $2^{32}$ internal states. Clearly, doing a bruteforce search is infeasible in the given time frame. So we have to look for constraints that we know the LCG state musst satisfy.
Constraint 1: Correct Jump Target
Coming back to the indirect jump, assuming we want to hit the flag calculation function, we know that the last output of the LCG must be 0x555555554E9F-0x555555554E51 = 0x4e. This reduces the search space by a factor of $2^8$ there are still too many values to try.
Constraint 2: LCG State state1
LCG state state1 governs the behavior of the jump_forward_lcg function, and has not been overwritten. Therefore, we were able to reconstruct the LCG sequence for state1: 0x00002a45 -> 0x8a2f73f4 -> 0x584112e7 -> 0x791dc20e meaning that whenever jump_forward_lcg was called, it skipped 0x2f -> 0x41 -> 0x1d (in forward order) bytes in the outer function. To our surprise, this actually is consistent with the assembly contained in the binary, with the jumps being
0x55555555515E -> 0x55555555518D (0x2f) skipping the bogus return from main
0x5555555551A8 -> 0x5555555551E9 (0x41) skipping some bogus part saying “this is the flag”
0x555555554E80 -> 0x555555554E9D (0x1d) skipping around a magic constant saying 0xff0011 ( = fool?)
Nopping out these ranges, for the first time made Hex-Rays decompile the main function! Back then, we knew we were on track! :)
int __cdecl main(int argc, const char **argv, const char **envp)
{
char *v3; // rax@13
char *v4; // ST28_8@13
int result; // eax@13
__int64 v6; // rbx@13
const char **argv_cpy; // [sp+0h] [bp-70h]@1
int i; // [sp+1Ch] [bp-54h]@7
int j; // [sp+1Ch] [bp-54h]@10
char flagfile[32]; // [sp+30h] [bp-40h]@13
unsigned int state0; // [sp+50h] [bp-20h]@7
int state1; // [sp+54h] [bp-1Ch]@7
__int64 v13; // [sp+58h] [bp-18h]@1
v13 = *MK_FP(__FS__, 40LL);
printf("Thanks for choosing Ps Security\n", argv, argv);
if ( argc <= 4 )
{
printf("Not enough parameters\n");
exit(1LL);
}
if ( strlen(argv_cpy[4]) > 0x1F )
{
printf("Filename too long\n");
exit(1LL);
}
state0 = 0;
state1 = 0;
state0 = (unsigned __int64)atoi((void *)argv_cpy[1]);
state1 = (unsigned __int64)atoi((void *)argv_cpy[2]);
for ( i = 0; i < strlen(argv_cpy[1]); ++i )
argv_cpy[1][i] = 'x';
for ( j = 0; j < strlen(argv_cpy[2]); ++j )
argv_cpy[2][j] = 'x';
load_noise((__int64)argv_cpy[3], &state0, (__int64)&state1);
alignment_and_noise((__int64)&state0, (__int64)&state1);
strcpy(flagfile, argv[4])
v3 = &flagfile[strlen(flagfile)];
*(_DWORD *)v3 = 'tXt.';
v3[4] = 0;
v4 = (char *)alignment_and_noise + (signed int)lcg(&state0) % 65 + 0x1C;// 0x00745874 -> 0xefa46567
printf("Hold your breath..\n");
((void (__fastcall *)(char *, unsigned int *, int *))v4)(flagfile, &state0, &state1);
result = 0;
v6 = *MK_FP(__FS__, 40LL) ^ v13;
return result;
}
Constraint 3: Sync state of LCG state state0
Back to our main problem of finding state0 we now have at least the precise original control flow the program took prior to crashing. The main function calls the alignment_and_noise function which in turn calls a get_alignment function (0x555555554BD2) which invokes the LCG many times until it returns zero:
void __cdecl get_alignment(__int64 a1, __int64 a2)
{
unsigned int *s1; // [sp+0h] [bp-20h]@1
unsigned int *s0; // [sp+8h] [bp-18h]@1
int v4; // [sp+14h] [bp-Ch]@1
int v5; // [sp+18h] [bp-8h]@1
v4 = 0;
v5 = 0;
printf("Waiting for the proper alignment:\n ", a2, a1);
while ( lcg(s0) )
{
if ( !(++v4 % 50) )
{
printf(".");
if ( !(++v5 % 50) )
printf("\n ");
}
}
jump_forward_lcg(s1); // 0x584112e7 -> 0x791dc20e
printf("\n");
}
Remember how the LCG output with state0 was used as a seek offset earlier? As explained earlier we know that this was a zero, and here the LCG is called on state0 until it returns 0 again. This means that we additionally know that there must be two zero outputs with a particular distance. If we only knew that distance …
Looking again at the get_alignment function we realize that it actually gives away the magnitude of the number of LCG invocations! For every 50 LCG calls it prints one “.” to stdout. For every 50 * 50 LCG calls it writes out a newline character. If we only had stdout output …
And it turns out we are lucky again! Reconstructing glibc’s FILE structs we find the following:
0000555555757260 48 6F 6C 64 20 79 6F 75 72 20 62 72 65 61 74 68 Hold your breath
0000555555757270 2E 2E 0A 2E 2E 2E 2E 2E 2E 2E 2E 2E 2E 2E 2E 2E ................
0000555555757280 2E 2E 0A 2E 2E 2E 2E 2E 2E 2E 2E 2E 2E 2E 2E 2E ................
0000555555757290 2E 2E 2E 2E 2E 2E 0A 00 00 00 00 00 00 00 00 00 ................
This output could only be produced if the LCG was called 50 * 50 times, producing four spaces, 50 dots and a newline (in total 55 characters), after being overwritten by four spaces, 30 dots and a newline, which is in turn overwritten by the Hold your breath.. announcement of the binary directly before the indirect jump. Unfortunately to us, we still have to many possible answers to this, as we cannot tell how many times the first (50 * 50) linewrap was triggered. What we derive from the observations above is that the distance separating two zero LCG return values has to follow the formula 50 * x + 30. If we only could precisely determine this x …
And it turns out we are lucky once more! After staring at the fragments of the function frames on the stack contained in the coredump
00:0000│ 0x7fffffffebb8 —▸ 0x5555557588b0 ◂— 0x1d9ce04233647a0b
01:0008│ 0x7fffffffebc0 —▸ 0x7fffffffec94 ◂— 0xdc7ab200791dc20e
02:0010│ 0x7fffffffebc8 —▸ 0x7fffffffebe0 —▸ 0x7fffffffec10 —▸ 0x7fffffffec30 —▸ 0x7fffffffecb0 —▸ 0x5555555552d0 ◂— ...
03:0018│ 0x7fffffffebd0 —▸ 0x555555554b22 ◂— movzx eax, al
04:0020│ 0x7fffffffebd8 —▸ 0x7fffffffec94 ◂— 0xdc7ab200791dc20e
05:0028│ 0x7fffffffebe0 —▸ 0x7fffffffec10 —▸ 0x7fffffffec30 —▸ 0x7fffffffecb0 —▸ 0x5555555552d0 ◂— ...
06:0030│ 0x7fffffffebe8 —▸ 0x555555554cae ◂— nop
07:0038│ 0x7fffffffebf0 —▸ 0x7fffffffec94 ◂— 0xdc7ab200791dc20e
08:0040│ 0x7fffffffebf8 —▸ 0x7fffffffec90 ◂— 0x791dc20eefa46567
09:0048│ 0x7fffffffec00 ◂— 0x55554b22 /* '"KUU' */
0a:0050│ 0x7fffffffec08 ◂— 0x1000000e6
0b:0058│ 0x7fffffffec10 —▸ 0x7fffffffec30 —▸ 0x7fffffffecb0 —▸ 0x5555555552d0 ◂— push r15
0c:0060│ 0x7fffffffec18 —▸ 0x555555554e9d ◂— leave
0d:0068│ 0x7fffffffec20 —▸ 0x7fffffffec94 ◂— 0xdc7ab200791dc20e
0e:0070│ 0x7fffffffec28 —▸ 0x7fffffffec90 ◂— 0x791dc20eefa46567
0f:0078│ 0x7fffffffec30 —▸ 0x7fffffffecb0 —▸ 0x5555555552d0 ◂— push r15
10:0080│ rsp 0x7fffffffec38 —▸ 0x5555555552aa ◂— mov eax, 0
11:0088│ 0x7fffffffec40 —▸ 0x7fffffffed98 —▸ 0x7fffffffef43 ◂— 0x6b73612f706d742f ('/tmp/ask')
12:0090│ 0x7fffffffec48 ◂— 0x500f0b5ff
13:0098│ 0x7fffffffec50 ◂— 0xc2
14:00a0│ 0x7fffffffec58 ◂— 0xaffffec86
15:00a8│ 0x7fffffffec60 ◂— 0x1
16:00b0│ 0x7fffffffec68 —▸ 0x555555554e9a ◂— inc dword ptr [rax]
17:00b8│ rcx rdi 0x7fffffffec70 ◂— 0x6c69665f73696874 ('this_fil')
18:00c0│ 0x7fffffffec78 ◂— 0x635f6c6c69775f65 ('e_will_c')
19:00c8│ 0x7fffffffec80 ◂— 0x745f6e6961746e6f ('ontain_t')
1a:00d0│ 0x7fffffffec88 ◂— 0x2e67616c665f6568 ('he_flag.')
1b:00d8│ rsi rdx-4 0x7fffffffec90 ◂— 0x791dc20eefa46567
1c:00e0│ 0x7fffffffec98 ◂— 0x853f88dcdc7ab200
1d:00e8│ 0x7fffffffeca0 —▸ 0x7fffffffed90 ◂— 0x5
1e:00f0│ 0x7fffffffeca8 ◂— 0x0
1f:00f8│ rbp 0x7fffffffecb0 —▸ 0x5555555552d0 ◂— push r15
20:0100│ 0x7fffffffecb8 ◂— 0x7ffff75d51c1
21:0108│ 0x7fffffffecc0 —▸ 0x7fffffffedc8 —▸ 0x7fffffffefa4 ◂— 'COLUMNS=136'
22:0110│ 0x7fffffffecc8 —▸ 0x7fffffffed98 —▸ 0x7fffffffef43 ◂— 0x6b73612f706d742f ('/tmp/ask')
23:0118│ 0x7fffffffecd0 ◂— 0x500000000
24:0120│ 0x7fffffffecd8 —▸ 0x555555554ff7 ◂— push rbp
25:0128│ 0x7fffffffece0 ◂— 0x0
26:0130│ 0x7fffffffece8 ◂— 0x7ef90cea2d1b8aca
27:0138│ 0x7fffffffecf0 —▸ 0x5555555549d0 ◂— xor ebp, ebp
we spotted the answer to the million dollar question clandestinely hiding at offset 0x7fffffffec08: 0xe6 = 230 = 50 * 4 + 30. This is the value v5 contained in the frame of the get_alignment function. We therefore have a second, strong constraint on the state0 variable!
Putting it all Together
To summarize, we now look for two zero outputs of the LCG separated by at least 230 * 50 and at most 231 * 50 (otherwise there would have been another dot on stdout) steps. Additionally, the value after the second zero must satisfy (((((nxt >> 16) & 0x7fff) % 65) + 0x1c) == 0x4e). With this knowledge, our mathemagician wrote a Sage script
#!/usr/bin/env sage
R = Zmod(2**32)
a = R(214013)
b = R(2531011)
good = list(range(2**16)) + list(range(2**31, 2**31+2**16))
for n in range(230*50, 231*50+1):
A = a**n
B = sum(a**i*b for i in range(n))
f = lambda x: int(A*x+B)
t = lambda v: (int(v)>>16)&0x7fff
for x0 in good:
xn = f(x0)
nxt = int(a*xn+b)
if t(xn) == 0 and t(nxt) % 65 + 0x1c == 0x4e:
print '{:5d} {:08x} {:08x} {:08x}'.format(n, x0, xn, nxt)
producing the outputs 0x1c6158d4, 0x374b2e90, and 0x6ea5b54d. Feeding the first value into the flag calculation function from above yields the flag Flag:{d589ec6f60145e9d6cdb750f74d24ccd-00001a5f}.