캘리포니아 대학교 샌디에이고 캠퍼스와 프랑스 국립 디지털 과학기술 연구소 Inria의 연구팀이, RSA의 공개 키를 소인수 분해하지 않고도 1024비트 RSA의 서명을 위조할 수 있는 공격을 대규모 계산 실험으로 실증했습니다. ucsd-hacc/NSNFSSSFSFN: 거의 SNFS-속도 서명 위조 없음 요인 분해 Nhttps://github.com/ucsd-hacc/NSNFSSSFSFNNearly SNFS-Speed Signature Forgery Sans Factoring N (NSNFSSSFSFN)(PDF 파일)https://eprint.iacr.org/2026/2131.pdf RSA는 두 개의 큰 소수를 곱하여 만든 정수를 공개 키의 일부로 사용하는 공개 키 암호 방식입니다. RSA의 안전성은 거대한 정수를 원래의 두 개의 소수로 분해하는 “소인수 분해”가 어렵다는 것을 전제로 평가되어 있으며, 키 길이별 안전성은 일반 수체 ふるい法(GNFS)에 의한 소인수 분해의 계산량을 기준으로 추정되어 왔습니다.
연구팀이 구현한 것은 수체 필터링(NFS)의 일종인 “루트-e NFS”라고 하는 알고리즘입니다. 제도 자체는 2007년에 제안된 것으로, 연구팀은 이번 실험에서 이 알고리즘을 처음 공개 구현하고, 1024비트 RSA를 대상으로 대규모 계산을 실행했습니다. 이번 제도 자체는 소인수 분해를 수행하지 않고, 일시적으로 생 RSA 서명을 이용할 수 있다는 조건으로, 이후 어떠한 서명도 위조할 수 있는 능력을 얻는 것입니다. 따라서, 특정 조건에서는 RSA의 안전성이 소인수 분해에 기반한 추정보다 낮아질 가능성이 시사되었습니다. 그러나, 루트-e NFS로 인해 RSA가 쉽게 해독된 것은 아니며, 알고리즘은 다항식 시간이라기보다는 여전히 준 지수 시간에 분류됩니다. 즉, 키의 자릿수가 커질수록 필요한 계산량이 폭발적으로 증가하는 점은 기존과 다릅니다. 그럼에도 불구하고 일반적인 RSA의 소인수 분해에 사용되는 GNFS보다 빠르고, 특별한 형태의 정수를 소인수 분해하는 특별 수체 필터링(SNFS)과 유사한 계산량으로 동작한다고 합니다.
공격에는 공개키뿐만 아니라 RSA의 서명 또는 복호화 처리 기능을 수행하는 “오라클”에 일시적으로 접근할 수 있어야 합니다. 공격자는 오라클에 임의의 입력을 제공하고, 패딩 없는 원시 RSA 연산 결과를 수신합니다. 이 쿼리에서 필요한 정보를 수집한 후에는 오라클에 대한 접근을 잃어도 서명을 위조할 수 있습니다. 공격은 사전 계산, 오라클 쿼리, 서명 위조의 3단계로 진행되었습니다. 1024비트 RSA 실험에서는 공개키에 의존하는 사전 계산에 약 1200CPU 코어년, 즉 CPU 1코어를 1200년 동안 지속적으로 작동시키는 데 상당한 계산량을 요구했습니다. 이후 오라클에 232회(약 40억 회)의 쿼리를 수행하고, 임의의 서명을 1건당 약 180CPU 코어년 동안 오프라인으로 생성할 수 있는 상태를 만들었습니다. 전체적으로 약 1380CPU 코어년을 요구했으며, 실제 소요 시간은 약 5개월였습니다.
연구팀은 실증 실험에서 비밀 키를 안전하게 보관하고 외부로부터의 요청에 응답하여 서명(署名)을 수행하는 하드웨어 보안 모듈(HSM)을 활용했습니다. 공격에서는 비밀 키 자체를 훔치는 것이 아니라, 이 HSM에 생(生) RSA 서명을 반복적으로 요청하여 필요한 정보를 수집합니다. 이후에는 HSM에 접근할 수 없게 되더라도, 임의의 서명을 위조(僞造)할 수 있다는 것이 확인되었습니다. 동일하게, 생(生) RSA 서명을 외부에서 이용할 수 있는 메커니즘에서는 이번 공격이 성립(成립)될 가능성이 있습니다. 연구팀은, 이 공격 모델에서는 “2048비트 RSA의 안전성이 기존에 예상된 112비트에서 약 90비트 상당(相當)까지 저하(低下)되고, 4096비트 RSA에서도 128비트 상당(相當)에는 도달하지 못한다”고 추정( 추정)하고 있습니다.
하지만 일반적인 RSA 서명에서는 서명 전에 데이터를 일정하게 처리하는 “패딩”이 수행됩니다. 이번 공격은 이러한 패딩을 적용하기 전의 원시 RSA 연산을 직접 활용할 수 있음을 전제로 하기 때문에, 연구팀은 “PKCS#1 v1.5나 RSA-PSS와 같은 패딩을 적용하는 오라클에서는 소인수분해와 비교하여 큰 속도 향상을 얻을 수 없다고 판단되며, 현대의 RSA 운영의 대부분에 있어 시급한 위협이 아니라고 설명하고 있습니다.”라고 설명하고 있습니다. 연구팀은 이번 결과에 대해 “RSA의 안전성을 소인수분해의 어려움만으로 평가하면, 일부 사용 방법에서는 실제보다 높게 과대평가될 수 있습니다.”라고 주장합니다. 동시에 이번 결과는 양자 컴퓨터 대응으로 나아가는 내성 암호로의 전환에 맞춰 RSA에서 완전히 벗어나야 할 이유 중 하나로 제시되었습니다.
원문 보기 | 출처: Gigazine