[Zer0pts 2023] - moduhash

이 문제는 대회 도중에 내가 가장 많은 시간을 쏟은 문제.. 하지만 선배님들께 빼앗겨버린 문제.. 그리고 신박했던 문제이다. 공식적인 풀이가 올라온 뒤에 풀이를 보았는데, 도대체 이런 발상을 어떻게 할 수 있는지가 정말 궁금했던 문제이다. 반대로 앞으로 문제를 풀면서 절대 까먹지 않을 하나의 문제이기도 했다. ㅎㅎ

 

p.s 최근 들어 복소수 관련 문제들이 점점 많이 보이는데,, 이게 트렌드인가 싶기도 하고.. 여튼 나를 조금 더 동기부여했던 대회인 것 같다. 아주 만족스러웠던 대회 ~

🖲️ Code Analysis

import os

flag = os.environb.get(b"FLAG", "test{dummy_dummy_dummy}")

def S(z):
	return -1/z

def T(z):
	return z + 1

def gen_random_hash(n):
	r = bytes([getrandbits(8) for _ in range(0, n)])
	return r

def to_hash(st):
	res = ""
	for s in st:
		sts = bin(s)[2:].zfill(8)
		for x in sts:
			if x == "0":
				res += "S"
			else:
				res += "T"
	return res

def hash(z, h):
	res = z
	for s in h:
		if s == "S":
			res = S(res)
		elif s == "T":
			res = T(res)
		else:
			exit()
	return res

def hash_eq(h1, h2, CC):
	for _ in range(100):
		zr = CC.random_element()
		h1zr = hash(zr, h1)
		h2zr = hash(zr, h2)
		if abs(h1zr - h2zr) > 1e-15:
			return False
	return True

CC = ComplexField(256)
for _ in range(100):
	n = randint(32, 64)
	h1 = to_hash(gen_random_hash(n))

	zi = CC.random_element()
	print(f"zi	: {zi}")
	print(f"h1(zi): {hash(zi, h1)}")

	h2 = input("your hash> ")

	if not hash_eq(h1, h2, CC):
		print("your hash is incorrect")
		exit()

print(flag)

1. 임의의 복소수 zi 를 설정한다.

2. 일련의 random bytes 를 설정하여 각 비트가 0 이면 S, 아니면 T 로 바꾸어 string을 만들어낸다. 

3. 각 생성된 string에 대해서 S면 함수 S ( -1/ z) 를 실행하고, T 이면 함수 T( z + 1) 을 실행하게 된다. 

4. 모든 연산을 마쳤을 때의 결과값을 주고, 입력과 출력값으로 주어진 hash 를 역연산해내면 된다. 

5. 이 과정을 100번 통과했을 때 flag 가 주어진다. 

💡 Main Idea

먼저, 각 hash 함수에서 특징을 몇 가지 발견할 수 있다. 

 

1. S 연산이 2번 이상 반복되면 삭제된다는 것. 다시 말해서 SS 는 아무 연산도 하지 않은 상태가 된다. 

2. STSTST 또한 아무 연산도 하지 않은 상태가 된다. 이는 곧 $T^{-1} = STSTS$ 연산으로 이어진다. 

 

Decomposition of modular group elements

그 후에 이 페이지를 읽어보면 매우 흥미로운 점을 확인할 수 있다. 각 S, T 함수가 아무리 반복되어도 1차 꼴의 분수로 표현된다는 것이다. 

따라서 $h(zi) = \frac{a*zi + b}{c*zi + d}$ 꼴로 표현이 가능하다는 이야기다. 따라서 이 a, b, c, d 를 구해낸다면 역연산하는 것이 더 쉬워질 수 있을 것 같다. (유클리드 호제법 느낌으로 주어진 식에 n을 빼서 분자의 zi 계수를 최소화하고, S 연산을 통해 역수로 바꾸고,, 이런 계산을 반복하면 결국 zi 만 남도록 할 수 있지 않을까...?)

 

추가로, LLL 알고리즘을 이용해서 a, b, c, d 를 구해낼 수 있다고 한다. 

From mitsu on the Zer0pts discord server, Thanks to other people helped me to construct the matrix.. Thanks !!!

 

하지만, 아쉽게도 이 포스팅에서는 색다른 방법을 제시할 것이다. 바로 Mitsu 님의 공식 풀이인데, 이 풀이가 매우 참신해서 기억에 남는다. 

앞선 방식과는 다르게, mapping 을 이용해서 $zi$ 와 $h(zi)$ 를 서로 이어주는 작업을 할 것이다. 

 

두 점 모두 복소 평면에서 표현했을 때, 일련의 작업을 통해서 이 두 점을 다른 같은 점으로 대응시킬 수 있다면, 어느 한 과정을 역연산하여 합쳐준다면 $zi$ 를 $h(zi)$ 로 대응시킬 수 있다는 뜻이 된다. !!

 

그렇다면 이 주어진 두 점을 대응시킬 수 있는 복소 평면 위의 구역 (집합) 을 정의해보자. 

$ F = \left \{ point \;|\; abs(point.real()) < 0.5,\; point.norm() > 1 \right \}$

이를 그림으로 표현하게 되면 다음과 같다. 

y means imag, x means real number

여기서 잘 생각해보면, S 연산을 할 때는 norm 이 항상 1을 기준으로 바뀌는 것을 알 수 있다. 다시 말해서 위 사진의 원 내부에서 S 연산을 하면 항상 원 밖으로 나가게 되고, 반대로 원 외부에서 S 연산을 하면 원 내부로 들어오게 된다. 

 

또, 모든 필드의 점을 정수 부분만을 조정함으로써 real number 부분의 절댓값이 0.5 보다 작게 만들 수 있다 !!!

 

결국 이 말은, 위에서 말한 $F$ 라는 집합은 S 와 T 연산 상에서 독립적이라는 이야기이다. 서로 다른 $F$ 위의 점 a, b 는 S, T 연산을 통해서 절대 이어질 일이 없다는 것이다. 

 

따라서 $zi, h(zi)$ 를 모두 이 $F$ 상에 대응시킬 수 있다면, 같은 점이 될 것이라는 것은 자명함을 알 수 있다. 여기서부터는 이제 주어진 점을 F 위로 옮기는 작업인데, 이는 매우 쉬우니 생략하도록 하자. 

📖 Exploit Code

from pwn import *
from tqdm import *

REMOTE = 1
if REMOTE:
    io = remote("crypto.2023.zer0pts.com", int(10444))
else:
    io = process(["/usr/local/bin/sage", "server.sage"])

# context.log_level = "debug"

CC = ComplexField(256)

def S(z):
	return -1/z

def T(z):
	return z + 1

def inv_T(z):
    return z - 1

def hash(z, h):
	res = z
	for s in h:
		if s == "S":
			res = S(res)
		elif s == "T":
			res = T(res)
		else:
			exit()
	return res

def hash_inv(hsh):
    payload = ""
    for h in hsh:
        if h == "S":
            payload = "S" + payload
        else:
            payload = "STSTS" + payload
    return payload

def mapping(z):
    payload = ""
    while not (z.norm() > 1 and abs(z.real()) < 0.5):
        if z.real() >= 0.5:
            z = inv_T(z)
            payload += "STSTS"
        elif z.real() < -0.5:
            z = T(z)
            payload += "T"
        else:
            z = S(z)
            payload += "S"
    payload = payload.replace("SS", "").replace("TSTSTS", "")
    return (payload, z)

for _ in trange(100):
    io.recvuntil(b"zi	: ")
    zi = CC(io.recvline().strip().decode())
    io.recvuntil(b"h1(zi): ")
    hshzi = CC(io.recvline().strip().decode())

    (map1, res1) = mapping(zi)
    (map2, res2) = mapping(hshzi)
    hsh = map1 + hash_inv(map2)

    assert abs(res1 -  res2) < 1e-15

    io.sendlineafter(b"your hash> ", hsh.encode())

flag = io.recvline().strip().decode()
print(flag)