암호론 논문 리딩 #4: The Return of Coppersmith’s Attack: Practical Factorization of Widely Used RSA Moduli

Matus Nemec, Marek Sys, Petr Svenda, Dusan Klinec, Vashek Matyas - 2017

1. Introduction

이 논문은 2017년의 논문으로, 제목처럼 많이 사용되는 RSA 공개키를 소인수분해하는 방법을 다룬다. 

앞선 논문 리딩에서 언급했듯이 RSA 공개키를 소인수분해하면 RSA 기반 암호는 깨진다. 이는 Textbook RSA든 RSA-OAEP든 마찬가지다.

그러니 이 논문은 당연하게도 많은 사람들에게 충격을 주었고, 실제로 이 논문 때문에 시스템을 교체한 곳도 많다고 한다.

논문의 제목처럼, 이 공격은 저번에도 언급된 Coppersmith's Attack과 관련이 깊다. 그러니 이에 대한 이해가 필수적이다.

이번 논문 리딩에서는 Lattice에 대한 기본적인 내용을 훑고, Coppersmith's Attack에 대한 내용을 증명과 함께 살펴본다.

그 후, 본격적으로 논문을 읽으면서 많이 사용되는 RSA 공개키들이 어떻게 생성되고, 이들이 어떠한 약점을 가지고 있는지 살펴본다. 

2. Brief Introduction to Lattices

사실 나도 잘 모르는 분야지만, 이 논문을 읽는데 필요한 지식들을 간단하게 나열해본다. 자세한 건 나도 빨리 배워야한다.

우리가 다룰 Lattice란, 쉽게 말해서 $\mathbb{R}^n$의 선형독립인 벡터 $v_1, v_2, \cdots, v_d$가 있을 때, $\{ \sum_{i=1}^d a_i v_i  | a_i \in \mathbb{Z} \}$에 해당한다. 

즉, $\mathbb{R}^n$의 subspace를 생각하되 가능한 계수를 $\mathbb{Z}$로 한정시켜서 생각하는 것이다.

이러한 Lattice가 주어졌을 때, 생각할 수 있는 어려운 문제들이 있다. 이들을 간단하게 소개한다.

Shortest Vector Problem: Lattice에 속하는 nonzero vector 중 가장 norm이 작은 것을 구한다.

Closest Vector Problem: Lattice에 속하는 vector 중 주어진 벡터에 가장 가까운 것을 구한다.

이 문제들은 상당히 어려운 것으로 알려져 있고, 이는 곧 Lattice가 암호학에 쓰이는 이유가 된다. (양자내성암호)

Shortest Vector Problem에 대해서 조금 더 논의를 해보자. 

Geometry of Numbers에서 가장 중요한 정리 중 하나인 Minkowski's Theorem을 생각해보자. 이를 활용하면, invertible한 $n \times n$ 행렬 $A$의 column으로 생성되는 Lattice에서 가장 짧은 nonzero vector의 norm이 최대 $\sqrt{n} \cdot \text{det}(A)^{1/n}$임을 어렵지 않게 증명할 수 있다.

그런데 이건 단순히 존재성의 여부이고, 실제로 계산하기에는 매우 어렵다. 

생각해보면, Lattice의 기저가 orthogonal인 경우에는 Shortest Vector Problem이 매우 쉽다는 것을 알 수 있다.

그러니 Lattice 자체는 그대로 유지하면서, 기저를 orthogonal하게 바꾸고 싶다는 전략이 나온다.

단순한 $\mathbb{R}^n$ 공간이었다면 Gram-Schmidt가 가능하지만, 여기서는 정수 계수를 유지해야 하므로 쉽지 않다.

이를 대신하는 알고리즘이 LLL 알고리즘이다. 자세한 디테일은 나도 모르므로 생략하지만, 다음 결과는 중요하다.

이 알고리즘을 통해서, 크기가 $2^{(n-1)/4} \cdot \text{det}(A)^{1/n}$ 이하인 nonzero vector를 찾을 수 있다는 것이다.

또한, LLL 알고리즘은 $n$에 대한 다항시간에 작동하므로, 효율적인 알고리즘이다.

3. Coppersmith's Attack

여기서는 Coppersmith's Attack이 무엇인지를 다룬다. 기본적으로 변수 1개인 경우를 다룬다.

다항식 $h(x) = \sum_{i=0}^n a_i x^i$에 대하여, $||h||^2 = \sum_{i=0}^n |a_i|^2$이라고 하자.

Theorem. (Coppersmith) $N$은 자연수고, $f \in \mathbb{Z}[x]$는 최고차항의 계수가 $1$인 $d$차 다항식이다. $\epsilon \ge 0$을 잡고, $X = N^{1/d - \epsilon}$이라 하자. $N, f$가 주어졌을 때, $|x_0| < X$와 $f(x_0) \equiv 0 \pmod{N}$을 만족하는 $x_0$를 모두 다항식 시간에 찾을 수 있다. 

이 정리를 증명하고, 실제로 $x_0$를 어떻게 찾는지까지 생각해보자.

그 전에 필요한 사전지식이 하나 더 있는데, 바로 다항식을 $\mathbb{Z}[x]$의 원소로 봤을 때 정수근을 찾는 것은 쉽다는 것이다.

이에 대한 내용을 알기 위해서는, 먼저 $\mathbb{F}_p$ 위에서 다항식의 인수분해가 쉽다는 것을 알아야 한다. 이 자료 참고.

그러니 (아마) 충분히 큰 $p$를 잡고 $\mathbb{F}_p$ 위에서의 다항식의 근을 찾은 다음 실제로 근이 되는지를 보면 될 것이다.

이제 본격적으로 Coppersmith's Theorem을 증명한다. 우선 핵심적인 Lemma를 소개한다.

Lemma. $h(x) \in \mathbb{Z}[x]$는 $d$차 다항식이고, $X$는 자연수다. 

$||h(xX)|| < N/\sqrt{d}$이며, $|x_0| < X$가 $h(x_0) \equiv 0 \pmod{N}$을 만족한다면, $h(x_0) = 0$이다.

Proof of Lemma. 접근의 방식 자체는 어렵지 않다. 목표는 $|h(x_0)|<N$을 보이는 것이다.

$|h(x_0)| = \left| \sum_{i=0}^d a_i x_0^i \right| = \left| \sum_{i=0}^d a_i X^i \left( \frac{x_0}{X} \right)^i \right| \le \sum_{i=0}^d \left| a_i X^i \left( \frac{x_0}{X} \right)^i \right| \le \sum_{i=0}^d |a_i X^i|$이다.

위 식의 우변은 Cauchy-Schwarz 부등식에의하여 $\sqrt{d} ||h(xX)||$ 이하가 되고, 다시 조건에 의하여 $N$ 미만이 된다. 증명 끝.

이제 새로운 전략이 나온다. $f(x) \equiv 0 \pmod{N}$의 근을 모두 찾고 싶다면, $f$의 배수인 다항식 중 norm이 작은 것을 하나 찾자.

만약 norm이 충분히 작은 다항식이 나온다면, 그 다항식의 정수근을 찾는 것으로 위 과정을 대체할 수 있다.

$\pmod{N}$을 생각하면서 근을 찾는 것보다 그냥 정수다항식의 정수근을 찾는 것이 훨씬 쉬우므로, 이는 괜찮은 전략이다.

이는 결국 $f(x), xf(x), x^2f(x), \cdots$를 잘 조합해서 작은 norm을 만드는 문제가 되고, Shortest Vector Problem의 냄새가 난다.

하지만 이렇게 단순한 방법으로는 좋은 다항식을 찾기 어렵다는 것을 알 수 있고, 약간의 트릭이 필요하다.

트릭은 $N$ 대신 $N$의 거듭제곱을 생각하는 것이다. $g_{u, v} (x) = N^{m-v} f(x)^v x^u$라는 다항식을 생각하자.

이때, $0 \le u \le d-1$이고 $0 \le v \le m$이다. $m$은 임의로 잡은 값이며 추후에 결정되는 자연수이다.

만약 $x_0$가 $f(x_0) \equiv 0 \pmod{N}$을 만족하면, $g_{u,v}(x)$는 자동으로 모두 $N^m$의 배수이다.

그러므로 바라보는 대상을 $g_{u,v}$로 바꾸고, norm에 대한 제약조건을 $N^m$에 대한 조건으로 바꿔주자.

이제 $n = d(m+1)$이라 하자. $g_{u, v}(xX)$의 차수는 $u + vd$이므로, 이는 $0$부터 $n-1$까지의 값을 순서대로 갖는다.

$g_{u,v}(xX)$의 계수들을 벡터로 보고 Lattice를 만든 후, 이를 행렬로 생각해보자. 이 행렬은 자명하게 triangular하다.

$g_{u,v}(xX)$의 최고차항의 계수가 $X^{u+dv} \cdot N^{m-v}$이므로, 이 행렬의 determinant는 이를 각 $u \in [0, d)$, $v \in [0, m]$에 대하여 곱한 값인 $X^{n(n-1)/2} \cdot N^{dm(m+1)/2}$가 된다. 이제 LLL 알고리즘을 돌려서 'Shortest Vector'를 찾자.

 

여기서 얻는 'Shortest Vector'의 길이는 최대 $2^{(n-1)/4} \left( X^{n(n-1)/2} \cdot N^{dm(m+1)/2} \right)^{1/n}$이다.

이는 정리하면 최대 $(\sqrt{2}X)^{(n-1)/2} \cdot N^{m/2}$가 되고, 우리의 목표는 이 값이 $N^m / \sqrt{n}$ 미만이 되는 것이다.

그런데 식을 정리해보면 $X = N^{1/d - \epsilon}$일 때 생각보다 잘 부등식이 정리가 되지 않음을 알 수 있다.

이를 해결하기 위해서, $X = \frac{1}{2} N^{1/d - \epsilon}$을 생각해서 우선 Coppersmith's Theorem의 약한 버전을 증명하자.

그 후, $X$의 상위 비트에 대해서 brute force를 진행하면서 각각의 경우에 대하여 위 정리를 반복해서 사용해주자.

그러면 $X$가 $N^{1/d - \epsilon}$인 경우에 대해서도 다항식 시간에 해를 모두 구할 수 있다는 것을 알 수 있고, 나아가 $\epsilon = 0$인 경우까지도 다룰 수 있다.

이 알고리즘은 변수가 두 개인 경우로 확장될 수 있으며, 이를 통해서 다음 결과도 얻을 수 있다.

Theorem. (Coppersmith) $N = pq$가 $n$-bit RSA modulus라 하자. 

이때, $p$의 $n/4$ least significant bits을 알거나 $p$의 $n/4$ most significant bits를 알면, $N$을 다항식 시간에 소인수분해 할 수 있다.

실제로 이 정리에 해당하는 공격을 수행하기 위해서, 변수가 하나인 형태의 Coppersmith's Attack을 사용할 수도 있다.

위 식에서 $N = pq$라고 하면, 우리는 $N$은 알지만 $p$는 모르는 상태다.

만약 충분히 큰 $r$에 대해서 $u = p \pmod{2^r}$을 알고 있다면, 결국 $2^r x + u$라는 일차식이 $\pmod{p}$에서 작은 근을 갖는다는 것을 알 수 있다.

이를 최고차항의 계수가 $1$이도록 바꿔주면 $x + u \cdot (2^{-r} \pmod{N})$이라는 일차식을 얻는다.

우리는 실제로 $p$를 모르지만, $p$의 배수 $N$을 알고 있으므로 Coppersmith's Attack의 모든 부분을 수행할 수 있다.

즉, norm이 $p^m / \sqrt{n}$ 이하인 다항식을 만들기 위해서 $N$을 사용하는 방식을 택할 수 있다.

위 방법을 그대로 사용하면 부등식 계산 부분에서 뭔가 잘 안된다는 것을 알 수 있다.

대신, $x^i f(x)^m$ 형태의 다항식을 몇 개 추가해주면 LLL 알고리즘이 잘 돌아갈 조건을 제공함을 알 수 있다. 이 구현 참고. 

직관적으로 생각해보면, $N$을 사용한 다항식은 계수가 지나치게 큰 것이므로 ($p$를 모르니 그 배수를 쓴 것이니) $x^i f(x)^m$ 형태의 다항식을 추가해서 이를 희석시킨 것이라고 생각해도 될 것 같다. 아무튼 하면 된다 :) 이제 본격적으로 논문을 읽어보자.

4. RSA Key Generation, and RSALib

RSA 키는 어떻게 만들까? 예를 들어 1024 비트 키를 만들고 싶다고 하자. 

그러면 512 비트 소수 $p, q$를 찾아서, $N=pq$를 잡고, $e = 2^{16}+1$이라 한 다음, $d$를 $ed \equiv 1 \pmod{\phi(N)}$이 성립하도록 잡으면 된다. 

안전성을 위해서는 $p, q$가 갖춰야 할 여러 조건들이 있고, 이에 대해서는 앞선 리딩에서 다뤘다.

하지만 결론적으로 웬만하면 랜덤한 $p, q$를 잡으면 된다는 사실 역시 알고 있다.

소수 정리에 의해서 $x$ 근처의 자연수가 소수일 확률은 매우 대충보면 $1/\log x$ 정도다.

그러니까 랜덤한 자연수를 잡고, Miller-Rabin 등 소수 판별 알고리즘을 돌리는 것을 소수가 나오기 전까지 반복하면 소수를 얻을 수 있다.

그런데 RSA 키를 가능한 빠르게 생성하고 싶다고 가정하자. 어떻게 위 과정을 최적화할 수 있을까?

기본적으로 소수를 찾는 과정이 가장 느리므로, 이 과정을 더 빠르게하면 좋을 것 같다.

당장 랜덤한 자연수를 찍으면 2부터 100까지의 소수 중 하나의 배수가 될 확률이 상당히 높을텐데, 이거라도 미리 거르면 좋을 것 같다.

그래서 RSALib는 다음과 같은 방법을 채택했다. $n$이란 자연수를 먼저 설정하는데, 이는 RSA 키의 길이에 따라서 결정된다.

그 후, $M$을 첫 $n$개의 소수의 곱으로 설정한다. 이제 랜덤한 $k, a$를 잡아서 $k \cdot M + (65537^a \pmod{M})$을 소수 후보로 잡는다.

이렇게 하면 첫 $n$개의 소수는 약수로 갖지 않게 된다는 것이 자명해지고, 소수 판별을 반복하는 횟수가 줄어든다.

그런데 생각해보면, $M$은 여러 소수의 곱이니 원시근이 없고, $65537^a \pmod{M}$은 $M$과 서로소인 모든 나머지를 표현하지 못한다.

다르게 말하면 이는 이 새로운 방식이 생성할 수 없는 소수들이 있고, 실제로 이 방식은 랜덤하지 않다는 것이다.

또한, $p, q$가 이 방식으로 생성되었다면, $N \pmod{M}$ 역시 $65537$의 거듭제곱으로 표현할 수 있다.

$M$은 큰 값이지만 smooth 하므로, Pohlig-Hellman Algorithm으로 $N \equiv 65537^c \pmod{M}$인 $c$를 찾을 수 있다.

이는 생성된 키 $N$이 제대로 계산되었는지 (RSALib로 생성되었는지) 확인하는 방법이 될 수도 있다.

다시 강조하지만, $M$과 서로소인 나머지 중 $65537^a \pmod{M}$으로 표현될 수 있는 값의 비율은 매우 낮다.

이제 이 RSA 키의 특수한 형태를 극도로 활용하여, $N$을 아예 소인수분해하는 방법을 찾아보자.

5. The ROCA Vulnerability

생각보다 아이디어는 그렇게 어렵지 않다. $p = k \cdot M + (65537^a \pmod{M})$이라 하자.

만약 우리가 $a$를 안다면, $p$의 하위 비트를 아는 것이 되며 이는 Coppersmith's Attack을 사용할 환경을 제공한다.

$T$를 $\pmod{M}$에 대한 $65537$의 order라고 하자. $c$를 $N \equiv 65537^c \pmod{M}$인 값이라고 하자.

$T, c$는 모두 어렵지 않은 정수론 알고리즘을 (order-finding algorithm, Pohlig-Hellman) 사용하여 계산할 수 있다.

이제 $a$를 $c/2$부터 $c/2 + T/2$까지를 brute-force하면서 계산하면, $p$가 걸리던 $q$가 걸리던 뭔가 걸린다.

즉, Coppersmith 공격을 약 $T/2$번 반복하면, $N$을 소인수분해 할 수 있다. 여기서 $T$가 작으면 좋겠다는 생각을 할 수 있다.

이를 위해서 일종의 최적화를 한다. $M'|M$인 $M'$을 잡되, 다음 조건을 모두 만족하도록 하자.

조건 1: $\pmod{M'}$에 대한 $65537$의 order가 작은 편이다.

조건 2: $M'$이 충분히 커서, $p \pmod{M'}$을 고정하면 Coppersmith's Attack을 수행할 수 있다. 즉 $M' > N^{1/4}$.

$M'$을 최적화하는 과정은 휴리스틱, 그리디, 전탐색 등을 든든하게 섞어서 해시코드 식 접근을 했다고 한다.

이제 이 과정을 모두 합치면 $N$을 소인수분해 할 수 있다. 대표적인 구현은 이 코드를 참고하자.