[Cyber Apocalypse CTF 2022] MOVs Like Jagger

1. Investigation

문제에서 주어진 파일의 압축을 풀면 3 개의 파일이 나옵니다.

 

>> app.py

from flask import Flask, request, jsonify
from flask.templating import render_template
from navigation_system import calculatePointsInSpace, checkDestinationPoint
from utils import generateLocation

app = Flask(__name__)

E = None
Q, nQ = None, None
P, nP = None, None

FLAG = "HTB{--REDACTED--}"


@app.route('/', methods=['GET', 'POST'])
def index():
    if request.method == 'POST':
        try:
            travel_result = checkDestinationPoint(request.form, P, nQ, E)
            location = generateLocation(travel_result)

            if travel_result:
                return render_template('travel.html', location=location, flag=FLAG)
            else:
                return render_template('travel.html', location=location)
        except ValueError as error:
            return render_template("index.html", error_message=str(error),
                                   departed_x=hex(Q.x()), departed_y=hex(Q.y()),
                                   present_x=hex(P.x()), present_y=hex(P.y()))
    return render_template('index.html', departed_x=hex(Q.x()),
                           departed_y=hex(Q.y()), present_x=hex(P.x()),
                           present_y=hex(P.y()))


@app.route('/api/coordinates', methods=['GET'])
def coordinates():
    points = {
        'departed_x': hex(Q.x()), 'departed_y': hex(Q.y()),
        'present_x': hex(P.x()), 'present_y': hex(P.y())
    }
    return points


@app.route('/api/get_flag', methods=['POST'])
def get_flag():
    try:
        travel_result = checkDestinationPoint(request.json, P, nQ, E)
        location = generateLocation(travel_result)

        if travel_result:
            return {"location": location, "flag": FLAG}
        else:
            return {"location": location}
    except ValueError as error:
        return {"error": error}


if __name__ == '__main__':
    Q, nQ, P, nP = calculatePointsInSpace()
    app.run(host='0.0.0.0', port=1337, debug=False, use_reloader=False)

main 함수부터 보면 caculatePointsInSpace() 라는 함수를 통해 현재 어떤 값인지는 모르겠으나 Q, nQ, P, nP 라는 값들을 반환한 뒤 Flask 를 이용한 웹 서버를 가동시킨다는 것을 알 수 있습니다.

 

루트('/') 경로에 POST 메소드를 이용하여 접근 시 Request 의 form 데이터, P, nQ, E 값을 인자로 checkDestinationPoint() 함수를 호출한 뒤 그 결과를 travel_result 에 반환하여 참이면 FLAG 를 보여주고, 아니면 보여주지 않는다는 것을 확인할 수 있습니다.

 

루트('/') 경로에 GET 메소드로 접근 시에는 departed_x, departed_y 에 Q 의 x, y 좌표를, present_x, present_y 에 P 의 x, y 좌표를 보여준다는 것을 알 수 있습니다.

 

나머지는 웹 페이지에 직접 접근하지 않고 API 를 호출해서 사용하기 편하도록 구현해놓은 것으로 보입니다.

 

>> navigation_system.py

from ecdsa import ellipticcurve as ecc
from random import randint

a = -35
b = 98
p = 434252269029337012720086440207
Gx = 16378704336066569231287640165
Gy = 377857010369614774097663166640
ec_order = 434252269029337012720086440208

E = ecc.CurveFp(p, a, b)
G = ecc.Point(E, Gx, Gy, ec_order)


def generateKeyPair():
    private = randint(1, 2**64)
    public = G * private
    return(public, private)


def calculatePointsInSpace():
    Q, nQ = generateKeyPair()
    P, nP = generateKeyPair()
    return [Q, nQ, P, nP]


def checkCoordinates(data: dict) -> list:
    if data['destination_x'] == "" or data['destination_y'] == "":
        raise ValueError('Empty coordinates...')

    try:
        destination_x = int(data['destination_x'], 16)
        destination_y = int(data['destination_y'], 16)
    except:
        raise ValueError('Coordinates are not in the right format (hex)')

    return (destination_x, destination_y)


def checkDestinationPoint(data: dict, P: ecc.Point, nQ: int, E: ecc.CurveFp) -> list:
    destination_x, destination_y = checkCoordinates(data)
    destination_point = ecc.Point(E, destination_x, destination_y, ec_order)
    secret_point = P * nQ
    same_x = destination_point.x() == secret_point.x()
    same_y = destination_point.y() == secret_point.y()

    if (same_x and same_y):
        return True
    else:
        return False

문제 풀이에 가장 중요한 부분입니다.

 

타원 곡선 암호 기법 (Elliptic Curve Cryptography) 을 사용한다는 것을 확인할 수 있는데, 여기서 유의깊게 봐야할 것은 ec_order 입니다. 이 값이 짝수이면 작은 여러 개의 소수들로 소인수분해가 될 수 있고 (Smooth 하다는 뜻), Discrete Logarithm Problem (이산 로그 문제) 를 합리적인 시간 내에 풀어 타원 곡선 암호 기법에서 사용된 개인키 (private key)를 알아낼 수가 있게 됩니다.

 

(타원 곡선 암호 기법에서의 개인키는 다음과 같이 계산함: P = d * G 에서 P 가 공개키, d 가 개인키, G 는 생성자)

 

(타원 곡선 암호 기법의 강점은 소수 p 와 order 가 충분히 크고 안전한 소수일 때 P 와 G 를 알아도 d 를 알아내는 것은 굉장히 어렵다는 것에 있음)

 

그래서 개인키를 알아내는게 문제 풀이에 어떤 연관이 있을까요?

 

위에서 먼저 분석한 app.py 의 main 함수에서 caculatePointsInSpace() 함수를 호출하고 해당 함수에서는 generateKeyPair() 함수를 호출하여 1 ~ 2^64 사이의 랜덤한 정수를 private 에 저장한 뒤 public = G * private 을 계산하여 public 값과 private 값을 각각 Q, nQ 그리고 P, nP 에 저장하여 반환하게 됩니다.

 

그리고 루트('/') 경로에 POST 메소드로 destination_x, destination_y 좌표를 전송하면 checkDestinationPoint() 함수를 호출하여 secret_point = P * nQ 를 계산하고 전송받은 destination_x, destination_y 와 secret_point 의 x, y 좌표가 일치하는지 확인하여 참/거짓 여부를 반환하게 됩니다.

 

여기서 P 는 공개되어 있기 때문에 쉽게 알 수 있지만 nQ 는 Q 를 계산할 때 사용된 개인키이기 때문에 원래라면 공격자가 알아낼 수 있는 방법은 없습니다. 하지만 위에서도 설명했듯이 ec_order 가 Smooth 하기 때문에 개인키를 합리적인 시간 내에 알아낼 수 있는 알고리즘을 사용하여 nQ 를 알아낸 뒤 secret_point = P * nQ 를 계산하여 x, y 좌표를 얻어낸다면 해당 좌표를 전송하여 FLAG 를 얻어낼 수 있을 것 입니다.

 

>> utils.py

import random

locations = [
    'the Galactic Federation\'s head courters',
    'Urkir',
    'Rohendel',
    'Longhir',
    'Vinyr',
    'the Dying Sun',
    'Thoccarth',
    'the Glowing Sea'
]


def generateLocation(success: bool) -> list:
    if success:
        return 'secret location of the weapons'
    else:
        return random.choice(locations)

위 파일은 그저 리스트에서 랜덤으로 문자열을 선택해 반환해주는 함수가 구현되어 있습니다. (secret_point 와 일치하지 않는 좌표를 전송하면 FLAG 대신 해당 함수에서 랜덤으로 선택된 문자열이 출력됨)

---

2. Solution

제가 알고있는 타원 곡선 암호 기법에서의 이산 로그 문제를 합리적인 시간 내에 풀 수 있는 알고리즘은 대표적으로 두 가지가 있습니다.

 

첫째는 Pohlig-Hellman 알고리즘, 둘째는 Weil-Pairing 알고리즘 입니다. (둘다 SageMath 에 구현되어 있음)

 

(Pohlig-Hellman 설명 + 예제 : https://risencrypto.github.io/PohligHellman/)

(Weil-Pairing 설명 + 예제 : https://crypto.stanford.edu/pbc/notes/ep/pairing.html)

 

맨 처음에는 Pohlig-Hellman 알고리즘을 사용하여 풀어보려 했으나 개인키가 합리적인 시간 내에 나오지 않아서 문제 제목을 다시 한번 보니 MOVs Like Jagger 이었기 때문에 MOV Attack (Weil-Pairing 과 같은 기법을 사용한 공격 명칭) 이 떠올라서 구글링한 코드를 통해 성공적으로 개인키를 구할 수 있었습니다.

(MOV Attack : https://crypto.stanford.edu/pbc/notes/elliptic/movattack.html)

 

(REF#1 : https://github.com/victini-lover/CSAW-Quals-2021-Writeups/blob/main/ECC-Pop-Quiz/solution.sage)

(REF#2 : https://sectt.github.io/writeups/Volga20/crypto_keygreed/README)

 

>> sol.sage

a = -35
b = 98
p = 434252269029337012720086440207
Gx = 16378704336066569231287640165
Gy = 377857010369614774097663166640
ec_order = 434252269029337012720086440208

E = EllipticCurve(GF(p), [a, b])
order = E.order()   # same as ec_order

G = E(Gx, Gy)

# P = Generator
# Q = Public Key
# Finding d, when Q = d * P

P = G
Q = E(0x5162f29901bf720f0b732b0a2, 0x1c586a04cc60dd787c14b95ab)   # P = E(px,py)
#Q = E(0x113a512fb7ae7e6d1bce535a, 0x5b5b603e21c7241e7a40b67c)     # Q = E(qx,qy)

n = P.order()

k = 1
while (p**k - 1) % order:
    k += 1
print(k)   # 2
# k must be small, k <= 6
    
K.<a> = GF(p**k)
EK = E.base_extend(K)
PK = EK(Q)
GK = EK(P)

# Finding new point S that is linearly independent to G.
# In other words, there is no n such that S = n * G.
while True:
    R = EK.random_point()
    m = R.order()
    d = gcd(m,n)
    S = (m//d)*R
    if n / S.order() not in ZZ:
        continue
    if n == S.order():
        break
        
# Weil-Pairing        
alpha = GK.weil_pairing(S,n)
beta = PK.weil_pairing(S,n)
dd = beta.log(alpha)
ans = str(dd)
print(ans)
# P = ans * G, nP = ans
# or
# Q = ans * G, nQ = ans

nP = 1482997312087825522
nQ = 6838982938819515899

# P for present point, Q for departed point given from web server.
P = E(0x5162f29901bf720f0b732b0a2, 0x1c586a04cc60dd787c14b95ab)
Q = E(0x113a512fb7ae7e6d1bce535a, 0x5b5b603e21c7241e7a40b67c)

# Calculating coordinates of secret_point = P * nQ.
x, y = (nQ * P).xy()
print(hex(x), hex(y))
# 0x47c4c489bc21f6da07be06b01 0x22ea1817370d3c2756ccb57dd
# Found secret coordinates
# Now send them to web server.

🚩FLAG : HTB{I7_*********************_15_i7?}