brunch

라이킷 2 댓글

You can make anything
by writing

C.S.Lewis

계정을 잊어버리셨나요?

by 고려대학교 IT경영학회 ITS May 15. 2023

PQC, 양자컴퓨터도 풀기 어려운 암호가 있다?!

기술스크랩

양자내성암호(PQC)

양자내성암호(Post-Quantum Cryptography, PQC)는 양자 컴퓨터의 공격 시도에도 안전하다고 여겨지는 암호 알고리즘이다. 이론적으로는 양자 컴퓨터도 풀어내는 데 무려 수십억 년이 걸린다는 수학 알고리즘을 사용한다.

그렇다면 왜 PQC가 등장하게 되었을까? 양자 컴퓨팅(Quantum Computing) 기술이 등장하면서 보안 문제가 가장 큰 위협으로 떠올랐기 때문이다. 아직 상용화 이전의 기술 개발 단계이지만, 기존 컴퓨터보다 연산 능력이 압도적으로 뛰어난 양자컴퓨터를 사용하면 기존 암호화 알고리즘을 짧은 시간 내에 무력화할 수 있을 것으로 예상된다.

더욱 자세히 알아보기 위해 한 예시를 들어보겠다. 인터넷을 사용하다 사이트에 접속했을 때, ‘암호화된 연결을 사용할 수 없습니다’라는 경고 문구를 발견한 적이 있을 것이다. 이 경고 문구에도 불구하고 호기심이나 필요에 의해서 그대로 사이트에 ‘연결’ 버튼을 누른 경험이 있을지도 모른다. 사용자와 웹사이트가 주고받는 데이터가 암호화되지 않는다면, 제 3자가 주고받는 모든 데이터를 조회 가능하다는 것이다. 반면 ‘암호화된 연결’에서는 이 데이터가 암호화 후 안전하게 전송되기 때문에 제 3자가 원본 데이터를 조회하거나 위/변조할 수 없다. 이때 데이터 암호화/복호화에 사용할 공통 비밀키를 설정할 때 사용되는 것이 공개키 암호 알고리즘이다. TLS 프로토콜이 적용된 HTTPS 통신에서는 알고리즘에 RSA나 ECC(타원곡선암호) 방식 같은 공개키 암호 알고리즘이 사용된다.

RSA와 ECC 알고리즘의 안전성은 각각 소인수분해와 이산대수 문제에 기반을 두고 있다. 즉 0과 1의 ‘비트’ 연산을 사용하는 현재 컴퓨터에서 이 수학적 문제들을 푸는 시간은 입력값이 커짐에 따라 아주 빠르게 증가한다. 즉 현재 사용되는 비트 연산 컴퓨터로도 아주 오랜 시간이 걸리는 큰 수를 암호 알고리즘에 이용한다면 공개키 암호의 안전성이 보장될 것이다.

그렇지만, ‘큐비트’ 처리 단위를 가지고 슈퍼컴퓨터가 백만 년에 걸리는 문제를 양자중첩으로 0과 1을 동시에 나타낼 수 있고, 양자병렬계산을 통해 1초에서 하루 만에 풀어내는 양자 컴퓨터가 등장한다면 어떨까? 0과 1 비트 연산과 다른 원리로 동작하는 컴퓨터가 등장한다면, 기존 공개키 기반 암호 알고리즘은 보안이 취약해 사용이 어려워질 것이다.

PQC 전환, Mosca의 부등식

양자컴퓨터 상용화 이전에 기존 공개키 기반 암호 알고리즘을 PQC로 전환해야 하는 이유는 ‘Mosca의 정리’를 통해 설명할 수 있다. 여기서 X = 데이터 보호를 원하는 기간(Shelf-life Time), Y = 현재 보안 시스템에서 Post Quantum 보안 시스템으로 전환되는 기간(Migration Time), Z = 양자컴퓨터가 상용화되어 기존 암호화를 위협할 때(Threat Timeline)를 의미한다. 즉, X + Y > Z 일 경우 남은 기간에 대해서는 데이터를 보호할 수 없다는 것이다. 따라서 X + Y와 Z를 비교하여 필요한 경우 PQC 전환을 서둘러야 한다는 것이 Mosca의 지적이다.

PQC(양자내성암호)의 유형 및 원리

PQC는 수학적 난제에 따라 다변수 기반(Multivariate-based), 코드 기반(Code-based), 격자 기반(Lattice-based), 아이소제니 기반(Isogeny-based), 해시 기반(Hash-based)의 5가지 유형으로 나뉜다.

다변수 기반(Multivariate-based) 암호는 유한체 위에서 계산하는 다변수함수 문제의 어려움에 기반하는 암호 시스템으로 주로 이차함수를 사용한다. 암호화 및 복호화가 다항식의 계산이기 때문에 전력 분석의 부채널 공격에 강하여 안전하다는 장점이 있다. 하지만 키 사이즈가 크기 때문에 주로 서명 기법에 사용되는 편이다.

Figure 1 : 코드 기반 암호

코드 기반(Code-based) 알고리즘은 일반적인 선형 코드를 디코딩하는 어려움에 기반하는 암호 시스템으로, 행렬 연산이기 때문에 연산 속도가 빠르다는 장점이 있으나, 복호화가 암호화보다 연산 속도가 느리고 키의 크기가 크다는 단점이 있다. 의도적으로 오류를 메시지에 주입해서 오류를 알고 있는 사용자만 메시지를 복원할 수 있도록 만드는 것이다.

Figure 2: 격자 기반 암호

격자 기반(Lattice-based) 암호는 격자 위에서 계산하는 문제의 어려움에 기반하는 암호 시스템이다. NP-hard라는 수학 문제에 안전성 기반을 두고 있기 때문에 안전성에 강점이 있으며 계산 효율성이 높다. 격자 기반 암호는 인수분해 등 어려운 수학을 쓰는 것이 아니라, 행렬처럼 쉬운 문제를 잡음(Noise)을 주어 답을 조금씩 다르게 하여 수학적으로 어렵게 만드는 것이다. 이때 200차원의 격자를 사용하기 때문에 답을 찾기 어려워진다. 가장 널리 연구되는 유형이다.

Figure 3: 아이소제니 기반 암호

아이소제니 기반(Isogeny-based) 암호는 순서가 같은 두 타원곡선 사이에 존재하는 아이소제니를 구하는 문제의 어려움에 기반을 두는 암호 시스템이다. 구현이 편리하나 연산속도가 느리다는 단점이 있다.

해시 기반(Hash-based) 암호는 해시 함수의 안전성을 기반으로 한 전자 서명 시스템으로, 양자 컴퓨팅 환경에서도 해시함수의 출력의 길이를 늘여서 안전성을 보장할 수 있다. 하지만 큰 서명 사이즈를 가진다는 단점이 있다.

활용 사례

SK텔레콤(이하 SKT)과 SK브로드밴드(이하 SKB)가 2022년 9월, 국제망을 이용하는 글로벌 가상사설망(VPN) 네트워크에서 양자내성암호(PQC)를 국내 처음으로 상용화했다. 구축을 맡은 SKB는 2022년 8월 소프트웨어(SW) 업데이트를 통해 'PQC-VPN' 설치를 완료하고 미국, 일본, 싱가포르 등 해외에서 네트워크 테스트를 성공시켰다.

기존 양자암호통신의 QKD(양자암호키분배기, Quantum Key Distribution)는 물리적인 키 분배장치를 구간마다 설치·운용하는 반면 PQC는 소프트웨어(SW) 방식으로 구현되어 보안 영역, 편리성 등에서 상호 보완적인 기술이다. SKT는 이번 적용을 통해 물리적 제약으로 QKD 네트워크를 사용하기 어려운 국제망 구간에서 PQC를 효율적으로 적용할 수 있음을 보여주었다. 또한 PQC-VPN은 인증 및 키분배 시 기존 공개키 알고리즘을 PQC 알고리즘과 동시에 활용하는 하이브리드 기술을 적용하여 안정성을 강화했다.

하이브리드 PQC는 현재 사용 중인 TLS 방식에 PQC 방식을 선택적으로 적용하는 방법으로, 기존 키 교환 방식과 PQC 중 하나를 XOR 연산으로 결합 후 최종 비밀키를 생성하여 사용한다. 기존 공개키 암호를 이용한 공통 비밀키 (K_DH) 설정과 PQC 키 교환 알고리즘을 이용한 추가 공통 비밀키 (K_pq)를 이중으로 설정하여 HNDL 공격을 효과적으로 방어함과 동시에, PQC 알고리즘에 대한 잠재적 공격을 함께 방어할 수 있다. PQC가 기존 방식을 대체하지만 덜 범용적이고 성능 저하 우려가 있다는 점과 달리, 하이브리드 PQC는 선택적 적용으로 더 범용적이고 성능 저하 우려 없이 사용이 가능하다.

기술과 사례에 대한 인사이트

결국 PQC 기술 개발에 선행되는 문제는 양자 컴퓨팅의 문제와도 맞닿아 있다. 양자 컴퓨팅의 보안 위협은 양자 컴퓨터가 어떤 시점에서 상용화될 것인지, 양자 컴퓨터 상용화 표준은 어떻게 설정될 것인지, 양자 컴퓨터 상용화 시 시급한 위협들은 무엇이 있는지, 양자 컴퓨터를 상용화해야 하는지 생각해 보는 과정이 선행되어야 한다.

양자 컴퓨터의 보안 위협은 암호화 키를 통해 접근 자격을 검증하여 SW 업데이트를 진행하는 자동차, 위성, 심장 모니터링 기기, 항공기 등의 장비들에도 적용된다. 양자컴퓨팅으로 암호화 키를 무력화시키고 악성 소프트웨어를 설치할 수도 있다. 또한, 가장 기본적으로 금융이나 의료, 기업의 암호화된 데이터가 안전하지 않을 수 있고, 디지털 신원(ID)에도 영향을 미쳐 신원 사칭/위조가 가능해진다. 기술 개발만큼, 미래 대비와 기술의 필요성 검증은 선결 과제이다.

함께 생각해 볼 만한 논점

Q1. 양자 컴퓨팅 기술 새로운 물질을 만들고 인간 DNA 조작을 가속화할 수 있다는 윤리적 우려가 있다. 어떤 기술이건 기술적 이점에 따라오는 윤리적 문제가 발생하기 마련이다. 양자 컴퓨팅이 상용화된다면, 우선적으로 해결해야 하는 상황들은 무엇이 있을까?

Q2. 양자 보안에 대한 관심 고취의 필요성이 크지만, PQC의 해킹이 절대 불가하다는 잘못된 환상을 가지게 하는 홍보는 피해야 할 것이다. 또한 단위 요소기술일 뿐인 QKD(양자암호키분배)나 QRNG(양자난수발생기) 기술을 양자 보안의 전부처럼 과도하게 부풀려 홍보하는 태도는 위험하다고 지적되기도 한다. 그렇다면, 기술을 홍보할 때에는 어떤 방식을 채택해야 할까?