Substraction

Posted on Mon 05 August 2024 in ctf

This is a writeup of the misc challenge Substraction in the n00bz CTF 2024.

The attached file server.py contained the following code:

import random

n = 696969

a = []
for i in range(n):
    a.append(random.randint(0, n))
    a[i] -= a[i] % 2

print(' '.join(list(map(str, a))))

for turns in range(20):
    c = int(input())
    for i in range(n):
        a[i] = abs(c - a[i])

    if len(set(a)) == 1:
        print(open('/flag.txt', 'r').read())
        break

The code generates 696969 random round integers and stores them in a list a. Then over 20 rounds we must enter integers c which are used to update a by calculating a[i] = abs(c - a[i]).

If we choose c every time so that it is the largest power of two that is smaller than the maximum in a then all values in a logarithmically approach 0. The following code will ensure that all values in a will be equal to 0 after 20 rounds. This way the check len(set(a)) == 1 will be equal to True and server.py will print the flag:

from pwn import *

def largest_power_of_two_less_than(n):
    if n <= 1:
        return 0
    power = n
    power |= power >> 1
    power |= power >> 2
    power |= power >> 4
    power |= power >> 8
    power |= power >> 16
    power |= power >> 32
    return (power + 1) >> 1

con  = remote('challs.n00bzunit3d.xyz', 10265, typ='tcp')
line = con.recvline()

a = [int(x) for x in line.split()]
c = largest_power_of_two_less_than(max(a))

for turn in range(20):
    print(f"[TURN {turn}]\tc: {c}\tmin: {min(a)}\tmax: {max(a)}\t#: {len(list(set(a)))}")
    con.sendline(str(c).encode('utf-8'))

    for i in range(len(a)):
        a[i] = abs(c - a[i])

    if len(set(a)) == 1:
        print("DONE")
        break

    c = largest_power_of_two_less_than(max(a))

    if c == 2:
        c = 1
    if c == max(a):
        c = largest_power_of_two_less_than(max(a) - 1)

line = con.recvline()
print(line)