[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?}