PQC로의 여정: 양자 컴퓨터 시대에 데이터 지키기

들어가며

안녕하세요. Security R&D 팀의 한주홍입니다. 저희 팀은 LY 그룹 서비스의 전반적인 보안을 강화하기 위해 다양한 보안 기술을 연구하고 개발 및 컨설팅하는 업무를 담당하고 있습니다.

현재 우리가 사용하고 있는 많은 IT 서비스에서는 안전한 서비스를 제공하기 위해 다양한 암호 기술을 사용하고 있습니다. LY 그룹 역시 종단 간 암호화 기술인 Letter Sealing부터 간편한 사용자 인증을 위한 FIDO(Fast Identity Online), 안전한 백업 시스템 구축 등 사용자가 안심하고 서비스를 이용할 수 있도록 다양한 곳에서 암호 기술을 사용하고 있습니다.

그런데 최근 양자 컴퓨터에 관한 연구가 활발해지고 양자 컴퓨터의 개발이 점점 가시화되면서 현재 우리가 안전하다고 믿고 사용하고 있는 암호 기술들의 안전성에 문제가 발생할 수 있게 되었습니다. 이에 대비하기 위해 많은 전문가들이 PQC(Post-Quantum Cryptography)라는 분야를 연구하고 있는데요. 이번 글에서는 양자 컴퓨터의 개발이 현재의 암호 시스템에 어떤 영향을 미치는지, 그리고 양자 컴퓨터의 시대에서는 어떻게 우리의 데이터를 지킬 수 있는지 이야기해 보겠습니다.

양자 컴퓨터의 위협에 현대 암호 알고리즘은 안전할까?

양자 컴퓨팅은 기존 컴퓨터와는 완전히 다른 방식으로 데이터를 처리하는 컴퓨팅 기술입니다. 현재 우리가 사용하는 컴퓨터는 비트(bit)를 사용해 데이터를 0과 1로 표현하지만, 양자 컴퓨터는 큐비트(qubit)를 사용해 0과 1의 상태를 동시에 가질 수 있습니다. 이러한 특성 덕분에 양자 컴퓨터는 기존 컴퓨터보다 특정 계산을 훨씬 빠르게 처리할 수 있습니다.

양자 컴퓨팅의 핵심 개념은 중첩(superposition)과 얽힘(entanglement)입니다. 중첩 상태의 큐비트는 0과 1의 상태를 동시에 가질 수 있어서 병렬 연산을 수행하는 것과 유사한 효과를 낼 수 있습니다. 또한 얽힌 큐비트들은 서로의 상태에 강하게 의존하는데 이때 한 큐비트의 상태가 결정되면 다른 큐비트의 상태도 즉시 결정됩니다. 양자 컴퓨팅의 이와 같은 특성은 양자 컴퓨터가 소인수 분해와 같은 특정 문제들을 매우 빠르게 해결할 수 있게 만듭니다.

2023년에 evolutionQ의 Michele Mosca와 Marco Piani 박사가 Global Risk Institute 라이선스로 발행한 QUANTUM THREAT TIMELINE REPORT 2023 보고서에 따르면, '키의 크기가 2048비트인 RSA 암호를 한 시간 안에 깰 수 있는 양자 컴퓨터'가 나올 가능성을 전문가들의 약 27%가 10년 이내 50% 이상으로 예측했고, 기간을 30년으로 늘리면 약 78%의 전문가가 70% 이상으로 예측했다고 합니다.

이처럼 양자 컴퓨터의 발전이 아직 초기 단계이긴 하지만 많은 전문가들은 수백 개 또는 수천 개의 큐비트를 다룰 수 있는 양자 컴퓨터의 개발이 멀지 않았다고 보고 있습니다. 이는 현재 양자 컴퓨터의 개발을 주도하고 있는 IBM의 양자 컴퓨터 개발 로드맵을 통해서도 예측해 볼 수 있는데요. 최근 IBM이 발표한 Heron 프로세서는 133개의 큐비트를 안정적으로 다룰 수 있으면서도 모듈형 구성을 통해 유연하게 확장할 수 있는 설계를 갖추고 있습니다. 현재는 세 개의 프로세서로 399큐비트까지 확장하는 것이 한계이지만, 2033년 이후에는 프로세서당 2000큐비트까지 다루는 것을 목표로 하고 있기 때문에 이를 모듈식으로 구성한다면 정말로 수천, 수만 개의 큐비트를 사용할 수 있게 될지도 모릅니다.

그렇다면 미래에 수만 개의 큐비트를 다룰 수 있는 양자 컴퓨터가 개발된다면 현대 암호 시스템에는 어떤 영향을 미칠까요?

대칭 키 암호와 해시 함수

대칭 키 암호는 데이터를 암호화하고 복호화할 때 동일한 키를 사용하는 알고리즘입니다. 일반적으로 빠르고 효율적이며, 큰 데이터 블록을 처리하는 데 적합합니다. 이런 장점 때문에 일반적인 데이터 암호화에는 대부분 대칭 키 암호를 사용한다고 생각하시면 됩니다.

대칭 키 암호는 일반적으로 키 길이에 따라 안전성이 결정됩니다. 즉, 128비트 키를 사용하는 알고리즘은 보안 강도가 128비트입니다. 여기서 보안 강도란 해당 암호의 키를 찾는 데 필요한 연산량을 의미합니다. 예를 들어 128비트 보안 강도라는 것은 암호 키를 찾기 위해 $2^{128}$ 번의 연산이 필요하다는 것을 의미합니다. $2^{128}$ 번의 연산은 현재의 컴퓨팅 능력으로는 약 10조년 이상 걸리기 때문에 현실적인 시간 안에서는 풀 수 없습니다.

하지만 이러한 대칭 키 암호는 Grover 알고리즘으로 무력화할 수 있습니다. Grover 알고리즘은 양자 컴퓨터에서 작동하는 양자 알고리즘으로, 비선형 검색 문제를 해결하는 데 드는 $O(N)$ 시간을 에서 $O(\sqrt{N})$ 으로 크게 줄일 수 있어 대칭 키 암호와 해시 함수의 안전성에 큰 영향을 미칩니다.

예를 들어, Grover 알고리즘을 사용해 대칭 키 암호를 공격하면 보안 강도가 반으로 줄어 128비트 대칭 키 암호화 알고리즘의 보안 강도가 64비트가 됩니다. 이는 10조년 이상 걸리던 공격 시간이 6개월 정도로 단축되는 결과를 가져옵니다.

해시 함수도 상황은 비슷합니다. 해시 함수는 데이터를 랜덤한 비트 열로 보이는 고유한 고정 길이의 출력값으로 변환하는 함수입니다. 해시 함수는 입력값이 한 비트만 달라도 전혀 다른 출력값을 만들기 때문에 주로 데이터의 무결성 검사에 사용하며, 위조 역시 굉장히 어렵습니다.

이러한 해시 함수는 일반적으로 $N$ 비트 해시의 경우 역상(해시값에 대응하는 원본 데이터)을 찾는 문제는 $2^N$ 번의 연산이, 충돌쌍(해시값이 같은 서로 다른 입력 데이터)을 찾는 문제는 $2^{\frac{N}{2}}$ 번의 연산으로 풀 수 있다고 알려져 있는데요. Grover 알고리즘을 사용하면 각각 $2^{\frac{N}{2}}$ , $2^{\frac{N}{3}}$ 번의 연산만으로도 풀 수 있습니다.

비대칭 키 암호

비대칭 키 암호(공개 키 암호)는 데이터 암/복호화와 서명 생성/검증 시에 서로 다른 키를 사용하는 알고리즘입니다. 하나의 키는 공개키로 누구나 접근할 수 있지만 다른 하나의 키는 비밀키로 소유자만 접근할 수 있습니다. 비대칭 키 암호는 주로 키 교환, 전자 서명, 인증 등의 용도로 사용하는데요. 대표적인 비대칭 키 암호 알고리즘에는 IFC 계열(Integer Factorization Cryptography)의 RSA(Rivest-Shamir-Adleman)와 ECC(Elliptic Curve Cryptography) 계열의 ECDSA(Elliptic Curve Digital Signature Algorithm), ECDH(Elliptic-curve Diffie–Hellman)가 있습니다.

현대의 공개 키 암호 알고리즘의 안전성은 대칭 키 암호와 해시 함수와는 달리 수학적으로 해결하기 어려운 문제에 기반합니다. 따라서 해당 수학적 문제를 해결할 수 있는 효율적인 알고리즘이 존재하지 않는다는 가정 하에 안전성이 보장됩니다.

하지만 이러한 비대칭 키 암호는 Shor 알고리즘으로 무력화할 수 있습니다. Shor 알고리즘은 양자 컴퓨터에서 작동하는 양자 알고리즘으로, RSA와 ECC 계열 암호의 기반 문제들을 짧은 시간 안에 해결할 수 있습니다. 예를 들어 큰 수를 소인수분해기 어렵다는 점을 이용해 설계한 RSA 알고리즘의 경우 현재 컴퓨터로는 2048비트의 키를 소인수분해하는 데 수조 년이 걸리지만, Shor 알고리즘을 사용하면 이 작업을 매우 짧은 시간(약 2천만 큐비트의 양자 컴퓨터로 약 8시간(참고)) 안에 해결할 수 있습니다.

양자 컴퓨터의 위협에 대비하는 방법

대칭 키 암호화와 비대칭 키 암호화는 금융을 비롯한 IT 시스템 전반에 걸쳐 광범위하게 사용되고 있고, 데이터 보호의 핵심 요소로 자리 잡고 있기 때문에 보안 위협에 대비하는 것이 매우 중요한데요. 그렇다면 이와 같은 양자 알고리즘으로부터 우리의 데이터를 어떻게 지킬 수 있을지 살펴보겠습니다. 아래는 각 암호화 방법별로 위협이 되는 양자 알고리즘과 그에 대한 대응 방안을 정리한 표입니다.

분류	양자 알고리즘	대응 방법	대응 전	대응 후
대칭 키 암호	Grover 알고리즘	키 길이 증가	128, 192, 256	256 이상
해시 함수	Grover 알고리즘	출력 길이 증가	224, 256, 384, 512	384, 512 이상
비대칭 키 암호	Shor 알고리즘	알고리즘 교체	IFC, ECC, FFC	Lattice, Code, Isogeny, Hash, Multivariate

다행히 대칭 키 암호에서의 대응 방법은 그리 어렵지 않습니다. 현재의 대칭 키 암호 알고리즘들은 대부분 256비트의 키까지 지원하기 때문에 128비트 또는 192비트의 키를 사용하는 시스템에서는 256비트로 키 길이를 늘리고, 해시 함수는 출력 길이가 더 긴 알고리즘으로 교체해서 128비트 이상의 보안 강도를 유지하면 됩니다. 물론 이미 배포된 시스템의 알고리즘을 교체하는 것이 쉽지 않을 수는 있지만, 이미 안전성이 충분히 증명된 알고리즘들이 있기 때문에 알고리즘을 새로 개발할 필요는 없습니다.

그러나 비대칭 키 암호는 대칭 키 암호나 해시 함수처럼 기존 알고리즘을 재사용하는 것으로는 대비할 수 없습니다. 알고리즘 설계에 사용된 기반 문제가 깨지는 것이기에 양자 알고리즘으로도 해결하기 어려운 새로운 기반 문제를 사용한 알고리즘을 만들어야 합니다. 이에 따라 현재 많은 전문가들이 이에 대비할 수 있는 PQC(Post-Quantum Cryptography)를 연구하고 있습니다.

PQC 표준화 및 전환

CRQC(Cryptographically Relevant Quantum Computer)는 NSA(National Security Agency, 미국 국가 안보국)에서 실제 암호화 시스템을 공격할 수 있는 양자 컴퓨터를 지칭할 때 사용하는 용어인데요. PQC는 CRQC의 공격에도 안전한 알고리즘을 의미하며, 그래서 양자 내성 암호(Quantum-Resistant Cryptography)라고 부르기도 합니다. 따라서 PQC의 범주에는 키 길이가 늘어난 대칭 키 암호와 출력 길이가 늘어난 해시 함수까지 포함될 수 있는데요. 일반적으로는 기존 환경과 양자 환경 모두에서 해결하기 어려운 수학적 문제를 기반으로 만들어 기존 공개 키 암호 알고리즘을 대체할 수 있는 알고리즘만을 PQC로 지칭하는 경우가 많습니다.

PQC 알고리즘 표준화 현황

2017년 미국 국립 표준 기술 연구소(National Institute of Standards and Technology, NIST)는 CRQC의 공격에도 안전한 암호 알고리즘을 표준화하는 목적으로 PQC 공모전을 시작했습니다. 이에 따라 전 세계의 전문가들이 다양한 수학에 기반한 알고리즘들을 제출했는데요. 해당 알고리즘들은 안전성 외에도 기존 컴퓨팅 환경에서의 성능, 교체 용이성, 완전 순방향 비밀성, 부채널 공격에 대한 내성, 오용에 대한 내성 등의 다양한 지표로 평가되었습니다.

PQC 공모전에는 총 69개의 알고리즘이 제출됐고, 여러 해에 걸친 평가 과정에서 많은 알고리즘이 탈락했습니다. 총 세 번의 라운드 끝에 2022년 7월에 다음 네 개 알고리즘이 최종 표준화 대상으로 선정됐습니다. 2024년에 최종적으로 연방 정보 처리 표준(Federal Information Processing Standard, FIPS)으로 승인되었습니다.

CRYSTALS-Kyber(ML-KEM): 격자 기반 비대칭 암호화 및 키 교환 알고리즘
CRYSTALS-Dilithium(ML-DSA): 격자 기반 전자 서명 알고리즘
FALCON(FN-DSA): 격자 기반 전자 서명 알고리즘
SPHINCS+(SLH-DSA) : 해시 기반 서명 알고리즘

그런데 선정된 알고리즘에서 KEM 알고리즘은 격자 기반의 알고리즘 단 하나였기에 NIST는 격자 기반 암호의 안전성에 문제가 생겼을 때를 대비하기 위해 다른 기반으로 만든 KEM 알고리즘들(BIKE, Classic McElliece, HQC, SIKE)을 후보로 네 번째 라운드를 진행하고 있습니다. 또한 4라운드에는 전자 서명 알고리즘이 포함되지 않았기에 전자 서명 알고리즘을 대상으로 한 추가 라운드를 진행하고 있습니다.

위협 모델과 전환 시점

많은 전문가들은 지금부터 PQC로의 전환을 준비해야 한다고 말하고 있습니다. 아직 CRQC 개발이 멀었기 때문에 이 글을 읽는 누군가는 왜 벌써 PQC를 연구하고 마이그레이션을 준비해야 하는지 의문이 들 수 있는데요. 그 근거는 HNDL 공격과 Mosca 정리로 설명할 수 있습니다.

HNDL(Harvest Now, Decrypt Later) 공격이란 현재 데이터를 수집해 저장해 뒀다가 나중에 CRQC를 이용한 공격이 가능한 시점이 왔을 때 복호화하는 공격을 말합니다. 이런 공격은 오랜 기간 보안을 유지해야 하는 민감한 데이터나 펌웨어 및 소프트웨어 등에 사용되는 서명처럼 수명이 긴 데이터에 영향을 미칠 수 있습니다. 따라서 아직 실제로 양자 공격이 가능하지 않더라도 사전에 이에 대비할 수 있는 암호 알고리즘을 개발하고 배포해야 할 필요가 있는 것입니다.

그렇다면 PQC로의 전환은 언제 시작해야 할까요? 우리는 Mosca 정리를 통해 대략적인 시점을 계산해 볼 수 있는데요. 이 이론은 세 가지 주요 변수를 고려하고 있습니다.

$x$ : 현재 사용하는 암호 알고리즘의 보안성이 유지되어야 하는 시간
$y$ : PQC 알고리즘을 설계, 표준화, 배포, 마이그레이션하는 데 걸리는 시간
$z$ : 양자 컴퓨터가 충분히 강력해져 현재의 암호 알고리즘을 깨뜨릴 수 있는 시점까지 남은 시간

우리가 CRQC의 위협에서 안전해지려면 다음 수식을 만족시켜야 합니다.

$x + y < z$

즉, PQC 알고리즘의 개발 및 마이그레이션( $x$ )에 걸리는 시간과 현재 사용하는 암호화 알고리즘의 유효 기간( $y$ )의 합이 CRQC가 개발되기까지의 시간( $z$ )보다 짧아야 합니다.

현재 많은 전문가들은 최근 과학 기술의 발전 속도가 매우 빠르기 때문에 양자 컴퓨터의 개발 속도를 보수적으로 잡아도 CRQC의 개발 시점이 대략 2030년 정도라고 예상하고 있습니다. 이 예상대로라면 PQC 알고리즘의 본격적인 연구 시점을 기준으로 $z$ 는 대략 20년 정도로 생각할 수 있습니다.

그러면, $y$ 에 해당하는 마이그레이션에 걸리는 시간은 어떨까요?

IT 환경에서의 마이그레이션 작업은 운영 환경에 따라 고려해야 할 요소들이 다르고, 다음 배포 시까지 수년이 걸리는 환경도 존재하기 때문에 생각보다 많은 시간이 필요합니다. 이는 과거에 진행됐던 다른 전환 사례들을 통해서 확인해 볼 수 있는데요. SHA2와 AES의 경우 표준화 이후 대부분의 시스템에 적용되기까지 대략 10년 가량 걸렸고, TLS역시 TLS 1.2로 전환하는 데 대략 10년 이상 걸렸습니다.

망치가 꽂힌 시기는 각 알고리즘에 대한 실질적인 공격이 성공했던 시기입니다.

PQC 전환 과정은 기존 마이그레이션 작업들과는 달리 더 복잡하고 광범위한 작업이 될 것으로 예상되기에, 우리는 마이그레이션에 걸리는 시간 $y$ 를 최소 10년 이상으로 생각해 볼 수 있습니다. 따라서 위 가정을 토대로 우리는 지금부터 마이그레이션을 준비할 필요가 있음을 알 수 있습니다.

실제로 국가별 PQC 전환을 위한 로드맵에도 이런 가정들이 반영된 것을 확인할 수 있습니다. 미국의 NSA는 PQC 알고리즘들이 포함된 CNSA 2.0(Commercial National Security Algorithm Suite 2.0)을 발표했는데 이때 발표된 로드맵에 따르면 대부분의 분야에서 2024년부터 준비를 시작해 2033년까지 전환하는 것을 목표로 하고 있습니다. 이 로드맵에 맞춰 백악관(참고) 및 주요 기관들은 새로운 정책과 규정을 발표하고 있고, 독일의 BSI(참고), 영국의 NCSC(참고), 프랑스의 ANSSI(참고), 캐나다의 CSE(참고)에서도 각각 PQC 전환을 위한 로드맵과 공공 및 민간을 위한 가이드라인을 발표하고 있습니다.

출처: Announcing the Commercial National Security Algorithm Suite 2.0

PQC 전환을 준비하는 방법: 하이브리드 모드

그렇다면 우리는 어떻게 PQC 전환을 준비해야 할까요? PQC 전환 과정에 대해서는 전문가들의 다양한 견해가 있지만 현재로서는 하이브리드 모드를 사용한 단계적 전환이 많이 채택되고 있습니다[참고 자료: 1, 2, 3, 4, 5, 6].

하이브리드 모드는 기존의 비대칭 키 암호 알고리즘과 PQC 알고리즘을 동시에 사용하는 방식인데요. 전문가들이 PQC 단독이 아닌 하이브리드 모드를 채택하는 가장 큰 이유는 현재 제안된 여러 PQC 알고리즘에 알려지지 않은 취약점이 있을 가능성에 대비하기 위해서입니다. 현재 제안된 PQC 알고리즘들은 연구를 시작한 지 그리 오래되지 않은 상대적으로 새로운 기술로, 이론적인 결함과 현재 시스템에서는 아직 발견되지 않은 취약점이 존재할 가능성이 있습니다. 따라서 PQC 전환 중에 새로운 취약점이 발견되더라도 여전히 기존 암호 알고리즘을 통해 보호받을 수 있도록 하이브리드 구조를 선택하는 것입니다. 하이브리드 모드를 선택하면 PQC 알고리즘이 완전히 검증되고 안정화될 때까지 점진적으로 전환할 수 있고, 새로운 취약점이 발견되더라도 기존 암호 알고리즘이 헤지(hedge) 역할을 하기 때문에 보안 리스크를 최소화할 수 있습니다.

실제로 NIST PQC 공모전에 제출돼 3라운드 최종 후보에 올랐던 알고리즘인 Rainbow는 새로운 키 복구 공격이 발표돼 공모전에서 탈락했고(참고), 과거에 Google Chrome에 실험적으로 적용됐던 SIKE 알고리즘에서 취약점이 발견됐는데(참고) 하이브리드 구조를 채택한 덕분에 보안 사고로 이어지지는 않았던 사례도 있습니다.

이외에도 하이브리드 모드는 기존 사양에 PQC 알고리즘을 추가하는 형태로 구성할 수 있어서 비교적 쉽게 기존 제품의 프로토콜에서의 가용성 및 여러 규제 요건을 만족시킬 수 있는 장점이 있어 현시점에서 전환을 준비하는 가장 효과적인 방법으로 평가되고 채택되고 있습니다.

물론 하이브리드 모드에도 리스크는 존재합니다. 하이브리드 구조는 두 가지 암호를 동시에 사용하기 때문에 설계와 구현이 복잡해질 뿐 아니라, 상호 운용성 문제와 키 관리가 복잡해지는 등의 추가 문제가 발생해 예상치 못한 보안 취약점이 생길 수도 있습니다. 또한 하이브리드 구조는 임시 해결책이기 때문에 PQC에 대한 안전성이 충분히 검증된 이후에는 결국 PQC 단일 구조로 전환해야 하는데요. 과거 AES와 SHA-2 등의 사례에서도 볼 수 있듯 이런 전환 과정은 많은 비용과 시간이 소요되는 복잡한 작업입니다. 따라서 하이브리드 모드는 현재의 보안 시스템을 유지하면서도 양자 컴퓨터의 위협에 대비할 수 있는 중요한 전략이긴 하지만, 장기적인 해결책은 아니라는 점을 명심해야 합니다.

마치며

이번 글에서는 양자 컴퓨터의 등장이 어떻게 현대 암호 시스템의 안전성을 위협하는지 살펴보고 그 상황에 대비해야 하는 이유와 방법을 알아봤습니다. 앞서 말씀드렸듯 대칭 키 암호와 해시 함수의 경우 비교적 간단히 해결할 수 있지만, 비대칭 키 암호의 경우 새로운 알고리즘을 개발하고 적용하는 데 많은 시간이 필요합니다. 따라서 우리는 하이브리드 모드와 같은 임시적인 해결책을 통해 비대칭 키 암호의 전환 과정을 단계적으로 준비해야 합니다.

각국의 정부와 보안 기관에서 발표한 PQC 전환 로드맵을 통해 볼 수 있듯, 앞으로의 10년, 20년은 PQC로의 전환을 준비하고 실행하는 중요한 시기가 될 것입니다. 양자 컴퓨터와 PQC에 대한 연구는 꾸준히 진행되고 있고 앞으로 많은 변화와 발전이 예상되므로, 미래에도 우리의 데이터를 지키기 위해서는 이러한 변화에 빠르게 적응해야 할 것입니다.

이번 글이 양자 컴퓨터 시대의 암호 기술과 보안에 대한 이해를 높이는 데 도움이 되었기를 바랍니다. 다음 글에서는 LY 그룹에서 PQC 전환을 위해 어떤 노력을 기울이고 있는지 다룰 예정이니, 많은 관심 부탁드리며 이만 마치겠습니다. 긴 글 읽어주셔서 감사합니다.