양자 컴퓨터가 128비트 대칭키를 위협하지 않는 이유

AI 요약

양자 컴퓨터의 등장으로 모든 암호 알고리즘을 더 긴 키로 바꿔야 한다는 오해가 퍼지고 있습니다. 원문은 양자 컴퓨터가 실제로 위협하는 영역과 그렇지 않은 영역을 나눠 설명합니다. Shor 알고리즘은 ECDH 키 교환과 RSA, ECDSA, EdDSA 디지털 서명을 공격할 수 있으므로 공개키 암호는 양자내성암호로 교체해야 합니다. 반면 AES, SHA-2, SHA-3 같은 대칭키 암호는 현재 알려진 양자 알고리즘 때문에 키 길이를 바꿀 필요가 없습니다.

■ Grover 알고리즘이 대칭키 보안을 단순히 절반으로 만들지 않는 이유

대칭키 키 공간의 검색에는 Grover 알고리즘을 적용할 수 있습니다. 키 공간 크기가 N이면 고전적인 전수조사는 대략 N번의 시도가 필요하지만, Grover 알고리즘은 이론상 제곱근 수준으로 줄입니다. 여기서 AES-128의 보안이 64비트로 낮아진다고 해석하는 경우가 많지만, 원문은 이 계산이 실제 공격 비용을 반영하지 않는다고 지적합니다.

Grover 알고리즘에서 검색 대상 함수를 구현한 오라클은 양자 회로 안에 들어가야 합니다. 오라클 호출은 순차적으로 실행해야 하며, 공격을 여러 양자 컴퓨터로 나눌 때 얻는 이점도 제한됩니다. 고전적인 전수조사는 서로 독립인 시도를 여러 장비에 나누면 전체 작업량을 그대로 유지하면서 빠르게 끝낼 수 있습니다. 반면 Grover 공격은 검색 공간을 분할할수록 제곱근 가속이 희석됩니다. 각 장비가 담당하는 공간을 줄이는 효과는 제곱근 안에서만 나타나지만, 여러 장비를 동시에 동원하면 전체 회로와 작업량이 커집니다.

■ AES-128 공격에 필요한 규모

원문은 매우 유리한 가정을 적용해도 AES-128 공격에 필요한 자원이 거대하다고 계산합니다. 초전도 큐비트 기반의 빠른 양자 아키텍처에서 논리 게이트 하나의 시간이 1마이크로초라고 가정합니다. 전원 중단이나 충실도 손실 없이 공격을 10년 동안 지속한다고 가정해도, 한 공격 인스턴스가 실행할 수 있는 순차 게이트 수에는 한계가 생깁니다.

Liao와 Luo가 2025년에 제시한 최적화 AES-128 Grover 오라클은 깊이 232의 T-gate와 폭 724를 사용합니다. 여기서 폭은 대략 동시에 작동하는 논리 큐비트 수입니다. 10년 안에 공격을 끝내려면 약 140조 개의 양자 회로를 병렬로 실행해야 하며, 각 회로에는 724개의 논리 큐비트가 필요합니다. 이 조건은 오류 정정이 가능한 논리 큐비트와 장기간 안정적인 실행을 이미 확보했다고 가정한 결과입니다.

공격 비용을 회로 깊이와 폭의 곱인 DW cost로 나타내면, AES-128 Grover 공격은 256비트 타원곡선에 대한 Shor 공격보다 430,000,000,000,000,000,000,000배 비쌉니다. Shor 공격은 10마이크로초의 빠른 게이트 시간을 가정해도 몇 분 안에 실행되는 시나리오가 논의되지만, AES-128 공격은 병렬화 비용 때문에 전혀 다른 규모가 됩니다.

■ NIST와 BSI의 판단

미국 국립표준기술연구소(NIST)는 AES-128을 양자내성암호 보안 범주의 기준으로 사용합니다. NIST가 설명하는 MAXDEPTH 개념도 공격 회로가 감당할 수 있는 최대 순차 계산량을 뜻하며, 이 한계를 넘지 않으려면 Grover 회로를 여러 인스턴스로 나눠야 합니다. 그 결과 이론적인 제곱근 가속은 현실적인 병렬 공격에서 크게 줄어듭니다.

NIST의 양자내성암호 FAQ는 AES 키 길이를 지금 두 배로 늘릴 필요가 없다고 명시합니다. 양자 컴퓨터가 고전적인 전수조사보다 적은 단계로 검색하더라도, 양자 하드웨어의 높은 비용과 Grover 알고리즘의 순차 실행 요구 때문에 실전 가속은 예상보다 작습니다. NIST는 AES-128, AES-192, AES-256을 계속 사용할 수 있으며, 대칭키와 해시 함수의 전환이 필요해지는 시점에 별도 지침을 내겠다고 설명합니다. 다만 고전적 보안 강도가 112비트보다 낮은 알고리즘은 사용하지 않아야 합니다.

독일 연방정보보안청(BSI)도 AES-128, AES-192, AES-256을 신규 암호 시스템에 권장합니다. BSI는 양자 컴퓨터에 취약한 고전적 키 합의 방식은 2031년 말까지만 사용하도록 권고하지만 AES-128은 교체 대상에 포함하지 않습니다. NIST의 전환 초안도 2035년부터 양자 취약 공개키 알고리즘을 허용하지 않는 방향을 제시하면서, AES 키 길이는 계속 허용합니다.

■ 대칭키를 불필요하게 바꾸지 말아야 하는 이유

양자내성 전환에서 시급한 작업은 공개키 암호 교체입니다. TLS에서 키 교환과 PKI 서명 알고리즘을 바꾸는 작업은 지원 암호 스위트에서 AES 키 길이를 바꾸는 작업과 별개입니다. 두 영역을 하나로 묶으면 필요하지 않은 변경까지 진행하면서 구현과 호환성 검증에 자원을 쓰게 됩니다.

TLS처럼 여러 라이브러리와 프로그래밍 언어가 함께 구현하는 개방형 생태계에서는 목표 사양에 합의해야 합니다. 기술적으로 필요하지 않은 AES-256 전환을 각자 다르게 해석하면 여러 변형을 동시에 지원해야 하고, 상호운용성 문제가 늘어납니다. 원문은 공개키 암호 전환에 집중하려면 이미 안전하다고 평가받는 대칭키 시스템은 그대로 두는 편이 낫다고 주장합니다.

■ 256비트 키가 필요한 경우

모든 상황에서 256비트 키가 무의미한 것은 아닙니다. 해시 충돌처럼 생일 공격이 적용되는 경우에는 128비트 충돌 보안을 얻으려면 256비트 해시 출력이 필요합니다. SHA-128이 존재하지 않는 이유도 여기에 있습니다. 여러 메시지나 키 가운데 하나를 공격하는 다중 표적 공격에서도 논스 사용 방식에 따라 추가 여유가 필요할 수 있습니다. 다만 이런 문제는 프로토콜을 설계하는 암호 엔지니어가 다루는 영역이며, TLS와 같은 잘 설계된 프로토콜은 이미 논스 구조에 필요한 여유를 반영합니다.

CNSA 2.0은 대칭키에 256비트 보안 수준을 요구하는 예외입니다. 하지만 이 정책은 양자 컴퓨터 때문에 AES 키 길이를 두 배로 늘린 결과가 아닙니다. CNSA 2.0은 ML-KEM-1024와 ML-DSA-87을 포함해 모든 항목을 256비트 수준으로 맞추는 일관된 정책을 선택합니다. AES-512 대신 AES-256을 지정한 점도 Grover 알고리즘이 AES 보안을 단순히 절반으로 낮추지 않는다는 점과 맞닿아 있습니다. AES-256은 AES-128보다 라운드 수가 많아 더 느리므로, 원문은 일반적인 시스템에서 불필요한 전환을 권하지 않습니다.

■ <출처> 반응

• @u/nicuramar — 좋은 글입니다. 양자 컴퓨팅이 암호에 가하는 위협을 일반인이 오해하는 일이 널리 퍼져 있습니다.
• @u/ryan017 — 앞으로도 당분간은 적어도 한 달에 한 번씩 올라와야 할 글 같습니다. 제가 보기에도 지금까지 계속 올라오고 있습니다.
• @u/Lonely_Translator_23 — 제가 이해한 바로는 키 길이와 무관하게, 양자 컴퓨터가 대칭키 암호에 가하는 위협은 동등한 고전 컴퓨터보다 더 크지 않습니다.
• @u/EmperorOfCanada — 이제는 끈 이론과 양자 컴퓨터 연구에 들어가는 자금을 합쳐야 한다는 생각이 듭니다. 적어도 웃음이라도 주는 초자연 현상 연구에 자금을 대는 편이 더 편할 것 같습니다.
• @u/zidanerick — 기술이 발전하기 전까지는 그 영향에 대해 아직 기본적인 이해만 가지고 있습니다. 양자 컴퓨팅에 접근할 수 있는 고도화된 AI가 결합하면 암호와 무관하게 심각한 피해를 일으킬 수도 있습니다.

원문: words.filippo.io / 번역·요약: Trawling