Write Up Misc — HTB Apocalypse 2023 — (Janken, Calibrator)
Introduction
A few weeks ago, I played CTF HTB Apocalypse 2023. The CTF ran for 5 days, and the challenges provided totaled 74, which was quite a lot.
In this CTF, I participated in several categories such as misc, reversing, and machine learning. I plan to write articles for each category, starting with this one, misc category.
Table of Content
· Introduction
· Table of Content
· Misc — Janken
· Misc — Calibrator
· Epilogue
Misc — Janken
The first misc challenge I solved was called Janken. It involved a socket connection and some provided files.
Here are the files provided to the user:
$ ls -lah
total 20K
drwxrwxrwx 1 alfan alfan 4.0K Mar 26 16:20 .
drwxrwxrwx 1 alfan alfan 4.0K Mar 26 16:20 ..
drwxrwxrwx 1 alfan alfan 4.0K Mar 13 21:27 .glibc
-rwxrwxrwx 1 alfan alfan 18K Mar 13 21:27 janken
$ file janken
janken: ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked, interpreter ./.glibc/ld-linux-x86-64.so.2, BuildID[sha1]=56b54cdae265aa352fe2ebb016f86af831fd58d3, for GNU/Linux 3.2.0, not strippedWhen you try to run the game, it presents a simple janken game that requires the user to win in order to proceed to the next round.
Looking at the source code below in the game function, we can see that the program calls strstr on our input using the needle array.
The strstr function has two arguments: the first is our input, and the second is the needle pointer. The strstr function returns a non-zero value if there are any substrings. To bypass this restriction, we should be able to input “rockscissorpaper” and win the round.
To automate this, I used pwntools and created a simple script. After running the script, the flag was acquired from the server.
from pwn import *
from sys import *
p = connect("178.62.64.13", 32538)
# p.recvuntil(">> ")
p.sendline("1")
for i in range(99):
print(i)
p.recvuntil(">> ")
p.sendline("rockscissorspaper")
p.interactive()
Misc — Calibrator
The next misc challenge I solved was called Calibrator.
Like the previous challenge, it involved a socket connection and some provided files.
Upon examining the files, there is a Python script that runs on the server, along with well-written documentation. Below is a screenshot of the game rules from the documentation:
The goal of this problem is to locate the center of a circle (radar) using the responses given. “DETECTED” means our coordinate guess is inside the circle, “UNDETECTED” means our coordinate is outside the circle, and if our guess is right on the center, the program returns “REFERENCE.”
The circle is large, so a naive method would not work, and we are only allowed 300 attempts at guessing. Another difficulty not mentioned in the documentation, but only in the code, is that we can only input integer values, which introduces floating-point errors if we use an algorithm.
Below is the server code:
So, how can we create an algorithm to solve this?
After trying and modifying several algorithms, I finally completed the challenge using binary search.
Binary search can be used in this challenge to find the circumference coordinate of the circle. For example, if we pick a random coordinate inside the circle (a number below the HI constraint circle) and perform a binary search on one side of the coordinate (e.g., binary search on Y), we should be able to get a coordinate close to the circumference (for example, if we choose X, A, the program returns “DETECTED,” and if we choose X, A+1, the program returns “UNDETECTED,” with A being the binary search calculation on coordinate Y).
With this approach, if we collect many circumference coordinates and spread them out, we can minimize the error. In the program I created, I performed 8 circumference coordinate searches.
After collecting all the circumference coordinates, we should be able to calculate the center of the circle if we have 3 or more points. Having more points would decrease center calculation errors.
Even after calculating the center, the program still has a chance of failing to detect the center. The remaining attempts can be used to guess the coordinates around our guess, hoping it will point to the center.
Below is my program to solve this case:
from pwn import *
import math
# while true ; do python3 final-final.py ; done
# while true ; do python3 solve.py ; done
ITERATIONS = 47
SIDE_LENGTH = 2 * 10 ** 9
ATTEMPTS = 300
HI = SIDE_LENGTH // 2
LO = -SIDE_LENGTH // 2
e = 2
# Connect to the challenge server
conn = remote('165.232.98.11', 30970)
# conn = process('python3 src/server.py'.split())
# print(log)
# Define binary search function
z = 0
global before
def binary_search(lo, hi):
# before = (lo, hi)
while lo <= hi:
mid = (lo + hi) // 2
conn.sendline(f"{mid} {mid}")
response = conn.recvline().decode().strip()
global z
print(z, lo, hi, mid, mid, repr(response))
z += 1
if mid == lo and mid == hi:
return (mid, mid)
elif "UNDETECTED" in response:
x, y = binary_search(lo, mid - 1)
if x is not None and y is not None:
return (x, y)
x, y = binary_search(mid - 1, mid - 1)
if x is not None and y is not None:
return (x, y)
elif "DETECTED" in response:
x, y = binary_search(mid + 1, hi)
if x is not None and y is not None:
return (x, y)
x, y = binary_search(mid + 1, mid + 1)
if x is not None and y is not None:
return (x, y)
return (None, None)
def binary_search_x(x_lo, x_hi, y, r):
while x_lo <= x_hi:
x_mid = (x_lo + x_hi) // 2
conn.sendline(f"{x_mid} {y}")
response = conn.recvline().decode().strip()
global z
print(z, x_mid, y, "|", x_mid, x_lo, x_hi, repr(response))
z += 1
if x_mid == x_hi and x_mid == x_lo :
return x_mid
elif "UNDETECTED" in response:
x = binary_search_x(x_lo, x_mid - 1, y, r)
if x is not None:
return x
x = binary_search_x(x_mid - 1, x_mid - 1, y, r)
if x is not None:
return x
elif "DETECTED" in response:
x = binary_search_x(x_mid + 1, x_hi, y, r)
if x is not None:
return x
x = binary_search_x(x_mid + 1, x_mid + 1, y, r)
if x is not None:
return x
return None
def binary_search_y(y_lo, y_hi, x, r):
while y_lo <= y_hi:
y_mid = (y_lo + y_hi) // 2
conn.sendline(f"{x} {y_mid}")
response = conn.recvline().decode().strip()
global z
print(z, x, y_mid, "|", y_mid, y_lo, y_hi, repr(response))
z += 1
if y_mid == y_hi and y_mid == y_lo :
return y_mid
elif "UNDETECTED" in response:
y = binary_search_y(y_mid + 1, y_hi, x, r)
if y is not None:
return y
y = binary_search_y(y_mid + 1, y_mid + 1, x, r)
if y is not None:
return y
elif "DETECTED" in response:
y = binary_search_y(y_lo, y_mid - 1, x, r)
if y is not None:
return y
y = binary_search_y(y_mid - 1, y_mid - 1, x, r)
if y is not None:
return y
return None
# Loop through iterations
for i in range(47):
z = 0
logx = conn.recvuntil("> ")
# Generate random circle parameters
R = random.randint(SIDE_LENGTH // 4, SIDE_LENGTH // 2)
X = random.randint(LO + R, HI - R)
Y = random.randint(LO + R, HI - R)
# Perform binary search
points = []
x, y = binary_search(LO, HI)
points.append((x, y))
# z = 0
MET = SIDE_LENGTH // 1000
x_mid = binary_search_x(LO, HI, MET, R)
# print(x_mid, MET)
points.append((x_mid, MET))
# z = 0
MET = -SIDE_LENGTH // 1000
x_mid = binary_search_x(LO, HI, MET, R)
# print(x_mid, MET)
points.append((x_mid, MET))
# z = 0
MET = SIDE_LENGTH // 100
x_mid = binary_search_x(LO, HI, MET, R)
# print(x_mid, MET)
points.append((x_mid, MET))
# z = 0
MET = -SIDE_LENGTH // 100
x_mid = binary_search_x(LO, HI, MET, R)
# print(x_mid, MET)
points.append((x_mid, MET))
# z = 0
MET = SIDE_LENGTH // 1000
y_mid = binary_search_y(LO, HI, MET, R)
# print(MET, y_mid)
points.append((MET, y_mid))
# z = 0
MET = -SIDE_LENGTH // 1000
y_mid = binary_search_y(LO, HI, MET, R)
# print(MET, y_mid)
points.append((MET, y_mid))
# z = 0
MET = SIDE_LENGTH // 100
y_mid = binary_search_y(LO, HI, MET, R)
# print(MET, y_mid)
points.append((MET, y_mid))
# z = 0
MET = -SIDE_LENGTH // 100
y_mid = binary_search_y(LO, HI, MET, R)
# print(MET, y_mid)
points.append((MET, y_mid))
# Input a list of points on the circle circumference
import numpy as np
# Create a matrix A and a vector b for the least squares circle fit equation
A = np.array([[2 * p[0], 2 * p[1], 1] for p in points])
b = np.array([-p[0] ** 2 - p[1] ** 2 for p in points])
# Solve the least squares circle fit equation to find the center of the circle
x, y, r = np.linalg.lstsq(A, b, rcond=None)[0]
center_x, center_y = int(-x), int(-y)
# Print the x and y coordinates of the center of the circle
print("The center of the circle is ({}, {}) {}".format(center_x, center_y, z))
if(b"DEBUGGGGG" in logx):
print(logx.split(b"DEBUGGGGG")[1].split(b"DEBUGGGGG")[0])
# conn.interactive()
# Send solution to challenge server
conn.sendline(f"{center_x} {center_y}")
# conn.interactive()
sisa = 300 - z
# tengah = int(sisa ** -1)
import math
tengah = int(math.sqrt(sisa)/2)
print(tengah)
print(z + tengah * 4, sisa)
data = conn.recvline()
print("CHECK COOR")
print(data)
if(b"REFERENCE" not in data):
print("FIXING COODINATE", tengah)
for aa in range(-tengah, tengah):
for bb in range(-tengah, tengah):
conn.sendline(f"{center_x+aa} {center_y+bb}")
z += 1
data = conn.recvline()
print(z, f"{center_x+aa} {center_y+bb}", repr(data))
if(b"REFERENCE" in data):
break
if(b"REFERENCE" in data):
break
print(i)
print(i)
print(i)
print(i)
print(i)
print(i)
print(i)
print(i)
print(i)
print(i)
print(i)
print(i)
print(i)
print(i)
print(i)
print(data)
conn.interactive()Run the program on the VPS using the loop below:
# while true ; do python3 final-final.py ; doneThe program will display the flag after a few attempts.
Epilogue
I enjoyed the calibrator challenge a lot, as there was a lot of optimization involved in modifying the code. After successfully completing and accomplishing all miscellaneous challenges, it became evident that AI assistance, such as ChatGPT, can be helpful in coding. However, it cannot solve everything. There are still optimizations required to address specific cases, and to achieve this, programmers need to understand the provided code in order to modify the outcome effectively.
