[ImaginaryCTF 2023] - tan

이번에는 imaginaryCTF.. soon_harri 씨가 사이코 톡방에 같이 할 사람을 모집했지만, 내 실력을 키우고 나서 같이 해야 할 것 같아서 일단 혼자서 진행해 보았다. 이번 씨텦에서는 신박한 문제들, 그리고 새로운 기법들이 많이 나와서 좋은 경험이 되었던 것 같다.

 

몇가지 아쉬운 점은,, 대회 당시에는 풀지 못했던 것들이 대회가 끝나고 나서야 쉬워보이는 것들이 상당히 많았다는 것이다.. 그래서 정말 정말 아쉬웠던 대회이지만, 많은 것을 얻어가기도 했던 것 같아 기분이 좋다.

🖲️ Code Analysis

print(tan(int.from_bytes(open("flag.txt", "rb").read().strip(), "big")).n(1024))
# -0.7578486465144361653056740883647981074157721568235263947812770328593706155446273431983003083023944193451634501133844062222318380912228469321984711771640337084400211818130699382144693337133198331117688092846455855532799303682791981067718891947573941091671581719597626862194794682042719495503282817868258547714

의심스럽겠지만 코드가 한줄이다. 플래그를 그냥 tan 함수에 넣은 값을 출력하는 것이다. 

당연하게도? tan 함수가 있다면 arctan 함수 또한 존재하기 때문에 바로 역연산이 가능할 것이다. 

💡 Main Idea

당연하게도 그렇게 바로 풀리는 문제였으면 블로그에 포스팅 하지도 않았다 ㅋㅋ

tan 함수 그래프

탄젠트 함수는 알다시피 $\pi$ 를 주기로 이루어진다. 그 말은 곧 arctan 함수의 치역, 공역은 $-\frac{\pi}{2}$ 과 $\frac{\pi}{2}$ 사이에서 모두 끝난다는 것이다. 따라서 flag 값이 나올 리가 없다. 

 

따라서 우리가 arctan 을 이용해서 구한 값은 $flag - n \times \pi$ 와 같은 형태가 될 것이다. 결국은 주어진 값에 $\pi$를 몇번 더하거나 빼서 정수로 만들어주는 것이 우리의 목표라고 생각할 수 있다. (소수점 아래 1024 비트를 표현했기 때문에 정수로 나타내는 것이 이 문제의 관건이 될 것이다.)

 

지금까지 크립토 해 왔으면 그냥 어떻게 풀지 생각나야 하는 문제라고 생각한다.. 바로 LLL 이다!!

그럼 바로 행렬을 구성해보자. 

$$\begin{bmatrix}
flag \times 2^{1024} & 0 & 0\\ 
\pi \times 2^{1024} & 1 & 0\\ 
2^{1024} & 0 & 1
\end{bmatrix}$$

 

이렇게 행렬을 구성하면, 모두 $2^{1024}$ 배를 해주었기 때문에 정수 부분만 생각해볼 수 있고, $\pi$ 와 1을 arctan 의 결과로부터 자동으로 빼주었기 때문에, LLL 돌린 행렬의 M[0][2] 부분이 진짜 flag 가 될 것이다. 

📖 Exploit Code

from Crypto.Util.number import *

res = -0.7578486465144361653056740883647981074157721568235263947812770328593706155446273431983003083023944193451634501133844062222318380912228469321984711771640337084400211818130699382144693337133198331117688092846455855532799303682791981067718891947573941091671581719597626862194794682042719495503282817868258547714

flag = int(atan(res) * 2^1024)
p = int(pi.n(1024) * 2^1024)

M = matrix([[flag, 0, 0],
            [p, 1, 0],
            [2^1024, 0, 1]])
M = M.LLL()

flag = long_to_bytes(int(M[0][2])).decode()
print(flag)

허허,,, cos 나 sin 도 깰 수 있냐고 하는데, 아마 동일한 방법으로 하면 깨질 것 같긴 하다.. ^^