[cryptoctf2023]Did it! write up

문제정보

대충 두 집합의 교집합을 구하는데 어려웠는데 결국 해냈다 너도 해 봐라 이런 얘기 였다.

문제

코드와 nc으로 접속할 수 있는 프로세스를 줬다.
문제 코드

#!/usr/bin/env python3

from random import randint
import sys
from flag import flag

def die(*args):
	pr(*args)
	quit()

def pr(*args):
	s = " ".join(map(str, args))
	sys.stdout.write(s + "\n")
	sys.stdout.flush()

def sc():
	return sys.stdin.buffer.readline()

def did(n, l, K, A):
	A, K = set(A), set(K)
	R = [pow(_, 2, n) + randint(0, 1) for _ in A - K]
	return R

def main():
	border = "+"
	pr(border*72)
	pr(border, ".::   Hi all, she DID it, you should do it too! Are you ready? ::.  ", border)
	pr(border*72)

	_flag = False
	n, l = 127, 20
	N = set(list(range(0, n)))
	K = [randint(0, n-1) for _ in range(l)]
	cnt, STEP = 0, 2 * n // l - 1
	
	while True:
		ans = sc().decode().strip()
		try:
			_A = [int(_) for _  in ans.split(',')]
			if len(_A) <= l and set(_A).issubset(N):
				DID = did(n, l, K, _A)
				pr(border, f'DID = {DID}')
				if set(_A) == set(K):
					_flag = True
			else:
				die(border, 'Exception! Bye!!')
		except:
			die(border, 'Your input is not valid! Bye!!')
		if _flag:
			die(border, f'Congrats! the flag: {flag}')
		if cnt > STEP:
			die(border, f'Too many tries, bye!')
		cnt += 1

if __name__ == '__main__':
	main()

분석

처음에 코드를 분석하는데 코드를 잘못 이해해서 뺑뺑 돌다가 주어진 코드를 살짝 손을 봐서 어떻게 돌아가는지 확인을 했다.

from random import randint
import sys

def die(*args):
	pr(*args)
	quit()

def pr(*args):
	s = " ".join(map(str, args))
	sys.stdout.write(s + "\n")
	sys.stdout.flush()

def sc():
	return sys.stdin.buffer.readline()

def did(n, l, K, A):
	A, K = set(A), set(K)
	R = [pow(_, 2, n) + randint(0, 1) for _ in A - K]
	return R

def main():
	flag="zzsla"
	border = "+"
	pr(border*72)
	pr(border, ".::   Hi all, she DID it, you should do it too! Are you ready? ::.  ", border)
	pr(border*72)

	_flag = False
	n, l = 127, 20
	N = set(list(range(0, n)))
	K = [randint(0, n-1) for _ in range(l)]
	cnt, STEP = 0, 2 * n // l - 1
	
	while True:
		ans = sc().decode().strip()
		try:
			_A = [int(_) for _  in ans.split(',')]
			if len(_A) <= l and set(_A).issubset(N):
				DID = did(n, l, K, _A)
				pr(border, f'DID = {DID}')
                print(set(K))
                print(set(_A))
				if set(_A) == set(K):
					_flag = True
			else:
				die(border, 'Exception! Bye!!')
		except:
			die(border, 'Your input is not valid! Bye!!')
		if _flag:
			die(border, f'Congrats! the flag: {flag}')
		if cnt > STEP:
			die(border, f'Too many tries, bye!')
		cnt += 1

if __name__ == '__main__':
	main()

그래서 코드보면서 이해한 것과 코드 수정한 것을 합치면, 문제를 풀려면 _A집합과 K집합이 같아야 한다.

				if set(_A) == set(K):
					_flag = True

K집합이 맞춰야 하는 집합인데 0부터 126까지 무작위 숫자 20개가 들어가 있다.

	n, l = 127, 20
    K = [randint(0, n-1) for _ in range(l)]

사진을 보면 맨 아래에서 2번째가 무작위로 들어간 K집합이다.

숫자하나를 맞추면 DID에 숫자가 안 나오고, 틀리면 틀린 숫자에 계산이 이루어진 뒤에 나온다. 계산식은 해당 숫자에 2를 제곱한 뒤에 127로 나누고, 그 나눈 나머지에 0 또는 1을 더한 뒤에 출력을 한다.

def did(n, l, K, A):
	A, K = set(A), set(K)
	R = [pow(_, 2, n) + randint(0, 1) for _ in A - K]
	return R
...
	n, l = 127, 20

그리고 숫자를 확인할 수 있는 횟수는 12번이다. 그 이후엔 자동으로 종료가 된다. 2곱하기 127를 하고 19로 나누고 그 몫만 확인하면 STEP이 13인 것을 확인할 수 있다.

	cnt, STEP = 0, 2 * n // l - 1
...
		if cnt > STEP:
			die(border, f'Too many tries, bye!')
        cnt += 1

그리고 한 번 확인하는데 입력된 숫자가 20개가 넘어가면 종료가 된다.

			if len(_A) <= l and set(_A).issubset(N):
...
		except:
			die(border, 'Your input is not valid! Bye!!')

즉 문제를 풀려면 20개씩 모든 숫자(0~126까지)를 넣어서 계산으로 나온 숫자들을 확인한 뒤 없는 숫자를 찾아서 마지막에 제출하면 된다.

그러기 위해서 먼저 계산식이 이루어졌을 때 나오는 숫자들을 코드로 짰다.

코드를 돌리면 이런 식으로 나온다. 그리고 61,62,63,64,65,66은 같은 숫자가 나오니까 따로 넣어서 확인한다.

그렇게 값들을 확인하면서 무작위 숫자 집합인 K를 찾아서 보내면 문제가 풀린다.

CCTF{W4rM_Up_CrYpt0_Ch4Ll3n9e!!}