Data Centric Security in Cloud Era ③ : Post-Quantum Crypto (PQC)

Data Centric Security in Cloud Era 3 - 양자내성암호(PQC)

양자컴퓨팅

미디어를 통해 ‘특정 기업이 N qubit의 양자컴퓨터를 개발했다’는 소식을 접한다면, 이때 N qubit가 의미하는 바는 무엇일까요?
N qubit 양자컴퓨터는 2N개의 N-bit 정보를 동시에 처리할 수 있다는 의미입니다. 현재 우리가 사용하는 N-bit 컴퓨터는 한 번에 N-bit 정보 하나씩만 처리할 수 있는데, 양자컴퓨터는 2N개를 동시에 처리할 수 있으니 qubit가 늘어날 때마다 컴퓨팅 능력은 기하급수적으로 늘어나는 셈입니다.

양자컴퓨팅 이해를 돕기 위한 Toy Example [그림1] 양자컴퓨팅 이해를 돕기 위한 Toy Example

그리고, 양자컴퓨팅을 이해하려면 측정(Measurement)의 개념을 이해하는 것이 중요합니다. 예를 들어 설명해보겠습니다.
만약 2 qubit 양자컴퓨터를 가지고 있다면 최대 22개의 양자정보를 동시에 처리할 수 있으며([그림1]), 계산이 완료된 후 결과를 측정할 필요가 있습니다. 하지만 측정 시에는 22개의 양자정보 중 단 하나만 측정할 수 있으며, 해당 양자정보는 측정 시마다 각각 자신이 측정될 확률이 있는데 이것이 바로 [그림1]의 Cij에 해당합니다. 따라서 양자컴퓨터를 이용해 계산할 때에는 측정될 양자정보 앞에 붙어있는 Cij가 최대한 1에 가까워지도록 양자알고리즘을 설계해야 합니다. 양자알고리즘에 대해서는 다음 단락에서 좀 더 설명하겠습니다.

Shor's Algorithm

컴퓨터를 사용할 때는 HW뿐 아니라 이를 사용하는 SW가 필요합니다. 양자컴퓨팅에서도 컴퓨터 외에 이를 사용할 양자알고리즘의 개발이 필요하죠. 양자컴퓨터가 현실화되면 적용 가능한 양자알고리즘들이 이미 제안되어 있는데, 그 중 암호해독에 큰 영향을 미치는 대표적인 양자알고리즘이 바로 Shor’s Algorithm입니다.

이전에 설명했듯이 우리가 광범위하게 사용하는 공개키 알고리즘은 공개키 등으로부터 비밀키를 알기 어렵도록 설계해야 하는데, 이를 위해 Reduction 기법을 많이 사용합니다. 쉽게 말하면 ‘어떤 수학 난제를 푸는 것이 현재의 컴퓨팅 환경에서는 불가능하므로 설계된 공개키 암호알고리즘이 안전하다’는 방법론을 사용하는 것입니다. 현재 모든 암호화 통신 및 전자서명에 사용되는 공개키 암호알고리즘인 RSA나 ECC는 Prime Factorization과 Discrete Logarithm Problem에 각각 그 안전성을 기반합니다. 즉, 위의 두 가지 수학 문제가 현재 컴퓨팅 자원으로는 풀기 힘들기에 RSA나 ECC가 안전하다고 주장하는 것이죠. 하지만 1994년 Shor는 양자컴퓨터를 이용해 굉장히 빠른 시간 안에 이 문제들을 풀 수 있는 양자알고리즘을 제안했습니다.

Post-Quantum Cryptography(PQC)

양자와 관련된 암호기술은 크게 두 가지로 분류됩니다. 먼저 양자를 이용해 키를 공유하는 암호기술이 있는데, 이를 ‘Quantum Key Distribution(QKD)’라고 부릅니다. 그리고 앞서 언급한 양자컴퓨팅 환경에서 안전한 암호알고리즘을 ‘양자내성암호’, 즉 ‘Post-Quantum Cryptography(PQC)’라고 부르죠. PQC는 양자컴퓨팅 출현 전부터 적용되어야 하며, 현 컴퓨팅 환경에도 적용 가능합니다.

PQC 표준화로 유력한 세 가지 암호알고리즘 [그림2] PQC 표준화로 유력한 세 가지 암호알고리즘

양자컴퓨터와 Shor’s Algorithm에 대한 안전한 암호알고리즘의 표준화를 NIST(미 표준국)에서는 아래 3가지 방식으로 진행 중입니다.

  1) Signature: 전자서명 표준(FIPS 186-4) 대안
  2) Encryption: Key Transport, Secret Sharing에 사용된 권고안 (SP 800-56B) 대안
  3) Key Establishment (KEMs): DH 키 공유 방식 (SP 800-56A) 대안

Code-based Cryptography, Hash-based Cryptography, Lattice-based Cryptography가 표준 후보로서 주목받고 있으며, PQC 표준화는 기존 AES나 SHA-3 표준화와 달리 하나의 표준 알고리즘이 아닌 여러 개의 알고리즘들(Good Choices)이 재정될 것으로 예상됩니다. 후보기술마다 장단점이 있으며, 특정 암호알고리즘을 공격할 양자알고리즘이 언제 개발될지 모르기 때문입니다.
NIST는 총 10년 계획으로 PQC 표준화를 진행하고 있으나, 표준화 기간이 너무 길다는 비판이 있어 오랜 기간에 걸쳐 안정성이 증명된 Hash 기반 Primitive(XMSS, IETF draft)를 우선 공고할 것으로 보입니다.

우리에게 남은 대응 기간

양자컴퓨터가 RSA나 ECC와 같은 공개키 암호알고리즘에 대한 공격에 사용되려면 적어도 2000 qubit 정도의 양자컴퓨터가 필요합니다. 그렇다면 현재 양자컴퓨터의 발전 현황과 속도는 어느 정도일까요? 아래 [표1]은 2016년 12월에 파악된 양자컴퓨터 개발 현황입니다. 그 후로 불과 1년 반도 지나지 않은 현재에는 Google의 경우 72 qubit까지 개발이 진행됐습니다([그림3]).

양자컴퓨터 개발 현황 (2016년 말), 출처: [사이언즈] 2016.12.2 [표1] 양자컴퓨터 개발 현황 (2016년 말), 출처: [사이언즈] 2016.12.2 양자컴퓨터 개발 현황 (2018년 초) [그림3] 양자컴퓨터 개발 현황 (2018년 초)

여기서 우리가 간과하지 말아야 할 것이 있는데, 바로 보안과 컴퓨터의 역사입니다.
예를 들어 우리는 1946년에 개발된 ENIAC이 최초의 컴퓨터라고 알고 있습니다. 하지만 영화 이미테이션 게임에 등장했듯이 이보다 3년 앞선 1943년에 이미 Colossus라는 컴퓨터가 존재했습니다([그림4]). 어째서 인류 최초의 컴퓨터가 음지에서 몰래 개발되었을까요? 이는 Colossus의 용도가 바로 암호알고리즘 해킹이었기 때문입니다. 즉, 우리는 Public Sector에서 진행되고 있는 양자컴퓨팅의 발전 현황만을 알고 있을 뿐이며, 어쩌면 양자컴퓨터의 발전은 우리 생각보다 이미 더 진전되었을지 모릅니다.

컴퓨팅의 발전 역사(양지와 음지) [그림4] 컴퓨팅의 발전 역사(양지와 음지)

그리고 더욱 심각한 이슈가 있습니다. 2013년에 캐나다 워털루 대학의 Mosca 교수는 양자컴퓨팅에 의한 암호알고리즘 공격에 대비하기 위한 시간을 이론으로 제시했습니다. [그림5]에서 x는 암호알고리즘으로 보호하고자 하는 데이터가 얼마 동안 보호되어야 하는지를, y는 PQC를 적용하는 데 소요되는 마이그레이션 시간을, z는 현재 사용되는 암호알고리즘을 공격할 수 있는 양자컴퓨터가 개발되기까지의 시간을 나타냅니다. 이때 데이터 의무보호 기간과 마이그레이션 기간을 합산한 시간이 양자컴퓨팅 발전 속도보다 길다면, 이는 공격으로 이어진다는 의미입니다.

Mosca 이론(x years: security shelf-life, y years: migration time, z years: collapse time) [그림5] Mosca 이론(x years: security shelf-life, y years: migration time, z years: collapse time)

이러한 공격이 가능한 이유는 다음과 같습니다. 특정 기업이나 조직을 공격하려는 공격자는 이미 네트워크 상에 오고 가는 데이터를 무작위로 수집하고 있습니다(Data Vaulting Attack). 이러한 데이터의 보호기간이 최소 10년이고, 양자컴퓨팅에 의한 암호 해킹 공격에 대비하기 위한 PQC 적용 기간이 2년이라고 가정해보겠습니다. 만약 공격자가 지금부터 암호화된 데이터를 수집해놓고 10년 안에 해킹 가능한 수준의 양자컴퓨터 사용이 가능해진다면, 그 순간 곧바로 암호화된 데이터를 양자컴퓨터를 이용해 복호화 할 수 있는 것입니다.

양자컴퓨팅에 의한 암호 해킹 공격 대응 방법

위와 같은 공격에 대비하기 위해 비공개 암호알고리즘을 사용할 수 있습니다. 예를 들어 암호화 통신을 위해서 양측이 key exchange protocol(인증 및 키 공유)을 수행한 후, 실제 데이터를 암호화할 때 비공개 암호알고리즘을 사용할 수 있죠. 이러한 접근 방법은 효과적일 순 있으나 완벽하진 않으며, 통상적으로 이러한 Security by Obscurity 접근 방식에 대해 보안업계의 대부분은 부정적인 시각입니다. 데이터 보호를 위해 비공개 암호알고리즘을 단독으로 사용하는 것은 언제 터질지 모르는 시한폭탄을 안고 있는 것과 같기 때문입니다.
양자암호 기반의 보안채널(Authenticated Key Exchange Protocol)이 없는 상황에서 가장 안전하고 효율적인 방안은 Cloud Security Alliance (CSA)에서 제시하고 있습니다. 대부분의 암호화 통신에서 사용되는 TLS에서는 Handshake 과정을 통해 Master Secret(S)을 생성한 후 KDF(키 유도함수)를 사용해 암호화 키(KA, KB)를 생성하고, 이를 데이터 암호화 키로 사용합니다([그림6]). CSA에서는 암호화 키 생성 시 TLS Handshake로부터 생성된 S뿐만 아니라 PQC(공개키 암호)를 사용해 주고받은 비밀값(q)도 키 생성 시 함께 사용하도록 제안합니다(KA or KB= KDF(S) → KA or KB =KDF(S,q)). 이렇게 하면 기존 표준 기반으로 성능 저하 없이 보안채널을 형성할 수 있습니다.

Quantum-safe Hybrid Protocol(출처: Cloud Security Alliance) [그림6] Quantum-safe Hybrid Protocol(출처: Cloud Security Alliance)

지금까지 Storage, Compute, Network 환경에서 새로운 데이터 보안에 대한 Emerging Trend에 대해서 살펴봤습니다. 암호는 지금까지 경험하지 못한 새로운 변곡점에 있으며 AI, Blockchain, Cloud, IoT, Mobility 등 다양한 기술을 통한 Data-Driven Digital Transformation 실현에 있어 매우 중요한 역할을 할 것입니다.



▶   해당 콘텐츠는 저작권법에 의하여 보호받는 저작물로 기고자에 저작권이 있습니다.
▶   해당 콘텐츠는 사전 동의없이 2차 가공 및 영리적인 이용을 금하고 있습니다.


조지훈 팀장
조지훈 팀장 보안 전문가
삼성SDS 보안연구팀

조지훈팀장은 University of Waterloo에서 석사학위(암호)를, Royal Holloway University of London에서 정보보안 박사학위를 각각 취득하였습니다. Mobile Security Architect로 스마트폰 보안업무를 담당한 경험이 있으며, 현재 삼성SDS 연구소 보안연구팀 팀장으로 암호기술 및 SW보안기술을 연구개발하고 있습니다.

구독하기

인사이트 리포트 소식을 메일로 받아보세요