암호학 엔지니어가 본 양자 컴퓨터 위협 타임라인 — '2029년까지 마이그레이션 안 하면 늦는다'

• 암호학 엔지니어 Filippo Valsorda가 양자 컴퓨터 위협 타임라인에 대한 입장을 대폭 수정함 — "몇십 년 후"가 아니라 "몇 년 내"로 바뀜
  • 최근 구글과 Oratomic의 두 논문이 결정적 계기
  • 암호학적으로 의미 있는 양자 컴퓨터(CRQC)가 256비트 타원곡선을 깨는 데 필요한 리소스가 종전 예측보다 훨씬 적다는 걸 보여줌

구글과 Oratomic의 연구 결과

• 구글 논문: NIST P-256, secp256k1 같은 256비트 타원곡선을 깨는 데 필요한 논리 큐비트와 게이트 수를 극적으로 하향 조정함
  • 초전도 큐비트 같은 고속 클럭 아키텍처에서 "수 분 내" 공격 가능
  • 실질적으로 WebPKI 중간자 공격(MITM)이 현실화될 수 있다는 뜻
• Oratomic 논문: 중성 원자(neutral atoms)의 비로컬 연결성을 활용하면 물리 큐비트 1만 개로도 256비트 타원곡선을 깰 수 있음
  • 구글 방식보다 느리지만, 한 달에 키 하나만 뚫려도 재앙적 결과를 초래할 수 있음

"확률 100%가 아니면 움직여야 한다"

• Valsorda가 제시한 리스크 프레이밍이 핵심임 — "2030년에 CRQC가 확실히 존재하느냐"가 아니라 "2030년에 CRQC가 확실히 존재하지 않느냐"를 물어야 함
  • 전문가들의 증언을 감안하면, 비전문가가 위협 확률이 1% 미만이라고 주장하기 어려움
  • 사용자는 "반반 확률"이 아닌 "거의 확실한 안전"을 요구하기 때문에 이 구분이 중요
• Scott Aaronson의 비유가 인상적 — 1939~1940년 핵분열 연구가 갑자기 공개 문헌에서 사라진 것과 비슷하다는 경고
  • "쇼어 알고리즘이 35를 인수분해하는 건 언제냐"고 묻는 건, 1943년 맨해튼 프로젝트 물리학자에게 "소규모 핵폭발은 언제 가능하냐"고 묻는 것과 같다는 논리

당장 해야 할 것들

• 키 교환(Key Exchange): ML-KEM으로 마이그레이션 진행 중이지만, 포스트양자 미지원 키 교환은 이제 사용자 경고를 표시해야 함
  • OpenSSH 모델을 따라 경고 → 에러 순서로 전환하는 게 바람직
  • 비대화형 키 교환(NIKE)은 당분간 포기 — 포스트양자 도구킷은 단방향 비인증 KEM만 제공
• 인증(Authentication): 하이브리드(기존+PQ) 방식을 버리고 순수 ML-DSA-44로 직행하라는 게 핵심 주장
  • 하이브리드 인증은 구현 복잡도만 높이고, 드래프트 표준에 복합 키 타입이 18개나 나와서 조율 시간만 잡아먹음
  • Kyber 2년간 배포 경험으로 모듈-래티스 체계에 대한 신뢰가 충분히 쌓였다는 판단
  • 하이브리드의 유일한 이점은 "CRQC보다 먼저 ML-DSA가 클래식하게 깨지는 경우"인데, 타임라인 긴급성을 감안하면 잘못된 트레이드오프임
• 대칭 암호화: 변경 불필요
  • Grover 알고리즘으로 128비트 키를 깨려면 회로 깊이 2^64 논리 게이트, 회로 크기 2^106 게이트 필요
  • 양자 속도 향상이 병렬화되지 않는다는 게 증명됨 — 256비트 키 강제 요구는 상호운용성만 해침

특히 심각한 영역들

• TEE(신뢰 실행 환경): Intel SGX, AMD SEV-SNP 등 하드웨어 증명 시스템이 비PQ 키를 쓰고 있는데, PQ 버전으로의 전환 진행이 전혀 보이지 않음
  • 하드웨어 교체 주기를 감안하면 시간 내 마이그레이션이 불가능할 수 있음 — "주요 보안 메커니즘"이 아닌 "심층 방어" 수준으로 격하해야 한다는 주장
• 암호화 ID 시스템: Atproto, 암호화폐 생태계는 즉각 마이그레이션이 필요
  • CRQC가 마이그레이션 완료 전에 도착하면 "사용자 침해" vs "계정 영구 잠금" 중 선택해야 하는 상황
• 파일 암호화: 지금 수집해서 나중에 복호화하는(store-now-decrypt-later) 공격에 가장 취약
  • age 암호화 도구의 PQ 수신자 지원이 v1.3.0에서야 추가됐는데, HPKE 하이브리드 수신자와 CFRG X-Wing 라벨 선정 과정에서 설계 변경 없이 거의 2년을 허비

왜 새 체계를 신뢰할 수 있나

• 래티스 기반 암호학은 타원곡선이 처음 배포될 때보다 더 오랜 기간 연구되었음
  • NSA가 ML-KEM과 ML-DSA를 Top Secret 등급 모든 국가안보 목적에 승인
  • ML-KEM과 ML-DSA는 기존 클래식 알고리즘보다 안전하게 구현하기 훨씬 쉬움
• Go 표준 라이브러리 기준, 암호 패키지의 대략 절반이 동시에 안전하지 않게 됨
  • SHA-1 → SHA-256 마이그레이션은 훨씬 덜 파괴적이었는데도 수년이 걸렸음
  • 이번 마이그레이션은 RSA + ECC를 동시에 교체하는 수준이라 비교가 안 됨

---

기술 맥락

• 여기서 말하는 ML-KEM(Module-Lattice Key Encapsulation Mechanism)과 ML-DSA(Module-Lattice Digital Signature Algorithm)는 NIST가 표준화한 포스트양자 암호 알고리즘이에요. 기존의 RSA나 ECDSA를 대체하는 건데, 핵심은 "격자(lattice) 문제"가 양자 컴퓨터로도 효율적으로 풀기 어렵다는 수학적 가정에 기반하고 있거든요.
• 하이브리드 vs 순수(pure) PQ가 왜 논쟁인지 이해하려면, 키 교환과 인증을 구분해야 해요. 키 교환에서 하이브리드는 "둘 중 하나만 안전해도 OK"라서 보험 역할을 하는데, 인증에서는 두 서명을 다 검증해야 하니까 복잡도만 올라가요. Valsorda는 2년간 Kyber 실전 배포 경험이 충분한 신뢰를 줬다고 보고, 인증에서만큼은 하이브리드를 버리자는 입장이에요.
• store-now-decrypt-later 공격이 파일 암호화에서 특히 위험한 이유가 있어요. 키 교환은 실시간이라 양자 컴퓨터가 나오기 전에 마이그레이션하면 되지만, 이미 암호화된 파일은 지금 당장 수집해뒀다가 나중에 깨면 되거든요. 그래서 파일 암호화 쪽이 타임라인 압박이 더 큰 거예요.
• TEE 마이그레이션이 유독 어려운 건 하드웨어 수준의 문제라서 그래요. 소프트웨어 라이브러리는 업데이트하면 되지만, SGX나 SEV-SNP의 증명 루트 키는 칩에 박혀있거든요. 하드웨어 교체 주기가 3~5년이니까, 지금 당장 PQ 버전 칩을 설계해도 전체 교체까지는 시간이 부족할 수 있어요.