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

양자 컴퓨터의 등장으로 모든 암호 알고리즘을 더 긴 키로 바꿔야 한다는 오해가 퍼지고 있습니다. 원문은 양자 컴퓨터가 실제로 위협하는 영역과 그렇지 않은 영역을 나눠 설명합니다. 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보다 라운드 수가 많아 더 느리므로, 원문은 일반적인 시스템에서 불필요한 전환을 권하지 않습니다.

Reddit 반응

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

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