RSA 서명 위조, 5개월 만에 1024비트 뚫렸다
Forging 1024-bit RSA signatures in nearly SNFS time [pdf]
RSA 보안은 소인수분해 난이도에 기반한다고 알려져 있지만, 2007년 Joux–Naccache–Thomé 알고리즘을 구현하면 서명 오라클에 일시적으로 접근한 뒤 키를 소인수분해하지 않고도 서명을 위조할 수 있다. 1024비트 RSA 공격에 1380 CPU 코어-년과 2^32회의 오라클 질의가 소요됐고, 사전 계산 후에는 오프라인에서 180 코어-년으로 임의 서명을 위조할 수 있었다. HSM을 오라클로 사용한 이 공격은 1024~4096비트 RSA의 실질 보안 강도가 기존 추정보다 15~30비트 낮으며, 4096비트조차 128비트 보안을 충족하지 못함을 보여준다.
1024비트 RSA는 일반적으로 80비트 보안을 제공하는 것으로 간주되지만, 우리가 구현한 알고리즘은 1024비트 RSA에 대해 2^65의 실행 시간을 가진다고 추정한다.