Ars Technica • 1일 전

RSA 암호를 깨는 새로운 방법이 등장했다

IMP

8/10

핵심 요약

새로운 연구에서 소인수분해 없이 '서명 위조(signature forgery)'를 통해 RSA를 공격하는 방법이 발표되어 암호학계를 놀라게 했습니다. 이 방법은 필요한 컴퓨팅 자원을 수십 배 단위로 줄여 2048비트·4096비트 키의 안전성 수준도 허용 한계 이하로 떨어뜨립니다. 다만 공격은 블라인드 서명(blind-signature) 방식의 RSA에만 적용되며 당장 실질적 위협은 제한적입니다.

번역된 본문

RSA 암호 체계의 수명이 얼마 남지 않았다는 사실은 수십 년 전부터 세상에 알려져 왔다. 양자 컴퓨팅이 실용화되는 시점이 도래하면(추정은 3년에서 20년 이상까지 다양하다) RSA가 제공하는 기초적인 보안은 무너질 것이다. 새로운 연구는 양자 컴퓨터가 아닌 고전적(classical) 컴퓨팅만으로 현재의 RSA 보안 수준을 허용 불가능한 수준 이하로 떨어뜨리는 새로운 방법을 밝혀냈다. 이 발견은 일부 극단적인 사례를 제외하면 당장 실질적인 위협이 되지는 않는다. 이미 폐기 권장된 1024비트 키에 대한 공격조차 국가급 역량이나 막대한 자원을 가진 기업이 아닌 이상 거의 아무도 수행할 수 없을 만큼 많은 연산을 필요로 한다. 널리 쓰이는 RSA 구현 또한 안전하다.

그럼에도 이 연구는 암호학자들을 놀라게 했다. 소인수분해 없이 RSA 키를 깨는 새로운 방법인 '서명 위조'를 도입했기 때문이다. 마찬가지로 중요한 점은, 이 새로운 방법이 필요한 컴퓨팅 자원을 자릿수 단위(orders of magnitude)로 줄인다는 것이다.

더 이상 닿지 않는 것이 아니다

"이 결과가 동료 검토를 통과한다면 정말로 개념적 돌파가 될 것"이라고 암호학 전문가이자 Allurity의 혁신 책임자인 카르스텐 놀은 인터뷰에서 말했다. "RSA는 큰 정수를 소인수분해하는 것만큼 깨기 어려운 것으로, 적어도 지금까지는 그렇게 알려져 있었다. 이 연구자는 키를 깨지 않고도 실질적으로 RSA를 깨는 방법이 있음을 보여준다."

캘리포니아대학교 샌디에이고 캠퍼스 교수이자 주 저자인 나디아 헤닝거는 다음과 같이 설명했다:

암호학자들은 유효한 RSA 디지털 서명을 계산하는 유일한 방법은 먼저 소인수분해를 통해 개인 키를 계산한 다음 그 개인 키로 서명을 계산하는 것이라고 생각했다. 1024비트 RSA의 경우 이는 매우 비싸지만, 대형 테크 기업이나 NSA 수준의 컴퓨팅 자원이 있다면 아마 가능할 것으로 여겨졌다. 키 하나당 수천만 달러 수준의 연산 비용이 드는 것이다. 2048비트 RSA는 완전히 불가능하다고 생각됐다.

헤닝거와 다른 연구진이 고안한 키 위조 공격은 1024비트 RSA의 붕괴를 이전 예상보다 훨씬 빨리 현실적인 영역으로 가져온다. 2048비트와 4096비트 키의 경우에도 이 방법은 RSA의 보안성을 허용 불가능한 수준으로 떨어뜨린다. 미국 국가안보국(NSA), 국립표준기술연구소(NIST), 유럽 사이버보안청(ENISA)은 모든 암호 체계가 최소 128비트 이상의 보안 수준, 즉 필요한 연산량이 2^128을 넘어야 한다고 요구한다. 위조 공격은 이 수준을 1024비트, 2048비트, 4096비트 키에 대해 각각 2^65, 2^90, 2^119로 떨어뜨린다. 헤닝거의 팀은 모든 코딩을 수작업으로 했고 위조 수행에 AI나 GPU를 전혀 사용하지 않았기 때문에 이 수준은 더 떨어질 수 있다. 연구자는 이러한 도구들이 안전성 수준을 "거의 확실히" 더 낮출 것이라고 말했다.

이 공격은 RSA의 블라인드 서명(blind-signature) 구현에만 작동한다. 현재 사용되는 대부분의 RSA는 PKCS 또는 PSS 패딩을 제공한다. 이는 암호화 전에 평문에 데이터를 추가하는 형식으로, 암호문이 결정론적으로 생성되는 것을 막고 사이드 채널 등 유사 공격에 덜 취약하게 만든다. 그럼에도 일부 실제 시스템은 여전히 '블라인드 서명 RSA'(텍스트북 RSA라고도 함)를 사용한다. 가장 잘 알려진 예시는, 헤닝거에 따르면, 사용자가 신원을 노출하지 않고 인증할 수 있게 해주는 프로토콜인 Privacy Pass이다. Privacy Pass는 Apple과 Cloudflare 등 많은 기업에서 사용된다. Privacy Pass에 대한 공격은 공격자가 Cloudflare, Apple 또는 다른 조직의 서버를 침해해 2^43개의 서명을 생성해야 한다. 헤닝거는 이 요구 사항이 "많이 들리지만 Cloudflare가 공개적으로 하루 정도에 처리한다고 밝힌 네트워크 트래픽과 비슷한 규모"라고 말했다. 대부분의 Privacy Pass 구현은 키를 순환(rotate)시킨다.

원문 보기

원문 보기 (영어)

Text settings Story text Size Small Standard Large Width * Standard Wide Links Standard Orange * Subscribers only Learn more Minimize to nav The world has known for decades that the RSA cryptosystem ’s days are numbered. Once quantum computing becomes practical (estimates for that range from 3 to 20 or more years), the foundational security it provides will crumble. New research has revealed a novel method that uses classical computing to reduce the current RSA security level to an unacceptably low threshold. The finding poses little to no practical threat in the immediate term, except possibly in a few edge cases. Even applying the attack against the deprecated use of 1024-bit keys, the method requires more computation than just about anybody—short of nation-states or companies with massive resources—can achieve. Widely used RSA implementations are also safe. Nonetheless, the research has taken cryptographers by surprise because it introduces signature forgery, a new way to break RSA keys without factoring. Equally important, this novel method reduces the required computing resources by orders of magnitude. Out of reach no more “If this result holds up under peer review, it would indeed be a conceptual break-through,” Karsten Nohl, a cryptography expert and the head of innovation at Allurity, said in an interview. “RSA is as difficult to break as it is to factor large integers, at least so we thought. The researcher suggests that you can practically break RSA without cracking its key.” Nadia Heninger, a University of California at San Diego professor and lead author, elaborated: Cryptographers thought that the only way to compute valid RSA digital signatures was to first compute the private key by factoring, and then use the private key to compute the signatures. For 1024-bit RSA, this was thought to be very expensive, albeit probably doable if you have the computational resources of the large tech companies or the NSA—on the order of tens of millions of dollars of computation time for a single key. For 2048-bit RSA, it was thought to be totally out of reach. The key forgery attack Heninger and the other researchers devised brings the breakage of 1024-bit RSA into the realm of possibility much sooner than previously estimated. Even for 2048- and 4096-bit keys, the method reduces the security of RSA to unacceptable levels. The National Security Agency, National Institute of Standards and Technology , and European Union Agency for Network and Information Security require that any cryptosystem should provide a level of no less than 128 or more bits, meaning the operations required must exceed 2 128 . The forgery attack drops these levels to 2 65 , 2 90 , and 2 119 for 1024-, 2048-, and 4096-bit keys respectively. These levels may further drop because Heninger’s team did all the coding by hand and used no AI or GPUs in performing the forgeries. The researcher said these tools will “almost certainly” drop the security levels further. The attack works only against blind-signature implementations of RSA. The overwhelming majority of RSA in use today provides PKCS or PSS padding, a format that adds data to the plaintext before it’s encrypted. It prevents ciphertext from being deterministic and makes it less vulnerable to side channel and similar attacks. Still, some real-world systems continue to use blind-signature, also known as textbook, RSA. The best-known example, Heninger said, is Privacy Pass , a protocol that allows users to authenticate themselves without revealing their identity. Privacy Pass is used by both Apple and Cloudflare, among many others. An attack on Privacy Pass would require an attacker to compromise a server belonging to Cloudflare, Apple, or another organization and generate 2 43 signatures. Heninger said the requirement “sounds [like] a lot, but is on the same order of magnitude of the network traffic that Cloudflare has said publicly it handles in about a day.” Most Privacy Pass implementations rotate keys regularly, a measure that greatly reduces, but doesn’t automatically eliminate, the chances of attacker success. The technique implements a variant of the number field sieve algorithm that was invented in 2007. This “‘special’ number field sieve” is used against an “oracle,” a weakness in RSA and some other cryptosystems that gives yes-or-no answers to specific queries. By performing a massive number of operations, attackers can gather enough information to decipher the ciphertext. (Again, this technique poses no practical threat against RSA that uses PKCS or PSS padding, because they eliminate the oracle.) While factoring a 1024-bit key requires an estimated 2 80 operations and 500,000 to 1 million CPU core-years, using the sieve to forge a signature took just (as noted earlier) 2 65 operations and 1,380 core-years. The paper’s authors and other researchers stress that the new attack poses little real-world threat. It does, however, drastically lower the estimated security of textbook RSA, and it does so in a way no one knew of previously. Cryptographers have worked furiously in recent years to devise alternative cryptosystems that aren’t vulnerable to quantum computing attacks. The new attack will further increase the urgency of completely moving away from the cryptosystem. The paper authors provide an easier-to-digest explainer here . Dan Goodin Senior Security Editor Dan Goodin Senior Security Editor Dan Goodin is Senior Security Editor at Ars Technica, where he oversees coverage of malware, computer espionage, botnets, hardware hacking, encryption, and passwords. In his spare time, he enjoys gardening, cooking, and following the independent music scene. Dan is based in San Francisco. Follow him at here on Mastodon and here on Bluesky. Contact him on Signal at DanArs.82. 4 Comments

암호학 보안 RSA 양자컴퓨팅 연구