RSA 개인 키의 비트가 무작위가 아니라 0에 심하게 치우쳐 있을 때, 공개 키에서 그 편향을 감지하고 다항식 기반 기법으로 빠르게 인수분해할 수 있다. 실제 인터넷 데이터에서 수백 개의 취약한 키를 찾아내고, 그 원인이 된 CompleteFTP의 버그와 시간에 따른 확산 양상을 분석했다.
RSA 개인 키의 비트가 무작위로 생성되지 않고 0에 심하게 치우쳐 있다면 무슨 일이 일어날까요? 공개 키의 비트도 우리가 실제 인터넷 환경에서 잘못 생성된 이러한 키를 탐지할 수 있을 만큼 충분히 치우쳐 있을 수 있습니다. badkeys 프로젝트의 Hanno Böck과 함께, 우리는 이런 성질을 가질 뿐 아니라 빠르게 인수분해할 수 있는 수백 개의 고유 키를 발견했습니다. 또한 이러한 키 다수를 만들어낸 버그도 찾아냈고, 과거 데이터를 분석해 시간이 지나며 이 문제가 어떻게 나타났는지도 추적했습니다. 놀랍게도 0 비트의 패턴은 종종 매우 구조적이어서, 그 패턴을 악용하는 강력한 다항식 기반 암호해석 기법을 개발할 수 있었습니다.
그림 1: 실제 사례에서 관찰된, 0 비트 블록이 반복되는 두 가지 RSA 모듈러스 패턴.
이러한 “반소매” 키는 0 비트가 큰 정수의 limb를 완전히 덮지 않는 모습에서 이름이 붙었으며, 대체로 두 가지 패턴으로 나뉘었습니다. 패턴 1은 여전히 원인이 밝혀지지 않았지만, 패턴 2는 오래된 버전의 CompleteFTP 파일 전송 소프트웨어에 있던 큰 정수 코드의 형식 불일치로 추적되었습니다. CompleteFTP 버그는 취약한 반소매 DSA 키도 생성했으며, 우리는 인터넷 스캔을 통해 603개의 고유한 RSA 개인 키와 74개의 DSA 키를 복구했습니다. 2016년 12월부터 2023년 12월 사이에 CompleteFTP를 사용해 호스트 키를 생성했다면, CompleteFTP는 키를 다시 생성해야 하는지 확인할 수 있는 도구를 공개했습니다.
badkeys 프로젝트는 공개 키의 알려진 취약점을 검사하는 오픈소스 서비스입니다. 이 도구를 개발하는 동안 Hanno는 Certificate Transparency 로그, 인터넷 전반의 TLS 및 SSH 스캔, PGP 키 등 공개 출처에서 실제 환경의 키를 대량으로 수집했습니다. 우리는 이 데이터셋에서 예상외로 희소한 RSA 모듈러스를 검색했고, 그 결과 그림 1의 패턴을 가진 많은 키가 실제 인터넷 환경에 존재한다는 사실을 밝혀냈습니다.
두 패턴 모두 겉보기에 무작위인 데이터 사이에 일정한 간격으로 배치된 여러 개의 전부 0인 블록을 포함합니다. 패턴 1은 Yahoo와 Verizon을 포함한 여러 대형 조직에 발급된 인증서의 CT 로그와 일부 NetApp 소프트웨어 실행 장치에서 나타납니다. 다행히 이 인증서들은 이미 만료되었지만, 우리는 여전히 이 회사들에 조사 결과를 공유했습니다. 어떤 제품이 이런 키를 생성했는지 더 알고 싶었지만, 답변을 받지는 못했습니다. 패턴 2는 EnterpriseDT의 CompleteFTP 소프트웨어를 실행하는 SSH 호스트에서 나타납니다. 근본적인 취약점은 10.0.0–12.0.0 버전(2016년 12월–2019년 3월)으로 생성된 RSA 키와 v10.0.0–23.0.4(2016년 12월–2023년 12월)로 생성된 DSA 키에 영향을 줍니다.
이 취약점들은 인터넷상의 소수 호스트에만 영향을 미치지만, 더 흥미로운 교훈은 서로 독립적인 암호 구현들이 비슷한 방식으로 실패했다는 점입니다. 더 많은 구현에도 같은 버그가 있을 수 있으므로, 이런 특정 유형의 실패에 맞춘 암호해석 알고리즘을 개발할 가치가 있습니다.
암호 알고리즘은 종종 수백 비트에서 수천 비트 길이의 정수를 필요로 하며, 이러한 “큰 정수”는 limb 라고 부르는 더 작은 기계 단위 값의 배열로 표현됩니다. 패턴 1을 128비트 limb의 수열로, 패턴 2를 32비트 limb의 수열로 해석하면, 반복되는 0 블록은 각 limb 안의 하나의 0 블록에 대응합니다. 각 limb는 연속된 작은 부분집합만 무작위 비트로 채워지고 나머지는 드러나 있으므로, “반소매 키”라는 별명이 붙었습니다.
이러한 모듈러스의 limb에 있는 수학적 구조를 이용하면, 어려운 정수 인수분해 문제를 쉬운 다항식 인수분해 문제로 바꿀 수 있습니다. 즉, 미지의 인수 와 를 갖는 모듈러스를 취해, 이를 작은 계수를 갖는 다항식으로 표현하고, 와 로 인수분해한 뒤, 이 인수들을 와 로 변환합니다. 정수와 다항식 사이를 변환하는 기법은 빠른 다항식 곱셈을 포함해 널리 쓰이지만, 안타깝게도 이를 빠른 정수 인수분해에 사용하는 방법을 설명하는 자료는 많지 않습니다.
구체적으로는, 정수의 밑수- 표현에서 각 자릿값을 사용해 다항식의 계수를 정합니다. 일반적인 10진 표현에서는 10의 거듭제곱을 의 거듭제곱으로 바꾸는 셈이고, 다항식을 다시 정수로 바꾸는 과정은 의 거듭제곱을 10의 거듭제곱으로 바꾸는 것입니다. 수학적으로, 정수의 밑수- 표현은 다항식 에 대응하고, 다항식 값 계산은 이를 다시 정수로 변환합니다. 반소매 키에서는 밑이 limb 크기에 대응하며, 각 limb의 추가 0 비트는 예외적으로 작은 계수를 갖는 다항식으로 이어집니다.
그림 2: 0 비트 블록을 가진 정수는 작은 계수를 가진 다항식으로 표현할 수 있다.
정수를 다항식으로 표현하는 이 방법이 유용한 이유는 값 계산의 곱이 곱의 값 계산과 같기 때문입니다 . 값 계산은 단지 를 로 치환하는 것뿐이므로, 이 치환이 곱셈 전이든 후이든 상관없습니다. 덧셈도 마찬가지입니다.1
-bit limb를 갖는 반소매 RSA 모듈러스의 경우, 밑수- 표현을 사용하면 예외적으로 작은 계수를 갖는 다항식을 찾을 수 있습니다. 만약 와 도 예외적으로 작은 계수를 갖는다면, 입니다. 올바르게 생성된 소인수의 경우 와 는 일반적으로 -bit 계수를 갖는다는 점에 유의하세요. 그래서 이 공격은 일반적으로는 통하지 않습니다.
다항식 인수분해는 쉽기 때문에, 를 인수분해하여 와 를 얻은 다음, 이 인수들을 에서 평가해 와 를 구할 수 있습니다. 이것이 공격의 기본 형태이지만, 실제 환경의 이 모듈러스들을 인수분해하는 데 필요한 핵심 통찰 하나를 의도적으로 생략했습니다. 전체 설명은 이 글의 마지막에 있습니다.
그림 3: 특수한 형태의 다항식은 인수분해되어 RSA 개인 키를 드러낼 수 있다.
정수와 다항식의 대응은 이러한 특수 형태 모듈러스의 인수분해를 쉽게 만들지만, 흥미롭게도 일반적인 RSA 모듈러스의 인수분해에도 도움이 됩니다. General Number Field Sieve(GNFS) 알고리즘은 알려진 것 중 점근적으로 가장 좋은 성능을 가지며, 첫 단계는 가 되도록 다항식과 평가점을 선택해 수체를 정의하는 것입니다.2
Hanno가 찾은 키들에 이 기법을 적용한 뒤, 우리는 개인 인수들이 실제로 반소매 형태라는 사실을 확인했습니다. 즉, 소인수들에는 설정되지 않은 비트의 크고 규칙적인 블록이 있었습니다. 두 번째 패턴을 가진 호스트의 SSH 배너는 CompleteFTP 소프트웨어 사용을 가리키고 있었기 때문에, 우리는 취약한 키가 왜 생성되었는지 알아내기 위해 체험판 버전을 리버스 엔지니어링했습니다.
동적으로 생성된 RSA 키에는 반소매 패턴이 없었기 때문에3, 데모 바이너리의 .NET 코드를 디컴파일하기 위해 ILSpy 도구를 사용했습니다. 약간의 리버스 엔지니어링 끝에, 반소매 키를 생성한 버그를 찾아냈습니다. 다음 함수는 bignumLimbs로 표현되는 큰 정수를 원하는 비트 길이의 무작위 값으로 채웁니다. 어디가 문제인지 찾아보세요.
public void genRandomBits(int bits) {
// Calculate the number of limbs
int numLimbs = bits / 32;
// Allocate space for the RNG output
byte[] array = new byte[numLimbs];
// Call the system RNG
rngProvider.GetNonZeroBytes(array);
// Copy to the limbs of the big number
Array.Copy(array, 0, bignumLimbs, 0, numLimbs);
// Set the top bit to ensure proper bit length
bignumLimbs[numLimbs - 1] |= 0x80000000;
// Store the length
dataLength = numLimbs;
}
그림 4: CompleteFTP의 취약한 genRandomBits를 디컴파일한 코드. 명확성을 위해 여러 분기는 제거했고, 주석을 추가했다.
limb의 크기와 RNG 출력의 크기 사이에 불일치가 있습니다! 각 limb에는 32비트의 무작위 재료가 필요하지만, Array.Copy는 RNG 출력의 각 8비트 원소를 큰 정수 limb의 각 원소로 암묵적으로 형변환합니다. 반소매 키의 반복 구조는 이 문제가 각 limb에 영향을 주기 때문이고, 0 비트가 생기는 이유는 각 limb에 너무 작은 값만 복사되기 때문입니다. 이는 우리가 암호해석한 키의 패턴과 정확히 일치합니다.
또한 왜 동적 테스트에서 깨진 키가 생성되지 않았는지도 알아냈습니다. 최신 버전에서는 genRandomBits 함수가 컴파일되어 포함되어 있었지만 도달 불가능했습니다. 오래된 버전들은 이 취약한 함수를 호출하는 자체 작성 키 생성 코드를 사용했고, 이후 표준 .NET 암호 API를 사용하도록 리팩터링되었습니다.
우리는 CompleteFTP의 더 오래된 버전을 리버스 엔지니어링해 genRandomBits에 대한 다른 호출을 찾았고, DSA 키 생성도 영향을 받았음을 발견했습니다. 160비트 DSA 개인 키는 이전에 이 함수로 생성되었고, 공개 키와 매개변수에는 생성기 와 목표 가 포함됩니다. 개인 키는 쉽게 복구할 수 있으며, 무엇을 찾아야 하는지 알고 나자 실제 환경에서도 취약한 DSA 키를 발견할 수 있었습니다.4
v12.1.0부터 CompleteFTP는 .NET의 RSACryptoServiceProvider를 사용해 RSA 키를 생성하고, v23.1.0부터는 DSA.Create API를 사용해 DSA 키를 생성합니다.
표준 라이브러리를 사용하도록 키 생성 코드를 리팩터링하기로 한 결정은 영향 범위를 크게 완화했습니다. 이는 실제로 데이터에도 반영됩니다. Nadia Heninger 교수는 우리가 깨진 SSH RSA 서명을 찾는 데 사용했던 과거 및 현대 SSH 스캔의 대규모 컬렉션을 보유하고 있어서, 저는 그 데이터에 CompleteFTP 호스트가 포함되어 있는지 확인했습니다. 각 IPv4 전역 스캔에는 보통 수백 개의 CompleteFTP 호스트가 있었고, 과거 스캔을 릴리스 이력에 맞춰 정렬해 보니 추세는 분명했습니다.
그림 5: 시간이 지날수록 취약한 소프트웨어를 실행하는 CompleteFTP 호스트 수는 줄어들지만, 여전히 상당한 비율이 취약한 키를 사용한다.
2016년 12월 RSA 취약점이 도입된 시점부터 취약한 키를 가진 호스트 수는 꾸준히 증가했고, 재작성된 RSA 코드가 2019년 3월에 릴리스되자 이 추세는 즉시 멈췄습니다. 그러나 그 이후 영향을 받는 버전을 실행하는 호스트 수는 꾸준히 감소했음에도, 영향을 받는 키의 비율은 정체 상태에 머물렀습니다. 이는 소프트웨어는 정기적으로 업데이트하지만 키는 한 번만 생성하는 고객들의 행동과 일치합니다.
EnterpriseDT 팀은 공개 과정 전반에 걸쳐 매우 신속하게 대응했습니다. 이러한 사용자들을 돕기 위해 EnterpriseDT는 2026년 5월 8일 CompleteFTP v26.1.0을 출시했고, 이 업데이트는 시스템이 취약한 RSA 또는 DSA 키를 사용하는지 자동으로 점검해 키를 다시 생성해야 하면 사용자에게 경고합니다. 또한 같은 기능을 하는 독립형 도구도 공개했습니다. 추가로, badkeys 웹사이트와 독립형 도구도 이제 취약한 반소매 RSA 키 탐지를 지원합니다.
전체적으로 우리는 CompleteFTP의 취약한 버전으로 생성된 603개의 고유한 RSA 공개 키와 74개의 DSA 키에 대한 개인 키를 복구했고, 정체를 알 수 없는 반소매 패턴을 가진 RSA 키 26개도 복구했습니다. 우리의 데이터 출처는 RSA SSH 키에 크게 편향되어 있으므로, 이 숫자가 실제 유병률을 반영하는 것은 아닙니다.
안타깝게도 우리는 반소매 패턴 1에 대해 더 많은 정보를 가지고 있지 않으며, 그 취약점이 다른 키 유형으로 확장되는지도 알지 못합니다. 암호해석 알고리즘은 흔히 불규칙한 간격으로 배치된 알려진 비트 블록의 지식을 이용합니다(ECDSA5와 RSA6를 포함). 그러나 반소매 누출의 규칙적인 간격은 새로운 구조를 추가하며, 이 성질을 활용할 수 있는 강력한 변형 알고리즘이 있을지도 모릅니다. 이런 유형의 누출이 RSA의 두 독립 구현에서 나타났다면, 세상에는 더 많은 반소매 키 사례가 있을 가능성이 큽니다.
이번 경우 취약점의 영향은 다행히 제한적이지만, 실용적 연구의 힘을 잘 보여줍니다. 알려진 취약점에서 영감을 받아 더 강력한 알고리즘을 만들고, 그런 알고리즘을 사용해 새로운 취약점을 찾아내는 과정은 암호해석에서 강력한 피드백 루프를 형성합니다. 이는 실제 암호 시스템이 현실에서 어떻게 실패하는지 이해하는 데 도움을 주며, 시스템이 어떻게 깨지는지 관찰해야만 그것을 더 안전하게 만드는 방법을 배울 수 있습니다.
이 프로젝트를 위해 Hanno를 소개해 주고 SSH 스캔을 사용할 수 있게 해 준 Nadia Heninger께 감사드립니다. 이 스캔은 Zakir Durumeric이 제공한 Censys 및 미시간 대학교의 과거 데이터와 Kevin He 및 George Sullivan의 현대 데이터 및 분석 스크립트로 구성되어 있습니다.
이 마지막 절은 공격을 구현하거나 공격이 동작한다는 증명을 작성하고 싶은 분들을 위한 것입니다. 본문에서는 핵심 세부 사항 일부를 생략했지만, 다음의 유도 질문들이 그 간극을 메우는 데 도움을 줄 것입니다. 먼저, 인수분해할 전체 모듈러스는 다음과 같습니다. 이 값들은 합성적으로 생성되었지만, 실제 환경의 키와 같은 패턴을 따릅니다. 의 인수는 결과가 소수가 될 때까지 반복문에서 genRandomBits(1024)를 호출해 생성했습니다.
n_1=0xc889f7ef523b08e400000000000000014d2ee8284c7a03c000000000000000012c16eeaeab96ddc8000000000000000201036d671407a06600000000000000022f743377005a840d0000000000000001e8e3c0efdd8054ba000000000000000306ee98c677dfdf190000000000000002de525d2b1011ceae0000000000000424455c59eec3a0654500000000000003f8d762d68bcbe8cc3a00000000000000d31291f9aaa7e9a7d60000000000000337a82a59342aadff570000000000000295c495b3690a69b66c00000000000000d9c5e55654e9b14cba000000000000040f0f0f7d3bfdce03d6000000000000026b89ac77db000000000000000000036a77
n_2=0x40000049000014ac8000900e00010ec58000b17b8001e0720001be890002169f80029cd5000349190003cd4480037c8c000397660003b28300041021000418cb00058a210004c2708004924980053b8780051cbd8005ebe80006bb27800765e6800651478007f62300073949800860950008614d800863988008d103800884c100099a260009a6d90009578f0007e84300080db800072e59000724f10007c0ec0006ec6600062231000605930005ca4c000566cc0005da92000574dd00040bf1000457dc0004cfbe0004c5640003fe6d0003ada60002de110002cbb30002d5a6000243840001cdf40001a8a9000151be000113f4000101070000acdf000029e5
수학적으로 말하면, 값 계산 사상은 환 준동형입니다.↩︎
더 정확히 말하면, 현대 인수분해 구현은 이 기법의 일반화를 사용합니다. 이들은 가 선형이고 가 의 작은 배수가 되도록 하는 다항식 쌍을 찾습니다. 가 monic인 특수한 경우에는 입니다.↩︎
Linux용 CompleteFTP RSA 키 생성에는 개인 지수가 65537로 설정되고 공개 지수가 크게 설정되는 별도의 문제가 있었습니다. 우리는 이를 공개했고, 이 문제는 v26.0.2에서 수정되었습니다. 이 도구의 Linux 버전은 다른 기능을 제공하며 Windows보다 덜 널리 사용됩니다. EnterpriseDT의 라이선스 데이터에 따르면, 그들은 이 문제로 영향을 받는 운영 환경 사용자가 없다고 보고 있습니다. 우리의 스캔도 이 주장을 뒷받침했는데, 이런 성질을 가진 키를 실제 환경에서 하나도 찾지 못했기 때문입니다.↩︎
Diffie-Hellman 키 교환도 이 취약한 함수를 사용했지만, 2048비트 지수를 사용했습니다. 이것은 취약하지 않으며, 이 함수를 사용한 DH 키 교환은 여전히 암호학적으로 안전하다고 우리는 믿습니다.↩︎
Hlaváč와 Rosa의 Extended Hidden Number Problem and Its Cryptanalytic Applications는 임의 위치에 여러 개의 미지 비트 블록이 있는 (EC)DSA nonce 문제를 다룹니다.↩︎
Herrmann과 May의 Solving Linear Equations Modulo Divisors: On Factoring Given Any Bits는 인수 중 하나에 여러 개의 연속된 미지 비트 블록이 있을 때 RSA를 인수분해하는 문제를 다룹니다.↩︎