양자컴퓨팅으로 더 커지는 보안 위협, 지금이 바로 PQC 전환을 시작할 때!

2023-03-15 조지훈, 윤효진, 김은경

양자 컴퓨팅으로 더 커지는 보안 위협, 지금이 바로 PQC 전환을 시작할 때!

1. 양자 컴퓨터와 PQC

누구나 한 번쯤 인터넷을 사용하다 ‘암호화되지 않은 연결을 사용하고 있는 사이트’라는 경고 문구를 만난 적이 있을 텐데요, 나의 개인 정보가 공격자에게 노출될 수 있다는 경고 문구가 신경 쓰이지만 당장 급한 마음에 경고문구를 무시하고 연결을 선택한 적이 있으신가요? 여기서 ‘암호화되지 않은 연결’은 어떤 의미일까요? 반대로, ‘암호화된 연결’은 어떤 차이가 있는 걸까요?

사용자가 인터넷 브라우저를 통해 웹사이트 접속을 클릭하면, 웹사이트에 포함된 수많은 데이터(텍스트, 이미지, 동영상 등)를 내려받아 브라우저에 해당 정보들이 표시됩니다. 사용자는 웹사이트에 텍스트 정보를 입력하거나 이미지, 동영상 파일을 업로드 하는 등 인터넷을 통해 수많은 데이터 주고받게 됩니다. 여기서, ‘암호화되지 않은 연결’을 이용하는 경우, 사용자와 웹사이트가 주고받는 데이터는 말 그대로 암호화되지 않기 때문에 제3자가 네트워크 패킷 분석 프로그램 등을 통해 주고받는 데이터를 들여다볼 수 있습니다. 신용카드 비밀번호나 메신저앱을 통해 공유한 생명보험 가입 서류와 같은 중요 데이터도 예외 없이 조회 가능하다는 뜻입니다.

이와 달리 ‘암호화된 연결’에서는 사용자와 웹사이트 간에 주고받는 데이터가 대칭 키 암호 알고리즘을 이용해 안전하게 암호화하여 전송되기 때문에 제3자가 원본 데이터를 조회하거나 위/변조할 수 없습니다. ‘암호화된 연결’을 위해 사용자와 웹사이트는 데이터를 주고받기 전, 데이터 암/복호화에 사용할 공통 비밀 키를 설정하게 되는데요, 이때 공개 키 암호 알고리즘을 이용하게 됩니다--본 기고에서는 강조한 분야 이외에도 다양한 곳에서 중요 데이터와 네트워크 통신을 보호하기 위해 공개 키 암호가 사용되고 있습니다--. 예를 들어, 전송계층보안 (Transport Layer Security, TLS) 프로토콜이 적용된 HTTPS 통신에서는 RSA 암호, 타원곡선 Diffie-Hellman (Elliptic Curve Diffie-Hellman, ECDH) 등의 공개 키 암호 알고리즘을 이용한 키 교환 방식이 사용되고 있습니다.

RSA 암호와 타원곡선암호 알고리즘의 안전성은 소인수분해 문제와 이산대수 문제라고 하는 수학적으로 아주 어려운 문제에 그 기반을 두고 있습니다. 간단히 말해, 공개 키 암호 알고리즘을 해독하는 비밀 키를 빠르게 찾아낼 수 있는 프로그램이 있다면, 소인수분해 문제나 이산대수 문제도 빠르게 답을 찾는 프로그램을 만들 수 있다는 건데요, 이는 우리가 현재 사용하는 컴퓨터로는 불가능하다고 알려져 있습니다. 우리가 현재 사용하는 0과 1의 비트 연산 기반 컴퓨터에서 이 문제들을 푸는 시간은 입력값이 커짐에 따라 아주 빠르게 증가합니다. 예를 들어, 15가 두 소수 3과 5의 곱이라는 것은 누구나 금방 찾을 수 있지만 111,901을 머릿속에서 암산으로 소인수분해 하는 것은 거의 불가능합니다. 물론 눈 깜짝할 새에 111,901을 317*353으로 소인수분해 하는 컴퓨터 프로그램을 작성하는 것은 아주 쉽습니다. 그러나 강력한 RSA-2048 암호에 쓰이는 600자리도 훨씬 넘는 아주 큰 수를 소인수분해 하는 것은 아무리 빠른 컴퓨터라도 아주 오랜 시간이 걸린다는 것이죠. 그래서 우리는 문제풀이 시간이 충분히 오래 걸리는 큰 수를 이용함으로써 공개 키 암호의 안전성을 보장하게 됩니다. 여기서 안전성을 보장한다는 것은 0과 1의 비트 연산 기반의 컴퓨터로는 공격이 어렵다는 뜻입니다. 그렇다면 0과 1의 비트 연산을 기반으로 하지 않고, 다른 원리로 동작하는 컴퓨터가 있다면 소인수분해 문제 기반의 공개 키 암호를 공격할 수 있을까요?

양자 컴퓨터와 공개 키 암호 시스템

영화를 좋아하시는 분들이라면 양자 세계나 양자 컴퓨터에 대해 한 번쯤 들어보셨을 텐데요, 공상과학영화에서나 존재할 법한 양자 컴퓨터가 실제로 발명된다면 소인수분해 문제나 이산대수 문제에 기반한 현재의 공개 키 암호 시스템은 완전히 붕괴될 것입니다. 이 문제들을 빠른 시간 안에 해결하는 양자 알고리즘이 알려져 있기 때문인데요, 대표적으로 1994년 미국의 수학자 피터 쇼어 (Peter Shor)가 발표한 쇼어 알고리즘 (Shor’s algorithm)이 있습니다. 쇼어 알고리즘이 발표된 당시에만 하더라도 암호 전문가들조차 실제 양자 컴퓨터의 발명은 아주 오래 걸릴 것이라고 생각하였습니다. 당시에는 0과 1비트를 처리하는 컴퓨터조차 본격적으로 일반에 확산되기 시작하던 시기였기 때문에 수백 자릿수나 되는 큰 수를 소인수분해 하는 양자 컴퓨터를 상상하기는 어려웠을 것입니다. 그러나, 컴퓨팅 기술이 눈부신 속도로 발전함에 따라 양자 알고리즘을 실행할 수 있는 양자 프로세서 개발이 가시화되고 있고, 이에 따라 공개 키 암호 시스템에 대한 양자 컴퓨터의 위협 역시 현실이 되고 있습니다. 양자 컴퓨터가 개발되는 시점을 Y2K에 빗대어 Y2Q (Years To Quantum)라고 부르기도 하는데요, Y2Q까지 우리에게 허락된 시간이 얼마나 남아있는지에 대해서도 이야기해보고자 합니다.

양자 컴퓨터 개발 전망

산업계에서 양자 컴퓨터 개발 및 상용화를 위해 어떤 노력을 하고 있는지를 설명하기위해서는 IBM을 빼놓을 수 없습니다. 최근 IBM에서는 2025년까지 4000 큐비트* 이상을 처리할 수 있는 양자 프로세서를 개발하고, 2026년까지 수만 큐비트를 처리하는 양자 프로세서를 개발하는 계획을 발표하였습니다 [그림 1]. 여기서 이야기하는 큐비트 수는 물리적 큐비트 수로, 양자 알고리즘을 기술할 때 쓰이는 논리적 큐비트와는 차이가 있으나, 2030년까지는 RSA-2048를 공격하는 데 사용되는 양자 프로세서를 개발할 것으로 기대하고 있습니다.
* 큐비트 (Qubit) : 양자 컴퓨터의 기본 처리 단위

[그림 1] IBM의 양자 프로세서 개발 로드맵

한편, 캐나다 Global Risk Institute에서 지난 12월 발간한 ‘2022 Quantum Threat Time Report’에서는 전문가들을 대상으로 24시간 이내에 RSA-2048을 무력화할 수 있는 양자 컴퓨터가 언제 개발될 것으로 예상하는지 설문조사 [그림 2]를 실시하였습니다. 대부분의 전문가들이 향후 5년 안에 현실적인 위협이 되는 양자 컴퓨터가 출현할 확률은 거의 없을 것으로 예상하고 있으나, 향후 15년 내에는 과반수 이상이 50% 이상의 확률로 양자 컴퓨터가 현실적인 위협이 될 것으로 예상하고 있습니다. 이와 같이 공개 키 암호에 대한 공격이 가시화된다는 이야기는 곧 대비책을 마련해야 한다는 이야기로 이해할 수 있습니다.

[그림 2] 24시간 이내에 RSA-2048을 무력화하는 양자 컴퓨터 출현 예상시기와 확률
(출처: Global Risk Institute)

양자내성암호 PQC (Post-Quantum Cryptography)

앞에서 ‘암호화되지 않은 연결’의 경우 통신 당사자 간에 주고받는 데이터를 제3자가 쉽게 조회하거나 위/변조할 수 있기 때문에, 안전한 통신을 위해서는 공개 키 암호알고리즘을 이용해 데이터 암/복호화에 사용할 공통 비밀 키를 설정하는 ‘암호화된 연결’을 사용해야 한다고 설명하였습니다. 이때 소인수분해 문제 또는 이산대수 문제를 기반으로 하는 공개 키 암호 알고리즘을 사용해 공통 비밀 키를 설정하면 양자 컴퓨터의 위협으로부터 안전하지 않습니다. 즉, ‘암호화되지 않은 연결’을 사용하는 것과 마찬가지로 제3자가 통신 당사자 간에 주고받는 데이터를 조회할 수 있다는 의미입니다. 따라서 ‘암호화된 연결’을 통해 안전하게 통신하려면 양자 컴퓨터 위협으로부터 안전할 것으로 기대되는 알고리즘을 이용해 공통 비밀 키를 설정해야 합니다. 이러한 알고리즘을 주로 양자내성 알고리즘 (Quantum-resistant Cryptography) 또는 포스트 양자 암호, PQC (Post-Quantum Cryptography)라고 부릅니다.

미국 국립표준기술연구소 (National Institute of Standards and Technology, NIST)에서는 PQC 알고리즘 표준화를 위해 2017년 11월, 1차 제출을 시작으로 표준 알고리즘 공모를 진행 중이며, 2023년까지 초안 표준 완료를 목표로 하고 있습니다. 현재까지 키 교환 알고리즘(Key Encapsulation Mechanism, KEM) 알고리즘 1종과 전자서명 (Digital Signature) 알고리즘 5종^[1]을 표준 알고리즘으로 선정하였고 [표 1], 추가로 키 교환 알고리즘 3종^[2]을 평가 중에 있으며 전자서명 표준 알고리즘 추가 공모도 함께 진행하고 있습니다. 국내에서도 한국 양자내성암호연구단에서 PQC 알고리즘 표준화^[3]를 진행하고 있는데요, 그렇다면 우리는 언제부터 PQC 표준 알고리즘으로의 전환 (PQC Migration)을 시작해야 할까요? PQC 표준 알고리즘이 선정된 직후일까요? 아니면 현재 사용 중인 공개 키 암호 알고리즘을 실제 공격 가능한 양자 컴퓨터가 개발된 직후일까요?

[표 1] Stateful Hash 기반 전자서명 포함 NIST 선정 PQC 표준 알고리즘 (~'22.7월)

2. 양자 위협, 유효기간 그리고 PQC Migration

Mosca의 정리: x+y > z?

앞 장에 이어 양자 취약 공개 키 암호 알고리즘을 PQC 알고리즘으로 전환해야 하는 시점에 대해 계속 생각해보겠습니다. PQC Migration을 위해서는 당연하게도 대상이 되는 정보시스템 (Information System)을 이야기해야 할 텐데요, 기업에서 사용되는 인사관리 시스템이나 구매 및 계약 처리 시스템부터 개인 간 자산 거래를 위한 증권거래 시스템, 병원의 환자정보 관리 시스템 등 우리는 생활 속에서 수많은 정보시스템을 이용하고 있습니다. 이러한 시스템들은 개인 또는 기업, 정부기관 등의 민감한 데이터를 다루는 경우 데이터 보호 규제를 준수하기 위해 공개 키 암호는 물론 데이터 암호화를 위한 대칭 키 암호 등 다양한 암호 알고리즘을 적용하고 있습니다. 시스템별로 다루는 데이터의 종류나 포맷이 다른 것은 물론이고, 적용된 암호의 종류나 적용 방식은 모두 상이합니다. 따라서, PQC Migration의 시급성은 대상 시스템과 데이터의 특성에 따라 판단할 수 있습니다.

Michele Mosca는 “Cybersecurity in an era with quantum computers: will we be ready? (2015)”에서 PQC Migration의 시급성을 결정하는 데 영향을 미치는 요인들과 이들 간의 상관관계를 간략하게 설명하였습니다 (Mosca의 정리). [그림 3]에서 Mosca의 정리를 도식화하고 있습니다.

[그림 3] Mosca의 정리 도식화

• x: Shelf-life Time
• y: Migration Time
• z: Threat Timeline

x는 정보시스템에서 다루는 데이터가 보호되어야 하는 유효기간을 나타내고 있으며, y는 대상 시스템에 양자 취약 암호 대신 PQC 암호를 적용하는 데 소요되는 Migration Time을 나타냅니다. 마지막으로 z는 양자 취약 암호가 적용된 정보시스템의 안전성이 훼손되는 시간을 나타냅니다. 물론, 데이터의 유효기간 x가 양자 위협 타임라인 z보다 큰 경우, y와 관계없이 이미 대상 시스템은 안전하지 않은 것으로 간주할 수 있습니다. 자세한 내용은 뒤에서 Harvest Now, Decrypt Later 공격과 함께 다시 한번 설명하겠습니다. 그렇다면, x가 z보다 작은 경우에는 안심할 수 있을까요? Mosca의 정리에서는 x, z와 함께 y를 강조하고 있습니다. PQC Migration 이후의 데이터 유효기간을 고려해야 하므로, x+y와 z를 비교하여 필요한 경우 PQC Migration을 서둘러야 한다고 지적하였습니다. 여기서, x는 주로 비즈니스 결정사항이나 관련 법규 및 규제에 의해 결정되는 경우가 많으며, z는 양자 컴퓨터 개발의 발전 속도와 관련이 있는 등 x와 z는 대상 시스템의 외부요인과 관련이 있습니다. 이와 달리, y의 경우 대상 시스템의 아키텍처의 복잡성, 적용된 알고리즘 종수 등 시스템의 내부요인과 관련이 높다고 할 수 있습니다.

따라서, 본 기고문의 주제와 관련 깊은 PQC Migration은 언제 시작해야 하는가에 답을 하기 위해서는 x와 z 관련 동향과 함께 y를 결정하기 위한 PQC Migration 대상 시스템에 대한 분석이 중요합니다.

Harvest Now, Decrypt Later 공격

1장에서 IBM의 로드맵과 전문가들이 생각하는 양자 위협 타임라인을 긍정적으로 바라보더라도 당장 10년 이내에 PQC Migration을 시작해야 할 시급성이 높지 않아 보이기도 합니다. 그러나 많은 전문가들은 양자 컴퓨터 위협은 이미 시작되었음을 지적하고 있습니다. 데이터의 중요도에 따라 x값이 아주 긴 경우나, 양자 컴퓨팅 관련 기술의 발전으로 z값이 갑자기 짧아지는 경우를 생각할 수 있습니다. [그림 4]에서는 실제로 x가 z보다 짧을 경우 생각할 수 있는 Harvest Now, Decrypt Later (HNDL) 공격 시나리오를 설명하고 있습니다.

[그림 4] Harvest Now, Decrypt Later 공격 (출처: CFDIR)

‘암호화된 통신’을 통해 전달되는 데이터는 다양합니다. 그중에는 시간이 지남에 따라 중요도가 떨어지는 데이터도 있을 것이고, 개인이나 기업, 국가의 일급비밀을 포함하고 있어 10년, 20년 비교적 긴 시간 동안 기밀성을 유지해야 하는 데이터도 있을 것입니다. [그림 4]의 HNDL 공격에서, 예를 들어 향후 11년 동안 안전하게 보호해야 할 데이터 (x = 11년)를 통신 당사자 간 암호화하여 주고받는 경우를 가정해 봅시다. 통신 당사자들은 타원곡선암호 등 공개 키 암호 알고리즘을 이용해 데이터 암/복호화에 사용할 공통 비밀 키를 설정한 후, 설정된 공통 비밀 키를 이용해 데이터를 암호화한 후 주고받게 됩니다. 이때, 공통 비밀 키를 모르는 공격자는 원본 데이터를 조회할 수는 없지만 공개된 네트워크를 통해 전송되는 공통 비밀 키 설정 메시지와 암호화된 데이터를 수집할 수 있습니다 (Harvest Now). 공격자가 저장한 암호화된 데이터의 유효기간 x를 11년이라고 가정하였는데요, 10년 후 양자 컴퓨터가 발명되었고 공격자가 이를 구매하였거나 또는 클라우드 서비스를 통해 양자 컴퓨터를 이용할 수 있다고 다시 한번 가정해 봅시다 (즉, z = 10년). 이제 공격자는 공통 비밀 키 설정 메시지를 보호하는 타원곡선암호를 무력화할 수 있게 되었습니다. 이를 통해 공통 비밀 키를 알아낸 후 암호화된 메시지를 복호화하여 (Decrypt Later) 유효기간이 1년이나 남은 경쟁사의 영업비밀이나 국가 기밀사항 등을 확인할 수 있습니다. 이처럼, x값이 z값보다 큰 경우 이미 해당 시스템과 데이터는 양자 위협에 노출되어 있습니다.

HNDL 공격 대응 – PQC 하이브리드

아직 최종 표준 알고리즘이 선정되지 않은 시점에서 우리는 HNDL 공격을 대비하기 위해 어떤 준비를 할 수 있을까요? 미국 NIST, 유럽 전기통신표준협회 (European Telecommunications Standards Institute, ETSI), 캐나다 CFDIR (Canadian Forum for Digital Infrastructure Resilience) 등 국가별 표준기관과 인터넷 표준을 제정하는 IETF (Internet Engineering Task Force), 클라우드 보안 협회 (Cloud Security Alliance, CSA)에서 공통으로 제안하는 해결 방법이 있습니다. 바로 기존 공개 키 암호 알고리즘과 PQC 알고리즘을 동시에 사용하는 PQC 하이브리드 키 설정 방법 [그림 5]입니다.

[그림 5] PQC 하이브리드 키 설정 방법

기존 공개 키 암호를 이용한 공통 비밀 키 (K_DH) 설정과 PQC 키 교환 알고리즘을 이용한 추가 공통 비밀 키 (K_pq)를 이중으로 설정하여 HNDL 공격을 효과적으로 방어함과 동시에, PQC 알고리즘에 대한 잠재적 공격을 함께 방어할 수 있습니다. 2022년 7월, NIST에서 래티스 기반의 CRYSTALS-Kyber 알고리즘을 표준으로 선정함에 따라, PQC 하이브리드 키 설정 방법은 이미 적용 가능한 양자 위협 대응책입니다. 미국 국립표준기술연구소(NIST)에서도 위에서 설명한 기존 표준 공동키 설정 방법과 추가적인 비밀 키 설정을 함께 사용하는 하이브리드 기법에 대한 문서를 발간하며^[4] 기존 표준암호 기반의 키 교환 방식과 양자내성암호 방식을 함께 사용하는 Hybrid 방식이 FIPS (Federal Information Processing Standards) 인증 지위를 유지하는 것으로 해석될 수 있다고 언급하였습니다.^[5] 이후 표준화 과정이 최종 완료되면 특정 시점부터는 기존 양자 취약 공개 키 암호 사용을 멈추고 PQC 표준 알고리즘만을 적용한 ‘양자내성 암호화된 통신’으로 전환해야겠지만, PQC 하이브리드 키 설정은 기존 공개 키 암호화 함께 PQC 알고리즘을 추가 적용함으로써 표준화 최종 완료 이전에도 적용 가능한 HNDL 공격에 대한 대비책으로 볼 수 있습니다. PQC 하이브리드 키는 존 공개 키 암호와 PQC의 안전성이 모두 깨지지 않는 한 안전성이 보장되며, PQC 하이브리드 키 설정 적용 이후 생성 데이터는 양자 위협으로부터 안전하다고 기대할 수 있습니다. 여기서 주목할 점은 PQC 하이브리드 키 설정을 적용하기 위한 Migration Time y가 소요된다는 점입니다. 다음 장에서는 Migration Time을 어떻게 추정할 수 있을지 생각해 보겠습니다.

3. PQC Migration, Why Now?

Crypto Migration의 역사

정확한 Migration Time은 기업의 상황이나 대상 시스템의 특성에 따라 달라지겠지만, 기존 암호 시스템 전환 (Crypto Migration)의 세 가지 역사 1) AES Migration, 2) SHA-2/3 Migration, 3) ECC Migration를 통해 PQC Migration Time 역시 예상보다 더 오래 걸릴 수 있음을 알 수 있습니다.
1) AES Migration : 1990년대 미국의 대칭 키 암호 표준이었던 DES와 3DES의 안전성을 보장할 수 없게 되자, NIST는 1997년 새로운 대칭 키 암호 표준 공모를 시작하였고, 2001년 Rijndael 알고리즘을 AES라는 이름의 표준으로 발표하였습니다. 이후 3DES가 적용된 시스템에 AES를 적용하는 AES Migration이 시작되었으나, 3DES의 공식적 은퇴가 발표된 이후에도 여전히 일부 시스템에 3DES가 적용되어 있어 AES Migration은 아직 현재 진행 중이라고 할 수 있습니다.

2) SHA-2/3 Migration : NIST 표준 해쉬함수 SHA-1의 경우, 1995년 표준 발표 이후 널리 적용되었지만, 2011년 취약성이 인정됨에 따라 SHA-1 적용을 중지하고 SHA-2 또는 SHA-3로 적용할 것을 권고하고 있습니다. NIST에서는 2030년 말까지 SHA-1 적용 중단을 예고하고 있어 SHA-2/3 Migration 기간이 20년가량 소요된다고 볼 수 있습니다.

3) ECC Migration : 공개 키 암호 시스템의 경우는 어떨까요? 역사적으로 1978년 발표된 RSA 암호 이후 우리는 PQC Migration과 같은 대대적인 공개 키 암호 시스템 전환을 단 한 번도 경험하지 못했습니다. 물론, 타원곡선암호 (Elliptic Curve Cryptography, ECC)로의 전환 (ECC Migration) 사례가 있었으나 ECC Migration은 효율성을 높이기 위한 선택사항으로, 필수 전환 대상은 아니었습니다. ECC 암호는 기존 RSA 암호에 비해 작은 footprint로 2004년 이후 전자여권, 블록체인 등 다양한 분야에 적용되고 있는 공개 키 암호 시스템입니다. 앞서 설명한 AES Migration이나 SHA-2/3 Migration과 같은 필수 전환 대상이 아니기 때문에 ECC Migration Time은 PQC Migration Time을 예측하는 직접적인 척도는 될 수 없습니다. 그러나 ECC Migration은 다른 시사점을 보여주고 있습니다. ECC Migration은 더 작은 사이즈의 키, 암호문, 서명을 적용하는 것으로, 기존 RSA 암호를 사용하였던 프로토콜이나 프레임 안에서 전환이 비교적 용이하게 이루어졌습니다.

그러나 PQC Migration의 경우, 더 큰 사이즈의 키, 암호문, 서명을 가지고 있는 PQC 알고리즘을 적용하는 것으로 네트워크 패킷 분할 (Packet fragmentation) 로 인한 안전성 및 효율성 저하 등 추가로 고려할 문제가 남아있습니다. 또한 양자 위협으로 인해 기존 알고리즘의 안전성을 보장할 수 없기 때문에 PQC Migration은 선택이 아닌 필수 사항이라는 점에서, ECC Migration에 비해 훨씬 복잡하고 시간도 오래 걸릴 것입니다. AES Migration, SHA-2/3 Migration 역시 필수 전환 대상이었는데요, 이들 Migration은 아직도 현재 진행 중이며, Migration Time이 길게는 수십 년까지 소요되었습니다. PQC Migration의 경우 훨씬 더 넓은 범위에 영향을 미치는 공개 키 암호 시스템 전환임에도 불구하고 PQC Migration을 위해 우리에게 허락된 시간은 10년이 채 남지 않았습니다.

Start PQC Migration Today!

그렇다면 PQC Migration에 필요한 Migration Time은 어떻게 결정될까요? PQC Migration을 준비하는 현재의 우리와 이전 Crypto Migration을 경험할 당시의 우리 모습은 크게 달라졌습니다. 현재의 IT 시스템은 그 어느 때보다 복잡해졌으며, ECC Migration과는 달리 PQC Migration은 전면적인 공개 키 암호 시스템 전환에 해당하기 때문에 클라우드를 포함한 모든 IT 시스템에 대해 자세히 파악하고 분석할 필요가 있습니다. 특히, IT 시스템에 적용된 공개 키 및 대칭 키 암호 알고리즘 적용 현황, 시스템 간 의존도 등 기존에는 고려하지 않았던 부분까지 고려해야 하는 것은 물론이고, 인터넷 보안의 기반이라 할 수 있는 PKI (Public Key Infrastructure) 역시 대상이 되는 만큼 PQC Migration은 이전 Crypto Migration에 비교해 아주 큰 작업입니다. 본 기고에서는 주로 ‘암호화된 통신’에 주목하여 PQC Migration을 설명하고 있지만, 실제 기업의 IT 환경에서 암호 기술이 사용되는 곳은 훨씬 다양합니다. 따라서, PQC Migration Time이 얼마나 소요되는지 예측하기 위해서는 시스템 전체에 대한 상세한 이해가 선행되어야 하며, 이 과정 역시 PQC Migration Time에 포함되기 때문에 우리는 지금 당장 양자 취약 암호 사용 여부를 식별하고 PQC Migration 전략을 수립해야 합니다.

시스템 복잡도로 인해 많은 시간이 소요될 수밖에 없다는 점 외에도 PQC Migration을 지금 바로 시작해야 하는 이유는 관련 법규 및 규제에서도 더 찾을 수 있습니다. 2022년 5월, 미국 백악관에서는 현재 암호 시스템에 대한 양자 컴퓨터 위협을 최소화하며 양자 컴퓨팅 관련 리더십 확보 방안 -- National Security Memorandum on Promoting United States Leadership in Quantum Computing While Mitigating Risks to Vulnerable Cryptographic Systems -- 에 대한 각서를 발표하였고, 미국 NSA (National Security Agency)에서는 2030년까지 미 정부 주요 시스템 내 PQC Migration 완료 — The Commercial National Security Algorithm Suite 2.0 (CNSA 2.0) -- 를 목표로 하고 있습니다. 이처럼 PQC Migration은 빨라지는 양자 위협 타임라인 z에 대비하는 것을 넘어, 관련 규제로 인해 Migration Time y 자체를 줄여야 하는 문제가 되었습니다. 특히, 미국 Biden 정부에서는 지난 12월, PQC Migration에 대한 법안 “Quantum Computing Cybersecurity Preparedness Act” (`22.12.21日)^[6]를 통과시켰으며, 미 관리예산실 (The Office of Management of Budget)에서는 연방기관들에게 양자 취약 암호 관련 리스크 관리 방안 및 필요 예산 수립을 위한 PQC Migration 전환 가이드를 발표하였습니다. 이처럼 미국, 유럽을 비롯하여 국내에서도 PQC Migration을 법제화하고 있는 움직임을 보이고 있어 지금 바로 PQC Migration을 시작해야 합니다.

미국 NIST에서는 PQC Migration Time을 최소화하기 위한 노력의 일환으로 2022년 6월부터 ‘Migration to Post-Quantum Cryptography’ 프로젝트를 진행하고 있습니다. 해당 프로젝트에서는 PQC Migration을 체계적으로 수행하기 위한 모범사례를 확보하고 PQC Migration에 대한 정부기관 및 기업들의 의식 제고를 목적으로 하고 있습니다. 삼성SDS는 아시아에서 유일하게 NIST 프로젝트에 참여하여 미국 주요업체 (AWS, Microsoft, IBM, JPMorgan Chase & Co. 등)들과 활발한 협업을 수행하고 있습니다. 특히, NIST PQC Migration 프로젝트에서는 DevOps 단계별 양자 취약 암호 사용 여부 식별 Tool을 확보하고, PQC 적용 시스템 간 상호운용성을 보장하기 위한 테스트를 수행하며 PQC Use case 및 PQC Migration 모범사례 발굴에 힘쓰고 있습니다.

[그림 6] NIST PQC Migration 프로젝트 타임라인 (출처: NIST)

삼성SDS 클라우드 보안 서비스 - 복잡한 클라우드 환경에서 꼭 필요한 보안, 삼성SDS가 해결해 드립니다

4. 맺음말

본 기고문에서 PQC 알고리즘과 PQC Migration 시급성에 대해 간략히 소개하였습니다. 저희 보안연구팀에서는 PQC Migration을 위한 기술적 고려사항과 취약 암호 사용 여부를 효율적으로 식별하기 위한 기술 연구를 진행하고 있습니다. 추후 이어지는 시리즈 기고문을 통해 양자 컴퓨터 위협과 PQC 알고리즘 표준화 현황에 대해 자세히 소개하고, DevOps 단계별 암호 사용 예와 함께 취약 암호 식별 방법에 대해 알아보도록 하겠습니다.

References
[1] 2018년 선정된 Stateful 해쉬기반 전자서명 알고리즘 2종과 2022년 7월 발표한 Stateless 해쉬기반 전자서명 알고리즘 1종, 래티스 기반 전자서명 알고리즘 2종 포함 총 5종
[2] NIST PQC 4라운드 알고리즘 4종 발표 이후 SIKE 알고리즘에 대한 공격 방법이 알려짐. 현재 SIKE 제외 3종 알고리즘 평가 진행 중
[3] 한국 양자내성암호연구단 https://www.kpqc.or.kr
[4] NIST, SP 800-56C Rev. 2 (Recommendation for Key-Derivation Methods in Key-Establishment Schemes)
[5] https://csrc.nist.gov/Projects/post-quantum-cryptography/faqs
[6] https://www.congress.gov/bill/117th-congress/house-bill/7535

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

양자컴퓨터에 따른 보안 위협

이 글이 좋으셨다면 구독&좋아요

여러분의 “구독”과 “좋아요”는
저자에게 큰 힘이 됩니다.

조지훈, 윤효진, 김은경 보안 전문가

조지훈 | 삼성SDS 연구소 보안연구팀장
삼성SDS 연구소 보안연구팀장으로 양자내성암호와 같은 암호기술, 개인정보보호 강화 기술, 그리고 클라우드 보안 기술을 연구개발하고 있습니다.

윤효진 | 삼성SDS 연구소 보안알고리즘Lab장
암호학을 전공하였으며, 삼성SDS 연구소 보안알고리즘Lab장으로 양자내성암호 원천 기술 및 전환 기술, 개인정보보호 강화 기술을 연구개발하고 있습니다.

김은경 | 삼성SDS 연구소 보안알고리즘Lab
타원곡선암호 등 현대암호학의 기반이 되는 수학 이론을 전공하여 박사학위를 취득하였습니다. IT 시스템 곳곳에 적용된 암호기술을 식별하여 안전하고 효율적으로 양자내성암호를 적용하기 위한 양자내성암호 전환 기술을 연구개발하고 있습니다.