DownUnder CTF (DUCTF) 2024 Writeup
V for Vieta
Implementing Vieta jumping algorithm
Problem
The following source code is given.
#!/usr/bin/env python3
import os
import random
import json
from enum import Enum
FLAG = os.getenv("FLAG", "DUCTF{dummy_flag}")
class State(Enum):
INITIAL = 1
TEST = 2
QUIT = 3
class Server:
def __init__(self):
self.level = 2048
self.target = 2048
self.finish = 8
self.state = State.INITIAL
def win(self):
return {
"flag": FLAG,
}
def generate_k(self):
self.k = random.getrandbits(self.level) ** 2
self.state = State.TEST
return {
"k": self.k,
"level": self.level,
}
def test(self, challenge):
a, b = challenge["a"], challenge["b"]
if a <= 0 or b <= 0:
self.state = State.QUIT
return {"error": "Your answer must be positive!"}
if a.bit_length() <= self.target or b.bit_length() <= self.target:
self.state = State.QUIT
return {"error": "Your answer is too small!"}
num = a**2 + a * b + b**2
denom = 2 * a * b + 1
if num % denom != 0 or num // denom != self.k:
self.state = State.QUIT
return {"error": "Your answer wasn't a solution!"}
self.level -= self.level // 5
if self.level <= self.finish:
self.state = State.QUIT
return self.win()
else:
return self.generate_k()
def main():
server = Server()
print("V equals negative V plus or minus the squareroot of V squared minus 4 V V all divided by 2 V!")
while True:
if server.state == State.INITIAL:
print(json.dumps(server.generate_k()))
elif server.state == State.TEST:
challenge = json.loads(input())
print(json.dumps(server.test(challenge)))
elif server.state == State.QUIT:
exit(0)
if __name__ == "__main__":
main()
The essence is, we need to find a pair of (a,b) which satisfies the requirement:
(a**2 + a * b + b**2) / (2 * a * b + 1)==k- along the way, k will get smaller, until it reaches 8 bit, but we still need to always supply a and be that are atleast 2048 bit
Approach
Re-arrange the quadratic equation in terms of a:
a**2 - (2*k-1)*b * a + (b^2 - k) == 0
The first few pairs of (a,b) that satisfy the quadratic equation above can be derived from the Wikipedia page on Vieta jumping, where r is the square root of the given k:
1st pair: (0 , r)
2nd pair: (r , 2 * r ** 3 - r)
3rd pair: (2 * r ** 3 - r , 4 * r ** 5 - 4 * r ** 3)
After observing the pattern, notice that
a[i] = b[i-1]
b[i] = (2 * r ** 2 - 1)*b[i-1] - a
where (a[i-1],b[i-1]) is the previous working pair before (a[i],b[i]). This means, we can determine the elements of the next pair from the previous elements.
Solution
The key thing to understand is, because k will keep getting smaller in each iteration, we cannot use the same form of (a,b) pair, as the earlier form of (a,b) will end up being smaller than 2048 bit for smaller k. This is why we need to jump to the next (bigger) form of (a,b), in order to be able to hit the 2048 bit requirement with smaller k.
Below is the solver script.
from pwn import *
from math import isqrt
import json
def calculate_a_b(k):
r = isqrt(k)
a = 2 * r ** 3 - r
b = 4 * r ** 5 - 4 * r ** 3
c = (2 * r ** 2 - 1)*b - a
while(a.bit_length() < 2048):
a=b
b=c
c = (2 * r ** 2 - 1)*b - a
return a, b
def main():
# Connect to the server
conn = remote('2024.ductf.dev', 30018)
#conn = process(['python', 'server.py'])
# Read the introductory message
intro_message = conn.recvline()
print(intro_message.decode().strip())
while True:
# Receive the challenge from the server
challenge = conn.recvline().decode().strip()
print("Received challenge:", challenge)
# Parse the challenge to get the value of k
challenge_json = json.loads(challenge)
k = challenge_json['k']
# Calculate a and b based on k
a, b = calculate_a_b(k)
# Prepare the solution in JSON format
solution = {"a": a, "b": b}
solution_json = json.dumps(solution)
print("Sending solution:", solution_json)
# Send the solution back to the server
conn.sendline(solution_json)
# Receive the server's response
# Close the connection
conn.close()
if __name__ == "__main__":
main()
FLAG: DUCTF{jump1n6_4nd_fl1pp1n6_up_7h3_hyp3r8011c_14dd3r}