테스트 방법

전제 조건은 gcc와 취약한 버전의 OpenSSL이 설치되어 있어야 합니다.

BN_mod_sqrt()의 버그 테스트: gcc -o my_bad_sqrt my_bad_sqrt.c -lcrypto로 컴파일하고 ./my_bad_sqrt를 실행하면 영원히 멈추는 것을 확인할 수 있습니다! :D

인증서로 테스트: 명령줄에서 openssl x509 -in certs/cert.der.new -inform DER -text -noout를 실행하면 역시 멈춥니다.

루프 진입

BN_mod_sqrt() 함수는 모듈러 제곱근을 찾기 위한 Tonelli-Shanks 알고리즘을 구현합니다. 즉, 정수 a와 소수 p가 주어지면 r^2 == a (mod p)를 만족하는 r 값을 반환합니다.

취약점을 패치한 커밋을 분석해 보면 원인은 b^(2^i)==1 (mod p)를 만족하는 최소 인덱스 i를 찾는 루프이며, 여기서 b는 알고리즘에서 이전에 정의됩니다.

루프가 다음과 같이 변경되었습니다.

에서

두 번째 경우에는 변수 e에 의해 제한되는 for 루프가 있습니다. 그러나 원래 코드에는 while 루프 안에 i==e 경우에 대한 확인만 있습니다.

이 루프들은 각 반복마다 e의 새 값을 현재 i 값으로 설정하는 더 큰 루프 안에 있으므로, 다음과 같은 공격 전략을 시도합니다:

1. 외부 루프의 첫 번째 실행에서 마지막에 i=1이 되도록 합니다. 이를 위해 b^2=1 (mod p)가 필요합니다.
2. 이렇게 하면 두 번째 실행 중에 e=1이 되고, 내부 루프에 진입할 수 있다면 i==e 확인은 항상 실패합니다.
3. 항상 t != 1 (mod p)이 되도록 관리한다면 루프에 영원히 갇히게 됩니다.

처음 두 단계는 실제로 소수 p를 사용하는 "정상" 실행에서 발생할 수 있습니다. 그러나 p가 합성수이면 세 번째 단계도 충족시킬 수 있습니다!

약간의 수학

Tonelli-Shanks 알고리즘은 p - 1 = 2^e * q로 쓰며, 여기서 q는 홀수입니다. 이는 p를 법으로 하는 정수의 곱셈군의 차수이며, 값 e와 q는 실행 중에 여러 번 사용됩니다. 그러나 p가 소수가 아닌 경우 곱셈군의 차수는 p-1이 아니므로 무한 루프에 빠지는 데 도움이 됩니다.

특히 b는 b = a^q (mod p)로 초기화됩니다. 즉, p가 소수라면 b는 2의 거듭제곱 차수를 가지며, 이를 루프를 통해 찾게 됩니다.

그러나 p = r * s로 설정하면 곱셈군의 차수는 r*s-1 대신 (r-1)*(s-1) = r*s - r - s + 1이 됩니다. 알고리즘은 q 값을 사용하여 차수가 정확히 2^e인 요소 y를 얻습니다. 그러나 p가 소수가 아닌 경우 q 값은 차수에 대해 특별한 의미를 가지지 않으므로 요소 y는 p=r*s를 법으로 할 때 2의 거듭제곱 차수를 가지지 않습니다.

첫 번째 외부 루프가 끝날 때 b는 b = b*y^(e-i) (mod p)로 설정되므로, 두 번째 반복에서 내부 루프는 b^(2^i) == 1 (mod p)를 만족하는 i 값을 찾으려고 시도하지만, y가 더 이상 2의 거듭제곱 차수를 보장받지 못하기 때문에 실패합니다.

익스플로잇

익스플로잇의 숫자는 매우 간단합니다. r=17, s=41을 취하면 p = r*s = 697입니다. 이는 계산된 e와 q 값이 p-1 = 2^3 * 87이 됨을 의미합니다.

그런 다음 a=696을 선택합니다. 이는 a == -1 (mod p)이며, 초기화 시 b == -1 (mod p)가 됩니다. 이는 1단계를 충족시켜 다음 외부 루프의 e=1을 설정합니다.

그런 다음 b는 2의 거듭제곱이 아닌 차수를 가진 요소로 설정되며, 내부 루프는 b^(2^i)==1 (mod p)를 만족하는 i를 찾으려다 멈추게 됩니다.

위험한 인증서 생성

자, 이제 압축 형식으로 인코딩된 기본 점이 있는 유효하지 않은 명시적 곡선 매개변수가 포함된 위험한 인증서를 만들어 보겠습니다.

이 섹션의 파일은 certs 폴더에 있습니다.

명시적 곡선 매개변수가 있는 일반 인증서 생성

먼저 EC 개인 키를 생성해야 합니다. 대상 인증서에 명시적 곡선 매개변수를 포함시키려면 키에도 명시적 곡선 매개변수가 포함되어야 합니다.

그런 다음 편의를 위해 자체 서명된 인증서를 생성하고 DER 형식으로 출력합니다.

인증서 정보를 확인해 보겠습니다. 예상대로 명시적 곡선 매개변수가 포함되어 있습니다.

유효하지 않은 인증서 제작

이제 이러한 매개변수(Prime, A, B, Generator)의 값을 수정해야 합니다. 이 값들은 아래 방정식을 만족해야 합니다.

여기서 p는 Prime, a는 A, b는 B입니다. p, a, b는 함께 곡선을 결정합니다. 점의 압축을 푸는 것은 해당 X 좌표에서 Y 좌표를 계산하는 것을 의미합니다.

분명히 모듈러 제곱근 연산이 사용되어야 하며, 이는 BN_mod_sqrt()를 호출합니다.

drago-96의 작업을 바탕으로 p=697, x^3+ax+b=696을 사용합니다. 그런 다음 두 번째 방정식을 만족하는 적절한 a, b, x를 선택하면 됩니다. 여기서는 x=8, a=23, b=0을 사용합니다.

이제 인증서를 수정하기 시작할 수 있습니다. ASN.1 구조를 수동으로 편집하는 것은 정말 끔찍합니다. xxd 도구를 사용하여 인증서를 16진수 형식으로 변환한 다음 vim으로 편집했습니다. 편집이 완료되면 xxd -r로 다시 변환했습니다.

더 편리한 도구를 찾지 못했습니다. 아는 분이 계시면 댓글로 알려주시기 바랍니다.

제작 단계는 대략 다음과 같습니다.

1. Prime, A, B, Generator의 값 변경
   1. Prime을 697, 즉 16진수 0x2b9로 변경
   2. A를 23, 즉 16진수 0x17로 변경
   3. B를 0으로 변경
   4. Generator의 X 좌표를 8(압축 형식으로 인코딩 시 0x020008 또는 0x030008)로 변경
2. OpenSSL은 ASN1_INTEGER의 패딩 형식을 확인하므로 Prime은 선행 0바이트를 포함하지 않아야 합니다. 따라서 Prime의 길이를 변경해야 합니다.
3. 마찬가지로 OpenSSL은 Prime의 길이와 점 문자열의 길이를 비교합니다. 따라서 Generator의 X 좌표 길이는 Prime과 동일해야 합니다. 그래서 Generator를 030008로 설정한 것이지 0308로 설정하지 않은 것입니다.
4. 인증서의 ASN.1 구조가 중첩되어 있으므로 외부 객체의 모든 길이도 함께 수정해야 합니다.
5. xxd -r을 실행한 후 파일 끝에 원치 않는 줄 바꿈 문자(0x0a)가 있을 수 있습니다. 이를 제거해야 합니다.

이제 일반 인증서의 ASN.1 구조를 살펴보겠습니다. 빨간색 선으로 표시된 부분이 변경될 부분입니다.

수정 전후의 길이는 다음과 같습니다.

ASN1 템플릿 사용하기

2020-03-21 업데이트:

훨씬 쉬운 방법은 wllm-rbnt가 작성한 asn1template 도구를 사용하는 것입니다.

저장소를 클론합니다:

이 인증서에서 DER 템플릿을 생성합니다:

그런 다음 위에서 언급한 매개변수를 변경합니다:

ASN1_generate_nconf(3)를 사용하여 다시 DER 인코딩 ASN1로 변환합니다:

출력된 cert_new.der는 수동으로 편집한 버전과 동일합니다.

이제 유효하지 않은 인증서를 성공적으로 제작했습니다. 새 ASN.1 구조를 살펴보겠습니다.

빨간색 부분이 모두 수정되었으며, 인증서가 DER 디코딩을 올바르게 통과할 수 있습니다.

유효하지 않은 인증서로 테스트

이제 인증서를 파싱해 보겠습니다. 모든 것이 예상대로 작동하면 프로세스가 무한 루프에 빠집니다.

보시다시피 openssl 프로세스의 %CPU가 100이고, 호출 스택이 BN_mod_sqrt() 내부에 있습니다.

악의적인 공격자가 SSL 핸드셰이킹 중에 이러한 조작된 인증서를 서버에 보내면 서버는 무한 루프에 빠져 DoS 공격을 유발할 수 있습니다.

인증서 생성, 대체 방법

OpenSSL C libcrypto 라이브러리를 사용하여 인증서를 만들어 보겠습니다.

앞서 살펴본 것처럼, 소수가 아닌 기저 필드를 가진 곡선을 사용하고 점을 압축 형식으로 인코딩해야 파싱 시 BN_mod_sqrt()의 버그에 걸릴 수 있습니다.

이는 곡선을 y^2 = x^3 + 1*x + 694 (mod 697)로 설정하고 생성자로 (1, 132)를 사용하여 수행할 수 있습니다. 이렇게 하면 my_bad_sqrt와 정확히 동일한 매개변수로 BN_mod_sqrt()를 호출합니다.

gcc -o my_bad_group my_bad_group.c -lcrypto && ./my_bad_group를 실행하면 ECparams를 DER 형식으로 포함하는 my_bad_group.der 파일이 생성됩니다.

OpenSSL로 해당 매개변수를 파싱하려고 하면 무한 루프가 발생합니다: openssl ecparam -in my_bad_group.der -inform der.

... 작업 중 ...