Cryptographic Backdoor
안녕하세요, 최근에 연달아 다소 난이도 있고 재미 없는 내용을 올렸는데 이번 글에서는 약간의 배경 지식을 필요로 하지만 굉장히 흥미로운 주제를 가지고 왔습니다. 꼭 암호학에 관심이 없더라도 읽어보면 재밌을만한 내용이니 편하게 즐겨주세요.
Introduction
Privacy vs National security
디지털 시대가 도래하면서 개인의 프라이버시와 국가 안보 사이에서 딜레마를 겪는 일이 많아지고 있습니다. 2015년 샌버너디노 총기 난사 사건 당시 수사기관은 애플에게 테러리스트의 휴대폰 잠금을 풀어줄 것을 요청했지만 애플은 이를 거부했고, 2017년 웨스트민스터 테러에서도 암호화된 테러리스트의 Whatsapp 대화를 풀어내지 못했습니다.
국내에서도 테러방지법, SNI 필드를 이용한 인터넷 패킷 검열, N번방 사건에서 텔레그램의 비협조 등의 문제로 이와 관련한 문제가 주기적으로 제기되었습니다. 프라이버시와 국가 안보 중에서 무엇이 옳다는 질문에 대한 답은 옳고 그름이 명백하게 정해지지 않는다고 생각합니다. 범죄자들이 익명성을 무기로 마음껏 범죄를 저지를 수 있는 사회가 오는 것은 바람직하지 않지만 이를 막겠다는 이유로 국가가 언제든 나의 사생활을 들여다볼 수 있는 사회 또한 썩 바람직한 모습은 아닌 것으로 보입니다.
실제로 카카오톡 사찰논란, 테러방지법 제정등과 같은 사건이 발생할 때 국내 메신저 대신 국내 수사기관의 검열이나 압수수색이 불가능하고 아예 창업자가 사생활을 보장받을 권리가 테러와 같은 위협보다 더 중요 하다고 발언할 정도로 프라이버시 보장을 모토로 하는 텔레그램으로의 이동이 대거 발생했는데 N번방 사건 당시 동일한 이유로 텔레그램이 수사에 협조하지 않자 많은 비난을 받는 등 국가 안보 혹은 범죄 방지를 위해 개인의 프라이버시가 어디까지 존중되고 어디까지는 침해될 수 있는지에 대한 부분은 쉽게 답을 낼 수 없는 문제로 보입니다. 개인의 프라이버시가 모든 것을 우선하는 사회도, 국가 안보가 모든 것을 우선하는 사회도 큰 결함이 있어보이기 때문에 이 문제는 사회의 구성원들의 건설적인 토론으로 합의점을 찾아나가야 할 것 같습니다.
Cryptographic Backdoor
프라이버시와 국가 안보 사이에서의 사회적 논의와 무관하게 정부는 모든 것을 알고 싶어 합니다. 전 NSA 요원 에드워드 스노든이 폭로한 프리즘과 같이 우연한 계기에 정부의 감청이 수면 위로 떠오르기도 했지만 지금 이 순간에도 각 나라의 첩보 기관은 서로의 정보를 캐내기 위해 노력하고 있을 것입니다.
만약 현대에 사용하는 AES, Diffie Hellman, RSA, ECC, SHA256 등과 같은 암호 시스템의 취약점을 찾아낸다면 제 2차 세계대전 당시 독일군의 에니그마를 해독한 것에 비견될 정도로, 어쩌면 비교도 할 수 없을 정도로 첩보전에서 큰 우위에 서게 될 것입니다. 하지만 이런 암호 시스템은 긴 세월동안 전 세계의 암호학자가 공격을 시도하고, 때로는 더 안전하게 수정하기도 하면서 발전해왔기 때문에 그럴 가능성은 적어보입니다.
그렇다면 첩보 기관에서 애초에 자신들만 아는 백도어가 있는 암호 시스템을 만들어내고 이를 표준으로 올려 전 세계가 이 시스템을 사용하도록 하는건 어떨까요? 굉장히 터무니 없고 음모론에서나 나올법한 이야기지만 이걸 시도하고 반쯤 성공한 일이 2000년대에 있었습니다.
Cryptovirology
Cryptovirology라니, 요즘처럼 코로나가 극성인 시대에 적합한 용어인 것 같네요. Cryptovirology는 Adam L. Young, Moti Yung이 90년대 중반부터 제창한 개념으로(링크), 어떻게 하면 암호 시스템에 바이러스를 삽입할지를 다루고 있습니다.
이들이 쓴 논문중에 The prevalence of kleptographic attacks on discrete-log based cryptosystems(링크)을 주목해봅시다.
해당 논문에서는 black-box cryptosystem $C$에 공격자만이 알 수 있는 백도어가 추가되었지만 공격자를 제외한 다른 모든 사용자는 출력값을 보고 백도어의 존재 여부를 알 수 없는 수정을 가한 cryptosystem $C’$을 만들어내는 방법을 서술하고 있습니다. 2.1장의 Discrete Log Kleptogram에서는 Diffie Hellman에서 쓰일 것 같은, $g^c mod p$를 랜덤하게 만들어내는 것 처럼 보이는 backdoored pseudorandom function을 소개하고 있습니다. 사용자나 기타 다른 사람은 이 함수를 보고도 이상한 점을 눈치챌 수 없었지만 공격자는 매번 지수 $c$를 알아낼 수 있고 이 black box를 누군가 Diffie Hellman 키 교환에서 사용한다면 공격자는 공유된 비밀 키를 알아내어 둘 사이의 통신을 마음껏 들여다볼 수 있을 것입니다.
그리고 NSA는 이것과 유사한 방식을 Random Generator에 넣을 생각을 합니다.
CSPRNG(Cryptographyically Secure Pseudorandom Number Generator)
현대에 있는 대다수의 암호 시스템에는 난수가 쓰입니다. 이 난수가 예측 가능하다면 RSA에서 소수를 예측할 수도 있고, Diffie Hellman에서 지수를 예측할 수도 있고 여러 가지로 암호 시스템이 안정되지 못할 것입니다. 이 부분은 암호를 잘 모르더라도 코드포스에서 예측 가능한 난수로 인해 Hack을 당한 경험이 있다면 잘 이해할 수 있을 것입니다.
CSPRNG는 좋은 성질을 만족하는 유사 난수(PRNG, Pseudorandom Number Generator)를 일컫는 용어입니다. 그 성질은 바로 아래와 같습니다.
CSPRNG로 만들어낸 수열과 실제 uniformly random하게 만들어낸 수열이 제시되었을 때 이들을 구분해낼 확률이 임의의 polynomial p(x)보다 작다.
이러한 관점에서 단순히 어떤 polynomial function $f$에 대해 $x_i = f(x_{i-1})$로 정의되는 PRNG나 seed의 state가 굉장히 적은 C언어에서의 random 함수는 CSPRNG가 아닙니다.
이렇게 난수를 만들어내는 일은 암호학적 관점에서 굉장한 중요한 일이고 실제 컴퓨터가 진정한 의미의 난수를 만들 수는 없기에 난수가 필요할 때에는 난수 대신 유사 난수를 사용합니다. 윈도우나 리눅스와 같은 운영체제에서는 별도로 CSPRNG를 제공하는 API를 제공하고, NIST(National Institute of Standards and Technology, 미국 국립표준기술연구소)와 같은 단체에서는 CSPRNG를 만드는 방법을 표준으로 제정해서 프로그램 제작자들이 표준대로 난수를 생성하게끔 합니다.
Dual_EC_DRBG
NIST가 2006년에 발표한 NIST SP 800-90A 표준을 보면 CSPRNG로 4가지를 제시하고 있습니다. 처음 3개는 Hash_DRBG, HMAC_DRBG, CTR_DBRG입니다. 그리고 마지막으로 제시된 CSPRNG는 Dual_EC_DPBG입니다. 이 Dual_EC_DPBG는 Eliptic Curve의 연산을 통해 난수를 생성하는 방법입니다. Eliptic Curve의 연산이란 Curve 위에 존재하는 점들 사이에서의 덧셈과 뺄셈을 의미하고 마치 $Z_n$에서 generator $g$와 $y$가 주어질 때 $g^x = y$를 만족하는 $x$를 찾는 것이 어려운 것과 같이 generator $G$와 점 $P$가 $P = xG$를 만족하는 $x$를 찾는 것이 어렵습니다.
Dual_EC_DPBG는 아래와 같은 절차를 거칩니다.
- 곡선과 점 $P, Q$가 주어집니다. 곡선은 256비트 크기의 곡선입니다.
- 첫 번째 시드 $s_0$을 랜덤으로 정합니다.
- 이후 $s_i = s_{i-1} \cdot P$로 정의됩니다.
- 계산된 $s_i$에 대해 $s_1 \cdot Q$부터 차례로 MSB 16비트를 잘라낸 값들을 난수로 사용합니다.
이 난수 알고리즘은 상당히 의문스러운 점이 많았습니다. 첫 번째로 $P$는 곡선의 generator였지만 $Q$는 정체를 알 수 없는 값인데 그 값이 매번 랜덤하게 정하는 대신 표준에 적힌 상수로 고정되어 있었기 때문입니다. 암호에서 상수가 필요할 땐 불필요한 의심을 덜기 위해 0123456789, 1414...($\sqrt{2})$, 2718...($e$), 3.1415926...($\phi$)과 같이 출처가 분명한 것을 사용하는 것이 일반적입니다. 이러한 관례적인 수를 Nothing-up-my-sleeve number라고 부릅니다. 반대로 말해 상수를 이런 수가 아니라 다른 값을 쓴다면 그 부분이 백도어가 아닌가 하는 의심을 받을 수 있습니다. 일례로 DES의 경우 추후 설계 원리에서 차분 공격을 막기 위한 설계였음이 밝혀지기도 했지만 S-box가 Nothing-up-my-sleeve number가 아니어서 의심을 사기도 했습니다. 아무튼 $Q$는 쓰임새가 중요한 난수인데 선정 이유에 대한 단서가 없다는 점이 문제였습니다.
두 번째로 $r_i$를 얻어내기 위해 MSB 16비트만 잘라내는 과정 또한 의심스러웠습니다. 잘라내는 비트가 충분하지 않아 $r_i$가 주어졌을 때 $s_i \cdot Q$의 후보군을 $2^{16}$개로 추측해낼 수 있었습니다.
세 번째로 원래 공개키 기반의 암호 시스템이 비밀키 기반의 암호 시스템보다 월등히 느린데 다른 CSPRNG와 다르게 Dual_EC_DRPG는 ECC(Eliptic Curve Cryptography) 기반이기 때문에 동작 속도가 많게는 수 천배 가까이 차이났습니다.
이렇듯 표준으로 등록될 때 부터 의심스러운 점이 많았던 Dual_EC_DRPG는 2007년 Microsoft의 Dan Shumow, Niels Ferguson이 백도어를 찾아내면서 그 쓰임새를 다했습니다. 백도어는 허무할정도로 간단했는데 $Q = dP$인 $d$를 알고 있는 공격자는 너무나 쉽게 난수로부터 시드를 복원해낼 수 있어 앞으로 나올 모든 난수의 값을 알 수 있었습니다.
구체적으로 공격법을 설명하자면 $R = (r_1, y_{r_1}) = s_1Q$라고 할 때 공격자는 MSB 16비트를 전수조사함으로서 우선 $R$을 복원할 수 있습니다. 이후 $Q = dP$인 $d$를 알고 있으면 $s_1$을 모르더라도 $dR = s_1P = s_2$이기 때문에 앞으로의 난수 생성에 필요한 seed를 계산해낼 수 있습니다.
Bullrun
어느 누가 보더라도 의심스러운 정황이 가득했던 이 사건의 전말은 2013년 스노든의 폭로로 명백하게 밝혀지게 됩니다. 스노든의 폭로에 따르면 NSA에서는 암호화를 꺨 수 있는 방법을 연구하는 Bullrun이라는 프로젝트를 운영했습니다. NSA는 상용으로 쓰이는 암호 시스템에 취약점을 넣고 싶어 했고 Dual_EC_DRBG가 그 대표적인 예시였습니다. Dual_EC_DRBG에 백도어가 숨겨져 있다는 사실이 널리 알려진 이후에도 RSA security 회사는 자사의 BSAFE toolkit과 Data Protection Manager라는 프로그램에 Dual_EC_DRBG를 2013년까지 사용했고 Dual_EC_DRBG를 사용하는 대가로 NSA가 뒷공작으로 1000만 달러의 거금을 RSA에 지급했다는 사실이 드러났습니다. 해당 모듈은 TLS 통신에 쓰였기 때문에 NSA는 Daul_EC_DRBG가 쓰인 RSA의 취약한 모듈을 이용해 생성된 TLS 통신을 해독할 수 있었을 것입니다.
Conclusion
저는 이 Dual_EC_DPBG를 최근에 알게 되었고 굉장히 충격적이었습니다. 표준이 발표되고 또 이후 취약점이 발견된 2006, 2007년에는 제가 어렸고 2013년 스노든의 폭로가 발생했을 때에도 전 세계를 감청한다는 PRISM에 대한 얘기를 많이 들었을 뿐 Dual_EC_DPBG에 관한 내용은 몰랐습니다. 최근에 암호학 관련 문제를 풀다가 이 Dual_EC_DPBG로 생성된 난수를 예측해야 하는 문제를 만나서 찾아보다가 관련된 일련의 사건을 알게 되었습니다.
사실 나 자신을 제외하고는 어느 것도 믿을 수 없다는 관점에서는 할 수 있는게 아무 것도 없습니다. 애플의 개발 툴인 Xcode를 정식 앱스토어가 아닌 다른 곳에서 설치했더니 컴파일러에 백도어가 숨겨져있어서 만들어내는 어플리케이션이나 프로그램에 백도어를 만들어버리는 일도 있었고(링크) 극단적으로 말해 애초에 인텔에서 만들어낸 CPU 자체에 백도어가 숨겨져 있을수도 있겠죠.
하지만 사실상 음모론의 수준에서 막연하게 그럴 가능성이 있다는 정도로만 생각하는 것과 그 실체가 공개된 것에는 분명한 차이가 있습니다.
그나마 다행이라고 한다면 AES 혹은 SHA3과 같은 구조는 특정 기관에서 주도적으로 만들어내는 대신 전 세계의 공모를 받아 나름 합리적인 기준을 정해 그 기준 아래에서 가장 좋은 구조를 채택하는 방식으로 정해지기 때문에 기존에 널리 쓰이고 있는 암호 시스템에도 백도어가 있는 것이 아닌가 하는 걱정은 조금 덜어낼 수 있습니다.
이 일을 거치고 Dual_EC_DRBG는 결국 표준에서 제거되었지만 그 외에는 크게 달라진 것은 없습니다. 어쩌면 다음에는 훨씬 더 교묘한 방법으로 백도어가 숨겨진 암호 시스템이 제시될 가능성도 있습니다. 결국 이러한 문제는 민간에 있는 다수의 선량한 전문가들의 자발적인 협력으로 해결해야 할 문제라고 생각합니다.