RSA Attack Using LLL

Understanding Boneh-Durfee Attack

Posted by ebmoon on May 23, 2019 · 11 mins read

0. Intro

이번 글에서는 최근에 있었던 DEFCON CTF 예선 문제로 등장한 asrybab 문제를 풀면서 공부한 RSA 공격 테크닉을 적어보려 합니다. 해당 문제는 LLL reduction을 이용한 공격 기법 중 하나인 Boneh-Durfee RSA Attack을 응용해서 푸는 문제였는데, 문제를 풀기 위해 삽질하는 과정에서 배운 것들을 공유하고자 합니다.

1. RSA Cryptosystem

그냥 넘어가기에는 어색하니 RSA 암호의 기본 원리를 간단히 설명하고 가도록 하겠습니다. 이미 RSA 암호체계에 대해 알고 있다면 아래로 쭉 내려도 무방합니다.

RSA 암호 체계는 public exponent $e$와 private exponent $d$, modulus $N$ 총 3개의 키로 구성되어 있습니다. 세 개의 키 중 $e$와 $N$은 모두에게 공개되는 public key이며, $d$와 $N$은 특정 개인만 알고 있는 private key 입니다.

RSA 암호 체계에서 암호화 함수와 복호화 함수는 각각 $enc(m) = m^e \bmod N$과 $dec(c) = c^d \bmod N$으로 정의됩니다. 물론 정상적인 암호체계라면 $dec(enc(m)) = m^{ed} \bmod N = m$이 성립해야 하겠지요.

1.1. Key Generation

일반적으로 키 생성 과정은 다음과 같습니다.

  1. 두 개의 소수 $p$와 $q$를 준비합니다
  2. $N$을 두 소수의 곱으로 정의합니다.
  3. $\varphi(N)$과 서로소가 되도록 ($\varphi(N)$보다 작은) $e$를 선택합니다. (일반적인 경우에는 페르마 소수 65537(=0x10001)이 사용됩니다)
  4. $d = e^{-1} \bmod \varphi(N)$으로 정의합니다.

참고로 4번 과정에서 inverse는 항상 존재합니다. $\varphi(N)$과 $e$는 서로소이기 때문에 디오판토스 방정식 $\varphi(N) \cdot x + e \cdot y = 1$의 해가 되는 정수쌍 $(x, y)$가 무수히 많이 존재하기 때문이지요.

1.2. Correctness of Key Generation

위의 과정을 따라 생성된 키가 $dec(enc(m)) = m^{ed} \bmod N = m$을 만족하는 이유는 페르마의 소정리라 불리는 아래의 정리 때문입니다.

Theorem. Suppose two nonzero natural number $m$ and $N$ are relatively prime. Then $m^{\varphi(N)} \bmod N = 1$.

Proof. Let $m’ = m \bmod N$. Since $m$ and $N$ are relatively prime, we know that $m’$ is an element of multiplicative group $(\mathbb{Z}/N)^{\ast}$. By the Lagrange’s theorem, the order of $m’$ divides $\vert (\mathbb{Z}/N)^{\ast} \vert = \varphi(N)$. Thus $m^{\varphi(N)} \bmod N = m’^{\varphi(N)} \bmod N = 1$.

위의 정리를 사용하면 $m^{ed} \bmod N = m^{k \varphi(N) + 1} \bmod N = m$이기 때문이지요. 사실 원래 RSA는 Euler’s totient function $\varphi$가 아니라 Carmichael’s totient function $\lambda$로 기술됩니다. 하지만 위의 증명에서는 $\lambda(N)$이 $\varphi(N)$의 약수임을 바로 알 수 있지요.

2. Idea

RSA를 푸는 방법 중 하나는 polynomial equation modulo $N$을 푸는겁니다. RSA는 기본적으로 $(x^e - c) \bmod N = 0$이 되는 $x$를 구하면 되는 문제니까요. 문제는 modulo polynomial equation을 풀기가 상당히 어렵다는 점입니다.

하지만 ‘일반적으로’ 해를 구하기 어렵다는 말이지 특정 조건을 만족하는 polynomial equation은 비교적 쉽게 풀 수 있을지도 모릅니다. 그 특정 조건 중 하나로 아래 서술할 Howgrave-Graham Theorem이 있습니다.


Theorem. (Howgrave-Graham) Let $g(x)$ be an univariate polynomial with $n$ monomials and let $m$ be a positive integer. Suppose that

  1. $g(x_0) = 0 \bmod N^m$ where $\vert x_0 \vert \leq X$
  2. $\Vert g(x X) \Vert < \frac{N^m}{\sqrt{n}}$

Then $g(x_0) = 0$ holds over the integers.

Proof.

Since $g(x_0)$ is a multiple of $N^m$, it must be zero. $\square$

(참고로 $\Vert g(x) \Vert$는 다항식을 coefficient 벡터로 보았을 때의 norm입니다.)


Howgrave-Graham Theorem이 말하는 내용은 polynomial의 해와 계수가 충분히 작다면 modulo polynomial equation 대신 정수 전체 범위에서 polynomial equation을 풀어도 무방하다는 겁니다.

이 정리를 사용하기 위해서는 주어진 modulo polynomial equation을 잘 변형해서 같은 해집합을 가지지만 norm이 작은 polynomial을 만들면 되겠네요. 바로 그 norm이 작은 새로운 polynomial을 만드는 테크닉이 바로 LLL Lattice Basis Reduction입니다.

3. Usage of LLL Lattice Basis Reduction Algorithm

앞으로 계속 등장할 lattice라는 용어는 어떤 group의 discrete subgroup을 뜻합니다. Basis 벡터들의 integer combination으로 만들어진 subspace라고 생각해도 좋습니다.

3.1. LLL Lattice Basis Reduction Algorithm

선형대수학 개론 수업을 들은 사람이라면 Gram-Schmidt 알고리즘을 이용해 주어진 basis로부터 orthonormal basis를 찾는 방법을 알고 있을겁니다. Lattice에서도 역시 Gram-Schmidt 알고리즘을 이용해 orthogonal basis를 구할 수 있습니다. 다만 lattice에서는 주어진 벡터의 norm을 바꿀 때 주의해야 합니다. $\mathbb{R}^2$에서 벡터 $(1, 0)$은 lattice $\mathbb{Z} \times {0}$을 생성하지만 벡터 $(2, 0)$은 lattice $\mathbb{2Z} \times {0}$을 생성하니까요.

LLL Lattice Basis Reduction 알고리즘은 orthogonal basis 중에서도 ‘좋은 성질’을 만족하는 basis를 구하는 알고리즘입니다. 아래는 LLL-reduced basis의 정의입니다.

Definition. Let $B = {b_0,\, \ldots,\, b_n }$ be a basis of lattice, and $B^{\ast} = {b_0^\ast,\, \ldots,\, b_n^\ast }$ be an orthogonal basis generated from the Gram-Schmidt method. Define $\mu_{i, j}$ as the Gram-Schmidt coefficient $\frac{\langle b_i, b_j^\ast \rangle}{\langle b_j^\ast, b_j^\ast \rangle}$ for any $1 \leq j < i \leq n$.

Then the basis $B$ is LLL-reduced if it satisfies:

  1. (size-reduced) $\mu_{i, j} \leq \frac{1}{2}$ for every $1 \leq j < i \leq n$.
  2. (Lovász condition) $\frac{3}{4}\Vert b_{k-1}^\ast \Vert^2 \leq \Vert b_{k}^\ast \Vert^2 + \mu_{k, k-1}^2 \Vert b_{k-1}^\ast \Vert^2$ for every $1 \leq k \leq n$.

3.2. Property of LLL Reduced Basis

LLL-reduced basis가 만족하는 성질은 다음과 같습니다.

  1. $\Vert b_1 \Vert \leq \Vert b_2 \Vert \leq \cdots \leq \Vert b_n \Vert$
  2. $\Vert b_i \Vert \leq 2^{\frac{n(n-1)}{4(n+1-i)}} \cdot det(L)^{\frac{1}{n+1-i}}$ for every $1 \leq i \leq n$, where $L$ is the lattice generated by the basis.

사실 별거 없고 그냥 벡터 norm이 특정 값으로 잘 bound 된다는 소리입니다. 증명은 생략하도록 하겠습니다.

3.3. Attack Scenario

이제 어느정도 공격 시나리오가 감이 잡힙니다. 대강 이렇게 하면 되겠네요.

  1. 풀고싶은 RSA 문제를 modular polynomial equation 문제로 기술한다.
  2. 주어진 modular polynomial equation 문제와 같은 해를 가지는 polynomial들로 lattice를 구성한다.
  3. LLL Lattice Basis Reduction 알고리즘을 적용하여 LLL-reduced basis를 구한다.
  4. LLL-reduced basis에서 norm이 가장 작은 polynomial을 정수 범위에서 푼다.

3.4. Lattice Construction (Univariate Case)

Lattice를 구성하는 방법은 간단합니다. 어차피 우리는 polynomial을 새로 고안해내는게 아니라 이미 다른 사람들이 머리 싸매고 고민한걸 가져다 쓰면 되는거니까요. 우선은 풀어야 할 변수가 하나인 경우만 보겠습니다.

  • $g_{i,j} (x) = x^j · N^i · f^{m−i} (x)$ for $0 \leq i < m$, $0 \leq j <\partial f$
  • $h_i(x) = x^i · f^m(x)$ for $0 \leq i < t$

이 polynomial들로 lattice를 구성하면 됩니다. 이 polynomial들은

  1. modulo $N^m$에서 같은 해 $x_0$을 가지고
  2. polynomial을 생성하는 매 iteration마다 새로운 항이 등장합니다.

2번째 성질 덕에 lattice는 lower triangular 꼴로 나타내어지고, 결과적으로 determinant를 계산하기가 매우 쉬워집니다. Determinant를 계산하기 쉽다는 점은 중요합니다. 3.2에 기술된 2번 성질과 Howgrave-Graham Theorem의 bound를 잘 조합해 $X$의 상한값을 구하기 위해서는 $det(L)$을 알아야 하니까요.

3.5. Application (Stereotyped Message)

이 공격 기법이 사용될 수 있는 상황 중 하나는 stereotyped message입니다. 만약 평문 $m$의 앞부분이 항상 일정하다고 할 때, 평문 $m$은 우리가 알고 있는 부분 $m_0$와 모르는 부분 $x$의 합으로 나타낼 수 있겠지요.

그럼 풀어야 할 방정식은 $(m_0 + x)^e - c \bmod N = 0$이 되고, $m_0$이 충분히 커서 구해야 할 $x$값이 Howgrave-Graham Theorem의 bound를 만족한다면 위의 방법으로 $x$를 구할 수 있겠지요.

참고로 평문의 뒷부분을 알고 있는 경우에도 적용될 수 있습니다. $m = (m_0 + x \cdot 2^k)$ 꼴로 나타내면 되거든요. 이 외에도 변수가 한개인 modular polynomial equation을 풀어야 하는 다양한 상황에 유용하게 쓰일 수 있습니다.

4. Boneh-Durfee Attack

Boneh-Durfee Attack은 private exponent $d$가 작을 때 성립하는 공격입니다. 정확히는 $d < N^{0.292}$일 때 성립하는데, $d < \frac{1}{3} N^{0.25}$일 때 성립하는 Wiener’s attack에 비해 좀 더 적용 범위가 넓습니다.

4.1. Idea

$\varphi(N)$을 이용해 키를 생성하는 통상적인 RSA에서는 아래의 식이 성립합니다.

$e · d = k · \varphi(N) + 1$ $\Rightarrow k · \varphi(N) + 1 = 0 \pmod e$ $\Rightarrow k · (N + 1 − p − q) + 1 = 0 \pmod e$

여기서 우리가 값을 모르고 있는 미지수는 $k$와 $-(p + q)$ 두 개가 있습니다. 그럼 private exponent $d$를 구하는 문제는 bivariate modular polynomial equation $f(x, y) = x \cdot (N + 1 + y) = 0 \pmod e$의 해를 구하는 문제로 볼 수 있겠네요.

4.2 Lattice Construction (Bivariate Case)


Theorem. (Howgrave-Graham) Let $g(x, y)$ be an bivariate polynomial with $n$ monomials and let $m$ be a positive integer. Suppose that

  1. $g(x_0, y_0) = 0 \bmod N^m$ where $\vert x_0 \vert \leq X$, $\vert y_0 \vert \leq Y$
  2. $\Vert g(x X, y Y) \Vert < \frac{N^m}{\sqrt{n}}$

Then $g(x_0, y_0) = 0$ holds over the integers.


변수가 두 개인 경우도 비슷하게 이변수 Howgrave-Graham Theorem을 사용하면 됩니다. 일변수 방정식을 풀 때는 LLL reduction을 진행한 후에 norm이 가장 작은 basis 하나만 사용해 식을 풀었으니, 이변수 방정식을 풀 때는 norm이 가장 작은 basis 2개를 사용해서 식을 풀면 됩니다.

이번에는 다음 polynomial들로 lattice를 구성하면 됩니다.

  • $g_{i,k}(x, y) = x^i · f^k (x, y) · e^{m−k}$ for $0\leq i \leq m − k$ and $0 \leq k \leq m$
  • $h_{j,k}(x, y) = y^j · f^k (x, y) · e^{m−k}$ for $0\leq j \leq t$ and $0 \leq k \leq m$

Boneh, Durfee 선생님들께서는 $g_{i, k}$를 x-shifts, $h_{j, k}$를 y-shifts라고 불렀다고 하네요.

4.3. Helpful Vectors

기본적인 아이디어는 이미 설명이 끝났지만 bound $d < N^{0.292}$를 얻기 위해서는 determinant 값을 줄이기 위한 약간의 최적화가 더 필요합니다. 결국 LLL-reduced basis의 norm은 lattice의 determinant에 영향을 받으니까요.

Boneh-Durfee Attack에서는 전체 polynomial의 수를 $n$이라고 할 때, lattice의 determinant가 $e^{mn}$을 넘지 않도록 조절합니다. Diagonal element가 $e^m$보다 큰 y-shift들을 제거하면서 말이지요. 하지만 이 경우 lattice가 더이상 lower triangular 꼴이 아니게 되어 determinant 계산이 상당히 힘들어집니다.

그래서 실제로는 이 문제를 해결하기 위해 substitution $u = 1+xy$를 도입합니다. 그럼 기존 polynomial $f(x, y) = 1 + xy + x \cdot (N + 1)$는 $\bar{f}(u, x) = u + x \cdot (N+1)$ 꼴로 변형되겠지요. 그리고 다음 polynomial들로 lattice를 구성합니다. 이렇게 구성된 lattice를 Herrmann-May’s Matrix라고 한다네요.

  • $\bar{g}_{i,k}(x, y) = x^i · \bar{f}^k · e^{m−k}$ for $0\leq i \leq m − k$ and $0 \leq k \leq m$
  • $\bar{h}_{j,k}(x, y, u) = y^j · \bar{f}^k · e^{m−k}$ for $1 \leq j \leq t$ and $\lfloor \frac{m}{t} \rfloor \cdot j \leq k \leq m$

뭐 이렇게 뽑으면 잘 된다는데 자세한 내용은 paper에서 Herrmann-May’s Matrix 부분을 참고하시면 될 듯 싶습니다.

5. Summary

대회 중에 공부하면서 왜 이렇게 보기 힘들게 썼냐고 불평하던 기억이 나서 최대한 쉽게 정리하려고 노력해봤습니다. 그런데 막상 다 쓰고보니 제가 쓴 글도 눈에 잘 안들어오는 것 같네요. 원래는 bound 계산하는 부분도 적으려 했는데 귀찮기도 하고 괜히 난잡해질 것 같아 생략했습니다.