1977년에 발명된 RSA (Rivest Shamir Adleman)는 일반적으로 암호화뿐만 아니라 디지털 서명 생성도 할 수 있는 최초의 알고리즘이다.[1] RSA를 사용하기 위해선 암호화 키가 필요한데, 이 키는 비밀 키와 공개 키로 항상 쌍으로 구성된다. 따라서 RSA를 비대칭 키 암호 시스템이라고도 하는데, 이러한 키 쌍은 두 개의 매우 큰 소수를 기반으로 먼저 생성된다.[2] 하지만 여기서 사용되는 소수가 적절한 길이의 값인지, 그 수가 정말로 소수인지 확인하는 작업은 오늘날에도 어려운 일이다. 더욱이, RSA가 적용되는 애플리케이션마다 요구 사항이 틀리기도 하므로 이런 부분을 구현할 때는 제조사마다 혹은 적용하는 애플리케이션마다 조금씩 다르다.[3] 때때로, 애플리케이션 상 RSA가 이루어지는 시간이 적을 때는 키 쌍을 만들기 위해 가속 알고리즘을 사용하기도 하는데, 이를 ‘Fast Prime’ 이라고 한다. 이 알고리즘은 소프트웨어 기반으로 이루어지며, 하드웨어와는 전혀 무관한 알고리즘이다.[4] 사실 RSA 알고리즘만 봤을 때 문제가 없지만, 오늘 날 발견된 취약점으로 인해 Fast Prime 알고리즘이 적용되어 있다면 문제가 생긴다. 오늘은 RSA의 취약점 ROCA에 대해 알아보자.[5]

Fast Prime는 2000년부터 언급되어 10년 동안의 철저한 검토를 거친 후, 실제로 사용되었다. Fast Prime은 암호화 소프트웨어 라이브러리의 하위 부분으로, 고객이 자체적으로 개발할 수 있는 기반이 제공되는 소프트웨어다. 또한, 독일의 BSI (Federal Information Security Security)에 인증을 거친 알고리즘으로, 수학적 약점이 알려져 있지 않고, 취약한 부분이 발견되지 않아 인증 프로세스로 많이 쓰인다.[6] 즉, 해당 소프트웨어는 전자 서명 기능과 같은 보안적 인증을 요구하는 전자 상거래 등에서 광범위하게 활용된다. 이 소프트웨어는 칩으로 기능을 구현하는데 특히, 이번 취약점에 영향을 받는 업체로 Infineon Technologies AG를 들 수 있다. 그들은 이 소프트웨어를 하드웨어 칩으로 제작하여 암호화 스마트카드, 보안 토큰 및 기타 보안 하드웨어 칩에 적용하여 Microsoft, Google, HP, Lenovo, Fujitsu 등으로 우리가 많이 들어본 업체에 공급한다.[7] 이 말은 즉, 이 칩을 적용한 여러 업체가 제공하는 인증에 취약한 점이 있을 수도 있단 얘기다.

문제는 이 암호화 알고리즘에서 최근 취약점이 발견되었다는 것이다. ROCA라고 불리는 이 취약점은 암호화 라이브러리에서 RSA 키 쌍 생성을 구현할 때 문제가 발생했다. 이 취약점은 CRoCS 연구소, Masaryk University, Enigma Bridge, Ca 'Foscari University의 연구원들은 제조사의 스마트카드에서 만들어 내보내는 많은 수의 RSA 키를 검사하면서 이를 발견하게 되었다고 전했다. 그들은 RSA 비밀 키 계산을 단순화하기 위해 사용되는 Fast Prime에서 악용 수 있는 특정 알고리즘의 약점을 확인하다 발견되었다고 덧붙였다.[8]

좀 더 자세히 얘기하면, Fast Prime이 적용된 칩을 TPM 이라고 한다. TPM (Trusted Platform Module)은 하드웨어 및 소프트웨어의 인증을 위하여 PC에서 주로 사용되는 보안 마이크로 컨트롤러다.[9] Common Criteria EAL4에 따라 인증된 Infineon TPM의 경우, TPM 펌웨어에서 Fast Prime 알고리즘을 사용한다. TPM의 기본 키는 가속화되지 않은 알고리즘을 사용하여 키가 만들어지는 중에 생성되므로 영향을 받지 않는다. 하지만 디스크 드라이브 암호화 목적으로 TPM 자체에서 생성된 RSA 키가 노출될 수 있다.[10] 즉, 공개 키가 알려질 수도 있단 이야기다. 특히나, 상대방이 장치에 물리적으로 접근하거나 원격 공격이 먼저 활용되는 경우에 말이다.

이 취약점이 트리거가 되기 위해선 전제 조건이 따랐다. 먼저, RSA를 사용하는 애플리케이션 소프트웨어는 Fast Prime 알고리즘을 사용할 수 있어야 했다. 또한, 이 알고리즘을 사용하는 칩, 카드나 토큰에서 RSA 키 쌍을 생성해야 한다는 것이 전제조건이다. 이러한 전제 조건이 만족하면 취약점이 발생하고 2048비트까지의 RSA키 길이가 암호화 강도에서 크게 약화한다는 것이다. 더욱이 RSA 암호화, 암호 해독 및 RSA 서명 생성 및 검증을 위한 소프트웨어 기능은 영향을 받지 않았다.[11][12]

그렇다면 무엇이 문제인 것일까. 발견된 알고리즘의 취약점은 RSA에서 키를 생성하는 과정에서 소수의 특정 구조로 만들어진다. 특히, 생성되는 키의 길이가 1024bit 혹은 2048bit를 포함하여 일반적으로 사용되는 키 길이를 실제로 분해할 수 있게 한다. 이를 하기 위해선 공개 키에 대한 지식만 있으면 할 수 있으므로 따로 취약한 장치에 대한 물리적인 접근이 필요하지 않다. 따라서 이 취약점은 낮은 강도의 암호나 잘못된 난수 생성기에 의존하지 않고, 그냥 취약한 칩에 의해 생성된 모든 RSA 키가 영향을 받는다고 보면 된다. 이 공격은 무작위로 선택된 1024bit RSA 키와 여러 개의 선택된 2048bit키에서 실제로 확인되었다.[13]

문제가 되는 소수 구조는 매우 큰 데이터 세트에서도 취약한 키를 빠르게 검색할 수 있게 해준다. 이 속성은 사용자가 취약점 때문에 자체 키를 평가할 수도 있지만, 잠재적인 공격자가 시간이 오래 걸리는 인수 분해를 시도할 필요 없이 사전에 선택될 수 있는 인수 분해에 사용될 취약한 키를 찾을 수 있다. 1024bit 혹은 2048bit 키의 인수 분해에 대한 최악은 최근 CPU의 단일 코어에서 각각 3 CPU-month 및 100 CPU-years 미만이며, 예상 시간은 최악의 경우의 절반으로 줄어버린다. 인수 분해는 여러 CPU에서 쉽게 병렬화될 수 있는데, 만약 k개의 CPU를 사용할 수 있다면, 공격에 필요한 시간을 단축할 수 있다. 다만 이 인수 분해 공격의 어려움은 모든 열쇠 길이에 대해 같게 적용되지 않고 일정하게 증가하지 않는다는 것이다. 즉, RSA의 긴 키는 보안이 더 강할 것이라 생각되지만 사실은 오히려 짧은 키가 더 보안을 강화시킨다.[14]

이처럼 공격자는 취약점을 통해 공개 키의 값으로부터 RSA 개인 키를 계산할 수 있다. 비공개 키는 합법적인 소유자의 명의도용, 민감한 메시지의 해독, 서명 위조 등 기타 관련 공격에 악용될 수도 있다는 이야기다. 취약점이 실제로 미치는 영향은 이 취약점이 사용되는 시나리오나 공개 키 가용성, 사용된 키 길이에 따라 조금씩은 다르다. 하지만 이는 이미 전자 서명, 인증 토큰, 부팅 장치, 소프트웨어 패키지 서명, TLS / HTTPS 키, PGP 등 다양한 곳에서 사용되고 있으며, 이처럼 취약한 키를 찾아본 결과, 현재 확인된 취약한 키의 수는 약 760,000개이고 최대 2~3 개의 키가 더 취약할 수도 있다.[15]

이 같은 취약점이 발견되고, 이 소프트웨어가 적용되어 현재 서비스되고 있는 것들에 대해 여러 연구가들의 우려가 섞인 말이 나왔었다. 그 도마 위에 올라온 것은 독일의 Infineon Technologies가 만든 보안 하드웨어다. 특히, 그들이 만든 보안 하드웨어 칩을 두고 여러 연구가는 안전하지 않다라는 견해차가 컸다. 이에 최근 스페인에서 이와 관련하여 스마트카드 사용에 대한 어려움이 보이고 있는 것 같다.[16] 스페인에서 사용되는 DNIe ID 카드에는 신분증과 전자 서명을 위한 두 개의 인증서가 포함된 칩이 있고, 해당 취약점에 대상이 된다는 것이다. 따라서 스페인에서만 약 6천 만개의 카드가 위협에 노출되어 있는 상황인 것이다. 하지만 해당 카드는 다양한 공공기관 및 민간 서비스에 카드를 사용된다고 하니 당장 사용 중지할 수도 없는 노릇이다. 하지만, El Pais 언론 매체에 따르면, 스페인 사람들은 몇 년 동안 공공 서비스를 약 0.02 % 정도만 사용했으니 당장 중지해도 문제가 없다고도 얘기했다.[17] 그렇다고 해서 취약점이 없어지는 것은 아니지만 복구해낼 수 있는 시간은 만들 수 있지 않을까라는 말이다.

그렇다면 어떻게 이 취약점을 발견하고 해결할 수 있을까. 먼저, 취약점이 있는 라이브러리에서 칩을 사용하는지 아는 것이 우선이다. 취약점은 칩 소프트웨어 라이브러리에 존재하고, 특정 하드웨어 배치에만 국한되지 않으므로 신뢰할 수 있는 유일한 방법은, 장치에서 RSA 키 쌍을 생성하고 제공된 도구로 공개 키를 테스트하는 것이다. 또한, 이미 사용 중인 키도 테스트하는 것이 좋을 듯하다.[18] 현재 온라인에서는 이와 같은 취약점을 테스트할 수 있는 도구를 제공하고 있으며, 취약한 키가 발견될 경우 소프트웨어를 업데이트하고, 취약한 라이브러리가 없는 장치로 교환할 것을 권하고 있다. 아래에는 취약점을 테스트할 수 있는 테스트 도구다.

• Offline testers( https://github.com/crocs-muni/roca) - 오프라인 도구를 통해 테스트
• Online testers( https://keychest.net/roca /  https://keytester.cryptosense.com)- 공개 키를 업로드 하여 테스트
• Email S-MIME/PGP tester( roca@keychest.net ) - 서명한 이메일을 보내면 취약점 분석과 함께 자동 답변해주는 테스트