AES-128, 양자 공격에 사실상 안전 — 암호학자 분석

원제: Cryptologist Finds AES-128 Likely Safe From Quantum Attack

암호학 연구자 Filippo Valsorda의 분석에 따르면, AES-128 등 128비트 대칭키 암호화는 Grover 알고리즘의 현실적 제약으로 인해 대규모 양자 컴퓨터가 등장하더라도 사실상 안전한 수준을 유지할 것으로 판단된다. 포스트 양자 전환기에 실질적인 위협은 대칭키가 아닌 공개키 암호 체계에 집중돼 있다는 분석이다.

저자: Matt Swayne

핵심 포인트

01Grover 알고리즘은 병렬화 시 알고리즘 이점이 감소하는 구조적 한계로 인해 AES-128에 대한 실용적 위협이 되기 어렵다

02AES-128 전수 공격에 필요한 병렬 양자 시스템 수는 약 2⁴⁷개로 추산되며, 이는 현실적으로 구현 불가능한 규모다

03Grover 기반 AES-128 공격 비용은 Shor 기반 타원곡선 암호 공격보다 약 2⁷⁸·⁵배 높다

04NIST와 독일 BSI 등 주요 표준 기관은 AES-128을 포스트 양자 환경에서도 안전하다고 판단하고 있다

05포스트 양자 전환의 우선순위는 대칭키가 아닌 공개키 암호 체계 교체에 두어야 한다는 결론이다

06분석은 동료 심사를 거치지 않은 블로그 포스트 형태이므로 추가 검증이 필요하다

Grover 알고리즘과 '키 길이 반감' 통념

양자 컴퓨팅 위협론에서 자주 언급되는 주장 중 하나는 Grover 알고리즘이 대칭키 암호의 유효 안전성을 절반으로 줄인다는 것이다. 128비트 키가 양자 환경에서는 사실상 64비트 수준으로 약화된다는 논리로, 이를 근거로 키 길이를 두 배로 늘려야 한다는 권고가 일부 보안 커뮤니티에서 제기돼 왔다.

Valsorda의 분석은 이 통념에 정면으로 이의를 제기한다. Grover 알고리즘은 이론적으로 2¹²⁸번의 연산이 필요한 전수 조사를 약 2⁶⁴번 수준으로 줄일 수 있지만, 이 이점은 연산을 순차적으로 반복 적용해야만 유지된다는 구조적 한계를 갖는다. 고전 컴퓨팅에서는 병렬 처리가 전체 연산량을 늘리지 않고도 시간을 단축시키지만, Grover 알고리즘을 여러 양자 시스템에 분산할 경우 알고리즘 자체의 이점이 희석돼 오히려 총 연산 비용이 증가하는 구조다.

공격 비용 정량화: 2⁴⁷개의 병렬 시스템

분석은 AES-128 공격에 필요한 자원을 구체적으로 추산하기 위해, 연산 속도 마이크로초 수준에 10년간 무중단 가동이 가능한 고성능 양자 시스템을 가정했다. 이는 현재 기술 수준을 크게 상회하는 낙관적 가정임에도 불구하고, 공격을 완수하려면 약 2⁴⁷(약 140조)개의 병렬 양자 시스템이 필요하다는 결론이 도출됐다. 각 시스템은 수백 개의 논리 큐비트로 구성된 복잡한 회로를 구동해야 하며, 총 연산 비용은 회로 깊이와 너비를 종합할 때 약 2¹⁰⁴·⁵에 달한다.

이를 공개키 암호 공격과 비교하면 격차가 뚜렷해진다. Shor 알고리즘을 활용한 타원곡선 암호 공격에는 수천만 회 수준의 양자 연산이 필요한 것으로 추정되는 반면, Grover를 이용한 AES-128 공격 비용은 그보다 약 2⁷⁸·⁵배—대략 400섹스틸리언(sextillion)배—더 크다. 양자 위협이 공개키 체계에 훨씬 먼저, 훨씬 낮은 비용으로 현실화될 것임을 보여주는 수치다.

NIST 등 표준 기관과의 정합성

이번 분석 결과는 미국 국립표준기술연구소(NIST)의 공식 입장과 일치한다. NIST는 포스트 양자 암호화 프레임워크에서 AES-128을 보안 수준 기준점으로 계속 활용하고 있으며, Grover 알고리즘의 실용적 효과가 제한적임을 명시하고 있다. 독일 연방정보보안청(BSI) 역시 AES-128 및 더 긴 키 변형을 지속 권고하고 있어, 서방 주요 표준 기관들 사이에서 일관된 시각이 형성돼 있음을 확인할 수 있다.

포스트 양자 전환에 대한 시사점

현재 진행 중인 포스트 양자 마이그레이션은 주로 RSA와 타원곡선 암호 등 키 교환·디지털 서명 알고리즘의 교체에 초점을 맞추고 있다. 이번 분석은 대칭키 암호까지 이 전환 범위에 포함시키는 것이 불필요하며 역효과를 낼 수 있다고 지적한다. 통신 프로토콜, 하드웨어 구현, 소프트웨어 라이브러리 전반에 걸친 대칭키 업데이트는 호환성 문제를 야기하고, 실질적 위협에 대응하는 데 써야 할 자원을 분산시킬 수 있다.

방법론의 한계와 향후 과제

이 분석은 이론적 추론과 자원 추정을 결합한 방식으로 수행됐으며, 아직 동료 심사(peer review)를 거치지 않은 블로그 포스트 형태다. 미래 양자 하드웨어에 대한 가정에 의존하고 있으며, 논리 큐비트 구현에 필요한 양자 오류 정정 오버헤드는 충분히 반영되지 않았다. 오류 정정 비용까지 포함하면 공격 비용은 더 높아질 것으로 예상된다. 또한 아직 알려지지 않은 새로운 양자 알고리즘의 등장 가능성은 이 분석의 범위 밖에 있다.