최근 암호화에 대한 양자 컴퓨팅의 위협에 관해 많은 이야기를 들으셨을 것입니다. 이와 함께 이른바 '양자 위협'이 무엇이며 암호화 솔루션에 어떤 영향을 미칠지 궁금증도 많으실 텐데요. 양자 컴퓨팅과 암호화에 미치는 영향에 대해 가장 자주 묻는 몇 가지 질문을 살펴보겠습니다.
양자 컴퓨터란 무엇입니까?
양자 컴퓨터는 범용 고성능 슈퍼컴퓨터가 아니며 대규모 병렬 방식으로 마법처럼 작동하지도 않습니다. 대신 고유한 양자 알고리즘을 효율적으로 실행합니다. 이러한 알고리즘은 이론적으로 기존 컴퓨터보다 특정 연산을 훨씬 더 효율적으로 수행할 수 있습니다.
그러나 의미 있는 수준의 양자 컴퓨터, 즉 현대의 전통적인 컴퓨터를 실제로 능가할 수 있는 컴퓨터의 개발은 극도로 어렵습니다. 양자 컴퓨팅 기술은 1980년대부터 개발되어 왔으며 2010년대 이후 점진적으로 개선된 작동형 양자 컴퓨터가 등장했습니다. 그러나 현재의 기술 수준을 미래로 외삽(extrapolating)하고 전통적인 컴퓨터의 무어의 법칙에 상응하는 지수적 개선을 가정하더라도, 전문가들은 의미 있는 양자 컴퓨터가 현실화되려면 최소 15~20년은 걸릴 것으로 예상합니다.(1), (2)
암호화에 대한 양자 위협이란 무엇입니까?
1990년대에 일부 양자 알고리즘이 특정 전통적 암호화 기법의 보안에 영향을 미칠 수 있다는 사실이 발견되었습니다. 우려를 제기하는 두 가지 양자 알고리즘은 다음과 같습니다.
이러한 양자 알고리즘이 의미 있는 양자 컴퓨터에서 실행될 수 있다면 현재의 암호화 기법 보안에 영향을 미치게 됩니다.
공개키 암호화 솔루션에 미치는 영향은 무엇입니까?
현재까지 가장 중요하고 널리 사용되는 공개키 프리미티브는 RSA, 이산 대수 또는 타원 곡선 암호화를 기반으로 합니다. 의미 있는 양자 컴퓨터가 상용화되면 이 모든 것은 쇼어 알고리즘에 의해 효율적으로 해제될 수 있습니다. 이로 인해 현재 사용 중인 거의 모든 공개키 암호화가 보안에 취약해집니다.
영향을 받는 공개키 암호화 및 키 교환 프리미티브의 경우 이 위협은 이미 오늘날의 현실입니다. 현재(또는 과거에) 교환된 암호화된 메시지를 캡처하고 저장하는 공격자는 나중에 의미 있는 양자 컴퓨터가 작동할 때 이를 복호화할 수 있습니다. 따라서 지금까지 전달된 고도로 민감하거나 장기적인 보안 정보는 이미 위험에 노출되어 있습니다.
15년 미만의 단기 약정에서 영향을 받는 서명 프리미티브를 사용하는 경우 문제는 덜 긴급합니다. 그러나 의미 있는 양자 컴퓨터가 등장하면 그 시점부터 모든 서명의 가치가 무효화됩니다. 따라서 15~20년 이상 검증 가능해야 하는 장기 약정 서명에는 영향을 받는 프리미티브를 사용하지 않아야 합니다.
지난 10년 동안 암호학계는 쇼어 알고리즘(또는 양자든 기타 방식이든 알려진 다른 효율적인 알고리즘)으로 해결할 수 없는 수학적 문제를 기반으로 하는 새로운 공개키 프리미티브를 설계했습니다. 이러한 알고리즘을 통칭하여 포스트 양자 암호(post-quantum cryptography)라고 합니다. NIST는 최근 표준화를 위해 이러한 알고리즘의 선정 결과를 발표했습니다.(3)
대칭 암호화 솔루션에 미치는 영향은 무엇입니까?
잘 설계된 대칭 키 프리미티브의 보안 수준은 비밀 키를 무차별 대입(brute-forcing)하는 데 필요한 노력과 같습니다. 전통적인 컴퓨터에서 비밀 키를 무차별 대입하는 노력은 키의 길이에 직접적으로 지수 비례합니다. 의미 있는 양자 컴퓨터를 사용할 수 있게 되면 그로버 알고리즘은 무차별 대입 공격의 속도를 2차적으로 가속할 수 있습니다. 필요한 노력은 여전히 지수적이되, 키 길이의 절반에 대해서만 적용됩니다. 따라서 그로버 알고리즘은 특정 길이 알고리즘의 보안을 50% 감소시킨다고 볼 수 있습니다.
그러나 명심해야 할 몇 가지 중요한 사항이 있습니다.
대칭 암호화에 대한 양자 컴퓨터의 실질적인 영향은 현재로서는 매우 제한적입니다. 최악의 경우, 현재 사용되는 프리미티브의 보안 강도는 (키 길이의) 50%로 감소하지만, 그로버 알고리즘의 한계로 인해 이는 가까운 미래에 지나치게 비관적인 가정입니다. 양자의 무차별 대입 공격에 대응하기 위해 대칭 키의 길이를 두 배로 늘리는 것은 확실히 문제를 해결할 수 있는 매우 광범위한 일괄 조치이지만 지나치게 보수적입니다. 현재 양자 강화 대칭 키 암호화에 대한 권장 사항은 없으며, AES-128 또는 SHA-256과 같은 128비트 보안 강도 프리미티브는 현재 및 가까운 미래에 사용하기에 안전한 것으로 간주됩니다.
정보론적 보안(Information-theoretical Security)에는 어떤 영향이 있는가?
정보론적으로 안전한 방법(무조건적 보안 또는 완벽한 보안이라고도 함)은 보안성에 대한 주장이 수학적으로 증명된 알고리즘 기법입니다. 중요한 정보론적 보안 구조 및 프리미티브의 몇 가지 예로는 버넘 암호(Vernam cipher), 샤미르의 비밀 공유(Shamir’s secret sharing), 양자 키 분배(8)(포스트 양자 암호와는 혼동하지 말 것), 엔트로피 소스 및 물리적 복제 방지 기술(PUF),퍼지 커밋먼트(fuzzy commitment) 체계 등이 있습니다.(9)
정보론적 증명은 양자 컴퓨팅을 포함한 어떠한 연산 능력과 관계없이 공격자가 보안성을 무너뜨릴 수 있는 충분한 정보를 갖고 있지 않음을 보여주므로, 정보론적으로 안전한 구조는 양자 위협의 영향을 받지 않습니다.
Synopsys SRAM PUF
모든 Synopsys PUF 제품의 기반이 되는 핵심 기술은 SRAM PUF입니다. 다른 PUF와 마찬가지로 SRAM PUF는 실리콘 칩의 제조 공정에서 발생하는 예측 불가능한 변동에서 비롯된 디바이스 고유의 응답을 생성합니다. SRAM PUF의 동작은 실질적으로 모든 디지털 칩에서 쉽게 구할 수 있는 기존의 SRAM 회로를 기반으로 합니다.
수년간의 지속적인 측정과 분석을 바탕으로, 시놉시스는 SRAM PUF의 동작을 매우 정확하게 설명하는 확률적 모델을 개발했습니다(10). 이러한 모델을 사용하여 당사는 SRAM PUF의 예측 불가능성에 대한 엄격한 한계를 결정할 수 있습니다. 이러한 예측 불가능성의 한계는 엔트로피 측면에서 표현되며 근본적인 것으로, 양자 연산을 비롯한 어떠한 연산량으로도 극복할 수 없습니다.
Synopsys PUF
Synopsys PUF는 SRAM PUF 기술을 기반으로 하는 하드웨어 보안 솔루션입니다. Synopsys HW PUF의 중심 구성 요소는 SRAM PUF 응답으로 루트 키를 보호하고 공개 헬퍼 데이터를 생성하는 퍼지 커밋먼트 체계(9)입니다. 헬퍼 데이터는 루트 키에 대한 정보를 전혀 노출하지 않는다는 것이 정보론적으로 증명되어 있으므로, 헬퍼 데이터가 공개된다 하더라도 루트 키의 보안에는 아무런 영향이 없습니다.
수백만 대의 디바이스에 수년간 배포되어 유지되어 온 이 무누출(no-leakage) 증명은 시스템에 채택된 PUF가 확률적 모델로 표현되는 엔트로피 소스라는 점에 의존합니다. Synopsys HW PUF는 엔트로피 소스를 사용하여 루트 키를 처음으로 초기화하며, 이는 이후 퍼지 커밋먼트 체계에 의해 보호됩니다.
퍼지 커밋먼트 체계 및 엔트로피 소스 외에도 Synopsys HW PUF는 표준 대칭 암호 프리미티브(특히 AES 및 SHA-256)를 사용하는 인증된 표준 준수 구조 기반의 암호화 연산을 구현합니다. (11) 이러한 연산에는 다음이 포함됩니다.
Synopsys PUF의 보안 아키텍처는 루트 키의 생성 및 보호를 위한 정보론적 보안 구성 요소와 기타 암호화 기능을 위한 기존의 대칭 암호화를 기반으로 합니다. 정보론적 보안 구조는 양자 공격에 영향을 받지 않습니다. 대칭 암호화에 미치는 양자 위협의 영향은 제한적이며 현재나 가까운 미래에 별도의 조치가 필요하지 않습니다. 중요하게도 Synopsys PUF는 양자에 취약한 공개키 암호화 프리미티브를 배포하지 않습니다.
Synopsys PUF의 모든 버전은 양자 보안을 지원하며 권장되는 포스트 양자 지침을 준수합니다. Synopsys PUF의 256비트 보안 강도 변형을 사용하면 먼 미래에도 강력한 양자 저항성이 제공되며, 128비트 변형 역시 현재와 향후 가까운 시기에 사용하기에 완벽하게 안전한 것으로 간주됩니다.