blisstoner's profile image

blisstoner

July 18, 2020 21:00

안녕하세요, 이번 글에서는 2017년 2월에 제보된 RSA 구현에서의 취약점인 ROCA(Return Of Coppersmith Attack)에 대해 다뤄보겠습니다.

RSA

RSA는 별도의 설명이 필요없을 정도로 너무나 유명한 공개키 암호 시스템입니다. 암호화/복호화 과정이 헷갈리시는 분은 RSA_암호 위키를 참고하시는 것을 추천드립니다.

RSA는 큰 소수 2개를 곱하는 것은 쉽지만 소인수분해하는 것은 어렵다는 사실을 이용한 암호 시스템입니다. 비록 소인수분해를 다항 시간에 처리하는 양자 알고리즘이 존재하지만 실제 양자컴퓨터가 개발되어 RSA가 무력화되기까지는 아주 긴 시간이 필요할 것으로 예상됩니다. 이외에는 RSA 암호 시스템 자체에 대한 취약점이 발견되지 않고 있습니다. RSA 암호 시스템 자체에 대한 취약점이 발견되지 않았다는 뜻은 임의의 $p, q, e, M$에 대해 암호문 $C$로부터 $M$을 빠르게 복원하는 알고리즘이 존재하지 않는다는 의미입니다.

RSA에 대한 공격들

비록 Classical Computer에서 RSA 암호 시스템 자체에 대한 취약점은 아직 발견된 것이 없으나 $p, q, e, M, d$ 등이 특정 조건을 만족할 때에는 복호화가 가능할 수 있습니다.

Boneh, Dan. "Twenty years of attacks on the RSA cryptosystem." Notices of the AMS 46.2 (1999): 203-213.을 보시면 다양한 공격들이 있는데 일부 초보적인 공격의 조건과 공격 방법을 다뤄보겠습니다.

Duplicate Prime

서로 다른 $N_1, N_2$에서 중복된 $p$가 쓰였다면 $p = gcd(N_1, N_2)$로 쉽게 계산할 수 있습니다.

Small Prime Diference

소수 $p, q$의 차이가 크지 않다면 $N$이 Fermat Factorization을 이용해 쉽게 소인수분해될 수 있습니다.

Low Private Exponent

비밀키 $d$가 $d < \frac{1}{3}N^{1/4}$를 만족한다면 continued fraction을 이용해, 그리고 $d < N^{0.292}$를 만족한다면 LLL 알고리즘을 이용해 $d$를 쉽게 복원할 수 있습니다.

그러나 보통 공개키 $e$를 3 혹은 65537과 같은 작은 값으로 두기 때문에 일반적인 상황에서 쉽게 발생 가능한 공격은 아닙니다.

Hastad’s Broadcast Attack

공개키 $e = 3$이고 같은 $M$을 서로 다른 $N_1, N_2, N_3$에 대해 암호화한 결과인 $C_1 = M^3 mod N_1$, $C_2 = M^3 mod N_2$, $C_3 = M^3 mod N_3$를 알고 있다고 하면 Chinise Remainder Theorem을 이용해 $M$을 복원할 수 있습니다.

Franklin-Reiter Related Message Attack

공개키 $e = 3$이고 선형 함수 $f$에 대해 두 메시지 $M_1, M_2$가 $M_1 = f(M_2)$ 라는 관계식을 만족하고 $f$가 알려져있다면 $M_1, M_2$를 복원할 수 있습니다.

당연한 얘기지만 이 취약점들은 올바르지 않은 방법으로 암호화를 수행하기 때문에 발생하는 취약점입니다. 실제 제품들에서는 $p, q$를 랜덤하게 택하고 $e$를 65537과 같은 작은 값으로 정하고 메시지에 올바른 패딩을 붙여 암호화를 진행하기 때문에 이런 취약점들로 공격이 가능할 여지는 거의 없다고 볼 수 있습니다.

그러나 이번 게시글에서 소개할 ROCA는 당시 스마트카드와 TPM(Trusted Platform Module) 등에 널리 쓰이고 있던 Infineon Technologies의 라이브러리에서 RSA 키 생성 단계에서의 취약점을 이용한 공격이기 때문에 전 세계의 TPM device 중 1/4 가까이가 이 공격에 취약했을 정도로 파급력이 컸습니다.

Coppersmith Attack

ROCA를 이해하기 전에 먼저 Coppersmith Attack에 대해 이해할 필요가 있기 때문에 Coppersmith Attack을 소개하겠습니다.

암호학 분야에 관심이 많으신 분이라면 Coppersmith라는 인물에 대해 아주 많이 들어봤을 것입니다. DES를 IBM에서 만들 때 S-box가 차분 공격에 대해 안전할 수 있게 관여했고, n by n matrix 두 개의 곱을 $O(n^{2.375477})$에 수행하는 Coppersmith-Winograd algorithm을 만들기도 했습니다.

그리고 RSA와 관련된 분야에서도 Coppersmith Method를 만들어내어 다양한 공격 기법이 탄생하는데 큰 기여를 했습니다. 지금부터 소개할 내용은Coppersmith D. (1996) Finding a Small Root of a Univariate Modular Equation. In: Maurer U. (eds) Advances in Cryptology — EUROCRYPT ’96. EUROCRYPT 1996. Lecture Notes in Computer Science, vol 1070. Springer, Berlin, Heidelberg 논문을 바탕으로 작성한 내용입니다.

Coppersmith Method는 $N = pq$이고 ring $\mathbb{Z}_N$에서 정의된 다항식의 해가 특정 조건을 만족할 때 빠르계 계산할 수 있는 방법입니다.

구체적으로 다항식 $p(x) = x^k + a_{k-1}x^{k-1} + \dots + a_2x^2 + a_1x + a_0$이고 $p(x_0) = 0 (mod \space N)$인 $x_0$가 $|x_0| < N^{1/k}$를 만족할 때 해당 $x_0$를 $log \space N$과 $k$에 비례한 시간에 찾을 수 있습니다.

그리고 더 나아가 $N$의 인자 $b \geq N^\beta$과 최고차항의 계수가 1이고 차수가 $\delta$인 $f(x)$에 대해 $f(x) = 0 \space mod \space b$의 해 중에서 $|x_0| \leq cN^{\frac{\beta^2}{\delta}}$를 만족하는 $x_0$들을 빠르게(정확히는 $O(c\delta^5log^9N)$에) 구할 수 있다는 정리가 있습니다. 이 정리를 정리 1이라고 부르겠습니다.

갑자기 기호가 많이나와 당황스러울 수도 있지만 너무 어렵게 생각할 필요는 없고 $N = pq$이고 $f(x) = 0 \space mod \space p$를 만족하는 $x$가 $N$에 비해 많이 작다면 그 해를 $p, q$는 모르고 $N$만 알고 있는 상황에서 구할 수 있다는 의미로 이해하면 되겠습니다.

정리 1의 증명은 May A. (2009) Using LLL-Reduction for Solving RSA and Factorization Problems. In: Nguyen P., Vallée B. (eds) The LLL Algorithm. Information Security and Cryptography. Springer, Berlin, Heidelberg에서 확인할 수 있습니다.

이 Method를 이용한 공격의 시나리오들은 아래와 같습니다.

## Stereotyped Messages

평문의 $1/e$를 제외한 나머지 부분을 알고 있을 때 암호문으로부터 평문을 복원할 수 있습니다.

예를 들어 $e = 3$이고 평문의 형태가 Your Account Number is _____ 라고 한다면 $f(x) = (prefix+x)^3 - c$의 해를 구하는 문제로 치환할 수 있고 $x < N^{1/3}$이기에 $x$를 복원할 수 있습니다.

## Partial Key Exposure Attack

RSA에서 $N$이 $n-bit$일 때 $d$의 LSB $n/4-bit$이 주어지거나 $p$의 LSB 혹은 MSB $n/4-bit$이 주어지면 $N$을 소인수분해할 수 있습니다.

먼저 $d$의 LSB $n/4-bit$이 주어진 상황을 생각해보면 RSA의 기초적인 성질 중 하나로 $ed - k(N-p-q+1) = 1$을 만족하는 $1 \leq k < e$가 존재합니다. 그리고 $d$의 LSB $n/4-bit$이 주어진다는 것은 곧 $mod 2^{n/4}$에서의 $d$ 값을 안다는 의미와 동일하니 $ed - k(N-p-q+1) = 1$ 식에서 $q = N/p$로 두고 양 변에 $p$를 곱하면 $(ed)p - kp(N-p+1)+kN = p (mod 2^{n/4})$라는 식을 얻을 수 있습니다.

이 식은 $p$에 대한 이차식이므로 $e-1$개의 가능한 $k$ 후보군에 대해 전부 식을 세워보면 $p (mod 2^{n/4})$를 구할 수 있기 때문에 $d$의 LSB $n/4-bit$이 주어졌을 때 $e\space log\space e$의 연산을 통해 $p$의 LSB $n/4-bit$을 알 수 있습니다.

그리고 $p$의 LSB 혹은 MSB $n/4-bit$이 주어지면 $N$을 소인수분해할 수 있는 이유는 위에서 언급한 정리 1로부터 유도됩니다.

ROCA 취약점

이 단원의 내용은 Nemec, Matús et al. “The Return of Coppersmith's Attack: Practical Factorization of Widely Used RSA Moduli.” Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security (2017): n. pag.의 논문을 바탕으로 합니다.

앞의 여러 예시들을 통해 $\mathbb{Z}_N$에서 상대적으로 작은 해를 가지는 적절한 다항식을 세우면 그 해를 알아낼 수 있음을 알게 되었습니다. 이것이 어떻게 공격에 쓰일 수 있게 되었는지를 같이 알아보겠습니다.

RSA에서 쓰일 소수를 만드는 방법으로는 임의의 $n-bit$ 수를 만들어내고 Miller-rabin testing을 거쳐 해당 수가 소수인지 확인하는 방법이 가장 일반적입니다. $n-bit$ 수가 소수일 확률은 대략 $1/n$ 정도이기 때문에 1024-bit의 소수가 필요하다고 하면 평균적으로 1024번의 시도를 거치면 소수를 얻을 수 있을 것으로 기대할 수 있습니다.

그러나 암호 모듈에 따라 이 방법 대신 다른 방법으로 소수를 만들어내기도 하는데, 크게 아래의 3가지 목적이 있습니다.

1. Pollard’s p-1 method와 같은 공격에 더 안전하도록 만들고 싶다.

2. 소수 $p$에 대해 $p-1$과 $p+1$이 충분히 큰 factor를 가져야 한다는 NIST FIPS 140-2 표준을 준수하도록 하고 싶다.

3. 키 생성 과정의 속도를 빠르게 하고 싶다.

특히 연산 능력이 제한적인 환경에서의 키 생성을 염두에 둔 모듈의 경우에는 어쩔 수 없이 생성 과정에서 더 낮은 엔트로피가 쓰이도록 하는 경우가 종종 있고 이로 인해 소수가 예측 가능하게 되는 취약점이 종종 있었습니다.

이 ROCA가 공격대상으로 삼은 RSAlib 또한 연산 능력이 3번의 목적으로 소수를 독특한 방식으로 만들어냅니다.

바로 $p = kM + (65537^a\space mod\space M)$ 꼴로 만드는 것입니다. $k, a$는 알 수 없는 값이고 $M$은 처음 $t$개 소수의 곱입니다. 예를 들어 key size가 512 to 960일 때에는 $t = 39$여서 $M = 2 \times 3 \times \dots 167$이고 key size가 992 to 1952일 땐 $t = 71$이어서 $M = 2 \times 3 \times \dots 353$입니다. 이러한 방식으로 만든 소수를 Fast Prime이라고 부릅니다.

물론 Fast Prime이 아무런 근거 없이 도입된 것은 아닙니다. 이 구조는 Joye, M., Paillier, P., & Vaudenay, S. (2000). Efficient Generation of Prime Numbers. CHES.와 Joye M., Paillier P. (2006) Fast Generation of Prime Numbers on Portable Devices: An Update. CHES에서 제안된 구조로 속도가 빠르고 충분한 엔트로피 또한 갖추고 있기 떄문에 Infineon 사에서 이 구조로 소수를 만들었을 것입니다.

그러나 의도와 다르게 두 Fast Prime이 곱해진 $N$이 Coppersmith Method를 이용해 쉽게 소인수분해될 수 있었습니다. 그 과정을 같이 보겠습니다.

먼저 $N$이 512-bit일 때를 살펴보면 $M$이 219-bit이기 때문에 $k$는 최대 37-bit의 수이고 $ord_M(65537)$이 $2^{62}$ 미만이므로 $a$는 최대 62-bit의 수입니다.

두 소수 $p = kM + (65537^a \space mod \space M), q = lM + (65537^b \space mod \space M)$으로 두겠습니다. 만약 운좋게 $a$를 알게 되었다고 하면 우리는 $f(x) = Mx + (65537^a \space mod \space M) = 0 (mod\space p)$를 만족하는 해 $x$가 바로 $p$에서의 $k$임을 알 수 있고 $k$는 37-bit의 수로 최대 512-bit인 $N$에 비해 상당히 작기 때문에 $f(x)$에 $M^{-1} mod N$을 곱해 최고 차항의 계수가 1인 다항식으로 변형한 후 정리 1을 사용하면 쉽게 $p$를 복원할 수 있습니다.

그러면 일단 $2^{62}$개의 모든 $a$의 후보에 대해 위의 다항식의 근을 구하는 방식으로 $N$을 소인수분해 할 수 있습니다.

여기서 더 나아가 논문에서는 $a$의 후보를 $2^{62}$개보다 더 줄일 수 있는 방법을 제안합니다.

그 방법은 바로 $M$의 약수이면서 65537에 대한 order가 작은 $M’$을 이용해 식을 구성하는 방법입니다. 식은 $f(x) = M’x + (65537^a \space mod \space M’) = 0 (mod\space p)$ 꼴로 변형되는데 정리 1을 사용하기 위해서는 $x < N^{1/4}$를 만족해야 합니다. 그러기 위해서는 $M’ > N^{1/4}$이어야 합니다.

즉 $M’$은 $M’ > N^{1/4}$을 만족하면서 $ord_{M’}(65537)$이 최대한 작을수록 유리합니다. 이러한 $M’$을 효과적으로 알아내는 다양한 방법을 논문에서 제시하지만 그 부분은 생략하고, $M’ = $0x1b3e6c9433a7735fa5fc479ffe4027e13bea일 때 $ord_{M’}(65537) = 1201200$으로 $2^{62}$와 비교할 때 훨씬 줄어든 것을 확인할 수 있습니다.

이후 $N = 65537^c\space mod\space M’$을 만족하는 $c$는 $M$이 작은 소수들의 곱이므로 Pohlig-Hellman 알고리즘을 이용해 간단히 알아낼 수 있기 때문에 $c/2 \leq a \leq (c+ord_{M’}(65537))/2$에 대해 정리 1을 사용하면 $p$를 얻어낼 수 있습니다.

결론적으로 key size가 512-bit일 땐 최악의 경우 1.93 CPU hours, 1024-bit일 땐 97.1 CPU days, 2048-bit일 땐 140.8 CPU years에 해를 구할 수 있습니다. 각각에 대해 쓰이는 $M’$ 값은 여기를 참고하면 됩니다.

실제 roca를 수행하는 코드는 링크 1, 링크 2를 참고하시면 됩니다.

마무리

이번 글에서는 ROCA에 대해 알아보았습니다. RSA 자체가 취약한 것은 아니었으나 RSAlib에서 소수 생성의 문제점으로 인해 결론적으로 RSA가 안전하지 못하게 되었습니다.

이후 소수 생성 과정을 어떻게 패치했는지 열심히 찾아봤으나 아쉽게도 제 검색능력이 부족한지 찾아내지 못했습니다.

사실 상용화된 모돌조차 이와 같이 취약점을 가지고 있었던 상황인만큼 세상에 믿을게 하나도 없다는 말이 틀린 말이 아니지만 그래도 어찌됐든 직접 구현한 암호 알고리즘보다는 상용화된 모듈이 더 철저한 검증을 거친 후에 사용되고 있을 것이니 앞으로 개발할 프로그램에서 암호화/복호화 과정이 필요하다면 검증된 모듈을 사용하도록 합시다.