jagacha
Description
CTF: STACK the Flags 2022
As a wise man once said, there is no greater happiness in life than to hit a homerun with your SSS-tier gacha pulls on the first try. However, reality is not that easy. Therefore, we are providing a chance for you to pull the SSS-rarity flag if you can guess the number correctly. However, if you are still unsure of your chances of guessing it right, you're always welcome to do a random gacha pull until you change your mind.
Note: Submit the flag in all caps.
jagacha.py
config.py
Solution
Pwned by @skytect (opens in a new tab)
Looking through jagacha.py, you may realise that option 1 generates and shows
you the next 64 random bits, while option 2 allows you to guess the next 64
random bits for the flag.
# jagacha.py, L75–104
if option == 1:
num = rand.getrandbits(64)
gacha = GACHA_KEYS[num % len(GACHA_KEYS)]
writer.writelines(
(
f"Congrats! You have pulled a {gacha}!\n".encode(),
GACHAS[gacha],
b"Here are the stats of your character:\n",
f"STR: {num>>48 & 0xffff}\n".encode(),
f"DEX: {num>>32 & 0xffff}\n".encode(),
f"INT: {num>>16 & 0xffff}\n".encode(),
f"LUK: {num & 0xffff}\n".encode(),
b'\n',
)
)
elif option == 2:
num = rand.getrandbits(64)
lucky_number = await read_number(
reader, writer, b"Enter your lucky number: "
)
if lucky_number == num:
writer.writelines((
b"Congrats! You have pulled the limited SSS-rated rarity flag-chan!\n",
FLAG,
))
option = 3 # Quit
else:
writer.write(
b"Oops! Looks like you are not as lucky as you thought! Try again!\n\n"
)Next let's see how the seed is generated. Unfortunately, config.py shows us
that we can't really determine the seed as it's generated by the nanosecond.
# config.py, L6–8
def get_seed():
SEED = 0xdeadc0de
return SEED + time.time_ns()However, we can still use existing knowledge to determine the state of the random generator. Python uses the Mersenne Twister (opens in a new tab) algorithm to generate random numbers, which shifts its state every 624 32-bit numbers. So, we can crack it with that many bits.
I wrote a solve script below using
randcrack (opens in a new tab).
import re
import time
from pwn import *
from randcrack import RandCrack
conn = remote('157.245.52.169', '31301')
conn.recvuntil(b'> ')
def get_64_bits() -> int:
conn.sendline(b'1')
r = conn.recvuntil(b'> ').decode()
m = re.findall(r'Here are the stats of your character:\nSTR: (\d+)\nDEX: (\d+)\nINT: (\d+)\nLUK: (\d+)\n', r)
n = [int(s) for s in m[0]]
return n[0] << 48 | n[1] << 32 | n[2] << 16 | n[3]
def submit_flag(n: int) -> str:
conn.sendline(b'2')
r = conn.recvuntil(b': ')
conn.sendline(str(n).encode())
r = conn.recvall().decode()
return r
rc = RandCrack()
for i in range(624 // 2):
b = get_64_bits()
rc.submit(b & 0xffffffff)
rc.submit((b >> 32) & 0xffffffff)
r = submit_flag(rc.predict_getrandbits(64))
print(r)Running the script gives us the flag.
[x] Opening connection to 157.245.52.169 on port 31301
[x] Opening connection to 157.245.52.169 on port 31301: Trying 157.245.52.169
[+] Opening connection to 157.245.52.169 on port 31301: Done
[x] Receiving all data
[x] Receiving all data: 0B
[x] Receiving all data: 86B
[+] Receiving all data: Done (86B)
[*] Closed connection to 157.245.52.169 port 31301
Congrats! You have pulled the limited SSS-rated rarity flag-chan!
STF22{W@IFU5_L@1FU5}STF22{W@IFU5_L@1FU5}