Real World CTF 3rd - Homebrewed Curve
新年明けましておめでとうございます、今年も./VespiaryとXornetをよろしくお願いします。
遅い新年の挨拶になりましたが今年最初のWriteup記事はReal World CTF 3rdからHomebrewed Curveになります。このCTFは卒論のせいで参加していなかったのですが、CryptoHackのDiscordを覗いたらこの問題で盛り上がっており人のWriteup記事から問題を覗いてみたら、独自の曲線で群を構成する問題で面白そうだったので解くことにしました。
Writeup §
配布スクリプト §
次のようなスクリプトと実行結果をくれる
#!/usr/bin/env python3
import random
import hashlib
from libnum import invmod
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
from Crypto.Util.Padding import pad
from secret import FLAG, P
class Curve:
def __init__(self, **kwargs):
self.__dict__.update(kwargs)
def add(self, p1, p2):
if p1 == self.zero:
return p2
if p2 == self.zero:
return p1
x1, y1 = p1
x2, y2 = p2
if x1 != x2:
l = (y2 - y1) * invmod(x2 - x1, P)
else:
l = 2 * self.a * x1 + self.b
x = ((l - self.b) * invmod(self.a, P) - self.zero[0]) % P
y = ((x - self.zero[0]) * l + self.zero[1]) % P
return (x, y)
def mul(self, p1, n):
if n == 0 or p1 == self.zero:
return self.zero
res = self.zero
while n:
if n & 1:
res = self.add(res, p1)
p1 = self.add(p1, p1)
n >>= 1
return res
def gen_key(self):
sk = random.randint(1, P)
pk = self.mul(self.gen, sk)
return sk, pk
curve = Curve(
a=338105350242668308929697763396044301660,
b=70631159681042046635446173236982478064116538177970218795092411634131296885767,
zero=(9754705134713370500425418962906364916694128219443986534870265438313712052553913556304578048773182865236181393234774811636563665254738358548547686098321918938336999994543320310489785839068889289585561389237322554300534800377365494547910434446171077511660646734142974631896227159038644834795595939445003783184271907835168083982210804135992472981458997056367475361358045062954295385753362817510369968941277639065938619221482008127361125972584968230982231483416783792258479416113581249377750311129019561848383083514672254514692875070293706012921153875918378772956871354902564753931679232128607231527456371560574893648150, 1568631189076775839914050721386821274436631828518639911590203429753674249963724465949098434816249858592209181914562366684848647341809527620103035336678319490054708958682690371323396425059326761139960520329829342510826324634871361342587962617109233961205192373716747727013613655062002124851676969800006190929713777159839273173689438005523473921392011053323705509027606365967531781465002057406686284573053674133382181877418753925610208463393821516137543581472014268533517599374830226690216017114664929426655189944119312800402788151756994817725042844409983509754618168400455155658767237036605650525875166823462486072842),
gen=(12532998589621080097666945122441206260965625062664570083674602252675892295679594034580389931735096079697125441246960301905307858329289188790029626634485829771734823159182904621402737540757430079518142479215838577833498703259391220160619426650385355407344355318793784733990238754982178179201863773450543367485332580658467529082154218982726945799974265641603861234501912638573835723384717842487988638277214429988591192513007462677389252245306874828268739787612245357189986581131725474432904172834643657027954405787429995826738074015516166702962206858859896933459093477305874443350335332968385035927605359630747331204285, 9677982578222119974363478748399786948047636069661692206522662047830643067492306311529114015320387572903840619331518584584400368845497864412752196098241604714699115186432809693851692194762433385961429711487895639093866274072187416400859677893102613898063134064507994013600600120524875666883108971040402000931357050726739367647257578379098507781478457700720118945453670136245178829199722575486626106268256525611370267664890630521019846806960099333376121482220389744953231843397729642415527736926160072478730239575933321480584291410141867063436921546657245313608614224909988684794138541856898030369431518091733072867437),
)
ak, A = curve.gen_key()
bk, B = curve.gen_key()
print(A)
print(B)
shared = curve.mul(A, bk)[0]
key = hashlib.sha256(long_to_bytes(shared)).digest()
aes = AES.new(key, AES.MODE_ECB)
ciphertext = aes.encrypt(pad(FLAG, AES.block_size))
print(ciphertext.hex())
Curveというクラスが定義されており、見ると加算と乗算も定義されている。楕円曲線と比べると形が異なっている上にどのような曲線なのかは明記されていないが、有理点の集合に演算を定義したものであると推測出来る。
これを群として利用してDH鍵共有を行い、共有した数字をハッシュ化したものを鍵としてAESでフラグを暗号化している。
曲線の特定 §
兎にも角にも曲線の特定をしないことには始まらない。よくある曲線の特定問題とは異なり、何次なのかもどの係数が0で無いのかもわからないのでまずはそこから判明させる。
まず注目すべきはCurve.addの部分で、ここではx1 != x2の真偽で変数lの形が変わっている。真の場合は単純に2点の傾きを取るだけだが、偽の場合(つまり同じ点の加算)においては別の式になっている。ここで、楕円曲線上で有限群を定義したのと同様の事を考えるとここは微分する事で傾きが求まる事になる。この曲線でも同様の事をした結果がl = 2 * self.a * x1 + self.bだとするとこれをxで積分すれば良いのでこの曲線の形は$y \equiv ax^2 + bx + c \bmod p$だと推測できる。
この仮定の下で実際に加算をしてみる。まず変数lは異なる点の加算において次のように計算される。
$$ \begin{aligned} l &= \frac{y_2 - y_1}{x_2 - x_1} \cr &= \frac{(ax_2^2 + bx_2 + c) - (ax_1^2 + bx_1 + c)}{x_2 - x_1}\cr &= \frac{a(x_2^2 - x_1^2) + b(x_2 - x_1)}{x_2 - x_1}\cr &= a(x_2 + x_1) + b \end{aligned} $$
一方同じ点の加算では$l = 2ax_1 + b$となったが、これは$l = a(x_2+x_1) + b$の$x_2 = x_1$とした場合に等しいため同じ形で表す事が出来た。
続いてzeroで定義されている点を$O = (x_0, y_0)$と定義すると加算後のxは次のようになる。
$$ \begin{aligned} x :&\equiv \frac{l-b}{a} - x_0\cr &\equiv x_2 + x_1 - x_0 \bmod p \end{aligned} $$
yは先程のxの計算結果を用いると次のようになる。
$$ y :\equiv (x - x_0)l + y_0 \equiv (x_1 + x_2 - 2x_0)(a(x_1 + x_2) + b) + (ax_0^2 + bx_0 + c) \bmod p $$
ここで$X := x_1 + x_2$と定義すると$x = X - x_0$になり、yに関して次のようになる。
$$ \begin{aligned} y :&\equiv (X - 2x_0)(aX + b) + (ax_0^2 + bx_0 + c) \cr &\equiv aX^2 - 2ax_0X + bX - 2x_0b + ax_0^2 + bx_0 + c \cr &\equiv a(X - x_0)^2 + b(X - x_0) + c \cr &\equiv ax^2 + bx + c \end{aligned} $$
これで$y \equiv ax^2 + bx + c \bmod p$という曲線においてこの加算が上手く定義されている事がわかった。
倍算の性質 §
この問題では上記の加算においてx座標に関する離散対数問題を解くとDH鍵共有の秘密鍵が判明するため、有理点の倍算について考察をする。以下、点$P := (x_1, y_1)$とおく。
この時3倍算までについて次のようになる。
$$ \begin{aligned} (2P)_x &\equiv 2x_1 - x_0 \bmod p\cr (3P)_x &\equiv (P + 2P)_x = x_1 + (2x_1 - x_0) - x_0 = 3x_1 - 2x_0 \bmod p \end{aligned} $$
これを見るとどうも$(nP)_x \equiv nx_1 - (n-1)x_0 \bmod p$という関係がありそうである。実際数学的帰納法を使えば証明できると思うが、面倒なので省略し成り立つものとする。
ということはこれを変形すると$n$が求まり次のようになる。
$$ n \equiv \frac{(nP)_x - x_0}{x_1 - x_0} \bmod p $$
パラメータの特定 §
この問題では$a, b$らしきものは与えられているが$c, p$が与えられていない。先程の$n$に関する式より$c$は求める必要は無さそうだが$p$は求める必要がある。
ここで点$P_i := (x_i, y_i)$に対して次が成り立つ。
$$ y_i - ax_i^2 - bx_i \equiv c \bmod p $$
右辺が$i$に依らないことから左辺を$z_i$とおくと$i \neq j$である2点$P_i, P_j$に対して
$$ z_i - z_j \equiv 0 \bmod p $$
が成り立つ。よって$z_i - z_j$は$p$の倍数であるからこの形のものを複数持ってきて最大公約数を取れば$p$が抽出出来る。
なお、実際に計算すると素数であるはずの$p$に素因数2がどうしても含まれてしまったので結果を2で割っている。
これで後は離散対数問題を解いてDH鍵共有の手順を経れば暗号化されたフラグを復号する事ができる。
Code §
import random
import hashlib
from itertools import combinations
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
from Crypto.Util.Padding import pad
from xcrypto.result import Result
from xcrypto.num_util import list_gcd
from xcrypto.prime import is_prime
def invmod(x, p):
return pow(x, -1, p)
class Curve:
def __init__(self, **kwargs):
self.__dict__.update(kwargs)
def add(self, p1, p2):
if p1 == self.zero:
return p2
if p2 == self.zero:
return p1
x1, y1 = p1
x2, y2 = p2
if x1 != x2:
l = (y2 - y1) * invmod(x2 - x1, self.P)
else:
l = 2 * self.a * x1 + self.b
x = ((l - self.b) * invmod(self.a, self.P) - self.zero[0]) % self.P
y = ((x - self.zero[0]) * l + self.zero[1]) % self.P
return (x, y)
def mul(self, p1, n):
if n == 0 or p1 == self.zero:
return self.zero
res = self.zero
while n:
if n & 1:
res = self.add(res, p1)
p1 = self.add(p1, p1)
n >>= 1
return res
# challenge info
a=338105350242668308929697763396044301660
b=70631159681042046635446173236982478064116538177970218795092411634131296885767
zero=(9754705134713370500425418962906364916694128219443986534870265438313712052553913556304578048773182865236181393234774811636563665254738358548547686098321918938336999994543320310489785839068889289585561389237322554300534800377365494547910434446171077511660646734142974631896227159038644834795595939445003783184271907835168083982210804135992472981458997056367475361358045062954295385753362817510369968941277639065938619221482008127361125972584968230982231483416783792258479416113581249377750311129019561848383083514672254514692875070293706012921153875918378772956871354902564753931679232128607231527456371560574893648150, 1568631189076775839914050721386821274436631828518639911590203429753674249963724465949098434816249858592209181914562366684848647341809527620103035336678319490054708958682690371323396425059326761139960520329829342510826324634871361342587962617109233961205192373716747727013613655062002124851676969800006190929713777159839273173689438005523473921392011053323705509027606365967531781465002057406686284573053674133382181877418753925610208463393821516137543581472014268533517599374830226690216017114664929426655189944119312800402788151756994817725042844409983509754618168400455155658767237036605650525875166823462486072842)
gen=(12532998589621080097666945122441206260965625062664570083674602252675892295679594034580389931735096079697125441246960301905307858329289188790029626634485829771734823159182904621402737540757430079518142479215838577833498703259391220160619426650385355407344355318793784733990238754982178179201863773450543367485332580658467529082154218982726945799974265641603861234501912638573835723384717842487988638277214429988591192513007462677389252245306874828268739787612245357189986581131725474432904172834643657027954405787429995826738074015516166702962206858859896933459093477305874443350335332968385035927605359630747331204285, 9677982578222119974363478748399786948047636069661692206522662047830643067492306311529114015320387572903840619331518584584400368845497864412752196098241604714699115186432809693851692194762433385961429711487895639093866274072187416400859677893102613898063134064507994013600600120524875666883108971040402000931357050726739367647257578379098507781478457700720118945453670136245178829199722575486626106268256525611370267664890630521019846806960099333376121482220389744953231843397729642415527736926160072478730239575933321480584291410141867063436921546657245313608614224909988684794138541856898030369431518091733072867437)
A = (13487441097225225851381503721250882201348230291456769111220742564976603915541284733903445742010369949564133835184041848270925618065093927905336977954164490448790585095635629931682025014174873840946833423568776772534204109608898522472240761836716148677237778503440395160725865443571787537094238702604760374819569040510617361718394064021678094989416987996196517169045682067813960280671702291412278502544773112916378850480939772300572998243270196397238062178930871026435948325839912933370726600147757455774532767943291746849500590032985576917021393256167765909741347168603316800970606576192321995775188693736786445970160, 6017599616030668129613886703128129222334636061709939196813507723707943475088184604346025813500691639135280058944967720252980654491495661264318199620883475540203205404460632231139796107580037387665375828311005986158345466234113715267437612091657183380072338306002369357139146048822354864239891700619714889347124655297444781747932429314301652892318820172915980583258019186234125036141716353634569644160769758113796289362452914192384749373824618193948698071662955348463507865825856345882176096759589399552633775680285990970529819948425052395988810137569926613717988817522119415329098727602713461364878132364924903122354)
B = (12325243140409509948390016947224835770037275709809199983863357504628092935405755615708471085146623088629930125222768275569249161772533262995997384602018963893791998430652960945216562316807507576074802113883850941124224565729858452198366295197883539144659809879585978117675682586217166877317417820588576087650344398633914868028869563804325425499084148917013752420468723286815504458371864930365680607878997170362726942929241087236675902387482097261010616327896296714705736419010609802542459944267215680522857179358080459237676786115966499799125501709118451402926712061906091422526053306629229053727883903005288795696508, 11505268856676087471457416848355426459576355205947042999067185842545620763588462278320812379117467263916383145249098261720386127003988544590766801168503624732272757534718035824926881081717465079216152838849559029603087971046414561166054241351336879142412362035493311540826692018441037485743070162688102587726966007813519178658355297714620527127226989353344537573502931404623687629851431286618067819135715913162892925109669537524861927815259765868576488623808219606831381696710149107337624587114848589866865509992514440834069577162069420625328534884840613305250527515798029474049312705531575693278171514006918716216130)
def calc_c(point):
x, y = point
return y - (a * (x**2) + b*x)
def exploit() -> Result:
pks = []
pairs = combinations([A, B, gen, zero], 2)
for pair in pairs:
p1 = pair[0]
p2 = pair[1]
diff1 = calc_c(p1)
diff2 = calc_c(p2)
pk = diff1 - diff2
pks.append(pk)
p = list_gcd(pks) // 2
n_b = (B[0] - zero[0]) * pow(gen[0] - zero[0], -1, p)
curve = Curve(a=a, b=b, zero=zero, gen=gen, P=p)
shared = curve.mul(A, n_b)[0]
key = hashlib.sha256(long_to_bytes(shared)).digest()
aes = AES.new(key, AES.MODE_ECB)
flag = aes.decrypt(bytes.fromhex("1c002f8ecfa9177ffed879245681dbb606ed194f319c12a0a0940c7193e490095e9915d9ce9252f8377def6a92bcab6a"))
return Result(flag)
if __name__ == "__main__":
res = exploit()
if res.isSuccess():
print(res.unwrap())
Flag §
RWCTF{parab0la-curv3_1s_far_fr0m_g00d_en0ugh}
Thanks for reading! Read other posts?