2022 Christmas CTF 후기

7위

 

풀이 기록

드림핵에서 주최한 2022 Christmas CTF에 도롱뇽과학고등학교 2022 팀으로 참가하여 팀이 해결한 9문제 중 7문제를 해결하였고, 결과적으로 7위로 마무리하였다.

 

국내 ctf는 크립토 문제가 거의 출제되지 않거나 출제되어도 기초적인 수준인 경우가 많은데, 드림핵인 만큼 재밌게 풀만한 문제가 여럿 출제된듯 하다.

 

크립토 이외의 문제도 몇가지 해결하여 그 풀이도 기술할 예정이다.

 

Welcome - Misc

별다른 묘사 없이, flag를 읽는 파일의 존재와 ssh 접속 정보가 기술되어있다. ssh에 접속해보면 cd를 비롯하여 몇가지 제약사항이 있다는 것을 확인할 수 있다. 때문에 flag를 읽는 파일을 일반적으로 호출하기가 어려운데, 이를 find 명령어의 -exec 옵션을 이용하여 우회할 수 있다.

 

find a gift - Misc

리모트에 접속해보면, 현재 위치한 곳의 address와 갈 수 있는 address가 기술되어있다. 즉, 모종의 그래프 탐색을 요구하는 문제라고 볼 수 있다. 직접 몇 번 탐색을 해보니 완전이진그래프 꼴인 것 같았으나, ctf task로 출제한다면 노드의 수를 많게 해놓고 약간의 변형을 줄 수 있다 생각하여 일반적인 비재귀 DFS 알고리즘을 작성하여 문제를 해결하였다.

 

the present - Crypto

코드를 확인해보면 PRNG라는 class에서 유사난수를 생성하는 것을 확인할 수 있다. 그 생성 방식은 직전의 수를 거듭제곱하여 소수 P로 나눈 나머지를 취하는 것으로, 매우 취약한 방식이다. 직전의 수에만 의존하기 때문에 하나의 난수를 확보한다면 이후 난수를 전부 예측할 수 있기 때문이다. 다만 문제에서는 현재의 난수를 통해 직전의 seed를 계산해야 하기 때문에 문제의 난이도가 조금은 올라갔다고 볼 수 있다. 여기서 문제가 되는 것은 P를 4로 나눈 나머지가 3이므로 tonelli-shanks 알고리즘을 통해 이산 거듭제곱근을 계산하는 것이 매우 쉽다는 점이다. 따라서 단순히 거듭제곱근을 구하고, 가능한 두 거듭제곱근 중 flag 형식을 만족하는 수를 찾으면 된다.

 

Collatz_conjecture - Misc

콜라츠 추측은 수학계에서 매우 유명한 문제로, 단순한 문제 정의와는 상반되게  많은 수학자들의 노력에도 아직까지 해결되지 않은 난제이다. 컴퓨터를 이용하여 매우 큰 수까지도 콜라츠 추측이 성립함이 알려져 있으므로 실제 콜라츠 추측의 반례를 찾는 것은 의도된 풀이가 아닐 것이다. 문제에서 제시된 소스코드를 확인하여 보면 C언어로 작성되어, 입력을 unsigned int64에 저장하고 콜라츠 추측을 검증한다. 이때 콜라츠 추측은 입력보다 큰 수가 그 과정에서 등장할 수 있으며, 이는 오버플로우를 발생시켜 의도되지 않은 방향으로 프로그램을 진행시킬 수 있다. 체인의 길이가 긴 솔루션을 찾는 것은 다소 복잡하며 많은 시간을 요하므로 $3x+1=2^{64}$인 $x$를 찾아 $x$->0->0의 체인으로 문제를 해결하였다.

 

Red-Black Christmas Tree - Crypto

red-black tree는 많은 곳에서 사용되는 self-balancing binary search tree이므로 해당 문제에서 이와 관련된 것을 다룰까 하여 기대했으나, 아쉽게도 그렇지는 않았다. 아직까지 문제 제목이 왜 이런지는 의문이다만, 크립토 문제 중에서는 난이도가 있어 솔브수가 적은 문제였다.

Red-Black Christmas Tree - First Solve :)

문제 난이도 때문에 끝까지 단독 솔브를 기대했으나, 또다른 팀이 풀어 2솔브로 마무리된 문제이다.

문제에서 제시된 코드를 확인해보면, $O(N^2)$ 곱셈을 구현한 듯한 함수와 분할정복을 이용한 거듭제곱을 구현한 듯한 함수를 확인할 수 있다. 다만 눈에 띄는 점은, 덧셈과 뺄셈이 있어야 할 자리에 XOR이 있다는 점이다. 여기서 생각할 수 있는 것은 대부분의 ctf task에서 단 하나뿐이다. 비트별로 별도의 수를 의미하는, $\mathbb{F}_2$ 상의 연산이라는 것이다. 즉, 해당 문제에서 각각의 정수는 $\mathbb{F}_2/n$의 원소인 다항식을 의미한다. 이때 $n$은 제시된 정수 $n$을 다항식으로써 해석한 것이다. 조금 다르게 말하자면 2진법에서 각 자리수는 0 또는 1이라는 규칙은 남긴채로 진수만 2에서 $X$로 변경한 것이다. 따라서 본 문제의 풀이는 $\mathbb{F}_2/n$에서의 RSA이며, RSA의 암호학적 안전성은 order의 비밀성에서 기인한다는 점을 생각할 때 $\mathbb{F}_2/n$의 order를 계산하면 문제를 해결할 수 있으므로 이를 계산하여 0x10001제곱하는 연산의 역연산을 구하여 계산하면 flag를 복구할 수 있다.

 

where's the box - Crypto

정수 $m$을 임의의 난수 $r$에 대해 $g^mr^n\mod n$으로 암호화하는 암호 시스템의 encrypt oracle, decrypt oracle, encrypt flag oracle이 제공된다. 이때 임의의 두 정수가 서로소일 확률은 $\frac{6}{\pi^2}$이므로 flag를 3회 정도 encrypt한 후 gcd를 취하면 $g^{flag}$를 어렵지 않게 구할 수 있다. 이때 decrypt oracle에서는 복호화 결과가 flag의 배수이면 결과를 보여주지 않는데, 이는 $g^{flag}$를 거듭제곱한 값의 복호화를 방지한다. 그럼에도 $g^{flag+1}$의 복호화 결과는 보여주므로 이를 계산하여 복호화하면 flag를 얻을 수 있다.

 

santa's sack - Crypto

flag를 내가 습득하진 않았지만, 풀이를 도우며 도출한 풀이를 작성한다. b[0]의 값이 될 수 있는 후보는 1226~2450의 1225개의 정수이다. 이에 대응되는 b[1]의 개수까지 고려하면 (b[0],b[1])의 개수는 대략 몇백만개 정도로 bound된다. 각각의 후보에 대해, $x\times b[0]+y\times b[1]=\gcd(b[0],b[1])$의 확장 유클리드 호제법을 해결하면 $r\times \gcd(b[0],b[1])+kq$의 값을 얻을 수 있다. $\gcd(b[0],b[1])$이 1일 확률은 다소 높으므로 그럴 것이라 가정하고 수식을 전개하면 $q$ 값 역시 복구할 수 있으며, 이렇게 얻은 $r$과 $q$가 올바른 값임은 b 배열을 모두 복구하여 superincreasing sequence임을 확인하여 알 수 있다. b 배열을 복구한 후에는 암호문에 적절한 연산을 취한 후 복구한 b 배열의 knapsack 문제로 변환되므로 이를 CJLOSS 알고리즘을 이용하여 해결하면 flag를 얻을 수 있다.

 

Windows Search - Forensic

.edb 파일이 제공되어, https://moaistory.blogspot.com/2018/10/winsearchdbanalyzer.html에서 WinSearchDBAnalyzer 다운로드 후 flag.txt를 찾으면 된다.