개인 키 복구 없이 서명을 위조하는 New Attack Against RSA

RSA 연구진이 공개 모듈러스를 인수분해하거나 개인 키를 복구하지 않고도 1,380 CPU 코어년을 투입해 1024비트 서명 위조를 완료했다.

이 결과는 New Attack Against RSA에 눈길을 끄는 제목을 안겨주지만, 그 기반 알고리즘은 2007년에 나온 것이다. 실제 진전은 이론적 방법을 전면적인 계산으로 완성한 구현에 있다.

이 구분이 중요한 이유는 이 공격이 모든 RSA 배포 환경을 무력화하는 것은 아니기 때문이다. 이 공격은 일시적으로 원시(raw)·비패딩 RSA 연산에 접근할 수 있는 시스템을 겨냥한다. 표준화된 인코딩을 사용하는 현대적 서명은 입증된 공격 모델의 범위 밖에 있다.

Bruce Schneier의 공격 평가는 핵심적인 관점 전환을 잘 보여준다. 이는 실제 암호해석 성과이지만, RSA 개인 키를 추출하는 범용 기술은 아니다.

New Attack Against RSA에서 실제로 달라진 점

연구진은 그동안 간과돼 온 2007년 알고리즘을 실제 서명 대상에 대한 완성된 1024비트 서명 위조로 구현했다.

Laura Shea, Miro Haller, Adam Suhl, Nadia Heninger, Emmanuel Thomé는 UC San Diego와 Inria가 참여한 협업을 통해 이 공격을 구현했다. 이들의 1024비트 계산은 2026년 8월 31일에 완료됐다.

연구팀은 9월에 논문과 지원 코드를 공개했다. 공개 자료는 이 작업을 거의 special number field sieve 시간 복잡도로 수행한 서명 위조라고 설명한다.

이 명칭은 공격의 점근적 성능을 가리킨다. number field sieve는 큰 정수의 인수분해를 포함해 어려운 정수론 계산을 처리하는 알고리즘 계열이다.

일반 number field sieve, 즉 GNFS는 일반적인 RSA 모듈러스를 인수분해하는 데 알려진 가장 빠른 고전적 방법이다. special number field sieve, 즉 SNFS는 기반 문제가 활용 가능한 대수적 구조를 가질 때 더 나은 성능을 낸다.

새 구현은 사실상 공격의 일부를 더 빠른 범주로 옮긴다. 그렇다고 RSA 암호해석이 쉽거나 다항 시간에 풀리는 문제가 되는 것은 아니다.

연구진은 계산에 1,380 CPU 코어년이 소요됐다고 보고했다. 병렬 처리는 이 전체 작업량을 학술용 컴퓨팅 클러스터에서 수개월의 실제 경과 시간으로 줄였다.

여전히 상당한 규모의 작업이다. 그러나 연구팀은 같은 1024비트 모듈러스를 인수분해하려면 50만~100만 CPU 코어년이 필요할 것으로 추정한다.

이 추정치를 보편적인 금전 비용으로 직접 환산할 수는 없다. 하드웨어, 소프트웨어, 메모리, 네트워킹, 구현 선택이 모두 실제 운영 비용에 영향을 미친다.

그럼에도 핵심 기술적 결과는 분명하다. 요구되는 오라클 조건에서 RSA 서명을 위조하는 데는 관련 모듈러스를 인수분해하는 것보다 훨씬 적은 계산이 필요할 수 있다.

오라클은 공격자가 선택한 입력에 대해 암호 연산을 수행하고 결과를 반환하는 시스템이다. 여기서 공격자는 원시 RSA 서명 또는 복호화 연산에 일시적으로 접근해야 한다.

이 접근이 영구적으로 유지될 필요는 없다. 공개 키와 연결된 대규모 사전 계산을 완료하면 공격자는 추가 유효 출력을 생성할 수 있는 오프라인 능력을 얻는다.

이러한 지속성은 결과를 단순한 서명 서비스 오용보다 더 중요하게 만든다. 공격자는 원래 오라클에 대한 접근을 잃은 뒤에도 위조 능력을 보유할 수 있다.

연구팀의 연구진 설명 자료는 이 능력이 실질적 효과 면에서 비밀 키 탈취와 유사하다고 말한다. 이는 실제 개인 인수가 복구됐다는 뜻은 아니다.

연구진은 구현과 중간 데이터도 공개했다. 이러한 투명성 덕분에 다른 암호학자들은 가정을 재현하고, 엔지니어링 결정을 검토하며, 제안된 대응책을 시험할 수 있다.

따라서 뉴스가 되는 사건은 완성된 실행 자체다. 이를 가능하게 한 수학은 거의 19년 전부터 공개돼 있었다.

2007년 알고리즘이 지금 중요한 이유

이 구현은 새로운 수학적 지름길을 제시하지는 않지만, 특정 공격 모델에서 RSA의 보안 추정치를 바꾼다.

Antoine Joux, David Naccache, Emmanuel Thomé는 2007년 논문에서 기반 기술을 설명했다. 이들은 RSA 수에 대한 특정 근을 계산하는 일이 그 수를 인수분해하는 것보다 언제 쉬워지는지 연구했다.

단순화하면, RSA는 합성수에 대한 모듈러 지수 연산을 적용한다. 개인 연산은 비밀 키를 모르면 계산 불가능해야 하는 근을 구한다.

2007년 연구는 선택된 오라클 응답이 더 빠른 공격에 필요한 충분한 구조를 드러낼 수 있음을 보였다. 저자들은 선택적 위조부터 범용 위조 능력까지의 결과를 설명했다.

이 결과가 공격자가 일반 RSA 공개 키를 수동적으로 관찰한 뒤 즉시 서명을 위조할 수 있다는 뜻은 아니었다. 신중하게 구성된 개인 키 연산에 반복적으로 접근해야 했다.

2026년 전까지 누구도 1024비트 규모에서 전체 과정을 공개적으로 입증하지 못했다. 대규모 암호해석 계산에는 논문에 적힌 복잡도 식 이상의 것이 필요하다.

연구진은 적절한 다항식 선택을 구축하고, 관계식을 수집하며, 방대한 데이터셋을 처리하고, 희소 선형대수를 수행한 뒤 최종 재구성을 완료해야 한다. 작은 비효율도 수개월의 작업에 걸쳐 증폭될 수 있다.

새 연구팀은 이러한 단계를 연결해 1024비트 대상에서 결과를 입증했다. 구현의 상당 부분은 number field sieve 계산을 위한 확립된 소프트웨어 모음인 CADO-NFS를 기반으로 한다.

이론과 구현의 차이는 New Attack Against RSA의 핵심이다. 알고리즘은 알려져 있었지만, 실제 상수와 엔지니어링 요구 사항은 불확실한 상태로 남아 있었다.

완료된 계산은 이러한 미지수를 근거로 바꾼다. 위조와 인수분해의 계산상 격차가 단지 점근적 호기심에 그치지 않음을 보여준다.

입증된 대상에서 연구진은 공격 비용을 약 2^65 연산으로 추정한다. 이는 유사한 1024비트 RSA 모듈러스를 인수분해하는 데 필요한 약 2^80 작업과 대비된다.

더 큰 키에 대해서는 취약한 오라클 모델 아래 2048비트 RSA를 공격하는 데 약 2^90, 4096비트 RSA에는 약 2^119의 작업이 필요할 것으로 추정한다.

이러한 더 큰 공격은 완료되지 않았다. 이는 알고리즘, 측정된 구현 성능, 예상되는 확장 거동에서 도출한 전망치다.

보안 강도는 시스템을 무너뜨리는 데 필요한 예상 작업량을 측정하므로, 이 전망은 주목할 가치가 있다. NIST는 S비트 보안 강도를 대략 2^S회의 기본 연산으로 정의한다.

다만 이 수치는 RSA 키의 모든 사용이 아니라 노출된 구성에 적용된다. 프로토콜의 인코딩, 접근 제어, 속도 제한, 키 수명은 모두 실질적 보안의 일부로 남는다.

비교에도 맥락이 필요하다. 2^90 계산은 바람직한 이론적 여유보다 낮더라도, 완료된 1024비트 실험보다 압도적으로 어렵다.

연구진은 이것이 2^80 계산보다 약 1,000배 더 많은 작업을 요구할 것이라고 말한다. 아직 어느 공개 연구팀도 이에 상응하는 1024비트 인수분해 작업을 완료하지 못했다.

그러므로 이 결과는 현재 운영 시스템보다 보안 모델에 더 큰 압박을 가한다. 설계자는 더는 인수분해가 항상 원시 RSA 연산에 대한 최선의 공격 추정치를 제공한다고 가정할 수 없다.

이러한 수정은 하드웨어 보안 모듈, 블라인드 서명 프로토콜, 특수 인터페이스에 중요하다. 이 시스템들은 때때로 개인 RSA 연산을 노출하면서도 그것이 승인할 수 있는 범위를 제한하려 한다.

주변 프로토콜이 필요한 오라클을 제공하면 GNFS에만 기반한 키 길이 추정은 보안을 과대평가할 수 있다. 이 구현은 설계자에게 그러한 분석을 수정할 구체적인 이유를 제공한다.

New Attack Against RSA는 키 복구가 아닌 위조다

이 공격은 선택 입력 조건에서 서명 기능을 무력화하지만, 공개 정보로부터 RSA 개인 키를 도출하지는 않는다.

RSA 키에는 공개 모듈러스와 지수, 그리고 모듈러스의 비밀 소인수에서 파생된 개인 값이 포함된다. 전통적인 인수분해 공격은 이 소인수를 찾는다.

이를 복구하면 공격자는 실제 개인 키를 얻는다. 그 키는 프로토콜 세부 사항에 따라 영향을 받은 RSA 구성에서 승인되는 모든 연산을 지원할 수 있다.

이 서명 위조 기법은 다른 경로를 따른다. 원시 RSA 오라클의 응답을 이용해 이후 근 계산을 지원하는 데이터를 준비한다.

공격자는 패딩되지 않은 개인 키 연산을 수행하는 장치나 프로토콜에 일시적으로 접근하는 것으로 시작한다. 공격자는 특별히 선택한 많은 값을 제출하고 응답을 기록한다.

그런 다음 사전 계산은 number field sieve 변형을 사용해 대수적 관계를 찾는다. 충분한 관계가 수집되면 공격자는 이를 결합해 선택한 출력을 위조할 수 있다.

비용이 큰 계산의 대부분은 공개 키에 의존한다. 이 단계를 마치면 개별 위조를 생성하는 비용은 크게 낮아진다.

방어자 관점에서 결과는 개인 키 탈취와 비슷하게 보일 수 있다. 권한 없는 당사자가 진짜 공개 키로 검증되는 서명을 생성할 수 있기 때문이다.

하지만 메커니즘과 범위는 여전히 다르다. 공개 모듈러스는 인수분해되지 않았고, 개인 지수도 반드시 재구성된 것은 아니다.

이 구분은 사고 대응에 영향을 미친다. 영향을 받은 키를 교체하면 일반적인 침해 이후와 마찬가지로 해당 공개 키에 의한 향후 검증을 중단할 수 있다.

취약성 평가에도 영향을 준다. 필요한 원시 서명 인터페이스가 없는 시스템은 RSA 인증서를 사용한다는 이유만으로 취약해지지 않는다.

이 연구를 “RSA 키”의 파괴라고 부르면 이러한 경계가 흐려질 수 있다. 이는 인증서나 공개 키만으로 시작하는 수동적 공격을 암시할 수 있다.

입증된 공격에는 더 많은 것이 필요하다. 공격자는 선택된 원시 RSA 결과를 제공하는 상호작용형 소스와, 그 소스가 사라지거나 키가 교체되기 전 충분한 질의가 필요하다.

연구진의 전체 논문은 기여를 거의 SNFS 시간에 서명을 위조한 것으로 규정한다. 이 표현은 결과와 복잡도 개선을 모두 정확하게 식별한다.

이는 또 다른 흔한 오해도 막아준다. 준지수 시간은 다항 시간, 즉각적 처리, 또는 저비용을 뜻하지 않는다.

다항 시간 알고리즘은 입력 크기의 고정된 거듭제곱에 따라 확장된다. 준지수 알고리즘은 다항 시간 알고리즘보다 빠르게 증가하지만, 완전 지수 알고리즘보다는 느리게 증가한다.

SNFS와 GNFS는 모두 준지수 범주에 속한다. 이 공격이 더 빠른 이유는 어려운 계산을 없애서가 아니라, 상수와 구조가 더 유리하기 때문이다.

완료된 실험은 GPU가 아닌 CPU를 사용했다. 연구진은 코드 최적화에 인공지능도 사용하지 않았다고 밝혔다.

연구진은 GPU와 추가 구현 작업이 성능을 개선할 수 있다고 본다. 이는 합리적인 연구 방향이지만, 이번 실험에서 측정된 결과는 아니다.

따라서 극적인 GPU 가속에 관한 주장은 여전히 추정에 불과하다. number field sieve 작업 부하에는 여러 단계가 있으며, 각 단계는 특수 하드웨어에 서로 다르게 반응한다.

입증된 벤치마크는 연구팀의 실제 구현 전반에 걸친 1,380 CPU 코어년이다. 향후 더 낮은 수치는 재현 가능한 코드와 완료된 측정에서 나와야 한다.

이것이 이 글의 핵심적인 긴장 관계다. 이 연구는 인수분해 기반 가정에서 의미 있는 이탈이지만, 범용 RSA 키 복구 방법은 아니다.

실제 노출 범위는 좁지만 0은 아니다

일반적인 패딩 RSA 서명은 이번에 입증된 공격의 대상이 아니지만, 원시 서명 인터페이스는 즉시 검토해야 합니다.

현대 RSA 서명은 일반적으로 제한 없는 메시지에 개인 지수를 직접 적용하지 않습니다. 먼저 정의된 서명 방식으로 메시지 다이제스트를 인코딩합니다.

RSASSA-PSS는 RSA 연산 전에 무작위 포맷팅을 추가합니다. PKCS #1 v1.5는 식별자와 패딩을 포함한 구조적이고 결정적인 인코딩을 사용합니다.

이러한 인코딩은 공격자가 서명을 위해 임의의 원시 정수를 선택하지 못하게 합니다. 이 제한은 새 구현에 필요한 오라클 동작을 차단합니다.

연구팀은 PSS 또는 PKCS #1 v1.5를 사용하는 일반적인 RSA 서명에는 자사의 공격이 실현 가능해 보이지 않는다고 밝혔습니다. Schneier도 같은 실무적 결론에 도달했습니다.

이는 일반적인 인증서, TLS 인증 서명, 서명된 소프트웨어, 토큰이 자동으로 노출되는 것은 아니라는 뜻입니다. 관리자는 결론을 내리기 전에 실제 알고리즘과 인터페이스를 확인해야 합니다.

키 길이만으로 취약성 여부를 판단할 수는 없습니다. 원시 서명 API 뒤에 있는 2048비트 키는 검증된 PSS 서명으로 제한된 동일한 키와 노출 수준이 다릅니다.

검토가 가장 필요한 후보는 원시 개인키 연산을 허용하는 하드웨어 보안 모듈 인터페이스입니다. 애플리케이션은 때때로 모듈 외부의 맞춤형 프로토콜을 구현하기 위해 이런 접근을 요청합니다.

이러한 유연성은 모듈이 제공하려 했던 경계를 약화시킬 수 있습니다. 개인키는 장치를 떠나지 않지만, 제공되는 연산이 서명 오라클이 될 수 있습니다.

블라인드 서명은 그 목적상 서명자에게 숨겨진 콘텐츠에 서명하는 것을 포함하므로 더 면밀한 분석이 필요합니다. 클라이언트는 메시지를 변환하고 서명을 받은 뒤 블라인딩 인자를 제거합니다.

이 설계는 프라이버시를 보존하는 인증 및 디지털 현금 애플리케이션을 지원합니다. 동시에 클라이언트가 개인키로 처리되는 값에 영향을 미칠 수 있는 인터페이스를 만듭니다.

현대 블라인드 RSA 프로토콜은 인코딩 및 검증 요구사항을 추가합니다. 현재 블라인드 서명 표준은 클라이언트가 준비한 메시지 주변에 RSA-PSS 인코딩을 사용합니다.

하지만 서명 서버는 여전히 블라인딩된 대표값에 대해 RSA 개인 연산을 수행합니다. 새 논문은 이런 인터페이스가 발급 과정에서 필요한 원시 오라클을 어떻게 노출할 수 있는지 분석합니다.

Privacy Pass는 자주 언급되는 사용 사례입니다. 이 기술은 클라이언트가 발급과 이후 사용을 연결하지 않고 서비스가 검증할 수 있는 익명 토큰을 얻도록 합니다.

Apple과 Cloudflare는 프라이버시 서비스 및 챌린지 우회 시스템에서 Privacy Pass 관련 기술을 사용해 왔습니다. 그렇다고 모든 배포가 악용 가능하다는 뜻은 아닙니다.

실제 서비스에 대한 공격이 성공하려면 올바른 구성, 안정적인 공개키, 그리고 충분한 수의 승인된 오라클 질의가 필요합니다. 운영 통제는 계산 조건을 바꿀 수 있습니다.

연구진은 2048비트 블라인드 RSA 키를 공격하려면 훨씬 더 큰 오프라인 연산과 함께 약 2^43회의 오라클 질의가 필요하다고 추정합니다.

이 질의 수는 8조 회를 넘습니다. 개인 사용자에게는 막대한 규모이지만, 대규모 분산 서비스는 비슷한 총량의 트래픽을 처리합니다.

속도 제한은 하나의 계정, 기기, 네트워크 또는 자격 증명에 연결된 요청을 제한할 수 있습니다. 악용 탐지는 비정상적으로 반복적인 발급 패턴도 식별할 수 있습니다.

키 교체는 이용 가능한 수집 기간을 줄입니다. 공격자가 충분한 응답을 모으기 전에 서비스가 RSA 키를 교체하면, 이전 질의를 새 키로 단순히 이전할 수 없습니다.

따라서 짧은 키 운용 주기는 공격자의 운영 비용을 높입니다. 그러나 수학 자체를 바꾸거나 프로토콜 수준의 방어를 완전히 대체하지는 않습니다.

연구진은 영지식 증명이 더 강력한 중기 대응책이 될 수 있다고 제안합니다. 이러한 증명은 숨겨진 메시지를 공개하지 않고도 클라이언트 입력을 제한할 수 있습니다.

더 긴 RSA 키도 공격 비용을 높이지만, 논문은 이 오라클 모델에서 그 보안 여유를 의문시합니다. 저자들은 4096비트에서도 128비트 미만의 강도라고 추정합니다.

그렇다고 공격자가 이제 4096비트 서명을 위조할 수 있다는 뜻은 아닙니다. 2^119라는 추정치는 완료된 1024비트 계산보다 여전히 훨씬 먼 수준입니다.

다만 프로토콜 설계자는 더 큰 키를 유일한 장기 해답으로 여겨서는 안 된다는 뜻입니다. 취약한 인터페이스는 더 높은 비용으로 동일한 구조적 문제를 유지할 수 있습니다.

대부분의 조직에 적절한 대응은 긴급 중단이 아니라 자산 목록화입니다. 보안팀은 RSA 키를 찾아 허용된 모든 개인키 연산을 식별해야 합니다.

암호화, 일반 서명, 블라인드 서명, 인증서 발급, 토큰 서명, 맞춤형 HSM 호출을 구분해야 합니다. 각 경로는 서로 다른 공격 표면을 노출합니다.

팀은 애플리케이션이 일반적인 모듈러 지수 연산 대신 이름이 지정된 서명 메커니즘을 요청하는지 확인해야 합니다. 또한 서명된 객체를 수용하기 전에 잘못된 인코딩을 거부해야 합니다.

현재 NIST의 키 관리 지침은 이미 최신 보호 요구사항에서 1024비트 RSA를 폐기된 것으로 취급합니다. 이번 실험은 남아 있는 배포를 제거해야 할 또 다른 이유를 제공합니다.

1024비트 원시 서명 서비스는 긴급한 개선 조치가 필요합니다. 표준 2048비트 PSS 배포는 같은 즉각적 문제에 직면하지 않지만, 더 폭넓은 마이그레이션 계획은 여전히 중요합니다.

방어자가 다음으로 주시해야 할 사항

다음 세 가지 신호는 독립적 재현, 프로토콜별 분석, 실제 구현에서 측정 가능한 변화입니다.

첫째, 암호학자들은 1024비트 계산을 독립적으로 재현하고 논문의 확장 추정치를 검토해야 합니다. 재현을 통해 보고된 비용에 모든 중요한 단계가 포함되는지 검증할 수 있습니다.

또한 예측을 강화하거나 약화할 수 있는 구현 병목 현상을 드러낼 수 있습니다. 재현 가능한 비용이 더 낮다면 노출된 원시 서명 인터페이스에 대한 우려는 커질 것입니다.

비용이 실질적으로 더 높다고 해서 개념적 결과가 사라지는 것은 아닙니다. 다만 운영상 위협을 좁히고 더 큰 키에 대한 추정의 시급성을 낮출 것입니다.

둘째, 표준화 단체와 프로토콜 설계자는 블라인드 RSA 구성에 대한 분석을 발표해야 합니다. 블라인딩이 서명자가 처리하는 대상을 바꾸는 경우 “패딩”에 관한 일반적 언급만으로는 충분하지 않습니다.

중요한 질문은 구체적인 프로토콜이 논문이 가정한 오라클 응답을 공격자에게 제공하는지 여부입니다. 질의 인증과 키 교체도 이 평가에 포함되어야 합니다.

Privacy Pass 배포는 프라이버시 목표, 반복적인 토큰 발급, 광범위하게 분산된 클라이언트를 결합한다는 점에서 특히 주목할 필요가 있습니다. 공개 설계 검토는 이론적 노출과 실제 도달 가능한 공격을 구분할 수 있습니다.

더 강력한 입력 증명을 요구하는 프로토콜 개정은 연구진의 경고를 뒷받침할 것입니다. 일반적인 배포가 필요한 오라클을 차단한다는 설득력 있는 증명은 결과의 실질적 범위를 좁힐 것입니다.

셋째, 방어자는 HSM 공급업체와 암호화 라이브러리를 주시해야 합니다. 문서, API 기본값, 감사 규칙, 사용 중단 공지는 업계가 이 결과를 어떻게 해석하는지 보여 줍니다.

HSM은 키 자료를 보호하면서도 위험한 연산을 노출할 수 있습니다. 공급업체는 원시 RSA 호출을 제한하거나, 질의 통제를 추가하거나, 메커니즘별 인터페이스를 권장할 수 있습니다.

라이브러리 유지보수자도 저수준 API를 강화할 수 있습니다. 원시 개인 지수 연산을 사용 중단하면 개발자가 실수로 노출된 서명 오라클을 구성할 가능성이 줄어듭니다.

이러한 신호 중 어느 것도 모든 RSA 인증서를 즉시 폐기할 필요는 없습니다. 입증된 공격은 수동적 관찰만으로 표준화된 패딩 서명에 도달하지 못합니다.

RSA는 암호학적으로 관련성 있는 양자 컴퓨터라는 별도의 장기 문제에도 직면해 있습니다. 이미 진행 중인 포스트퀀텀 마이그레이션 프로그램은 조직이 레거시 알고리즘 의존도를 줄일 기회를 제공합니다.

NIST는 2024년에 첫 포스트퀀텀 서명 알고리즘을 표준화했습니다. 인증서, 하드웨어, 프로토콜, 운영 도구가 함께 바뀌어야 하므로 마이그레이션에는 여전히 수년이 걸릴 것입니다.

새 공격은 시스템 전체를 재설계하지 않고 알고리즘을 교체할 수 있다는 의미의 암호 민첩성 계획을 뒷받침합니다. 호환성 테스트를 건너뛰거나 영향받지 않은 시스템을 긴급 변경할 근거는 되지 않습니다.

보안 책임자는 지금 네 가지 구체적인 질문을 해야 합니다. 아직 1024비트 RSA를 사용하는 서비스가 있는가, 원시 개인키 연산을 노출하는가, 블라인드 RSA를 구현하는가, 또는 비정상적으로 장기간 하나의 키를 유지하는가?

“예”라는 답은 프로토콜 검토, 로그 분석, 마이그레이션 일정을 촉발해야 합니다. 이미 개인키가 추출되었다는 뒷받침되지 않은 주장을 촉발해서는 안 됩니다.

RSA에 대한 새 공격은 오래된 이론적 경고를 완료된 계산으로 바꿨다는 점에서 중요합니다. 그 실질적 경계 역시 그만큼 중요합니다.

이 결과를 암호학적 가정과 인터페이스 설계를 검증하는 시험으로 다루십시오. 시스템이 어떤 연산을 노출하는지 확인한 뒤, 대응을 결정하기 전에 재현 결과와 프로토콜별 발견 사항을 추적하십시오.