서화정 ([email protected])

한성대학교 IT융합공학부 교수

양자 내성 암호

2019년도 10월 23일 구글에서는 세계 최초로 양자 우월성 (quantum supremacy)을 달성하였음을 nature를 통해 발표하였다 [1]. 해당 연구에는 구글에서 개발한 53-큐비트 프로세서가 탑재된 양자 컴퓨터인 시커모어 (sycamore) 상에서 생성된 난수가 진짜 난수인지 증명하는 것으로서 현존하는 슈퍼컴퓨터 상에서는 1만년이 걸리는 문제이지만 시커모어 상에서는 3분 20초 만에 가능하다. 현재 양자컴퓨터는 국제적인 IT 기업인 구글, IBM, 그리고 마이크로 소프트에서 주도적으로 개발에 나서고 있다. 투자에 대한 이유로는 현재 난제로 알려진 많은 문제 (머신러닝 그리고 정보검색)들에 대한 해답을 양자컴퓨터가 슈퍼컴퓨터보다 나은 성능으로 찾을 수 있기 때문이다. 양자 컴퓨터는 중첩 (superposition)과 얽힘 (entanglement)과 같은 역학적 현상을 이용하여 대량의 정보를 병렬로 연산할 수 있도록 설계된 초고속 컴퓨터이다. 기존 컴퓨터가 0과 1 중 하나의 정보만을 표현할 수 있었다면 양자 컴퓨터에서는 0과 1 모두를 확률적으로 가지는 중첩 상태를 통해 많은 정보를 표현하는 것이 가능하다. 이와 더불어 얽힘 현상은 사전에 연산이 수행된 두 양자 큐비트가 멀리 떨어져 있는 경우에도 한쪽의 상태가 관측을 통해 결정되게 되면 나머지의 상태도 이에 영향을 받아서 결정되는 것을 의미한다. [표 1]에는 기존 컴퓨터와 양자컴퓨터의 특징을 비교하여 나타내고 있다.

미래의 기술로 여겨지던 양자 컴퓨터 기술이 근래에 폭발적인 성장을 이룩함에 따라 현실 세계의 다양한 난제들이 해결될 것이라는 기대감이 커져 가고 있다. 하지만 이와는 별개로 난제로 남아 있어야 인류에게 도움이 되는 암호학적 난제들은 양자 컴퓨터 상의 양자 알고리즘을 통해 쉽게 해결됨으로써 현대 암호체계에 위기를 드리우고 있다.

여기서 양자 알고리즘이란 양자 컴퓨터 상에서 효율적으로 연산가능한 알고리즘을 의미한다. 암호학의 붕괴에 가장 큰 영향을 미치는 알고리즘으로는 Shor 알고리즘과 Grover 알고리즘이 있다 [2, 3]. 현재 상용화된 제품에 탑재되어 사용되고 있는 공개키는 RSA와 ECC이다. 해당 공개키 알고리즘은 Integer Factorization과 Discrete Logarithm Problem에 기반하고 있다. 해당 난제들은 Shor 알고리즘 상에서 주기를 찾는 문제로 변환되며 양자 컴퓨터 상에서 효율적인 양자 푸리에 변환을 이용하여 실시간으로 해답을 찾는 것이 가능하다. Grover 알고리즘은 n개의 분류되지 않은 데이터 상에서 특정 데이터를 찾아내는 양자 알고리즘이다. Grover 알고리즘은 고전 컴퓨터에서 무차별 대입 시 최대 의 검색 횟수가 필요하였다면 Grover 알고리즘을 사용하면 최대 만의 검색으로 결과를 찾아낼 수 있다. 기존 대칭키와 해시함수의 보안을 절반으로 감소시키지만 키 길이를 두 배로 증가시키는 것만으로도 충분한 보안성을 확보하는 것이 가능하다. 따라서 현재 대칭키보다는 공개키 알고리즘이 양자 컴퓨터에 보다 큰 영향을 받을 것으로 예상되며 이를 보완하기 위한 전세계적인 움직임이 이루어지고 있다. 그 중에서 가장 주목할만할 활동으로는 NIST 양자 내성 암호 표준화가 있다.

양자 내성 암호 표준화

미국 NIST에서는 양자 내성 암호 표준화 작업을 2017년부터 진행해 오고 있다. 양자 내성 암호 표준화는 현재 공개키 알고리즘 (RSA 그리고 ECC)을 대체하기 위한 작업으로써 양자 내성을 제공하는 공개키 알고리즘 (전자서명, 암호화, 혹은 키교환 프로토콜) 개발을 목표로 하고 있다. 제안되는 알고리즘이 만족해야 하는 보안 등급으로는 exhaustive key search 관점에서는 AES-128, AES-192, 혹은 AES-256를 만족하거나 collision search 관점에서는 SHA-256 혹은 SHA-384을 만족하도록 양자 내성 암호를 제안해야 한다.

[표 2]에는 NIST 양자 내성 암호 표준화 일정이 제시되어 있다. 초기에 양자 내성암호 표준화 작업은 10년으로 계획되었다. 하지만 양자 컴퓨터의 급속한 발전으로 인해 일정이 앞당겨 지고 있으며 빠르면 올해 말 그리고 늦어도 내년에는 최종 양자 암호 표준안이 발표될 것으로 예상된다. NIST에서 이전에 추진하였던 대칭키 암호 (AES)와 해시 함수 (SHA-3) 표준화와는 달리 양자 내성 암호 표준화에서는 다양한 수학적 난제 (격자, 다변수다항식, 코드, 해시, 그리고 아이소지니)를 기반으로한 알고리즘들이 제안되고 있다. 여기서 하나의 알고리즘을 선택한 이전 표준화 작업과는 달리 양자내성암호 표준화에서는 다수의 알고리즘을 선택할 것으로 보인다. 이는 양자내성암호 알고리즘들의 장단점이 너무나도 분명하며 이중에서 다양한 컴퓨터 시스템과 IT 서비스에 적합한 최선의 알고리즘 하나를 선택하는 것이 어렵기 때문이다. 현재 제안되고 있는 다양한 양자 내성 암호 알고리즘들의 특징은 아래와 같다.

격자기반 양자내성 암호는 1996년 Miklos Ajtai에 의해 제안되었다. 격자기반 양자내성 암호는 2가지 어려운 수학적 난제에 기반을 두고 있다. 첫 번째 문제는 SVP (Shortest Vector Problem)로써 좌표 안에 기본 벡터들이 주어진 경우에 이를 기반으로 하여 가장 짧은 벡터를 다항 시간 안에 찾기 어렵다는 것을 의미한다. 두 번째 문제는 CVP (Closest Vector Problem)로써 좌표 안에 기본 벡터들이 주어졌을 때 이를 표현할 수 있는 가장 가까운 벡터를 찾기 어렵다는 문제에 기반한다. 현재 다양한 격자기반 양자내성 암호가 제안되고 있지만 많은 관심을 받고 있는 것은 LWE (Learning With Error)와 LWR (Learning With Rounding) 기법이다. LWE는 격자기반 암호 구현 시 에러를 삽입하여 행렬식의 해를 찾기 어렵도록 하는 기법이며 LWR은 반올림을 통해 에러를 삽입함으로써 해를 찾기 어렵게 하는 기법이다.

1988년에 Matsumoto와 Imai에 의해 제안된 다변수 다항식 문제 기반 양자 내성 암호는 다른 암호화에 비해 수학적인 증명이 간단하다는 장점을 가지고 있다. 오랜 기간에 걸쳐서 다항식 기반 양자내성 암호에 대한 연구가 진행되었으며 특히 큰 키 문제를 해결하기 위한 최적화 기법들이 시도되고 있다. 하지만 키의 최적화는 보안취약점으로 이어지는 경우가 있어 지속적인 보안성과 효율성의 trade-off가 주된 연구로 이어지고 있다.

코드 기반 양자 내성 암호의 시초인 McEliece 암호화 시스템은 1978년도 Robert McEliece에 의해 제안되었다. 코드 기반 양자 내성 암호는 네트워크 장비 간의 통신 중에 노이즈가 신호 상에 포함되는 문제점을 해결하기 위해 노이즈를 검출하여 제거하는 기술을 연구하던 결과를 암호화 기법에 적용한 것이다. 즉 임의의 노이즈를 정보 상에 삽입하고 적법한 사용자만 알 수 있는 방식으로만 노이즈 제거가 가능하도록 하여 공격자는 실제 데이터를 확인하는 것이 어렵도록 하는 것이다. 코드 기반 암호 또한 다변수 다항식 문제 기반 암호와 유사하게 큰 키 문제로 인해 실제 장비 상에서의 운용에 있어 어려움이 있는 상황이다.

Ralph Merkle에 의해 제안된 해시 기반 양자 내성 암호는 기본 연산자인 해시 함수의 collision resistance 문제에 기반하고 있다. 이는 Grover 알고리즘에 의해 보안성이 기존의 절반으로 줄어들지만 보안 파라미터를 재설정함에 따라 양자 컴퓨터에 대한 내성을 확보할 수 있다. 해시 기반 양자내성암호는 해시함수와 서명 알고리즘을 결합한 형식으로 볼 수 있다. 따라서 해시함수 혹은 서명 알고리즘 상에 보안 상의 취약점이 존재하는 경우 취약점이 존재하는 부분만을 모듈 형식 (drop-in)으로 교체함으로써 보안성을 유지하는 것이 가능하다.

2011년도에 제안되어 최근에 연구가 활발히 진행되고 있는 양자내성암호는 아이소지니 기반 양자 내성 암호이다. 아이소지니 기반 양자내성암호는 Luca De Feo와 Plut Jao에 의해 제안되었으며 기반하는 수학적 난제는 Supersingular elliptic curve상에서의 연산 어려움에 기반하고 있다. 아이소지니 기반 양자 내성암호가 다른 암호에 비해 주목받고 있는 점은 오랜 기간에 걸쳐 연구가 진행된 Pairing과 타원곡선의 수학적 증명 활용이 가능하다는 점이다. 또한 다른 알고리즘과 비교 시 키와 메시지가 현재 네트워크 보안 프로토콜 상의 패킷 (SSL/TLS)에 적합한 크기를 가진다는 장점을 가지고 있다. 다만 아이소지니 기반 양자내성 암호는 연산속도가 다른 양자내성암호들에 비해 현저히 떨어지는 문제점을 가지고 있다.

NIST의 양자 내성 암호 표준화에 대한 생각

NIST에서 양자 내성 암호 표준화를 이끌고 있는 Dustin Moody는 매년 암호학회 및 NIST 워크샵에서 양자내성암호 표준화 과정에 대한 NIST의 의견을 대표하여 발표하고 있다. 아래에서는 NIST가 매년 발표한 자료를 토대로 NIST의 양자 내성 암호 표준화에 대한 생각과 앞으로의 계획에 대해 살펴보도록 한다.

PQCrypto’16에서는 “Post-Qunatum Cryptography: NIST’s Plan for the Future”라는 주제로 발표하였다. NIST에서는 약 2031년도에 1조원의 자금을 투여하면 RSA-2048에 대한 해킹이 가능할 것으로 예상하였다. 이는 특히 공개키 암호화에 지대한 영향을 미치게 된다. 양자 내성 암호 표준화에서 NIST의 역할은 양자 내성암호 표준화를 투명하고 제 시간에 수행하는 것을 목표로 한다. 제안하는 알고리즘은 전통적인 보안과 양자 내성 보안을 모두 달성해야 하며 실제 구현 결과를 제공함으로써 보안과 더불어 실용성을 고려한 양자 내성암호 후보군을 모집함을 공식화하였다.

Asiacrypt’17에서는 “The Ship has Sailed: The NIST Post-Quantum Cryptography Competition”이라는 주제로 발표하였다. NIST에서는 양자내성암호 표준화 작업을 시작하기에 앞서 해당 표준화가 시기상조인지에 대해서 내부적인 토의가 있었고 이는 결코 이르지 않음을 확인하였다. 여기에는 워터루 대학의 Michele Mosca 교수와 NSA에서 양자 내성 암호로의 전환이 곧 이루어져야함을 주장이 근거로 작용하였다. 양자내성암호 표준화에서는 전자서명, 암호화, 그리고 키 생성에 대한 알고리즘을 공모하며 보안성과 구현 효율성 관점에서 알고리즘을 분석하는 것을 목표로 한다. 해당 표준화에는 총 82개의 알고리즘이 제출되었다. 이 중에서 23개가 서명 알고리즘이며 59개가 암호화/키생성 알고리즘이다. [표 3]에는 기반 문제 별로 양자 내성 암호 알고리즘을 정리하여 나타내고 있다.

PQCrypto’18 (첫 번째 양자내성암호 표준화 워크샵)에서는 “Let’s Get Ready to Rumble-The NIST PQC Competition”이라는 주제로 발표하였다. 양자 내성 암호 공모전 제출본 82개 중 69개가 최종적으로 초기 평가를 통과하였다. 이 중에서도 5개가 제안을 철회하여 최종적으로 64개의 알고리즘이 NIST 표준화에 공식적으로 참여하게 되었다. [표 4]에는 기반 문제 별로 69개의 양자 내성 알고리즘 후보군들을 정리하여 나타내고 있다. 이와 더불어 NIST 표준화 작업에 대한 투명성을 확보하기 위해 공개된 채널을 제공하여 양자 내성 알고리즘에 대한 의견 교류가 활발히 이루어 질 수 있도록 하였다. NIST는 또한 (stateful) 해시 기반 서명의 경우 당장 양자 내성 암호를 도입해야 하는 경우 채택해도 괜찮은 암호군으로 지정하였다.

PQCrypto’19에서는 “Round 2 of the NIST PQC Competition- What was NIST Thinking?” 이라는 주제로 발표하였다. NIST는 제안된 알고리즘 중 다수에서 보안 취약점이 있음을 발견하였다. NIST 양자 내성 암호 표준화 시작 3 주만에 12개의 알고리즘에서 취약점이 발견되었으며 2018년도 4월까지 4개의 알고리즘에서 추가적인 보안 취약점이 발견되었다. NIST에서는 초기에 연산 효율성에 대해서는 크게 고려하지 않는다고 하였지만 특정 알고리즘 (PQRSA 그리고 DualModeMS)의 경우 너무나도 느린 성능을 가진다고 평가하였다. NIST 양자 내성 암호 1차 합격 알고리즘 분류는 [표 5]와 같다. 주요 특징으로는 격자 기반 암호가 가장 많은 후보군이 선정되었다는 점이다. 이와 더불어 2차 평가에서는 다수의 유사한 알고리즘들을 통합하여 하나의 암호군으로 선정하고 표준화를 진행하였다. 구현 관점에서는 Cortex-M4와 Artix-7 보드 상에서의 구현에 집중하여 성능을 비교 분석하는 것을 권장하였다.

두 번째 양자 내성 암호 표준화 워크샵에서는 Opening Remarks로 “The 2^nd Round of the NIST PQC Standardization Process”라는 주제로 발표하였다. 이전 발표와 크게 달라진 점은 없으며 양자 내성 암호의 실용적인 측면에서의 분석이 2차 공모전 결과에 크게 작용할 것이라고 언급하였다.

PQCrypto’20에서는 “NIST PQC Standardization Update – Round 2 and Beyond”라는 주제로 발표하였다. 해당 발표에서의 주된 내용은 2020년도 7월에 발표된 2차 최종후보군과 대체후보군에 대한 것이었으며 선정에 있어 큰 요인으로 작용한 것은 효율성이 아닌 보안성이었다. 선정된 알고리즘 양자내성암호 후보군은 [표 6]과 같다.

최종 후보군의 경우 3차 평가분석을 통해 양자내성암호 최종 표준화가 될 것으로 예상되는 암호군들을 의미한다. 최종 후보군에는 4개의 공개키 암호화/키교환 알고리즘 (Classic McEliece, CRYSTALS-KYBER, NTRU, 그리고 SABER)와 3개의 전자서명 알고리즘 (CRYSTALS-DILITHIUM, FALCON, 그리고 Rainbow)가 선정되었다. 대체 후보군의 경우 3차 평가분석 중에는 표준화가 되지 않는다. 다만 NIST에서도 대체 후보군들이 가지는 다양한 수학 기반을 양자 내성암호 표준안으로 고려하고 있다. 따라서 NIST에서는 대체 후보군들도 3차 평가분석을 함께 진행하며 경우에 따라서는 4차 평가분석을 통해 추가적인 표준화를 진행할 것으로 공표하였다.

세 번째 양자 내성 암호 표준화 워크샵에서는 Opening Remarks로 “NIST Status Update on the 3^rd Round”라는 주제로 발표하였다. 3차 평가 분석 중 다변수 다항식 기반 양자 내성 암호인 Rainbow와 GeMSS에 대한 보안취약성에 대한 문제가 제기되고 있음을 발표하였다. 또한 양자내성암호 서명 기법 중 SPHINCS+는 매우 보수적인 보안 강도를 지향하고 있기 때문에 표준화된 양자내성암호 서명 알고리즘에서 문제가 발생한다면 SPHINCS+를 바로 적용하는 것을 권장하였다. NIST에서는 양자 내성 암호 공모전과 별개로 일반적인 전자 서명 스킴에 대해서 공모전을 추가적으로 진행하겠다고 하였다. 이는 매우 작은 서명 크기를 가지는 스킴을 목표로 한다. 마지막으로 3차 평가 분석은 2021년도 말에는 결과를 도출할 예정이며 2022년과 2023년에는 양자내성암호 표준안에 대한 draft 작업에 들어간다고 하였다. 따라서 2024년에는 양자내성암호 표준화가 공식화되는 시점이 될 것이다.

다가올 미래

이 글을 작성하고 있는 현재 시점에서도 아이러니하게도 실용적인 성능을 달성하여 암호를 위협할 수 있는 양자 컴퓨터는 개발되지 않았다. 하지만 양자 컴퓨터 상에서 동작하는 양자 알고리즘들은 이미 활발히 연구가 진행되고 있으며 이는 암호학에 추후 지대한 영향을 미칠 것이다. 현재 암호학계에서는 그 어느때보다 선제적으로 다가올 미래가 양자알고리즘을 통한 해킹으로부터 안전할 수 있도록 연구에 매진하고 있다. NIST에서는 2021년도 하반기에 3라운드 최종 표준안을 발표한다고 하였다. 이를 시작으로 양자 내성 암호로의 전환이 보다 가속화 될 것으로 예상된다. 이와 같은 국제적인 흐름에 맞추어 국내에서도 양자 컴퓨터의 위협으로부터 안전한 IT 환경을 만들기 위해 산학연이 관심을 가지고 양자내성암호 연구 및 개발을 이어나가야 할 것으로 보인다.

[1] Arute et al. “Quantum supremacy using a programmable superconducting processor,” Nature, 574(7779), 2019, pp. 505-510.

[2] Shor, P. W. “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,” SIAM review, 41(2), 1999, pp. 303-332.

[3] Grover, L. K. “A fast quantum mechanical algorithm for database search,” In Proceedings of the twenty- eighth annual ACM symposium on Theory of computing, 1996, pp. 212-219.

본 원고는 KISA Report에서 발췌된 것으로 한국인터넷진흥원 홈페이지(https://www.kisa.or.kr/public/library/IS_List.jsp)에서도 확인하실 수 있습니다.

KISA Report에 실린 내용은 필자의 개인적 견해이므로, 한국인터넷진흥원의 공식 견해와 다를 수 있습니다.

KISA Report의 내용은 무단 전재를 금하며, 가공 또는 인용할 경우 반드시 [한국인터넷진흥원,KISA Report]라고 출처를 밝혀주시기 바랍니다.