Archive

사실 ctf를 참가하려 하면 막상 귀찮아 열심히 풀지 않는 경향이 있는데, 동아리 내부 퀄은 나름의 의무감을 핑계로 시간투자를 할 수 있어 공부하기에 괜찮은 시기인것 같다.

Crypto

baby_crypto

$q$가 $p$의 next prime이니, $N$을 fermat factorization하면 될 것 같다. 문제는 $N$이 주어져있지 않다. 따라서 $N$을 구해야 하는데, $c\equiv m^e\text{ }(mod\text{ }N)$이라는 점을 활용할 수 있다. 주어진 평문 2개와 그 암호문에 대해서, $m^e-c$는 $N$으로 나눈 나머지가 $0$이므로 $N$의 배수이다. 따라서 $\gcd(m_1^e-c_1,m_2^e-c_2)$는 $N$의 배수이며, 일반적으로 $N$을 얻는다. $N$을 구한 후에는 간단한 fermat factorization을 시행하면 $p,q$를 얻을 수 있고, $d$를 계산하여 플래그를 복구할 수 있다.

Monopoly

auth에서는 mod $(2^130-5)$에서, 입력을 16바이트단위로 끊어 $r$에 대한 다항식의 계수로 차용하고, 마지막엔 상수항으로 $s$를 더하여 그 suffix 128bit를 추출하여(mod $2^128$) 반환한다. 데이터에 패딩이 들어가긴 하나, 그 앞의 내용을 자유롭게 변형 가능하다는 점에서 문제를 쉽게 만든다. 마지막을 제외한 모든 블럭을 널바이트로 채우면 $r$에 대한 2차 이상의 항은 모두 소거되므로, $kr+s\mod (2^130-5)$의 suffix 128bit를 알 수 있다. 이때 잘린 비트는 고작해야 2개비트이므로, 많아야 4가지 경우의 수가 존재한다. 따라서 $k_1r+s=x_1\text{ }(mod\text{ }2^130-5)$과 $k_2r+s=x_2\text{ }(mod\text{ }2^130-5)$를 연립하여 $r,s$의 후보 최대 16개를 알 수 있으며 이를 모두 get flag에 시도하여 flag를 얻을 수 있다.

Penguin

뭔가 펭귄이 보여야할 것 같은 문제이다. 제목부터 ECB 취약점을 써야할 것 같은데, 우선 염두하고 첨부파일을 확인하면 타원곡선을 가장한 무언가가 보인다. chunkwise encryption이며, 각 청크는 청크의 값 $x$에 대해 $\left(g^x+f(i+a+b+gx+gy)+gy\right)\mod N$을 계산한다. 이때 $f$는 계수가 알려진 3차 다항함수이므로 아무 암호학적 기능을 하지 못한다. 따라서, 주어진 암호화에서 $x$는 구할 수 없으나, $g^x$까지는 구할 수 있다는 사실을 확인했다. 이때 $x$가 같으면 $g^x$도 같으므로, "펭귄이 보였던 것처럼" $g^x$로 작성된 bmp파일을 확인하면 flag를 읽을 수 있다.

Triple RSA

$d\mod (p-1)(q-1)$은 $\mod pq$에서의 $e$의 modular inverse이므로, $\mod pq$에서 $2^(e\times hint)$를 계산하면 $2^{p+\text{ironore15}}$이다. $\text{ironore15}$는 알려진 상수값이므로, 우리는 $2^p$의 값을 계산할 수 있다. $2^p$는 $\mod p$에서 2와 같으므로, $2^p-2$는 $p$의 배수이다. 따라서 $pqr$과 $2^p-2$의 gcd를 계산하면 $p$를 계산할 수 있다. 이번엔 $\mod N$에서 $2^(e\times hint)$를 계산하면 이 값은 $kpq+2^{p+\text{ironore15}}$과 같으므로, $2^(e\times hint)-2^{p+\text{ironore15}}$와 $N$의 gcd로 $pq$의 값을 구할 수 있다. 즉, $q,r$의 값을 계산하여 flag를 복구할 수 있다.

Circle Crypto

hyperbolic curve over finite field의 대표적 예시 중 하나인 circle curve를 제시하였다. 해당 집합에서의 additive DLP는 정수 유한체에서의 multiplicative DLP로 치환 가능하며, $p-1$이 smooth하기 때문에 쉽게 해결 가능하다.

수많은 양자컴퓨터에 관한 연구가 보고되고 있는 요즈음, 뉴스에서도 종종 양자컴퓨터에 대한 이야기를 들을 수 있다. 그러한 기사에서는 종종 "쇼어 알고리즘"을 언급하며 기존 보안체계 붕괴 등을 전망한다. 본 글에서는 양자컴퓨팅이란 무엇인지부터 시작하여 양자컴퓨팅에 대한 기반 지식이 없는 독자가 쇼어 알고리즘을 이해하는 것을 목표로 한다.

Part I. What is "Qubit"?

"비트(bit)"라는 말을 들어보았는가? 고전적인 컴퓨터(현재 사용되는 컴퓨터)에서 다루는 가장 기본적인 단위의 데이터이며, 0 또는 1의 값을 갖는 한 자리의 이진수이다. 고전 컴퓨터는 여러 비트를 조합하여 여러 자리의 이진수를 표현하고, 이를 이용하여 수많은 데이터를 표현한다. 예를 들자면, 이진수로 1011101로 표현되는 수 93은 7개 이상의 비트를 조합하여 표현할 수 있다. 고전적인 컴퓨터는 전류가 흐르거나 흐르지 않음으로 비트의 값을 표현한다. 일반적인 디지털 컴퓨터는 전류의 구체적 세기와는 무관하게 역치값 이상의 전류가 흐르느냐의 여부로 0과 1이 정확히 나뉘는 이산적인 체계를 갖고 있다. 이것이 "디지털" 컴퓨터라고 불리는 이유이기도 하다.
 
양자컴퓨터는 "큐비트(Qubit)"라는 단위로 정보를 저장한다. 고전적인 컴퓨터에서 비트에 대응되는 개념인데, 그 저장 방식이 처음 보면 다소 신기하다. 양자컴퓨터의 핵심은 "중첩"이라는 물리적 현상으로, 간단하게 이야기하자면 매우 작은 입자를 관측하지 않는다면 그 입자는 여러 상태가 동시에 존재하다가 관측할 경우 그 중 하나로 랜덤하게 상태가 확정되는 현상이다. 랜덤박스를 생각한다면 이해가 좀 더 쉬울 것이다. 열기 전까진(관측하기 전까진) 내용물을 알 수 없지만(여러 상태가 동시에 존재하지만) 상자를 열면(관측하면) 내용물이 무엇인지를 확실히 알 수 있다.(상태가 확정된다.) 다만 이러한 비유는 실제 물리적인 현상과는 차이가 있어 오개념이 생길 수 있으므로, 이해가 잘 되지 않는다면 단순히 관측하면 여러 값 중 하나가 랜덤으로 선택되어 보여진다고 생각하면 된다.

이제부터 약간의 수식들과 함께 설명하고자 한다. 수식 없이 쇼어 알고리즘을 설명하기란 불가능에 가깝기 때문에, 양해를 바란다.
하나의 큐비트는, 관측할 때 "0"과 "1"이라는 두 가지 상태 중 하나로 확정되는 중첩 상태에 놓여있다. 즉, 큐비트는 관측 시 각각의 상태가 될 확률을 표기하는 것으로 표현하는 것이 합리적일 것이다.

위 이미지에서 $a$와 $b$는 무엇을 의미하는 것일까? 자세한 물리적 내용은 생략하나 각각의 상태는 파동으로써 표현되어, 확률은 파동의 변위의 제곱으로 표현되므로 $a^2+b^2$이 확률의 총 합으로 1이 되어야 함을 알 수 있다. $a$와 $b$는 두 상태에 해당하는 파동의 scale factor라고 생각할 수 있다. (물리적인 디테일은 크게 중요하진 않으므로 이해가 가지 않는다면 생략해도 좋다.)
 
우리는 큐비트들을 벡터를 이용하여 표현한다. Bra-Ket Notation이라 하는 표기법을 이용하는데, 행벡터를 Bra, 열벡터를 Ket이라 부르고 다음과 같이 표기한다.
$$\vert x\rangle=\begin{bmatrix}a_1 \\a_2 \\\vdots\end{bmatrix}$$
$$\langle x\vert=\begin{bmatrix}a_1 a_2 \cdots\end{bmatrix}$$
양자컴퓨팅과 관련한 수식 전개에서 흔히 사용되는 곱셈은 주로 내적(inner product)이므로, 우리는 $\vert a\rangle$와 $\vert b\rangle$의 내적을 $\langle a\vert b\rangle$과 같이 적는다.
또한, 본 글에서 사용되는 모든 벡터는 복소수체 $\mathbb{C}$에서 정의되므로, transpose 대신 hermition을 취한다는 것을 염두하고 글을 읽도록 하자.
$$\langle x\vert = \vert x \rangle^H$$
 
임의의 큐비트의 상태는 $\vert x\rangle = A\vert 0\rangle+B\vert 1\rangle$과 같이 표현된다. 이때 아래의 사실을 기억하고 넘어가자.
$$\vert 0\rangle=\begin{bmatrix}1\\0\end{bmatrix},\vert 1\rangle=\begin{bmatrix}0\\1\end{bmatrix}$$
$$|A|^2+|B|^2=1$$
여기서 $A,B$는 복소수이므로 단순히 제곱하는 것이 아닌, norm의 제곱을 구하여야 한다.
복소수의 극형식을 이용하면 $\vert x\rangle=ae^{i\theta}\vert 0\rangle+be^{i\phi}\vert 1\rangle$와 같이 표현할 수 있고, 두 상태0과 1이 물리적으로는 파동으로 표현된다는 것을 생각하면 중요한 것은 진폭과 위상 차이뿐이며, 실제 위상의 값은 중요하지 않으므로 $e^{i\theta}$로 나누어 소거하면 $\vert x\rangle=a\vert 0\rangle+be^{i\phi}\vert 1\rangle$로 표현할 수 있다.
 
$a^2+b^2=1$이므로 $a=\cos{\frac{\theta}{2}},b=e^{i\phi}\sin{\frac{\theta}{2}}$로 표현해보자. 구면좌표계 $(\sin\theta \cos\phi,\sin\theta \sin\phi,\cos\theta)$를 이용하면 우리는 임의의 큐비트 상태를 어떤 구면 위에 표현할 수 있음을 알 수 있다. 이를 블로흐 구면(Bloch Sphere)라고 부른다. x,y,z축의 단위벡터는 각각의 $\theta,\phi$를 계산해보면 $\frac{\vert 0\rangle+\vert 1\rangle}{\sqrt{2}},\frac{\vert 0\rangle+i\vert 1\rangle}{\sqrt{2}},\vert 0\rangle$라는 사실을 발견할 수 있다. 흔히 $\frac{\vert 0\rangle+\vert 1\rangle}{\sqrt{2}}$를 $\vert+\rangle$로, $\frac{\vert 0\rangle-\vert 1\rangle}{\sqrt{2}}$를 $\vert-\rangle$로 쓴다.

여러 수식을 이용하여 거창하게 설명했으나, 기억해야 할 점은 아직 단 하나의 큐비트에 대해서 설명했을 뿐이라는 사실이다. 당연하게도 실제로 유의미한 알고리즘을 작성하려면 여러 개의 큐비트를 동시에 사용해야 한다. 큐비트 $\vert x\rangle_0,\vert x\rangle_1,\vert x\rangle_2,\cdots$를 동시에 사용하면, 그 전체를 다루기 위한 벡터를 다음과 같이 표기할 수 있다.
$$\vert \psi\rangle=\vert x\rangle_0\otimes\vert x\rangle_1\otimes\vert x\rangle_2\otimes\cdots$$
여기서 $\otimes$는 tensor product로, $m\times n$ 행렬 $A$와 $p\times q$ 행렬 $B$의 tensor product는 다음과 같은 $mp\times nq$ 행렬로 정의된다. 또한 정의에서 알 수 있듯, tensor product는 결합 법칙이 성립한다.
$$A\otimes B = \begin{bmatrix}A_{11}B & A_{12}B & \cdots & A_{1n}B \\A_{21}B & A_{22}B & \cdots & A_{2n}B \\\vdots & \vdots & \ddots & \vdots \\A_{m1}B & A_{m2}B & \cdots &A_{mn}B\end{bmatrix}$$
우리는 여러 큐비트를 다룰 때 $2\times 1$ 행렬 $n$개의 tensor product를 이용하므로 이는 $2^n\times 1$ 행렬로써 표현된다. 이는 각각의 큐비트가 0 또는 1로 관측되는 $2^n$개의 모든 경우의 수를 표현하며, 해당 entry에 존재하는 값은 그 상태로 관측될 확률에 비례한다고 볼 수 있다. 따라서 우리는 $n$개의 큐비트를 사용할 때 $2^n$개의 기저가 필요하며, 이를 0부터 $2^n-1$까지의 수에 대응하여 다음과 같은 벡터로 표기한다.
$$\vert 0\rangle,\vert 1\rangle,\vert 2\rangle,\cdots,\vert 2^n-1\rangle$$
 

Part II. Control Qubits

고전적인 컴퓨터에서는 비트를 조작하는 방법으로 논리 게이트를 이용한다. 하나, 혹은 그 이상의 비트의 값을 받아 또 다른 값(혹은 값들)을 생성하는 것이 AND, OR, NOT, XOR과 같은 게이트들의 기능임을 알고 있을 것이다. 마찬가지로 양자컴퓨터에서는 큐비트를 조작하는 방법으로써 양자 논리 게이트를 이용한다.
 
논리 게이트는 여러 값을 받아서 하나의 값을 출력하거나 하나의 값을 받아 여러 값을 출력할 수도 있었으나, 이는 양자 논리 게이트에서는 불가능하다. 양자 논리 게이트에서는 정보의 소실이 발생할 수 없기 때문이다. 이러한 조건을 만족하는 연산을 unitary operation이라 하며 며 이에 해당하는 행렬 $U$는 unitary matrix이다.
$$UU^H=I, U^{-1}=U^H$$
 
다음은 몇가지 게이트의 예시이다.
$$\text{Pauli-X}=\begin{bmatrix}0&1\\1&0\end{bmatrix}$$
$$\text{Hadamard}=\frac{1}{\sqrt{2}}\begin{bmatrix}1&1\\1&-1\end{bmatrix}$$
$$\text{Controlled Not(CX)}=\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\end{bmatrix}$$
Pauli-X 게이트는 블로흐 구면에서 X축을 기준으로 180도 회전하는 연산이며, Hadamard 게이트는 Y축을 기준으로 반시계 방향 90도 회전하는 연산이다. $H(\vert 0\rangle) = \vert+\rangle, H(\vert 1\rangle)=\vert-\rangle$이며 $H(\vert +\rangle) = \vert 1\rangle, H(\vert -\rangle)=\vert0\rangle$이므로 초기 상태를 중첩상태로 만드는 등의 상황에서 자주 사용한다. Controlled Not 게이트는 입력 중 첫 비트를 Controlled bit로 사용하여, 해당 비트가 1일 때만 두 번째 비트에 Pauli-X 게이트를 적용한다.

Part III. Shor's Algortihm explained

드디어 글의 주제인 쇼어 알고리즘을 설명하고자 한다. 쇼어 알고리즘은 어떤 자연수 $N$의 비자명한 인수를 비트 수에 대한 다항시간복잡도에 해결하는 알고리즘이다. 고전적인 컴퓨터에서는 현재 $O(N^{1/4+\epsilon})$ 정도의 알고리즘이 알려져 있다는 사실을 생각하면 큰 수에 대해서는 가히 혁명적인 개선이다. 쇼어 알고리즘은 크게 다음과 같은 4개의 단계로 구분할 수 있다. 단계에 따라 살펴보자.

1. 임의의 정수 $1<a<N$을 선택한다. $\gcd(a,N)\neq 1$이라면 $\gcd(a,N)$은 $N$의 비자명 인수이므로 이를 반환한다. (classic)
2. 정의역이 $\{0,1,2,\cdots,Q-1\}$인 함수 $f(x)=a^x\mod N$의 주기 $r$을 구한다. (quantum)
3. $r$이 홀수이거나, $a^{r/2}\equiv -1\text{ }(\text{mod }N)$이라면 1.로 돌아간다. (classic)
4. $\gcd(a^{r/2}-1,N)$과 $\gcd(a^{r/2}+1,N)$을 반환한다. (classic)

Step 1.

gcd의 정의에 따라 $\gcd(a,N)$은 $N$의 약수이다. $1\le \gcd(a,N)\le a<N$이므로 $\gcd(a,N)\neq 1$이면 $1<\gcd(a,N)<N$, 즉 비자명 인수가 된다.
 

Step 2.

본 과정에서는 $N^2<Q=2^q<2N^2$인 $Q,q$에 대해 $q+n$개의 큐비트를 이용한다. 이중 $q$개의 큐비트는 함수 $f$의 값이 동일한 입력이 충분하도록 $\frac{Q}{r}>N$을 보장하기 위해서이며, $n$개의 큐비트는 함수값을 계산하는 과정에서 이용한다.
Step 2는 다음과 같이 세분화할 수 있다.
 

1. Hadamard 게이트를 이용하여 0부터 Q-1까지의 모든 수가 동등한 비율로 존재하는 중첩 상태를 만든다.
   $$\frac{1}{\sqrt{Q}}\sum_{x=0}^{Q-1}\vert x\rangle = \left(\frac{1}{\sqrt{2}}\sum_{x=0}^{Q-1}\vert x\rangle_0\right)\otimes\left(\frac{1}{\sqrt{2}}\sum_{x=0}^{Q-1}\vert x\rangle_1\right)\otimes\left(\frac{1}{\sqrt{2}}\sum_{x=0}^{Q-1}\vert x\rangle_2\right)\otimes\cdots\otimes\left(\frac{1}{\sqrt{2}}\sum_{x=0}^{Q-1}\vert x\rangle_{q-1}\right)$$
2. 함수 $f$를 양자게이트로 구현한 연산 $U_f$를 적용한다. ($U_f(\vert x\rangle)=\vert a^x\mod N\rangle$)
   이는 지수인 $x$를 이진 전개하면 $a^x=a^{\sum x_i\times 2^i}=\prod a^{x_i\times2^i}$과 같이 식을 변형할 수 있으므로 $t$번째 비트(0-based)가 1인 $\vert x\rangle$을 $\vert a^t x \mod N\rangle$로 바꿔주는 conditional multiplication을 이용하여 구현할 수 있다.
   $$\frac{1}{\sqrt{Q}}\sum_{x=0}^{Q-1}\vert x,0^n\rangle\Rightarrow \frac{1}{\sqrt{Q}}\sum_{x=0}^{Q-1}\vert x,f(x)\rangle$$
3. Quantum Fourier Transform을 적용한다.
   $$w=e^{\frac{2\pi i}{Q}}$$
   $$QFT = \begin{bmatrix}1&1&1&\cdots&1\\1&w&w^2&\cdots&w^{Q-1}\\1&w^2&w^4&\cdots&w^{Q-2}\\\vdots&\vdots&\vdots&\ddots&\vdots\\1&w^{Q-1}&w^{Q-2}&\cdots&w\end{bmatrix}$$
   $$\frac{1}{\sqrt{Q}}\sum_{x=0}^{Q-1}\vert x,f(x)\rangle\Rightarrow \frac{1}{Q}\sum_{x=0}^{Q-1}\sum_{y=0}^{Q-1} w^{xy}\vert y,f(x)\rangle$$
   이를 $f(x)$의 값을 기준으로 묶어 다시 쓰면
   $$\frac{1}{Q}\sum_{x=0}^{Q-1}\sum_{y=0}^{Q-1} w^{xy}\vert y,f(x)\rangle\Rightarrow \frac{1}{Q}\sum_{y=0}^{Q-1}\sum_{z=0}^{Q-1}\left(\sum_{f(x)=z}w^{xy}\right)\vert y,z\rangle$$
   집합 $\{x\vert f(x)=z\}$는 최솟값 $x_0$과 $x_0+kr$ ($k\in\mathbb{N}$)으로 구성된다. 즉, $\sum_{f(x)=z}w^{xy}$는 등비가 $w^{ry}$인 등비수열이다. $m=\left\lceil\frac{Q-x_0-1}{r}\right\rceil$로 정의하면 다음과 같이 $\vert y,z\rangle$이 관측될 확률을 계산할 수 있다.
   $$\begin{align}\Pr(\vert y,z\rangle) &= \frac{1}{Q}\left\vert\frac{w^{mry}-1}{w^{ry}-1}\right\vert^2 = \frac{1}{Q}\left\vert\frac{\cos\left(\frac{2\pi mry}{Q}\right)-1+i\sin\left(\frac{2\pi mry}{Q}\right)}{\cos\left(\frac{2\pi ry}{Q}\right)-1+i\sin\left(\frac{2\pi ry}{Q}\right)}\right\vert^2\\ &= \frac{1}{Q}\left\vert\frac{2-2\cos\left(\frac{2\pi mry}{Q}\right)}{2-2\cos\left(\frac{2\pi ry}{Q}\right)}\right\vert = \frac{1}{Q}\left\vert\frac{4\sin^2\left(\frac{\pi mry}{Q}\right)}{4\sin^2\left(\frac{\pi ry}{Q}\right)}\right\vert \\&=\frac{1}{Q}\left\vert\frac{\sin\left(\frac{\pi mry}{Q}\right)}{\sin\left(\frac{\pi ry}{Q}\right)}\right\vert^2 \end{align}$$
4. 위 확률은 $\frac{ry}{Q}$가 정수에 가까울 수록 다른 경우에 비해 극단적으로 값이 커지는 경향을 보인다. 따라서 우리는 그러한 $y$를 구할 수 있다. 이때 $\frac{ry}{Q}\approx c\in\mathbb{Z}$라 하자. $\frac{y}{Q}$는 알려진 값이며, $\frac{c}{r}$의 근사치이다. 따라서, $\frac{y}{Q}$를 연분수 전개(continued fraction expansion)하면 $\frac{c}{r}$의 좋은 근사값을 여럿 얻을 수 있으며, 높은 확률로 정확한 $r$의 값을 얻을 수 있다.
   
   

Step 3.

$r$이 홀수라면 Step 4를 진행할 수 없고, $a^{r/2}\equiv -1\text{ }(\text{mod }N)$이면 비자명 인수를 얻을 수 없으므로 알고리즘을 다시 실행한다. 그러할 확률은 크지 않아 알고리즘을 재실행하는 횟수는 일반적으로 0회, 매우 높은 확률로 수 회 내로 성공한다.

Step 4.

$b=a^{r/2}\mod N$은 $\text{mod }N$에서의 1의 비자명한 제곱근이다. 이는 $b^2\equiv 1\text{ }(\text{mod }N)$을 의미하며, $b^2=kN+1$을 만족하는 $k\in\mathbb{Z}$가 존재한다. 따라서 $(b-1)(b+1)=kN$이므로, $\gcd(b-1,N)$과 $\gcd(b+1,N)$은 $N$의 비자명한 인수이다.

Part IV. Essence of Shor's Algorithm

쇼어 알고리즘을 자연수 $N$의 비자명한 인수를 찾는 알고리즘이라고 소개했지만, 가장 중요한 부분은 양자컴퓨터를 이용해 계산한 Step 2이다. $f(x)=a^x\mod N$의 특수한 성질을 쓴 것이 아니라, 그저 주기함수이며 양자 게이트로 구현 가능하다는 사실이 중요했다. 이는 바꿔말하자면, 그러한 함수들은 양자컴퓨터를 이용하여 빠르게 그 주기를 계산할 수 있다는 뜻이다. 이러한 방식은 다양하게 응용될 수 있으며, 군 등의 순환 구조를 핵심으로 하여 위수의 기밀성이 중요한 (양자 내성이 없는) 현대 암호가 취약할 수 있음을 알 수 있다. 실제로 RSA는 물론이거니와, 타원곡선에 대한 공격 또한 연구된 바 있다. 아직은 실질적인 공격이 가능한 만큼의 큐비트를 이용할 수 없지만, 머지 않은 미래에 가능해질 수 있다.

드림핵에서 주최한 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이므로 해당 문제에서 이와 관련된 것을 다룰까 하여 기대했으나, 아쉽게도 그렇지는 않았다. 아직까지 문제 제목이 왜 이런지는 의문이다만, 크립토 문제 중에서는 난이도가 있어 솔브수가 적은 문제였다.

문제 난이도 때문에 끝까지 단독 솔브를 기대했으나, 또다른 팀이 풀어 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를 찾으면 된다.

11월 치뤄진 2022년 Whitehat Contest 본선에는 Crypto 카테고리에 Integration Bee라는 제목의 1문제가 출제되었다.

문제 제목에 포함된 Integration이라는 단어로 유추하건데, integration attack을 이용하는 문제일 것을 짐작할 수 있으니 알아두고 넘어가자.

문제에 제시된 cipher를 확인하면 경험적으로 내지는 약간의 구글링을 통해 4-round PRINCE cipher임을 알 수 있다. 또한, 64회의 chosen plaintext encryption oracle을 제공하므로, 총 64쌍의 plaintext-ciphertext 쌍을 계산할 수 있다.

이는 4bit nibble을 사용하는 PRINCE cipher에 대해 integration attack을 하기에 충분한 oracle 횟수임을 추측할 수 있다.

약간의 구글링을 거치면, integration attack을 이용하여 round-reduce PRINCE cipher에 대한 key recovery attack을 구현하는 논문을 발견할 수 있다. 여기에는 다양한 round 수의 PRINCE cipher에 대한 공격 방법을 제시하는데, 4round PRINCE cipher의 경우 권장 160쌍, 최소 32쌍의 plaintext-ciphertext 쌍을 사용해야하는 공격 방법이 상세히 설명되어있다. 이를 그대로 구현하면 되는데, 이때 인터넷에 공개되어있는 구현체를 참고하면 빠르고 정확하게 구현할 수 있다.

본 문제의 풀이에서는 $k_1\oplus k_0^\prime$ 복구에 2개의 active nibble set(총 32쌍), $k_1$ 복구에 2개의 active nibble set(총 32쌍)을 사용하였다. 논문에 제시된 권장량보다 한참 적은 양이지만, 256번의 local test에서 약 60%의 확률로 $k_1\oplus k_0^\prime$ 복구에 성공함을 확인하여 충분히 시도 가능한 수치라 생각하여 풀이를 강행하였다.

또한 $k_1$을 복구한 후 $k_0$를 복구하기 위해 $k_0$의 최상위 비트값을 알아야 하는데, 0으로 가정하여 성공 확률이 절반으로 감소한 솔루션을 작성하였다.

작성된 솔루션은 여기에서 확인 가능하며, 약 10회 정도의 솔루션 실행 후에 아래와 같이 flag를 획득하였다.

KAIST의 정보보안 동아리인 GoN에서는 매 정규학기 초에 동아리 정규회원 자격 유지를 위한 Qual을 진행한다. GoN의 정규회원은 이에 의무적으로 참가해 학기차 별로 특정한 문제 수를 풀어야 하는데, 최근에는 드림핵에서 해당 Qual이 Open Contest 형태로 진행한다.

이번 학기에는 2학기차 정규회원으로서 Qual에 참가하여 Crypto 3문제, Forensic 1문제를 해결하였으며 아래 기술된 내용은 내가 해결한 문제에 대한 write-up이다.

N. Private Storage

제공된 oracle은 임의의 plaintext에 대한 encrypt oracle 정도로 요약할 수 있고, flag와 key에 대한 암호화 정보를 받을 수 있다. 보통의 crypto task라면 key를 조작하는 등의 연산을 사용하는 것이 정해이고 거기에 cryptographic한 제약조건이 달려있겠지만, 놀랍게도 그냥 ARC4가 취약하기 때문에 여기서 key recovery를 시도하는 것이 풀이이다. 구글링을 통해 간단하게 key recovery에 대한 코드를 얻을 수 있으므로 이하의 풀이는 생략한다.

O. Checkers

Checker이라는 처음 보는 게임에 관한 얘기도 있고, 무언가 열심히 구현되어있지만 크게 중요하지 않다.

문제에서 제공되는 oracle은 flag의 ciphertext, 임의의 plaintext에 대한 encrypt oracle이며 이들을 내가 원하는 대로 무한히 호출할 수 있다.

중요한 것은 encrypt 함수의 구조인데, straddling_checkerboard, substitute, straddling_checkerboard_inv라는 연산을 차례로 적용하는 것이 하나의 encrypt이다. 편의상 straddling_checkerboard를 $C$, substitute를 $S$, straddling_checkerboard_inv를 $C^I$로 표기하자. 이때 $S$에 대해서 먼저 관찰해보자. $S$ 함수는 두 10진수를 인자로 받아 non-carry add, 즉 받아올림이 없는 덧셈을 진행한다. 이는 각 자릿수를 값으로 가지는 임의 차원의 벡터를 mod 10에서 더하는 것과 같으며, 호출되는 $S$ 함수는 키를 반복하여 평문에 더하는 것이므로 평문 한 자리와 이에 더해지는 키 한 자리의 벡터 꼴의 표현 $p,k$에 대해서 동일한 평문을 $n$번 더한 중간 결과물은 $p+n\times k$로 표현할 수 있다.

$S$ 연산을 평문에 여러번 적용하는 것을 특정한 꼴로 압축할 수 있다는 것을 발견하였으니, 이것이 공격에 사용될 수 있는지를 고려해 보아야 한다. encrypt 함수는 $C$, $S$, $C^I$를 차례로 적용하는데, encrypt 함수를 여러번 실행한다면 $C$, $S$, $C^I$, $C$, $S$, $C^I$, ... 꼴로 함수가 적용될 것이다. 이때 $C^I$와 $C$가 연속적으로 실행되어 상쇄되고, 결국 $C$, $S$, $S$, ..., $S$, $C^I$ 순서로 실행된 결과물과 같은 암호문을 얻는다. 만일 연속된 $S$ 연산의 결과가 연산을 하지 않았을 때와 같다면, 즉 $C$, $S$, $S$, ..., $S$, $C^I$ 연산의 결과가 $C$, $C^I$ 연산의 결과와 같다면 encrypt 함수의 입력과 출력은 동일하다.

연속된 $S$ 연산의 결과가 연산을 하지 않았을 때와 같기 위해서 생각할 수 있는 간단한 방법은 $p+n\times k$에서 $n$이 10이면 mod 10에서 $p$와 $p+n\times k$가 동일하다는 것을 활용하는 것이다. 따라서, 우리는 flag의 암호문을 받아 9번 더 암호화하면 그 결과로 flag를 찾을 수 있다.

C. pprintable

흔한 RSA task의 코드와 유사하게 생겼다. 랜덤한 두 소수 $p,q$를 생성하고 $N=pq$를 계산 후, $c=m^e \mod N$을 계산한다. 문제에서는 $N,e,c$를 제공한다. 이 문제에서 추가적으로 제공하는 정보는 두 소수의 각 비트의 값을 0.35의 확률로 노출하는 mask와 그 마스크를 씌운 redacted prime의 값, 그리고 두 소수는 printable character로만 구성되었다는 것이다. 이걸 대체 어떻게 찾았나 싶지만 아무튼 만들어서 문제를 출제했으니 문제에만 집중해보자.

문제의 주석에서도 언급하듯이 빠르게 풀 수 있는 비트 노출의 확률은 0.5가 하한선이다. 그렇지 않을 경우 bruteforce에서 가지치기가 가능한 경우가 충분히 많지 않아 시간이 오래 걸리게 되는데, 이 문제에서는 printable character라는 조건으로 이를 잘 보완해보라는 것이 출제 의도이다.

확률이 충분히 클 경우의 solution은 $\mod 2^k$에서 $pq\equiv N$을 만족하는 p, q의 값을 찾아 bruteforce하는 것이다. k의 값을 점점 키워나가며 두 소수의 원본 값을 찾는 형태로 solution이 동작한다. 이 풀이를 약간 변형하면 printable이라는 조건을 활용할 수 있다.

우리는 바이트 단위로 bruteforce를 진행하여도 가능한 p,q의 값의 수는 최대 $256\times256=65536$으로 충분히 작고, mask에서 제공된 정보와 printable이라는 조건을 통해 후보를 filtering하면 가능한 p,q의 수가 많지 않고 여럿 존재하더라도 금방 배제될 수 있음을 짐작할 수 있다. 따라서 바이트 단위로 printable character만을 대상으로 bruteforce하면 flag를 찾을 수 있다.

S. sleepingshark

문제에서는 수많은 패킷이 포함된 pcap 파일이 제공된다. 어떠한 두 장치의 HTTP 통신을 캡쳐한 것으로 보이며, 종종 broadcast 등의 잡다한 패킷도 포함되어있는 것을 확인할 수 있다. 패킷을 조금 살펴보면, POST를 통해 질의를 보내는 패킷을 발견할 수 있다. 해당 패킷들의 query string을 url decode해보면 flag의 어떤 인덱스의 한 글자를 특정한 문자와 비교하고 동일하다면 3초간 sleep, 그렇지 않다면 그냥 종료하는 query임을 확인할 수 있다. 이를 이용하여, 이 쿼리의 response가 약 3초 이상 경과한 시점에 캡쳐되었다면 비교했던 두 문자가 동일했다는 정보로 간주할 수 있다. 이를 이용하여 POST와 그 response에 해당하는 패킷만 골라내어 캡쳐된 시각의 차이를 근거로 flag를 복원하면 된다. 플래그의 모든 문자에 대한 정보가 없을 수 있는데, 패킷이 워낙 많기도 하고 적은 수의 글자만이 누락되었다면 게싱 혹은 flag bruteforcing으로 해결할 수 있을 것이다. 다행히도 모든 문자에 대한 정보가 포함되어 있으므로  이를 그대로 제출하면 된다.

이때, 수많은 패킷 중에서 POST와 그 response에 해당하는 패킷을 손으로 골라내기란 현실적으로 불가능한 일이다. 실제로 패킷을 필터링한 후에도 약 만개의 패킷을 분석해야 한다. 따라서 이러한 패킷을 찾는데에는 약간의 게싱이 필요한데, 초반의 몇십 패킷을 관찰하면 우리가 원하는 패킷만 그 길이가 300~400 정도로 다른 패킷에 비해 길다는 사실을 확인할 수 있다. 따라서 통신하는 장치의 ip와 패킷 길이로 필터링하면 우리가 원하는 패킷만을 얻을 수 있다. 이후에는 csv로 export하여서 python을 통해 위에서 언급한 solution을 구현하면 flag를 쉽게 얻을 수 있다.

시작하기에 앞서, Baby-step Giant-step Algorithm(BSGS Algorithm)을 이해하기 위해 필요한 이산 로그 문제(Discrete Logarithm Problem, DLP)에 대해 간단히 설명하겠다.

일반적으로 양의 실수 집합에서 정의되는 로그(Logarithm)는 $a^x=b$에서 $x$를 의미한다. 이와 유사한 의미로, 한 원소를 곱셈의 항등원에 곱하는 연산을 몇 번 적용해야 하는지를 의미한다. 특히 $\mathbb{Z}/p\mathbb{Z}$에 대한 이산 로그 문제는 다음과 같이 정의할 수 있다. 이때 $p$는 소수이다.

$\mathbb{Z}/p\mathbb{Z}$의 원소 $b,n$에 대해 $b^x\equiv n\text{ }(\text{mod }p)$를 만족하는 $0$ 이상 $\phi(p)=p-1$ 미만의 정수 $x$를 찾아라.

BSGS Algorithm은 위와 같은 $\mathbb{Z}/p\mathbb{Z}$에서의 DLP를 $O(\sqrt{p}\lg p)$의 시간복잡도에 해결할 수 있는 알고리즘이다. 완전탐색을 제외한 DLP 알고리즘 중 간단한 편에 속한다. 알고리즘의 pseudo code를 소개하자면 다음과 같다.

1. $0$ 이상 $\lceil\sqrt{p}\rceil$ 미만인 모든 정수 $c$에 대해 $b^c\mod p$를 집합 $S$에 삽입한다. (Baby-step)
2. $1$ 이상 $\lceil\sqrt{p}\rceil$ 미만인 모든 정수 $k$에 대해 $n\times b^{-k\lceil\sqrt{p}\rceil}\mod p$를 계산하고, 이 값이 $S$에 있는지 확인한다. 있다면 $b^c\mod p = n\times b^{-k\lceil\sqrt{p}\rceil}\mod p$를 만족하는 $c$를 찾는다. (Giant-step)
3. $x=k\lceil\sqrt{p}\rceil+c$를 결과로써 반환한다.

BSGS Algorithm의 정당성 증명

임의의 $p$ 미만의 음이 아닌 정수는 $\lceil\sqrt{p}\rceil$ 미만이고 음이 아닌 두 정수 $a,b$에 대해 $a\lceil\sqrt{p}\rceil+b$ 꼴로 표현할 수 있다. $x$는 존재할 때 0 이상 $p-1$ 미만인 것이 존재한다는 것이 보장되므로, 모든 존재하는 지수는 $a\lceil\sqrt{p}\rceil+b$ 꼴로 표현 가능하다는 사실을 기억하자.

2.에서 $n\times b^{-k\lceil\sqrt{p}\rceil}\mod p$가 $S$에 존재한다면, $b^c\equiv n\times b^{-k\lceil\sqrt{p}\rceil}\text{ }(\text{mod }p)$를 만족하는 $\lceil\sqrt{p}\rceil$ 미만의 음이 아닌 정수 $c$가 존재한다는 것을 알 수 있다.

이 식의 양변에 $b^{k\lceil\sqrt{p}\rceil}$를 곱하면 $n\equiv b^{k\lceil\sqrt{p}\rceil+c}\text{ }(\text{mod }p)$을 얻는다. 따라서 $x=k\lceil\sqrt{p}\rceil+c$를 얻을 수 있다.

BSGS Algorithm의 시간복잡도 증명

분할정복을 이용해 거듭제곱을 계산하면 $a^b\mod p$는 $O(\lg b)$에 계산 가능하다. 또한 잘 구현된 집합 구현체를 이용하면 원소의 존재 여부를 집합의 크기 $n$에 대해 $O(\lg n)$에 판단 가능하다.

따라서 1.에서는 $\lceil\sqrt{p}\rceil\times O(\lg p)=O(\sqrt{p}\lg p)$의 시간이 소요된다.

2.에서는 거듭제곱과 모듈로 역원을 한 번 계산하고 집합에의 포함 여부를 판별하는데 각각 $O(\lg p)$의 시간이 소요되므로 총 $O(\sqrt{p}\lg p)$의 시간이 소요된다.

결론적으로 BSGS Algorithm은 $O(\sqrt{p}\lg p)$의 시간에 이산 로그 문제를 해결할 수 있음을 확인할 수 있다.

BSGS Algorithm의 구현

이산 로그를 구현한 대부분의 잘 알려진 구현체는 BSGS보다 빠른 시간에 동작하는 pollard-rho algorithm, 혹은 pohlig-hellman algorithm 등을 구현한다. 따라서 이들을 사용 가능하다면 사용하기를 권장한다. 아래는 C++로 구현된 BSGS algorithm이다.

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

ll ipow(ll x,ll n,ll p){
    if(n==0)return 1;
    if(n==1)return x%p;
    if(n==2)return (x%p)*(x%p)%p;
    ll k=ipow(x*x%p,n/2,p);
    if(n%2==1)k=k*x%p;
    return k;
}

ll discrete_log(ll n,ll b,ll p){
    set<ll> s;
    ll k=ceil(sqrt(p));
    ll binvk=ipow(ipow(b,k,p),p-2,p);//by fermat's little theorem
    ll t;

    //baby-step
    t=1;
    for(ll i=0;i<k;i++){
        s.insert(t);
        t*=b;
        t%=p;
    }
    
    //giant-step
    t=1;
    for(ll i=0;i<k;i++){
        ll x=n*t%p;
        if(s.find(x)!=s.end()){
            t=1;
            for(ll j=0;j<k;j++){
                if(t==x){
                    return i*k+j;
                }
                t*=b;
                t%=p;
            }
        }
        t*=binvk;
        t%=p;
    }
    return -1;
}