新年明けましておめでとうございます、今年も./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で積分すれば良いのでこの曲線の形はだと推測できる。

この仮定の下で実際に加算をしてみる。まず変数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} $$

一方同じ点の加算ではとなったが、これはとした場合に等しいため同じ形で表す事が出来た。

続いてzeroで定義されている点をと定義すると加算後の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 $$

ここでと定義するとになり、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} $$

これでという曲線においてこの加算が上手く定義されている事がわかった。

倍算の性質 §

この問題では上記の加算においてx座標に関する離散対数問題を解くとDH鍵共有の秘密鍵が判明するため、有理点の倍算について考察をする。以下、点とおく。

この時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} $$

これを見るとどうもという関係がありそうである。実際数学的帰納法を使えば証明できると思うが、面倒なので省略し成り立つものとする。

ということはこれを変形するとが求まり次のようになる。

$$ n \equiv \frac{(nP)_x - x_0}{x_1 - x_0} \bmod p $$

パラメータの特定 §

この問題ではらしきものは与えられているがが与えられていない。先程のに関する式よりは求める必要は無さそうだがは求める必要がある。

ここで点に対して次が成り立つ。

$$ y_i - ax_i^2 - bx_i \equiv c \bmod p $$

右辺がに依らないことから左辺をとおくとである2点に対して

$$ z_i - z_j \equiv 0 \bmod 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}

感想 §

楕円曲線以外の曲線というコンセプトの問題で面白かったです。ここ最近曲線と格闘している事が多かったので割とすんなり解けた気がしました。

そういえば昨年は公開したWriteupを媒体を問わなければ90問分書いたらしいです。卒論のせいでCTFに出る事が出来ず、既にペースが落ちてますが今年は100を超えるWriteupを書けるよう頑張りたいです。