무효 곡선 공격 - 400개 곡선 이 블로그 게시물에서는 제작자의 관점, 도전 동기, Business CTF 2022의 암호화폐 챌린지 400 Curves에 대한 내용을 다룹니다.

이 블로그 게시물에서는 공개 키의 유효성을 검사하지 않는 안전하지 않은 ECDH 구현을 악용해야 하는 중간 난이도 암호화 문제인 400Curves에 대한 솔루션을 살펴보겠습니다.

설명 📄

Felonious Forums 를 인수한 후 , 저희는 저수준 MonkeyBusiness APT 요원을 식별하고 체포했습니다. 이 개발자는 Zoid 맬웨어 패밀리의 구성 요소를 재판매하는 일을 맡았습니다. 요원의 컴퓨터에 대한 포렌식 조사 중에 저희는 TLS 기반 프록시 서비스의 프로토타입 소스 코드를 얻었는데, 이 소스 코드는 침해된 컴퓨터 간의 C2 트래픽을 난독화하여 가로채기/탐지를 회피하는 데 사용되었습니다. 원격 호스트는 여전히 작동 중이지만, 저희가 찾은 ssh 키는 그 이후로 무효화되었습니다. 구성 요소의 소스 코드를 평가하는 동안, TLS로 암호화된 트래픽의 키는 인터넷에서 가장 일반적인 곡선인 P-256 곡선을 사용하는 ECDH 프로토콜을 사용하여 생성된 것으로 보입니다. 프록시 서비스의 개인 키를 검색할 방법을 찾을 수 있습니까?

🎮 트랙 재생

아이디어 💡

ECC에 대한 실제 공격에 대한 연구를 하던 중, 무효 곡선 공격이라는 공격을 접했습니다. 이 공격에 대해 처음 알게 된 건 Joseph이 Tiramisu라는 Google CTF 2021 챌린지에 대해 쓴 글을 읽었을 때였습니다 . 당시에는 이 공격의 기본 수학을 이해할 만큼 지식이 부족해서 포기했습니다. 경험이 쌓이면서 자신감이 생겼고, 메모를 하고 이에 대한 기사를 더 읽기 시작했습니다. 다행히도 OWASP의 이 프레젠테이션을 찾았는데, 간단한 곡선을 사용한 예를 보여주었습니다. 또한 이 글을 발견했고, 이 챌린지에 도전할 준비가 되었습니다. 연구를 하면서 JCE와 Bouncy Castle의 이전 버전이 이 공격에 취약한 것으로 알려져 있다는 사실도 알게 되었는데, 이는 향후 펜테스팅 프로젝트에 유용할 수 있습니다.

한눈에 보는 애플리케이션 🔍

nc와 같은 명령으로 tcp 서버에 연결하려고 하면 TLS 핸드셰이크를 설정하려고 한다는 메시지가 표시됩니다.

┏━[~]
┗━━ ■ nc 0.0.0.0 1337
Establishing the TLS handshake...
Awaiting public key of the client...

서버에서 공개 키를 입력하라고 합니다. 무작위 키를 입력해 볼 수 있습니다. 오류가 발생했다는 메시지가 나타납니다.

1234
Error occurred!

이 시점에서 우리는 사물이 어떻게 작동하는지 이해하기 위해 소스 코드를 살펴봐야 합니다.

소스 코드 분석 📖

사용 가능한 파일은 server.py 하나 입니다.

서버.py

스크립트를 살펴보면 기본적인 작업 흐름은 다음과 같습니다.

우리의 공개 키를 기다립니다.
ECDH 프로토콜에 대한 공유 비밀을 계산합니다.
공유된 비밀을 다시 전송합니다.

이것은 코드로 번역됩니다:

    while True:
        C = receiveMessage(s, "Awaiting public key of the client...\n")
        try:
            x, y = [int(i) for i in C.strip().split()]
            S = multiply((x, y), bytes_to_long(FLAG), E)
            sendMessage(s, f"Shared secret: {S}\n")
        except:
            sendMessage(s, f"Error occurred!\n")

곱셈 함수를 살펴보면, 그것은 double and add 알고리즘의 교과서적 구현처럼 보입니다. 그래서 발견할 만한 흥미로운 것은 없습니다. 그럼 버그는 어디에 있을까요?

버그 찾기 👾

이 챌린지의 이름은 취약점이 무엇인지에 대한 힌트입니다. ECC 공격을 검색하면 많은 리소스를 찾을 수 있습니다. 일반적으로 CTF에 대한 훌륭한 논문은 이 것입니다. 안타깝게도 저희 사례는 논문에 설명된 사례에 해당하지 않습니다. 설명에 언급된 대로 TLS에 대한 실제 ECDH 공격을 검색하면 “Invalid Curve Attack”이라는 공격을 찾을 수 있습니다. 챌린지 이름을 다시 살펴보면 400이 잘못된 HTTP 요청이나 잘못된 HTTP 요청에 대한 응답 코드임을 알 수 있습니다. 따라서 챌린지 이름은 “Invalid Curves”를 의미합니다. 이러한 공격은 많은 애플리케이션이 공격자의 공개 키를 확인하지 않고 악성 페이로드를 보내면 개인 키를 추출할 수 있다는 사실을 악용합니다. 더 정확히 말해서 공격자는 서버의 곡선에 속하지 않는 공개 키를 보내 DL 문제를 훨씬 더 빨리 해결할 수 있습니다.

착취 🔓

수학

이제 우리는 공격을 결정할 위치에 있으며, 아이디어 섹션에서 언급했듯이 이 기사는 쉽게 찾을 수 있습니다. 이를 사용하여 수학적 배경을 이해해 보겠습니다.

우리가 곡선을 가지고 있다고 가정하자

a = 9, b = 17, p = 23
E = EllipticCurve(GF(p), [a, b])
E.plot()

Sage를 사용하여 곡선을 그리면 생성될 수 있는 32개의 점을 모두 볼 수 있습니다.

무효 곡선 공격 - 400개 곡선 이 블로그 게시물에서는 제작자의 관점, 도전 동기, Business CTF 2022의 암호화폐 챌린지 400 Curves에 대한 내용을 다룹니다.

ECDH 프로토콜을 설명하는 아래 다이어그램을 살펴보면 사용자 지정 곡선으로 프로토콜을 구현할 수 있습니다.

가정하면 공유 비밀은 다음 과 같습니다 .

무효 곡선 공격 - 400개 곡선 이 블로그 게시물에서는 제작자의 관점, 도전 동기, Business CTF 2022의 암호화폐 챌린지 400 Curves에 대한 내용을 다룹니다. 하지만 곡선 E 밖에서 Q’를 계산하면 어떻게 될까요? Q’는 작은 순서를 가질 수 있습니다. 즉, 숫자를 Q’에 곱하면 가능한 결과는 작은 숫자가 됩니다. 이러한 점을 생성하려면 다음 알고리즘을 사용할 수 있습니다.

무작위로 b를 선택하세요.
새로운 곡선을 초기화합니다.
곡선의 순서를 계산합니다.
순서를 인수분해하세요.
충분히 작은 요소를 선택하세요.
이 요소를 포함하는 악성 지점을 순서대로 생성합니다.

위에서 초기화한 가상 곡선을 계속 사용해 보겠습니다. 새로운 곡선이 다음과 같다고 가정합니다.

a = 9, b2 = 5, p = 23
E_2 = EllipticCurve(GF(p), [a, b2])
E_2.plot()

새로운 곡선은 포인트가 적습니다. 알고리즘을 따라가 봅시다.

3단계:

order = E_2.order()
order
18

4단계:

factors = prime_factors(order)
factors
[2, 3]

3은 매우 작으므로 3을 소수로 선택했습니다.

prime = 3

5단계:

마지막으로, 다음과 같이 3차 포인트를 생성합니다.

Q = E_2.gen(0) * int(order / prime)
Q
(3 : 6 : 1)
Q.order()
3

서버의 비밀 키가 라고 가정해 보자 . 이 지점을 서버로 보내면 우리가 얻는 결과는 이다 . 출력이 될 수 있는 가능한 값은 3가지이다.

>>> for i in range(10):
...     print(i * Q)
...
(0 : 1 : 0)
(3 : 6 : 1)
(3 : 17 : 1)
(0 : 1 : 0)
(3 : 6 : 1)
(3 : 17 : 1)
(0 : 1 : 0)
(3 : 6 : 1)
(3 : 17 : 1)
(0 : 1 : 0)

(0 : 1 : 0), (3 : 6 : 1) 또는 (3 : 17 : 1)

곱셈 함수를 사용하면:

multiply((3, 6), 8, E)
(3, 17)

이제 이산 로그 문제를 풀어 보겠습니다.

G.discrete_log(E_2(3, 17))
2

그리고 우리는 첫 번째 결과를 얻었습니다 . 이 과정을 다른 소수에 대해 반복하는 것은 CRT를 사용하여 개인 키를 추출하기에 충분합니다.

서버에 연결 중

pwntools를 사용하여 서버에 연결하기 위한 매우 기본적인 스크립트:

if __name__ == '__main__':
    r = remote('0.0.0.0', 1337)
    pwn()

포인트 생성

이 섹션의 수학은 이미 수학 섹션에서 설명했습니다. 지적해야 할 유일한 것은 소수 한계입니다. 비교적 짧은 시간 안에 DL 문제를 풀기 위해 우리가 선택하는 소수는 2**40보다 크지 않아야 합니다.

    b = randint(1, p)
    E = EllipticCurve(GF(p), [a, b])
    order = E.order()
    factors = prime_factors(order)

    valid = []
    for factor in factors:
        if factor <= 2**40:
            valid.append(factor)

    prime = valid[-1]

    G = E.gen(0) * int(order / prime)

전송, 수신 및 DL

    # Here we send G to the server
    tmp_point = G.xy()
    tmp_x, tmp_y = str(tmp_point[0]), str(tmp_point[1])
    tmp_point = tmp_x + " " + tmp_y
    message = b"Awaiting public key of the client...\n"
    r.sendlineafter(message, bytes(tmp_point, "Latin"))

    # We get back Q which is G * k
    data = r.recvline()
    print(data)

    if b"Error" in data:
        print("An error on the server occured")
        return None, None

    Q = eval(data[len("Shared secret: "):])

이제 공유 비밀이 있으므로 DL 문제를 해결할 준비가 되었습니다.

    try:
        Q = E(Q[0], Q[1])
        print("Computing the discrete log problem")
        log = G.discrete_log(Q)
        print(f"DL found: {log}")
        return (log, prime)
    except Exception as e:
        print(e)
        return None, None

위의 모든 것은 함수로 계산됩니다 getDLs(). 프로세스를 충분히 반복하면, 우리의 경우 16이어야 하며, CRT로 비밀 키를 찾을 수 있습니다.

깃발을 얻다

위에서 말한 모든 내용을 최종적으로 요약하면 다음과 같습니다.

악의적인 지점을 만듭니다.
해당 지점을 서버로 전송합니다.
소수의 이산로그를 계산합니다.
CRT를 수행하여 키의 서버(플래그)를 찾습니다.

이 요약은 함수를 사용하여 코드로 표현할 수 있습니다 pwn().

def pwn():
    dlogs, primes = getDLs()
    print(f"dlogs: {dlogs}")
    print(f"primes: {primes}")
    super_secret = CRT_list(dlogs, primes)
    print(long_to_bytes(super_secret))

최종 스크립트는 다음과 같습니다.

from Crypto.Util.number import long_to_bytes
from sage.all_cmdline import *
from pwn import *

a = 0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff


def solveDL():
    b = randint(1, p)
    E = EllipticCurve(GF(p), [a, b])
    order = E.order()
    factors = prime_factors(order)

    valid = []
    for factor in factors:
        if factor <= 2**40:
            valid.append(factor)

    prime = valid[-1]

    G = E.gen(0) * int(order / prime)

    # Here we send G to the server
    tmp_point = G.xy()
    tmp_x, tmp_y = str(tmp_point[0]), str(tmp_point[1])
    tmp_point = tmp_x + " " + tmp_y
    message = b"Awaiting public key of the client...\n"
    r.sendlineafter(message, bytes(tmp_point, "Latin"))

    # We get back Q which is G * k
    data = r.recvline()
    print(data)

    if b"Error" in data:
        print("An error on the server occured")
        return None, None

    Q = eval(data[len("Shared secret: "):])
    try:
        Q = E(Q[0], Q[1])
        print("Computing the discrete log problem")
        log = G.discrete_log(Q)
        print(f"DL found: {log}")
        return (log, prime)
    except Exception as e:
        print(e)
        return None, None


def getDLs():
    dlogs = []
    primes = []
    for i in range(1, 16):
        log, prime = solveDL()
        if log != None:
            dlogs.append(log)
            primes.append(prime)
        print(f"counter: {i}")
    return dlogs, primes


def pwn():
    dlogs, primes = getDLs()
    print(f"dlogs: {dlogs}")
    print(f"primes: {primes}")
    super_secret = CRT_list(dlogs, primes)
    print(long_to_bytes(super_secret))


if __name__ == "__main__":
    r = remote("0.0.0.0", 1337)
    pwn()

이것으로 도전과제에 대한 글을 마칩니다!

무효 곡선 공격 – 400개 곡선 이 블로그 게시물에서는 제작자의 관점, 도전 동기, Business CTF 2022의 암호화폐 챌린지 400 Curves에 대한 내용을 다룹니다.

От