The Hidden Number Problem with Small Unknown Multipliers: Cryptanalyzing MEGA in Six Queries and Other Applications

본 글에서는 MEGA의 취약점에 다룬 해당 논문에 대해 소개합니다.

해당 논문은 MEGA: Malleable Encryption Goes Awry에서 소개된 공격 표면에서 격자를 활용한 방법으로 실제 공격을 현실적으로 가능한 수준으로 개선합니다.

MEGA의 구성

위의 두 논문을 소개하기에 앞서, 간편화한 MEGA의 인스턴스를 소개하겠습니다.

MEGA 인스턴스는 유저가 계정을 생성하였을 때와 유저가 로그인을 시도할 때에만 동작한다고 가정합니다.

1. 유저 계정 생성 시

클라이언트는 다음의 두 키를 생성합니다.

• master key (16byte, 이하 $k_m$으로 표기)
  • AES 암호화를 위한 키입니다.
  • 본 인스턴스에서는 ECB 모드만 이용하므로 iv는 필요하지 않습니다.
• shared key (RSA2048 비밀키, 이하 $sk_\text{shared}$로 표기)
  • RSA2048의 비밀키입니다.
  • $p,q$ : 공개키 $N$의 서로 다른 두 소인수입니다. 각각 1024비트의 소수입니다.
  • $d$ : 비밀 지수입니다. 공개 지수 $e$에 대해 $ed\equiv_{\phi(N)} 1$을 만족합니다.
  • $u$: $q^{-1}\text{ mod }p$로 정의되는 값입니다. CRT-RSA에서 연산 속도 향상을 위해 저장합니다.

논문 작성 시점에서 MEGA 웹 클라이언트는 공개 지수 $e$로 $257$을 사용했습니다.
일반적으로 권장되는 $65537$과 비교하여 매우 작은 값이며, 흔히 $e=257$의 셋업을 쓰는 경우 다양한 대수적인 공격 옵션이 생깁니다.

해당 정보가 생성된 후 shared key $sk_\text{share}$은 다음과 같이 $sk_\text{shared}^\text{encoded}$으로 직렬화한 후 master key $k_m$를 이용하여 AES ECB 모드로 암호화한 값 $ct$가 서버에 저장됩니다.

\[sk_\text{shared}^\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$는 16바이트 정렬을 맞추기 위한 패딩입니다. 패딩을 제외한 값의 총 길이가 648바이트이므로 패딩 $P$는 8바이트로 구성됩니다.

위 이미지에서 붉게 표기된 1-8, 18, 34-40번 블럭이 두 논문에서 주요하게 이용되는 블럭입니다.

2. 유저 로그인 시

유저의 로그인 시도가 발생하면 서버는 다음과 같은 challenge $C$를 생성하여 클라이언트에 전송합니다.

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

클라이언트는 challenge $C$를 수신하고 다음의 계산과정을 통해 $SID$를 얻고 이를 회신합니다.

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

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

---

MEGA: Malleable Encryption Goes Awry

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

\[m := ((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$는 서버가 제공한 $ct$로부터 $sk_\text{shared}$를 계산하여 도출한다는 사실에 주목해봅시다.

이는 서버가 원한다면 $sk_\text{shared}$를 원본과 다른 값으로 바꿀 수 있음을 의미합니다.

$sk_\text{shared}$는 암호화된 상태로 서버에 존재하므로 아주 원하는 값으로 바꾸는 것은 물론 어렵습니다.
다만 해당 값의 무결성이 보장되지 않음은 이 논문에서 중요하게 작용합니다.

그렇다면 단순하게 떠오르는 방법은, 비밀키 중 어떤 수가 변조되었을 때 변조된 방법을 몰라도 $p,q$에 관한 유의미한 정보를 얻을 수 있는지 살펴보는 것입니다.

저자가 제시한 방법은 $ct$의 40번 블럭을 임의의 값으로 변경하여 $ct^\prime$을 만듦으로써 $u$이 서버가 알 수 없게 변조된 $u^\prime$을 이용하여 어떤 응답을 하는지 확인하는 것입니다.

이러한 점에서 서버는 유저의 로그인 시도를 일종의 오라클(oracle)로써 활용하고 있다 볼 수 있습니다.

서버가 적당한 $x$를 고른 후 클라이언트에 challenge $C:=(x^e\text{ mod }N, ct^\prime)$을 전송했을 때를 자세히 살펴봅시다.

1. $x<r$일 때

$x<r$ 이라면 $m_p=m_q$이므로 클라이언트가 계산한 평문 $m^\prime$은 $m_q$와 동일합니다.

이는 1024비트 이하의 값이므로 하위 128바이트 이내에 모두 포함됩니다. 즉, $SID:=m^\prime[2:44]=0$이 성립합니다.

2. $x\ge r$일 때

$m_p\neq m_q$이므로 이 값에 관해서 크게 이야기할 만한 성질을 찾을 수 없습니다. 높은 확률로 $SID\neq 0$입니다.

위 결과를 종합하자면, $x,r$의 대소관계에 따라 $SID=0$일 확률이 한 케이스에서는 1, 다른 케이스에서는 0에 매우 가깝습니다.

따라서 이러한 결과를 이용하여 $r$을 찾기 위한 이분탐색을 시행할 수 있고, $r$은 1024비트의 소수이므로 1024번의 로그인 시도를 통해 $r$의 값을 확실하게 구할 수 있습니다.

로그인 횟수 줄이기

하지만 1024번의 로그인 시도는 현실적으로 불가능하며, 가능하더라도 상당히 긴 수집 기간이 필요합니다.

$n$번의 이분탐색 루프를 통해 후보군을 $2^{-n}$배로 줄일 수 있다는 사실을 이용하면 이를 조금 더 줄일 수 있습니다.

512번의 로그인 시도를 이용하여 $r$의 상위 512비트를 구하고, 나머지 하위 512비트는 Coppersmith’s method를 사용해 계산하는 것입니다. 해당 내용은 논문의 3.D.1 절에 설명되어있습니다.

저자의 실제 PoC에서는 오라클 쿼리를 통해 상위 683비트를 얻은 후 Coppersmith’s method를 적용하는 것을 확인할 수 있습니다.

HNP-SUM: Cryptanalyzing MEGA in Six Queries and Other Applications

본 논문의 저자는 원 논문의 공격에 대해 다음과 같은 점을 지적했습니다.

• Coppersmith’s method의 SOTA를 고려할 때, 최소 512번의 비현실적인 수의 로그인 시도가 필요하다.
• 클라이언트는 각 challenge에 대해 344비트의 정보를 제공하나, 이를 이분탐색에서 1비트의 정보로만 소모한다.

오라클이 제공하는 정보가 기존 공격에서 활용하는 1비트보다 압도적으로 많다는 것은 오라클의 출력에서 더 많은 정보를 얻을 방법이 있을 수도 있다는 것을 의미합니다.

저자는 원 논문에서와 마찬가지로 CRT-RSA의 마지막 식에 주목했습니다.

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

위 식은 오라클의 출력이 쿼리에 따라 변하지 않는 값인 $q$에 대한 선형식으로 표현됨을 보여줍니다. 비록 긴 접미배열이 제거된 채로 출력되지만, 이러한 점은 Hidden Number Problem(이하 HNP)에서 잘 다뤄지는 종류의 정보 손실입니다.

저자는 이를 형식화하여 본 문제에 적합한 형태의 HNP 변형인 HNP-SUM을 소개합니다.

HNP with Small Unknown Multiplier

$N,a_i,T,E$가 주어질 때 $1\le i\le n$인 $i$에 대해

\[\begin{matrix} a_i \equiv _N t_i x + e_i \\ \vert t_i\vert \le T \\ \vert e_i\vert \le E \\ \end{matrix}\]

를 만족하는 $x,t_i,e_i$가 존재한다. 모든 $t_i$를 구하여라.

위 문제가 HNP-SUM의 정의입니다만, 식의 형태 상 $t_i$의 부호, 공약수 관계까지 모두 준수하며 구하는 것은 격자로 구하기 다소 어렵습니다. 따라서 부호와 공약수 정도의 오차를 감안하고 구하는 것이 HNP-SUM을 해결하는 것의 최종적인 목표가 됩니다.

HNP-SUM to MEGA RSA Key Recovery

HNP-SUM을 직접 해결하기 이전에, MEGA RSA의 키 복구 공격이 HNP-SUM을 풀 수 있을 때 가능함을 먼저 짚어보겠습니다.

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

\[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}\]

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}\]

두 식의 차는 다음과 같습니다.

\[(m_p-m_q)(u^\prime-u^{\prime\prime}) 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})\]

이때, $\delta_{i,j}:=pt_i-pt_j$에 대해 다음이 성립합니다.

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

몇몇 항을 새로운 변수로 정의하면, 다음과 같이 정리할 수 있습니다.

\[\delta_{i,j}x\equiv_N \Delta e_12^{b_1}+\Delta s2^{b_2}+\Delta e_2\]

위 식에서 $\Delta e_1$의 값을 안다면 $t=\delta_{1,2}, a=\Delta e_12^{b_1}+\Delta s2^{b_2}$인 HNP-SUM instance으로 간주할 수 있습니다.

$\vert\Delta e_1\vert<E_1:=2^8$ 으로 충분히 범위가 작아 brute-force를 통해 값을 안다고 가정할 수 있습니다.

즉, 서버는 각 로그인 시도로부터 $i,j$의 값을 바꿔가며 HNP-SUM에 필요한 식을 하나씩 획득할 수 있습니다. HNP-SUM의 최종적인 목표는 $t_i$를 복구하는 것이므로, 서버는 유용한 정보를 추출할 수 있도록 $\delta_{i,j}$를 선정하는 것이 중요합니다.

저자가 서술한 방식은 다음과 같습니다.

• $i=18$로 고정합니다. 18번 블럭은 $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$의 상위 비트들은 높은 확률로 $kN$과 동일함을 알 수 있습니다.

즉 $d$는 $\frac{kN}{e}$와 꽤 많은 수의 상위 비트를 공유합니다. 서버가 $k$의 값을 알지 못하나, MEGA의 웹 인스턴스는 $e=257$을 사용하며 보통의 경우 $e=65537$을 사용하는 것이 일반적입니다. 이는 brute-force하기에 많은 양은 아니므로 크게 문제되지 않습니다.

한편, $pt_1$의 첫 2바이트는 $l(q)$로 구성되어있습니다. 이는 주어진 조건에서 0x400의 값을 가지며, 이전 $e$개 후보들에서 해당 값을 계산하여 올바른 값이 도출되는지로 후보값의 검증이 가능합니다.

웹 인스턴스의 경우 거의 확실하게 유일한 $k$의 후보를 찾을 수 있으며, $e=65537$인 경우에도 false positive 수의 기댓값은 그리 크지 않습니다.

올바른 $k$의 값을 알면 $pt_j$의 값도 알 수 있습니다. 각 로그인 시도로부터 해당 값을 계산한 후 Coppersmith’s method를 적용하면 6~7개 정도의 $\delta_{i,j}$ 값을 통해 $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을 적용해 SVP의 근사해를 계산하고 $t_1,t_2$를 복구할 수 있습니다. 하지만 $g:=\gcd(t_1,t_2)\neq 1$인 경우 자명한 더 짧은 벡터가 존재하므로 공격자는 부호, 공약수 정도의 오차로 $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의 근사해를 HNP-SUM의 해와 연관지어 해석하는 것이 까다롭습니다.

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

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

이를 통해 해당 $(n-1)$개의 벡터를 기저로 갖는 밀도 높은(dense) 부분격자 $\mathcal{L}(B_\text{sub})$을 구성합시다.

\[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_{i,j}-k_{i,j}b_{n+1}\\ B_\text{sub} = \{v_{i,j}\vert i,j\in\{1,\cdots,n\},i\neq j\}\]

위와 같은 격자에 대해 저자는 다음의 $h_i$를 행백터로 갖는 $\mathcal{L}(B_\text{sub})$의 또다른 기저 $H$를 제시합니다. 여기서 $H$는 upper trapezoidal matrix입니다.

$H$는 대각 위 성분들이 Hermite Normal Form의 조건 범위 내라는 보장이 없으므로 $B_\text{sub}$의 HNF와 완전히 일치하지는 않습니다만, leading non-zero term과 마지막 행을 변형하지 않는 행 연산을 통해 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_1$를 계산할 수 있습니다.

---

여기까지의 내용으로 기본적인 공격의 골격을 알아보았습니다. 다만 아직 해결하지 못한 한계가 몇가지 존재합니다.

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

지금부터 이를 해결하는 저자의 방법을 소개하겠습니다.

---

How to make more available payloads

해당 문제에 대한 해결법은 사실 간단합니다. 이전에 40번 블럭을 변조하여 $u$의 값을 바꾸었는데, 그 대신 39,38,…번 블럭을 변조하면 됩니다.

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

\[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\]

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

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

\[y\in[a_t-E_1,a_t+E_1]\\ ry\in S_1=[ra_t-rE_1+rkN,ra_t+rE_1+rkN]\\\]

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

\[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로 한정할 수 있습니다. 그러한 $C$는 다음과 같은 격자 $B$에 포함되어 있습니다.

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

공격자는 lattice reduction을 통해 짧은 벡터 $v=(E(C2^{b_1}\mod N),E_2C)$을 찾을 수 있고, Gaussian Heuristic으로부터 다음과 같은 상한을 계산할 수 있습니다.

\[\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}\]

실제 공격에서 사용되는 값을 대입하여 위 식에서 보인 값의 상한을 확인하면 약간의 정보 손실이 존재하는 것을 확인할 수 있습니다. 다만 MSB의 값이 $N$의 소인수분해에 크게 도움이 되지 않고, 해당 기법을 통해 511번의 MSB bruteforce를 피하여 계산의 병목인 lattice reduction의 횟수를 줄일 수 있다는 것은 충분한 장점입니다.

---

Conclusion

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

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