양자컴퓨터를 기다리는 동안, AI가 먼저 도착했다

“AI 가 포스트양자 암호를 깼다.” 7월 말, 이 헤드라인이 보안 커뮤니티를 훑고 지나갔다. Anthropic 이 자사 모델로 NIST 포스트양자 서명 후보 HAWK-256 에 대한 키 복구 공격을 찾아냈다는 발표였다. 반응의 문법은 익숙했다. 양자컴퓨터가 나오면 모든 암호가 무너진다던 그 공포가, 주어만 AI 로 바꿔 달고 돌아온 것이다.

지난 글에서 나는 양자 공포를 분류로 해체했다. 암호는 한 덩어리가 아니고, 양자컴퓨터는 그중 한쪽만 무너뜨린다고. 이번에도 같은 도구가 필요하다. ‘깼다’ 는 동사 앞에서 멈추지 말고, 정확히 무엇이 깨졌고 무엇이 깨지지 않았는지를 갈라야 한다.

결론부터 적는다. 이번에 깨진 것은 당신이 쓰는 암호가 아니다. 깨진 것은 ‘암호가 신뢰를 얻는 속도’ 에 대한 업계의 전제다.

무엇이 깨졌나

사건의 실체는 두 건이다. 첫째, Claude 가 HAWK 격자 구조에서 자명하지 않은 자기동형사상(nontrivial automorphism) — 이론적으로는 존재 가능성이 거론됐지만 아무도 실물을 확인하지 못했던 대칭성 — 을 찾아냈고, 이를 이용해 최소 파라미터인 HAWK-256 의 공격 비용을 2^64 에서 2^38 연산으로 끌어내렸다. 유효 키 강도가 절반으로 깎인 셈이다. 둘째, 10라운드 중 7라운드로 축소된 연구용 AES-128 변형에 대한 기존 공격을, 열거 단계 하나를 통째로 제거하는 기법으로 200~800배 가속했다.

두 결과 모두 오늘의 실전 시스템에는 영향이 없다. Anthropic 스스로 발표문에서 반복해 강조한 사실이다. HAWK 은 어디에도 배포된 적 없는 심사 중 후보이고, 2^38 로 내려온 것도 최소 파라미터의 이야기일 뿐 더 큰 변형에는 여전히 비실용적이다. AES 쪽은 풀 라운드가 아닌 축소판이 대상이며, 공격은 여전히 ‘완전히 비실용적’ 이라고 명시되어 있다. 여기까지만 보면 헤드라인은 과장이다. 그런데도 이 발표는 중요하다. 왜 그런지를 보려면, 먼저 가장 흔한 오독부터 걷어내야 한다.

표준이 아니라 응시생이 깨졌다

“NIST 가 발표한 양자내성 표준이 깨진 것 아닌가.” 아니다. NIST 가 2024년 8월 확정한 표준은 ML-KEM(Kyber), ML-DSA(Dilithium), SLH-DSA(SPHINCS+) 세 가지이고, 이번 공격은 셋 중 무엇도 건드리지 않는다. HAWK 은 그 표준들과 별개로 진행 중인 ‘추가 전자서명 공모’ 의 3라운드 후보다. 합격자가 아니라 응시생이다.

그리고 응시생이 시험 도중 떨어지는 것은 이 공모의 실패가 아니라 존재 이유다. NIST 공모는 전 세계 암호학자들이 수년에 걸쳐 후보를 두들기고, 부서지는 것을 표준화 전에 걸러내는 절차다. 신약의 임상시험과 같은 구조다. 3상에서 부작용이 발견된 것은 시판된 약의 리콜이 아니라, 시판 전에 필터가 작동했다는 뜻이다.

전례도 뚜렷하다. 2022년, 4라운드까지 올라갔던 KEM 후보 SIKE 는 일반 노트북 한 대에서 한 시간 만에 고전적인 공격으로 무너졌다. 같은 해 3라운드 파이널리스트였던 서명 스킴 Rainbow 도 주말 사이에 깨졌다. 둘 다 인간 암호학자의 손으로 깬 것이고, 그때 누구도 “NIST 체계가 붕괴했다” 고 말하지 않았다. 심사가 제 일을 했다고 평가했다. 이번에 달라진 것은 단 하나다. 두들기는 손에 AI 가 합류했다는 점.

2년의 실패와 60시간의 성공

여기가 진짜 뉴스다. 표현을 정확히 할 필요가 있다. “2년 걸리던 분석이 60시간으로 단축됐다” 가 아니다. HAWK 은 공모에 제출된 이래 2년 넘게 공개 검토를 받아왔고, 문제의 automorphism 은 이론적 가능성만 거론됐을 뿐 그 기간 동안 아무도 실물을 찾지 못했다. 그러니까 이것은 단축이 아니라 반전이다. 인간 전문가 집단이 2년간 실패하던 일이, 60시간 만에 성공으로 바뀌었다.

수행 방식의 결도 눈여겨볼 만하다. HAWK 공격은 연구자 한 명의 간헐적이고 비기술적인 지시만으로 60시간 만에 나왔다. AES 쪽은 더 극단적이어서, 사흘간 실질적인 프롬프트 세 개를 받고 약 10억 토큰을 생성하며 거의 전자율로 진행됐다. 건당 API 비용은 약 10만 달러. 그리고 발표문에서 가장 흥미로운 대목은 따로 있다. AI 가 내놓은 AES 결과를 검산하는 데 인간 연구자들이 수백 시간을 썼다는 것, 그리고 Anthropic 이 “인간 연구자가 AI 산출물의 검토와 검증에서 병목이 될 것” 이라고 스스로 적었다는 것이다. 찾는 쪽은 기계가 됐고, 병목은 사람 쪽으로 넘어왔다.

다만 같은 발표 안에서 두 결과의 검산 비용이 극명히 갈렸다는 점은 따로 눈여겨볼 만하다. HAWK 공격의 검증은 상대적으로 쉬웠다. 키 복구 공격은 끝까지 실행해 키가 실제로 복구되는지 확인하면 되는, 검증 수단을 스스로 내장한 산출물이기 때문이다. 반면 AES 쪽은 논증 자체를 사람이 따라가며 재구성해야 했고, 그래서 수백 시간이 들었다. 검증 병목의 크기를 결정한 것은 AI 의 능력이 아니라 산출물이 ‘실행해서 확인 가능한 형태’ 였는지다. 이 비대칭은 암호분석 바깥의 AI 협업 전반에 걸리는 문제이지만, 그것은 다른 글에서 다룰 이야기다.

안전성은 증명서가 아니라 생존 이력이다

이 사건을 제대로 소화하려면 한 가지 사실을 정면으로 봐야 한다. 현대 암호의 안전성은 수학적으로 증명된 것이 아니다. AES 가 안전하다는 명제의 실체는 “전 세계가 사반세기 동안 두들겼는데 아직 아무도 못 깼다” 는 누적된 실패의 기록이다. RSA 도, 격자 암호도 마찬가지다. 암호학자들이 신생 알고리즘을 곧바로 신뢰하지 않는 이유가 여기에 있다. 신뢰의 단위는 증명이 아니라 ‘분석에 노출된 시간과 눈의 수’, 곧 생존 이력이다.

AI 암호분석이 건드린 것이 정확히 이 지점이다. 생존 이력이라는 신뢰의 통화는 지금까지 인간 전문가의 수와 시간으로만 발행됐다. 그런데 60시간에 10만 달러면 그 통화의 발행 속도가 달라진다. 두들김의 시계가 압축되는 것이다.

주의할 점은 이 압축이 양방향이라는 것이다. 시계가 빨라지면 약한 알고리즘은 더 빨리 부서지지만, 살아남는 알고리즘은 같은 기간에 더 많은 공격을 견딘 셈이 되어 생존 이력을 더 빨리 쌓는다. AI 망치는 신뢰를 깎는 도구이면서 동시에 신뢰를 벼리는 도구다. 화이트해커가 늘어난 회사의 보안이 나빠지지 않는 것과 같은 이치다.

그러면 PQC 로 갈아타라던 말은 유효한가

지난 글의 결론은 “공개키 영역은 PQC 로 전환하라” 였다. 그런데 갈아탈 대상인 PQC 는 신생이라 생존 이력이 얕고, AI 는 그 얕음을 빠르게 파고든다. 그렇다면 이미 확정된 PQC 표준의 신뢰도 떨어진 것 아닌가. 다음 표준을 기다려야 하나.

세 갈래로 답할 수 있다. 첫째, 이번 공격은 전이되지 않는다. 공격이 악용한 것은 HAWK 격자 고유의 대칭성이고, 확정 표준들은 다른 수학 문제(Module-LWE) 위에 서 있다. “격자 기반이 전부 위험해졌다” 가 아니라 “HAWK 의 고유 구조가 약했다” 가 정확한 서술이다. 오히려 HAWK 사례가 주는 교훈은 별개다 — 기반 문제가 견고해도 스킴 고유의 설계가 약할 수 있으며, 깨지는 곳은 대개 그 고유 설계 쪽이라는 것.

둘째, 방금 본 양방향성 때문에, 확정 표준들은 신뢰가 깎이는 게 아니라 시험이 강화되는 중이다. ML-KEM 은 2016년 공모 시작부터 8년 넘게 전 세계의 공격에서 살아남은 생존자이고, 이제 AI 의 공격까지 받으며 이력을 쌓는다. 살아남는 한, 신뢰는 예전보다 빠르게 자란다.

셋째, 기다리는 선택지는 실은 존재하지 않는다. 다음 표준을 기다리는 동안 쓰는 것은 RSA 와 ECC 인데, 이쪽은 쇼어 알고리즘 앞에서 무너지는 것이 ‘가능성’ 이 아니라 ‘예정’ 이다. 지난 글에서 다룬 Harvest Now, Decrypt Later 를 떠올리면, 수명이 긴 데이터의 노출은 이미 현재진행형이다. 결국 선택은 “검증이 덜 된 PQC 냐, 안전한 현상 유지냐” 가 아니라 “PQC 냐, 사형이 확정된 공개키냐” 다. 그래서 실무의 답은 여전히 하이브리드다. 기존 공개키와 PQC 를 병행하면, 만에 하나 PQC 쪽이 깨져도 고전적 안전성은 남는다.

언제 오느냐가 아니라 얼마나 걸리느냐

양자컴퓨터 상용화 시점 논쟁도 같은 틀에서 정리된다. RSA-2048 을 실제로 깨는 규모의 양자컴퓨터는 오류정정을 거친 논리 큐비트 수천 개, 물리 큐비트 수백만 개급이 필요하고, 전망은 대체로 2030년대 중후반에 걸쳐 있다. 그러나 방어 계획을 그 예측 위에 세우는 것은 과녁을 잘못 잡은 것이다. 기준은 ‘Q-Day 가 언제냐’ 가 아니라 ‘전환에 얼마나 걸리느냐’ 다.

대형 시스템의 암호 교체는 역사적으로 10년 단위가 걸렸다. 3DES 에서 AES 로, SHA-1 퇴출이 그랬다. 데이터 보존 연한에 전환 소요 기간을 더한 값이 Q-Day 까지 남은 시간보다 길다면 이미 늦은 것이라는 계산(Mosca 부등식)이 이 판의 기본 산수다. 각국 대응 체계가 예측이 아니라 데드라인으로 움직이는 이유다. 미국 NSA 의 CNSA 2.0 은 2033년까지 전면 전환을, NIST 는 RSA·ECC 를 2030년 비권고, 2035년 금지로 못 박았고, 한국의 범국가 암호체계 전환 계획도 2035년을 향한다. 실무 순서도 정해져 있다. 어디서 무슨 암호를 쓰는지 재고조사(인벤토리)부터, 하이브리드 적용, 그리고 어떤 알고리즘이든 교체할 수 있는 설계(crypto agility)까지.

마무리

다시 헤드라인으로 돌아가자. “AI 가 포스트양자 암호를 깼다.” 이제는 정확하게 고쳐 쓸 수 있다. AI 는 배포된 암호를 깬 것이 아니라, 배포되기 전에 걸러내는 시험장에서 인간이 2년간 못 찾던 균열을 60시간 만에 찾아냈다. 자물쇠를 딴 것이 아니라, 자물쇠 시험장의 망치를 바꾼 것이다.

망치가 빨라진 시대의 대비는 특정 알고리즘에 대한 믿음일 수 없다. 어떤 알고리즘이든 언젠가 부서질 수 있다는 전제 위에서, 부서지는 순간 갈아 끼울 수 있는 구조를 미리 갖추는 것 — 신뢰를 알고리즘이 아니라 교체 가능성에 두는 것이 대비의 실체다. 지난 글의 문장을 빌리면, 막연한 공포는 이번에도 정확한 분류 앞에서 힘을 잃는다. 무너진 것은 암호가 아니라 헤드라인이고, 남은 일은 빨라진 시계에 맞춰 전환의 순서를 밟는 것이다.