RSA 디지털 서명을 위조하는 데 필요한 자원을 크게 줄이는 공격 방법

캘리포니아 대학교 샌디에이고(UCSD) 연구진이 RSA 알고리즘에 대한 개선된 공격 기법을 개발했습니다. 이 기법을 사용하면 RSA 알고리즘의 기본 소수를 인수분해하거나 개인 키를 복구할 필요 없이 디지털 서명을 위조할 수 있습니다. 1024비트 RSA 키를 공격하는 데 필요한 연산량은 단일 프로세서 코어에서 1380년으로 추산됩니다. 연구팀은 대학의 기존 클러스터를 활용하여 5개월 만에 가짜 RSA 서명을 생성하는 데 필요한 매개변수를 결정할 수 있었습니다(이 실험에서는 AI 가속기나 GPU를 사용하지 않았지만, 이를 사용하면 연산 시간을 크게 단축할 수 있습니다). 이에 비해 기존의 인수분해 방식을 사용하면 단일 프로세서 코어에서 RSA-1024 개인 키를 복원하는 데 50만 년에서 100만 년의 연산 시간이 필요합니다.

공격을 실행하려면 권한 부여 서비스나 HSM 모듈에 접근하여 공격자가 생성한 데이터에 서명해 달라는 요청을 반복적으로 보낼 수 있어야 합니다. RSA-1024 파라미터를 얻으려면 232³²번의 요청이면 충분하고, Privacy Pass 프로토콜에서 사용되는 RSA-2048 키를 공격하려면 243⁴³번의 요청이면 충분합니다. 서명된 데이터 배열을 수신하면 파라미터 계산이라는 긴 과정이 시작됩니다(RSA-1024의 경우 약 265⁶⁵번의 연산). 이러한 파라미터가 계산되면 공격자는 어떤 데이터에 대해서든 가짜 서명을 생성할 수 있으며, 서명 하나당 단일 코어에서 약 180시간의 연산 시간을 소모하게 됩니다.

이 방법은 암호화 전에 포맷팅이나 패딩을 사용하지 않는 RSA 서명에만 적용 가능합니다. 프라이버시 패스 프로토콜에서 사용되는 것을 포함한 블라인드 서명 구현은 이 공격에 취약합니다. PKCS#1v1.5 및 RSA-PSS(TLS 및 SSH에서 사용됨)를 포함한 가장 일반적인 RSA 구현은 패딩을 사용하므로 이 공격에 취약하지 않습니다.

RSA 암호화는 큰 수를 큰 수로 나눈 나머지 연산을 이용하여 거듭제곱하는 방식에 기반합니다. 공개 키에는 모듈러스와 거듭제곱 값이 포함되어 있습니다. 모듈러스는 개인 키 소유자만 알고 있는 두 개의 임의의 소수를 사용하여 생성됩니다. 제안된 방법은 2007년에 발표된 연구를 기반으로 하며, 해당 연구에서는 비밀 인수를 알지 못한 상태에서 공개 키에 지정된 거듭제곱으로 암호화된 메시지의 근을 추출하는 것이 비밀 인수를 직접 계산하는 것보다 자원 소모가 적다는 것을 보여주었습니다.

연구진은 특수한 체 기반 숫자 필드(SNFS) 방식을 사용하여 RSA-1024 키를 해킹하는 데 필요한 연산 횟수를 265회로 줄여 최신 클러스터에 대한 실질적인 공격을 가능하게 했습니다. 2048비트 RSA 키의 경우, 해킹에 필요한 연산 횟수는 290회로 추정되며, 이는 대기업이나 정보기관에서 이론적으로 가능한 수준입니다. 4096비트 키의 경우, 해킹에 필요한 연산 횟수는 2119회로 현재로서는 현실적으로 불가능하지만, 미국 국가안보국(NSA), 미국 국립표준기술연구소(NIST), 유럽 네트워크 및 정보 보안국(ENISA)에서 권장하는 최소값인 2128회보다는 낮습니다.

출처 : opennet.ru