Archive

본 글에서는 MEGA의 취약점에 대해 다룬 논문(이하 2번 논문)을 소개합니다. 해당 논문은 MEGA: Malleable Encryption Goes Awry(이하 1번 논문)서 소개된 attack surface에서 정보를 더 효율적으로 추출하는 방법을 제안합니다.

간략히 설명하자면, 1번 논문에서는 RSA private key가 AES ECB mode로 암호화되었다는 사실을 이용하여 클라이언트의 로그인 시도가 임의의 수와 RSA public moduli $N$의 더 작은 소인수 간의 크기 비교가 가능한 oracle이 될 수 있음을 활용합니다. 이를 통해 512번 내지는 1024번의 로그인 시도가 축적되면 서버가 유저의 RSA private key를 알 수 있다는 점을 다루고 있습니다.

2번 논문에서는 유저가 challenge에 응답하는 과정에서 송신하는 정보의 양이 1번 논문의 공격자가 얻는 정보의 양보다 훨씬 많다는 점에 주목합니다. 다른 방식으로 다른 정보를 얻는 oracle과 payload를 구성하고, 적게는 6번에서 많게는 17번 정도의 로그인 시도만으로 유저의 RSA private key를 복구합니다.

MEGA의 구성

우선 공격 대상인 MEGA에서 프로토콜이 어떻게 구성되는지를 살펴보겠습니다. 공격 내용 설명의 편의를 위해 실제와는 다소 다를 수 있습니다.

[유저 생성 시]

각 유저에 대해 다음의 정보가 생성됩니다. 이는 로그인 시 변하지 않는 불변값입니다.

• master key (16byte) : AES Encryption을 위한 키입니다. MEGA에서는 ECB mode로만 AES를 활용하기에 iv값은 필요하지 않습니다.
• shared key : RSA2048 private key를 생성합니다. 구성은 다음과 같습니다.
  • $p,q$ : public moduli $N$의 서로 다른 두 소인수입니다. 각각 1024비트의 소수입니다.
  • $d$ : secret exponent입니다. public exponent $e$에 대해 $ed\mod \phi(N) = 1$을 만족합니다.
  • $u$ : $u\text{:=}q^{-1}\mod p$로 정의되는 값입니다. 연산속도 향상을 위한 CRT-RSA에서 사용되는 값으로써 저장되어있습니다

참고로, MEGA의 웹 클라이언트에서는 public  exponent $e$로 257을 사용합니다. 흔히 채택되는 65537과 비교하여 비트 길이 기준 절반 정도의 작은 크기입니다.

해당 정보를 생성한 후 shared key는 master key를 이용하여 AES ECB mode 암호화한 결과값 $ct$가 서버에 저장됩니다. 구체적으로는, RSA private key가 암호화 이전 다음과 같이 인코딩됩니다.

$$sk_{\text{share}}^{\text{encoded}} = l(q)\Vert q\Vert l(p)\Vert p\Vert l(d)\Vert d\Vert l(u)\Vert u\Vert P$$

$l(x)$는 $x$의 비트 길이를 의미하는 2바이트 값, $p,q,d,u$는 상기된 RSA private key이며 $P$는 16byte alignment를 맞추기 위한 패딩입니다. 여기서, 이전 데이터들의 총 길이가 648바이트이므로 패딩 $P$는 8바이트로 구성됩니다.

[유저 로그인 시]

유저의 로그인 시도가 발생할 시 서버는 다음과 같은 challenge $C$를 구성하여 유저에게 전송합니다. 마지막 SID의 추출에서 $m$은 256바이트로 패딩된 상태의 바이트열입니다.

$$C\text{:=}(SID_{\text{enc}},ct)$$

유저는 $C$를 수신한 후, 다음과 같은 계산 과정을 거쳐 $SID$를 구하고 이를 회신합니다.

$$\begin{align}m_p &\text{ := } c^{d\text{ mod }(p-1)}\text{ mod } p\\m_q &\text{ := } c^{d\text{ mod }(q-1)}\text{ mod } q\\m &\text{ := } ((m_p-m_q)u \text{ mod } p)q +m_q\\SID &\text{ := } m[2:44]\end{align}$$

서버는 해당 값이 $SID^e\text{ mod }N = SID_{\text{enc}}$를 만족하는지 확인하는지 확인합니다.

Malleable Encryption Goes Awry (1번 논문)

서술의 편의를 위해 $r\text{ := }\min\{p,q\}$라고 정의하겠습니다. CRT-RSA decryption의 마지막 계산식인

$$m \text{ := } ((m_p-m_q)u \text{ mod } p)q +m_q$$

에서 $m_p-m_q\neq 0$, 즉 $m_p \neq m_q$일 조건은 $m\ge r$입니다.

이때, 우리는 이 식을 계산할 때 사용되는 $p,q,d,u$가 서버가 제공하는 암호화된 shared key의 값에 의존적임을 상기해봅시다. 이는 즉 서버의 입장에서 암호화된 shared key를 다른 값으로 바꾸어도 이를 막는 장치가 없음을 의미합니다.

물론 이것이 암호화된 채로 서버에 저장되어있어 서버가 원하는 값으로 바꾸는 것은 불가능합니다만, 값을 바꾸는 것 자체는 가능합니다. 가령 40번 블럭을 랜덤으로 바꾸는 것이 이에 해당합니다.

위 내용을 기억하며, 서버가 challenge $({x}^e \text{ mod }N, ct^\prime)$을 보냈을 때를 생각해봅시다. 이때 $x$는 0 이상 $N$ 미만의 임의의 정수이며, $ct^\prime$은 $ct$의 40번 블럭을 임의의 값으로 변경한 암호화된 shared key입니다.

유저는 우선 $ct^\prime$을 복호화하여 조작된 shared key $(p,q,d,u^\prime)$을 획득합니다. 40번 블럭만이 변경되었으므로 $p,q,d$의 값은 변동이 없으며, $u^\prime$의 값은 서버가 알지 못함에 유의합시다.

유저는 아래 식을 이용하여 $m^\prime$을 계산합니다.

$$m^\prime \text{ := } ((m_p-m_q)u^\prime \text{ mod } p)q +m_q$$

여기서, $x$의 크기를 기준으로 경우를 나눠봅시다.

[ 1. $x<r$ ]

$m_p=m_q$이므로 $m^\prime = m_q$입니다. $m_q<q$이므로 $m^\prime$은 1024비트 이하의 값입니다.

따라서 $m^\prime$의 값은 패딩에 해당하는 후반 128바이트 내에 위치하며, $SID \text{ := } m[2:44]$에서 모두 truncate되어 결론적으로 $SID=0$이 도출됩니다.

[2. $x\ge r$]

$m_p=m_q$이므로 $m^\prime = ((m_p-m_q)u^\prime \text{ mod } p)q +m_q$입니다.

$m_p$는 높은 확률로 1024비트 이상의 값이므로, $SID\neq 0$입니다.

즉 우리는 SID가 0인지 아닌지를 통해 $x$와 $r$의 대소관계를 알 수 있습니다. 우리가 이러한 oracle을 갖고 있다는 것은 이분탐색을 통해 $r$의 값을 구할 수 있음을 의미합니다. $2\le p,q\le 2^{1024}$이며 각 로그인 시도에서 $r$의 MSB를 1비트씩 구할 수 있으므로 1024번의 로그인 시도로 $r$을 온전히 복구할 수 있습니다. 혹은, 512번의 로그인 시도로 상위 512비트를 구한 후 Coppersmith's method를 활용하여 512개의 LSB를 구할 수 있습니다. 1번 논문의 저자는 PoC에서 683번의 로그인 시도를 활용하여 RSA private key를 계산했습니다.

HNP-SUM: Cryptanalyzing MEGA in Six Queries and Other Applications (2번 논문)

2번 논문의 저자는 1번 논문에서 서술된 공격에 대해 다음과 같은 점을 지적했습니다.

• 1번 논문에서 이용하는 Coppersmith's method의 SOTA를 고려할 때, 로그인 시도의 수는 최소 512번 이상이다.
• 한 유저가 512번 로그인을 시도하는 것은 장기간의 수집이 필요하며, 현실적으로 불가능에 가깝다.
• 각 로그인 시도에서 유저는 344비트의 값을 반환하나, 이를 1비트의 정보로 치환하여 사용한다.

따라서 2번 논문의 핵심은 각 로그인 시도로부터 더 많은 정보를 얻는 것이며, 이는 CRT-RSA의 마지막 계산인

$$m \text{ := } ((m_p-m_q)u \text{ mod } p)q +m_q$$

가 Hidden Number Problem(이하 HNP)와 닮아있다는 것입니다. 저자는 이를 형식화하여 HNP-SUM을 소개합니다.

[HNP with Small Unknown Multiplier]

HNP-SUM에서 $N$, $a_i$, $T$, $E$가 주어지며 $1\le i \le n$인 $i$에 대해

$$\begin{align}a_i &\equiv_N t_ix+e_i\\\vert t_i\vert &\le T \\\vert e_i\vert &\le E\end{align}$$

를 만족하는 $x,t_i,e_i$가 존재합니다.

이때 공격자의 목표는 $t_i$를 부호, 공약수 정도의 오차로 구하는 것입니다.

[HNP-SUM to MEGA RSA Key Recovery]

HNP-SUM의 해결 방법을 다루기 전에, 이를 해결할 수 있을 때 MEGA에 어떻게 적용할 수 있는지 살펴보겠습니다.

모든 challenge $C$는 암호화된 shared key $ct$를 포함합니다. 이에 관해 몇가지 표기를 정의하겠습니다.

$$\begin{matrix}ct = ct_1\Vert ct_2\Vert\cdots\Vert ct_{41}\\ct_i = E_{\text{AES}}(pt_i)\\pt_i = D_{\text{AES}}(ct_i)\\pt = pt_1\Vert pt_2\Vert\cdots\Vert pt_{41}\end{matrix}$$

1번 논문에서와 유사하게 $u$의 값만이 변조된 상태를 생각해봅시다. 유저가 응답한 SID $s^\prime$는 다음과 같은 식을 만족합니다.

$$(m_p-m_q)u^\prime q +m_q\equiv_N e_1^\prime2^{b_1}+s^\prime2^{b_2}+2^{b_2-1}+e_2^\prime$$

$b_1,b_2$는 $s^\prime$을 제외한 $m$의 두 연속적인 부분의 위치를 나타내는 상수이며, $e_1^\prime,2^{b_2-1}+e_2^\prime$은 각 위치에 해당하는 $m$의 MSB, LSB입니다. $2^{b_2-1}$ 항은 $e_2^\prime$의 절댓값의 상한을 줄이기 위해 삽입되었습니다.

동일한 논리로, 같은 $m$과 다른 $u$값이 사용된 challenge의 유저 응답 $s^{\prime\prime}$에 대해서는 다음과 같은 식이 성립합니다.

$$(m_p-m_q)u^{\prime\prime} q +m_q\equiv_N e_1^{\prime\prime}2^{b_1}+s^{\prime\prime}2^{b_2}+2^{b_2-1}+e_2^{\prime\prime}$$

두 식을 빼면 다음과 같습니다.

$$(u^\prime-u^{\prime\prime})(m_p-m_q) q +m_q\equiv_N (e_1^\prime-e_1^{\prime\prime})2^{b_1}+(s^\prime-s^{\prime\prime})2^{b_2}+(e_2^\prime-e_2^{\prime\prime})$$

이때, 고정된 $i,j$에 대해 $ct^\prime,ct^{\prime\prime}$을 다음과 같이 구성합시다.

$$\begin{matrix}ct^\prime = ct_1\Vert ct_2\Vert \cdots \Vert ct_{33}\Vert ct_{i}\Vert ct_{i}\Vert \cdots\Vert ct_{i}\Vert ct_{41}\\ct^{\prime\prime} = ct_1\Vert ct_2\Vert \cdots \Vert ct_{33}\Vert ct_{i}\Vert ct_{i}\Vert \cdots\Vert ct_{j}\Vert ct_{41}\end{matrix}$$

이 경우 다음 식이 성립합니다. $\delta_{i,j}\text{ := }pt_i-pt_j$입니다.

$$u^\prime-u^{\prime\prime} = \delta_{i,j}2^{64}$$

위 식을 적용하여 서버가 획득한 정보를 다시 작성하면 다음과 같습니다.

$$2^{64}\delta_{i,j}(m_p-m_q) q +m_q\equiv_N (e_1^\prime-e_1^{\prime\prime})2^{b_1}+(s^\prime-s^{\prime\prime})2^{b_2}+(e_2^\prime-e_2^{\prime\prime})$$

이때 $x\text{ := }2^{64}(m_p-m_q)q, \Delta e_1\text{ := }e_1^\prime-e_1^{\prime\prime}, \Delta e_2\text{ := }e_2^\prime - e_1^{\prime\prime}, \Delta s\text{ := }s^\prime - s^{\prime\prime}$이라 하면 다음 식이 성립합니다.

$$\delta_{i,j}x\equiv_N \Delta e_1 2^{b_1} + \Delta s 2^{b_2} + \Delta e_2$$

위 식에서 $\Delta e_1$의 값만 알고 있다면, $t=\delta_{i,j},a = \Delta e_1 2^{b_1} + \Delta s 2^{b_2}$인 HNP-SUM의 instance로 볼 수 있습니다. 이때 $\vert \Delta e_1\vert< E_1\text{ := } 2^8$이므로 $\Delta e_1$은 brute-force를 통해 값을 알 수 있습니다.

즉, 서버는 각 로그인 시도로부터 $i,j$의 값을 바꿔가며 HNP-SUM의 식을 하나씩 획득할 수 있습니다. HNP-SUM에서 공격자의 목표가 $t_i$들을 복구하는 것이므로, 서버는 유용한 정보를 추출할 수 있도록 $\delta_{i,j}$를 선정해야 합니다. 2번 논문의 저자가 고른 방식은 다음과 같습니다.

• $i=18$로 고정합니다. 18번 블럭은 $d$가 포함된 두 번째 블럭이자 $d$의 비트만으로 구성된 첫 블럭입니다. 후술할 논리에 의해 이 값을 근사할 수 있습니다.
• $j$는 로그인 시도의 수에 따라 1부터 8까지를 사용합니다. 이는 $q$의 길이와 $q$의 상위 비트를 포함하는 블럭들입니다.

$2^{1024}$ 이상인 $m$을 랜덤하게 골라 고정하고 위와 같이 $ct$를 구성하여 로그인 시도를 수집하면 충분한 시도 수가 누적되었을 때 HNP-SUM을 통해 $\delta_{i,j}$를 구할 수 있습니다.

$\delta_{i,j}$를 올바르게 복구하였다고 가정합시다. RSA private exponent $d$는 다음 식을 만족합니다.

$$ed\equiv_{\phi(N)}1$$

이는 다음과 같은 정수 $k$가 존재함을 의미합니다.

$$ed=k\phi(N)+1=k(N-p-q+1)+1=kN-k(p+q-1)+1$$

또한, 비둘기집의 원리를 이용하여 그러한 음이 아닌 정수 $k$ 중 $e$ 이하인 것이 존재함을 알 수 있습니다.

이때, $p,q$가 $N$에 비해 매우 작으므로 $kN-k(p+q-1)+1$의 상위 약 1024비트는 $kN$과 동일함을 알 수 있습니다. 따라서 $pt_{18}$은 올바른 $k$에 대해 $\frac{kN}{e}$와 동일합니다.

서버는 $k$의 값을 알지 못하므로 0 이상 $e$ 미만의 모든 $k$에 대해 $pt_{18}$의 후보 $e$개를 획득합니다.

한편, $pt_1$의 첫 2바이트는 $l(q)$로 구성되어있습니다. $q$는 1024비트 정수이므로 이는 0x400의 값을 갖습니다. 따라서 이전에 구한 $e$개의 $pt_{18}$ 후보들이 구해진 $\delta_{18,1}$과 xor하여 상위 2바이트가 올바른 $l(q)$의 값인지 확인함으로써 서버는 각 $k$ 후보값을 검증할 수 있습니다.

올바르지 않은 $k$ 후보값에 대해 상위 2바이트는 uniform random의 결과값이라 간주하면, 올바르지 않은 $k$값이 검증을 통과할 false positive의 확률은 $\frac{e}{65536}$입니다. MEGA의 웹 클라이언트가 $e=257$을 활용하므로, 이 경우 거의 확실하게 유일한 $k$값의 후보를 얻게 됩니다.

올바른 $k$의 값을 획득하면 마찬가지로 $pt_j$의 값도 알 수 있습니다. 각 로그인 시도로부터 해당 값을 계산한 후 Coppersmith's method를 이용하면 6~7개 정도의 $\delta_{i,j}$ 값을 통해 public moduli $N$을 소인수분해할 수 있습니다.

[How to solve HNP-SUM with $n=2$]

$n=2$일 때, 공격자는 다음 관계를 만족하는 $N,a_1,a_2,T,E$를 알고 있다고 가정합니다.

$$\begin{matrix}a_1&\equiv_N& t_1x+e_1\\a_2&\equiv_N& t_2x+e_2\\\vert t_1\vert,\vert t_2\vert &\le& T\\\vert e_1\vert,\vert e_2\vert &\le& E\\\end{matrix}$$

이때 두 식의 적절한 선형조합으로 다음 식을 얻을 수 있습니다.

$$\begin{matrix}t_2a_1-t_1a_2&\equiv_N&t_2(t_1x+e_1)-t_1(t_2x+e_2)\\&\equiv_N&t_2e_1-t_1e_2\end{matrix}$$

위 값의 절댓값은 $2TE$ 이하로, $N$에 비해 작은 크기입니다. 따라서 다음의 격자 $B$는 짧은 벡터이며 SVP의 근사해로 추정되는 $(Et_2,-Et_1,t_1e_2-t_2e_1)$를 포함합니다.

$$B=\begin{bmatrix}E&0&a_1\\0&E&a_2\\0&0&N\end{bmatrix}$$

즉, $B$에 lattice reduction을 적용함으로써 공격자는 $t_1,t_2$를 얻을 수 있습니다. 다만 해당 값은 $g\text{ := }gcd(t_1,t_2)\neq1$인 경우 자명한 더 짧은 벡터 $(Et_2/g,-Et_1/g,(t_1e_2-t_2e_1)/g)$를 포함하므로 공격자는 부호와 공약수의 오차로 $t_1,t_2$를 계산할 수 있습니다.

[How to solve HNP-SUM with $n>2$]

$n=2$인 경우의 풀이로부터 자연스럽게 다음과 같은 격자 $B$를 생각해볼 수 있습니다.

$$B=\begin{bmatrix}E&&&&a_1\\&E&&&a_2\\&&\ddots&&\vdots\\&&&E&a_n\\&&&&N\end{bmatrix}$$

하지만 이 경우 lattice reduction으로 구한 SVP를 해석하는 것이 쉽지 않습니다. $n=2$인 경우와 다르게 $t_i$에 관한 식으로 SVP의 근사해를 표현하기 어렵기 때문입니다.

2번 논문의 저자는 두 행벡터만을 이용하여 구해진 부분격자(sublattice)들의 결과 역시 $N$에 비해서는 충분히 짧다는 사실을 이용하여 SVP의 근사해가 그러한 부분격자들의 선형 결합으로 표현될 확률이 높다고 가정합니다. 해당 가정이 참일 경우 각 부분격자에서의 가장 짧은 벡터들의 span은 $(n-1)$차원의 공간이 됩니다.

저자는 실험적으로 $B$에 대한 lattice reduction이 길이가 같은 선형 독립의 벡터 $(n-1)$개를 출력한다는 사실을 관찰하여 이를 뒷받침하였습니다.

이와 같은 결과를 활용하여 저자는 해당 $(n-1)$개의 벡터를 기저로 갖는 밀도 높은(dense) 부분격자 $B_\text{sub}$에 주목합니다.

$$\begin{matrix}b_i = i\text{-th row-vector of }B\\g_{i,j} = \gcd(t_i,t_j)\\v_{i,j} = t_jb_i/g_{i,j}+t_ib_j/g-k_{i,j}b_{n+1}\\B_\text{sub} = \{v_{i,j}\vert i,j\in\{1,\cdots,n\},i\neq j\}\end{matrix}$$

위와 같은 격자에 대해 저자는 다음의 $h_i$를 행벡터로 갖는 $B_\text{sub}$의 또다른 기저 $H$를 제시합니다. $H$는 upper-triangular matrix입니다.

$H$는 대각 위 성분들이 HNF의 조건 범위 내라는 보장이 없으므로 $B_\text{sub}$의 HNF와 완전히 일치하지는 않지만 leading non-zero term과 마지막 행을 변형하지 않는 행 연산을 통해 $B_\text{sub}$의 HNF를 만들 수 있습니다. 따라서 $H$를 구함으로써 $B_\text{sub}$의 HNF의 마지막 행을 계산할 수 있습니다.

이때, $u_{i,j}$는 $h_i$의 leading non-zero term을 최소화하는 계수로, 확장 유클리드 호제법을 통해 계산할 수 있습니다.

$$h_i = \begin{cases}\sum_{j=i+1}^{n} u_{i,j}v_{i,j} & \text{for } i<n-1\\v_{i,i+1}&\text{for }i=n-1\end{cases}$$

공격자는 $h_{n_1}$을 통해 $t_n$와 $t_{n-1}$의 값을 부호, 공약수의 오차로 구할 수 있음을 알 수 있습니다.

이러한 행렬의 정의는 각 $i$의 순서를 강제하지 않습니다. 따라서 적절히 순서를 바꿔가며 공격자는 전체 $t_i$를 계산할 수 있습니다.

여기까지의 내용으로 기본적인 공격의 골격을 알아보았습니다. 다만 위와 같은 과정만으로는 몇가지 한계가 존재합니다.

• 공격에서 사용 가능한 블럭의 수가 한정적이므로, 더 많은 로그인 시도를 확보할 수 있을 경우 사용할 페이로드의 수가 한정적입니다.
• 상위 8비트를 bruteforce하므로, 수행해야하는 lattice reduction의 수가 매우 많습니다.

따라서, 이후 내용에서는 위 3가지 한계에 대한 저자의 접근을 소개하겠습니다.

[How to make more available payloads]

해당 문제에 대한 해결법은 사실 간단합니다. 이전에 40번 블럭을 변조하여 $u$의 값을 바꾸었는데, 이를 대신하여 39, 38,...번 블럭을 변조하면 됩니다. 이와 같은 방법으로 다양한 $u$의 값으로부터 새로운 HNP-SUM 식을 얻을 수 있습니다.

이때 각 식에서 중복되는 $d_{i,j}$가 발생합니다. 이 경우 두 정보를 조합하여 더 압축적인 정보를 지닌 하나의 식으로 바꾸게 됩니다. 구체적으로는, 다음과 같은 식을 가진 상황입니다.

$$\begin{matrix}2^{128t}\delta_{i,j}x\equiv_N a_t-\epsilon_t\\2^{128t^\prime}\delta_{i,j}x\equiv_N a_{t^\prime}-\epsilon_{t^\prime}\end{matrix}$$

두 번째 식의 좌변은 첫 식의 좌변에 어떠한 상수를 곱한 값입니다. 따라서 두 식의 좌변을 각각 $y,ry$라 합시다.

첫 식으로부터 다음과 같은 사실을 알 수 있습니다.

$$y\in[a_t-E_1,a_1+E_1]$$

$$ry\in S_1=[ra_t-rE_1,ra_1+rE_1]$$

또한, 두 번째 식으로부터 다음과 같은 사실을 알 수 있습니다.

$$ry\in S_2\cup_{k=-\infty}^{\infty} [a_{t^\prime}-E_2+kN,a_{t^\prime}+E_2+kN]$$

이를 종합하면 $ry$는 $S_1\cap S_2$에 존재한다는 것을 알 수 있습니다. $S_1$,$S_2$의 각 구간의 길이는 $2rE_1+1$,$2E_2+1$이며 $S_2$의 각 구간 사이의 거리는 $N-2E_2-1$입니다. 이때 $S_1$의 길이가 $S_2$의 각 구간 사이의 거리보다 짧으므로 $S_1$은 $S_2$의 구간 중 최대 하나와 교차합니다. 해당 구간에 $ry$가 존재하므로 이와 같은 결과를 통해 $y$의 범위에 대한 두 식의 정보를 하나로 합칠 수 있습니다.

[How not to bruteforce MSBs]

상위 8비트를 bruteforce해야했던 가장 큰 이유 중 하나는, 모르는 비트의 위치가 불연속하면 lattice reduction을 통한 결과를 얻기 어렵기 때문입니다. 이와 같이 모르는 비트의 값이 2개의 연속한 위치로 표현되는 HNP의 변형 문제를 HNP-2H(2 Holes)라 하며 이 경우 다음과 같은 방법으로 해결할 수 있습니다.

핵심 아이디어는 $\Delta e_1C2^{b_1} \mod N$과 (\Delta e_2 C \mod N$을 동시에 작게 하는 $C$를 찾는 것입니다. 그러한 $C$를 잘 찾으면 공격자가 가진 HNP-SUM의 식들에서 $\Delta e_1$과 $\Delta e_2$의 영향을 연속한 LSB로 한정할 수 있습니다. 이는 다음과 같은 격자를 통해 구현됩니다.

$$B = \begin{bmatrix}E_1N&0\\E_12^{b_1}&E_2\end{bmatrix}$$

공격자는 lattice reduction을 통해 짧은 벡터 $v=E_1(C2^{b_1}\mod N),E_2C)$를 찾게 되며, Gaussian Heuristic에 의해 $C$는 다음과 같은 부등식을 만족합니다.

$$\begin{matrix}&\Vert v\Vert_2 \le \frac{2}{\sqrt{3}}\sqrt{\det B}=\frac{2}{\sqrt{3}}\sqrt{E_1E_2N}\\\Rightarrow&\vert \Delta e_1 C2^{b_1}+\Delta e_2C\mod N\vert\\\le&\vert\Delta e_1\vert\vert C2^{b_1}\mod N\vert+\vert\Delta e_2\vert\vert C\vert\\\le&E_1\vert C2^{b_1}\mod N\vert+E_2\vert C\vert\\\le&\Vert v\Vert_2+\Vert v\Vert_2\\\le&\frac{4}{\sqrt{3}}\sqrt{E_1E_2N}\end{matrix}$$

실제 공격에서 사용되는 값을 대입하여 위 식에서 보인 값의 상한을 확인하여 보면 약간의 정보손실이 존재하는 것을 확인할 수 있습니다. 다만 해당 기법을 통해 511번의 bruteforce를 피하고 HNP-SUM을 푸는 것만으로 문제를 해결할 수 있다는 장점이 있습니다.

Conclusion

본 글에서는 두 논문에서 MEGA의 구조적 취약점을 활용하여 유저의 RSA private key를 복구하는 과정을 살펴보았습니다.

특히 2번 논문에서는 격자를 활용한 정보 추출 방식과, 또다른 격자를 활용하여 공격을 최적화하는 방식을 확인하였습니다.

사실 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는 물론이거니와, 타원곡선에 대한 공격 또한 연구된 바 있다. 아직은 실질적인 공격이 가능한 만큼의 큐비트를 이용할 수 없지만, 머지 않은 미래에 가능해질 수 있다.

본 글에서는 Church Encoding의 기본적 개념과 이를 특정한 함수로 구현할 때 발생할 수 있는 문제점을 다룬다.

1. Church Numeral이란

Church Numeral은 어떤 함수 $f$에 대해 자연수 $k$를 $f^k$로 표현하는 것이다.

2. Church Numeral의 사칙연산

Church Numeral은 페아노 공리계를 만족하며 자연수에 대한 사칙연산을 정의할 수 있다.

• successor: 함수 $g$가 자연수 $n$을 encode하면 $f\circ g$는 $f\circ f^n=f^{n+1}$이므로 $g$의 successor이다.
• 덧셈: 자연수 $n$과 $m$을 encode하는 함수 $g$, $h$에 대해 $g\circ h$는 $f^n \circ f^m=f^{n+m}$이므로 $n+m$을 encode한다. 즉, $g\circ h$는 $g$와 $h$의 합이다.
• 곱셈: 자연수 $n$과 $m$와 $n$을 encode하는 함수 $g$에 대해 $g^m$은 $(f^n)^m=f^{nm}$이므로 $nm$을 encode한다. 즉 $g^m$은 $g$에 자연수 $m$을 곱한 결과이다.
• predecessor: $f$의 역함수 $f^{-1}$와 2 이상의 자연수 $n$을 encode하는 함수 $g$에 대해 $f^{-1}\circ g=f^{-1}\circ f^n=f^{n-1}$이므로 $f^{-1}\circ g$은 $n-1$을 encode하며 $g$의 predecessor이다.
• 뺄셈: 자연수 $n,m(n>m)$을 encode하는 함수 $g$, $h$에 대해 $g\circ h^{-1}$은 $f^n\circ (f^m)^{-1}=f^{n-m}$이므로 $n-m$을 encode한다. 즉, $g\circ h^{-1}$은 $g$와 $h$의 차이다. 이를 통해 $0$과 음수의 encoding을 자연스럽게 정의할 수 있다.

3. 유한 집합과 Church Numeral

Church Numeral을 특정한 함수를 이용하여 구현할 때, 어떤 함수를 쓰는지와는 무관하게 같은 수는 같은 함수로 encode된다. 다만, 사용하는 함수에 따라 "다른 수는 항상 다른 함수로 encode된다"는 명제는 성립하지 않을 수 있다. 특히, 유한 집합 $S$에 대해 $f:S\Rightarrow S$는 $f^a= f^b$를 만족하는 서로 다른 자연수 $a,b$를 무한히 많이 갖는다. 이를 증명해보자.

Proof: $\exists a,b\in S : a\neq b \land f^a = f^b$ 

$S$의 각 원소를 정점으로 갖고, 간선 집합이 $\{x\rightarrow f(x) | x\in S\}$인 함수 $f:S\Rightarrow S$가 존재하는 그래프를 functional graph라고 한다. functional graph가 사이클을 갖지 않는다고 가정하면, 임의의 $x\in S$에 대해 집합 $\{x, f(x), f^2(x),\cdots,f^{n(S)}(x)\}$는 크기가 $n(S)+1$이며 $S$의 부분 집합이다. 이는 모순이므로 functional graph는 사이클을 적어도 하나 가진다. 또한 모든 정점의 outdegree는 정확히 1이므로 모든 사이클은 단순 사이클이라는 것도 확인할 수 있다.

즉 functional graph는 단순 사이클과 그 사이클의 정점을 루트로 하는 몇 개의 트리로 구성된 component를 하나 이상 가진다. 따라서 모든 사이클의 길이 $L_1, L_2,\cdots$의 최소공배수 $L$, 어떠한 자연수 $N$에 대해 $x\ge N$이면 $f^x=f^{x+L}$인 $N$이 존재하므로 위 명제는 참인 동시에 그러한 $a,b$는 무한히 많이 존재한다.

4. 무한 집합과 Church Numeral

그렇다면, 무한 집합에서 정의되는 함수는 이러한 문제에서 자유로운가? $f(x)=ix$와 이를 일반화한 $f(x)=e^{i\frac{2k\pi}{n}}x$는 무수히 많은 길이 $n$의 단순 사이클이 나타난다.

이외의 예시로는 $f(x)=\sqrt{1-x^2}$이 있다. 위의 예시와는 다르게, 2개의 수가 사이클을 이루고 나머지 2개의 수가 사이클에 붙어 있는 꼴이다.

두번째 예시인 $f(x)=\sqrt{1-x^2}$와 $f(x)=-\frac{1}{x}$ 등의 예시를 통해 길이가 2인 사이클을 구성하는 수들을 정의역으로 할 때 사용한 함수 $f$는 $y=x$에 대해 대칭임을 알 수 있다. 나아가, $f:\mathbb{R}\Rightarrow \mathbb{R}$의 모든 사이클의 길이가 2일 필요충분조건은 $f:S\Rightarrow S$가 $y=x$ 대칭이며 정의역 $T$에서 $f$와 동일한 $g:T\Rightarrow S$가 존재하는 만족하는 두 집합 $S$와 $T=\mathbb{R}\backslash S$가 존재한다는 것임을 확인할 수 있다.

드림핵에서 주최한 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를 찾으면 된다.

Black Body Radiation

• Stephen-Boltzman Law: $P_{blackbody} = \sigma AT^4$
• Wien's Law: $\lambda_{peak}T=\text{Const.}$
• Rayleigh-Jeans Law: $R(\lambda,T)=\frac{2\pi ckT}{\lambda^4}$
• Plank's Law: $R(\lambda,T)=\frac{2\pi hc^2}{\lambda^5 (e^{hc/\lambda kT}-1)}$

Compton Effect: $\Delta\lambda = \frac{h}{m_0c}(1-\cos\theta)$

Bohr의 가정(각운동량 양자화): $L=mvr=n\hbar$

수소 원자

• $r_n = \frac{\epsilon_0n^2h^2}{\pi me^2}$
• $v_n = \frac{e^2}{2\epsilon_0 nh}$
• Bohr Radius $a_0=\frac{\epsilon_0h^2}{\pi me^2}$
• $r_n = a_0n^2$
• $K = \frac{me^4}{8\epsilon_0^2n^2h^2}$
• $U = -\frac{me^4}{4\epsilon_0^2n^2h^2}$
• $E=U+K = -\frac{me^4}{8\epsilon_0^2n^2h^2}$
• $R_H=\frac{me^4}{8c\epsilon_0^2h^3}$
• $\frac{1}{\lambda}=R_H\left(\frac{1}{{n_1}^2}-\frac{1}{{n_2}^2}\right)$

De Broglie wave length: $\lambda = \frac{h}{p}$

불확정성 원리: $\Delta x\Delta p\ge \hbar$, $\Delta E\Delta t\ge \hbar$

Schrodinger Equation(Time Independent)

• Hamiltonian: $H=\frac{P^2}{2m}+U$
• $P=\frac{\hbar}{i}\nabla=-\hbar^2\nabla^2=-\hbar^2\left(\frac{\partial^2}{\partial x^2}+\frac{\partial^2}{\partial y^2}+\frac{\partial^2}{\partial z^2}\right)$
• Schrodinger Equation: $H\psi = E\psi$
• Probability Density function: $P(x)=\psi^2(x)$
• normalization condition: $\int_{-\infty}^\infty\psi^2dx=1$

Bohr's correspondence principle: 양자적 현상의 scale을 키우면 고전역학적 분석에 수렴한다.

Inifinite Potential Well (1D)

• $-\frac{\hbar^2}{2m}\frac{d^2\psi}{dx^2}=E\psi$
• Boundary condition: $\psi=0$ at $x=0,L$
• $E=\frac{\hbar}{2m}\frac{n^2\pi}{L^2}=\frac{n^2h^2}{8mL^2}$
• $\psi_n=\sqrt{\frac{2}{L}}\sin\left(\frac{n\pi x}{L}\right)$

Infinite Potential Square Well (3D)

• $\psi(x)=A\sin\frac{n_x\pi x}{L}\sin{n_y\pi y}{L}\sin{n_z\pi z}{L}$
• $E = \frac{h^2}{8mL^2}({n_x}^2+{n_y}^2+{n_z}^2)$

Harmonic Oscillator

• $-\frac{\hbar^2}{2m}\frac{\partial^2 \psi}{\partial x^2}+\frac{1}{2}mw^2x^2\psi=E\psi$
• $-\frac{\hbar^2}{2m}\frac{\partial^2\psi}{\partial x^2}+\frac{1}{2}mw^2x^2\psi=E\psi$
• $E_n=\left(n+\frac{1}{2}\right)\hbar w$

Tunneling Effect: finite potential well의 경우 벽 너머서도 $\psi$가 nonzero -> 벽을 뚫고 외부로 나갈 확률 존재