廢文集中區

HITCON CTF 2021 WriteUps

發表於
分類於 CTF
English

和 Goburin’ 參加了 HITCON CTF 2021 拿了第十名，台灣第二。這次我主要解了幾個 crypto 和 web，其他的話就都是稍微幫忙點 misc 和 reverse 而已。這次因為打到一半去考個日檢才回來，有題 NTRU 的 crypto 沒解掉真的很可惜==。

  排行榜截圖

crypto

so easy rsa

from gmpy2 import next_prime, is_prime
from random import randint
from Crypto.Util.number import bytes_to_long

class Rand:
    def __init__(self):
        self.seed = randint(2, 2**512)
        self.A = next_prime(randint(2, 2**512))
        self.B = next_prime(randint(2, 2**512))
        self.M = next_prime(randint(2, 2**512))
        for _ in range(10000):
            self.next()
    
    def next(self):
        self.seed = self.seed * self.A + self.B
        self.seed = self.seed % self.M
        return self.seed

    def __str__(self):
        return f"{self.A}, {self.B}, {self.M}"
        

def gen_prime(r):
    while True:
        v = r.next()
        if is_prime(v):
            return v

r = Rand()
p,q = gen_prime(r), gen_prime(r)
n = p*q
e = 65537
flag = bytes_to_long(open('flag','rb').read())
val = pow(flag, e, n)

print(n)
print(r)
print(val)

RSA 的 pp qq 是用一個 LCG 生成的，它生成質數的方法是很直接的暴力檢查它是不是質數，不是就換下一個。由此可知 pp qq 存在一個多項式關係: q=f(p)q=f(p)，其中 f(x)f(x) 是個未知次數的 LCG 疊代而成的。

直接做一些實驗可以知道它 pp qq 大概只間隔 600 次以內，所以直接暴力搜尋那個次數就能得到多項式 f(x)f(x)。之後就用 p⋅f(p)≡N(modM)p \cdot f(p) \equiv N \pmod{M} 即可解出 pp 了。

from Crypto.Util.number import *

e = 65537
n = 198148795890507031730221728469492521085435050254010422245429012501864312776356522213014006175424179860455397661479243825590470750385249479224738397071326661046694312629376866307803789411244554424360122317688081850938387121934893846964467922503328604784935624075688440234885261073350247892064806120096887751
A = 1677936292368545917814039483235622978551357499172411081065325777729488793550136568309923513362117687939170753313352485633354858207097035878077942534451467
B = 5687468800624594128838903842767411040727750916115472185196475570099217560998907467291416768835644005325105434981167565207313702286530912332233402467314947
M = 1244793456976456877170839265783035368354692819005211513409129011314633866460250237897970818451591728769403864292158494516440464466254909969383897236264921
c = 48071438195829770851852911364054237976158406255022684617769223046035836237425012457131162001786019505606941050117178190535720928339364199078329207393922570246678871062386142183424414041935978305046280399687623437942986302690599232729065536417757505209285175593543234585659130582659013242346666628394528555

# def brute(interval):
#     Z = Zmod(M)
#     P = PolynomialRing(Z, "pp")
#     pp = P.gen()
#     qq = pp
#     for _ in range(interval):
#         qq = A * qq + B
#     f = pp * qq - n
#     return [ZZ(p) for p, e in f.roots()]


# for i in range(1, 1000):
#     r = brute(i)
#     print(i, r)
#     if len(r) > 0 and any(n % p == 0 for p in r):
#         break


# interval = 272
p = 243910118538351506548384880034426728169248862274637495579956619639346929105044407816656098657792419005522183874367421793338227934532131627126006227183679
q = n // p
d = inverse_mod(e, (p - 1) * (q - 1))
print(long_to_bytes(power_mod(c, d, n)))

這題雖然是水題，只是我沒想到居然能拿到 first blood ==

a little easy rsa

from Crypto.Util.number import *

N = 1024
P = 211
p = getPrime(P)
q = getPrime(N-P)
n = p*q
print(n.bit_length())
d = p
e = inverse(d, (p-1)*(q-1))
flag = bytes_to_long(open('flag','rb').read())

print(n)
print(e)
print(pow(flag, e, n))

這題有個 unbalanced RSA，其中 d=pd=p。由此可得 en≡epq≡q(modφ(n))en \equiv epq \equiv q \pmod{\varphi(n)}，所以 2en≡2q(modn)2^{en} \equiv 2^q \pmod{n}。這邊可以把它 reduce 到模 qq，由費馬小定理可知 2en≡2q≡2(modq)2^{en} \equiv 2^q \equiv 2 \pmod{q}，因此 gcd⁡(2en−2,n)\gcd(2^{en}-2,n) 是 nn 的一個 nontrival factor qq。

from Crypto.Util.number import *

n = 73105772487291349396254686006336120330504972930577005514215080357374112681944087577351379895224746578654018931799727417401425288595445982938270373091627341969888521509691373957711162258987876168607165960620322264335724067238920761042033944418867358083783317156429326797580005138985469248465425537931352359757
e = 4537482391838140758438394964043410950504913123892269886065999941390882950665896428937682918187777255481111874006714423664290939580653075257588603498124366669194458116324464062487897262881136123858890202346251370203490050314565294751740805575602781718282190046613532413038947173662685728922451632009556797931
c = 14558936777299241791239306943800914301296723857812043136710252309211457210786844069103093229876701608756952780774067174377636161903673229776614350695222134040119114881027349864098519027057618922872932074441000483969146246381640236171500856974180238934543370727793393492372475990330143750179123498797867932379

q = gcd(power_mod(2, n * e, n) - 2, n)
p = n // q
m = power_mod(c, p, n)

print(long_to_bytes(m))

這題有趣的地方是 flag 內容說的是 coppersmith，intended 的做法大概是利用 men≡m(modq)m^{en} \equiv m \pmod{q} 這個事實，取 c′=men(modn)c' = m^{en} \pmod{n} 之後可以用 coppersmith 找 f(x)=x−c′f(x)=x-c' 的 small root mm 吧。(flag 夠短，可以符合 m<n0.752m<n^{0.75^2})

如果要限制用這個解法解的話作者可能要把 ee 也拿掉才行。

其實這個題目之前我就有類似的想法了，只是沒有弄 unbalanced rsa 而已，有嘗試出給 ImaginaryCTF

magic rsa

import os
from Crypto.Util.number import *
from hashlib import *
from binascii import unhexlify

LEN = 17
magic = os.urandom(LEN)
print("Magic:", magic.hex())
print('Coud you use it to do encryption as hash?')

magic_num = bytes_to_long(magic)
try:
    N = int(input('N:>'))
    e = int(input('E:>'))
    data = unhexlify(input('data:>'))
    if N >> (384 - LEN*8) == magic_num:
        data2 = sha384(data).digest()
        num1 = bytes_to_long(data)
        num2 = bytes_to_long(data2)
        if pow(num1, e, N) == num2:
            print(open('flag','r').read())
        else:
            print('try harder!!!')
    else:
        print('try harder!')
except Exception as e:
    print('invalid')

目標要選個 n,en,e 符合 n >> 248 == magic，然後找到 d1e≡SHA384⁡(d1)(modn)d_1^e \equiv \operatorname{SHA384}(d_1) \pmod{n} 才行。

題名雖說是 RSA，但明顯是個 dlog 問題才對。目標就要想辦法找個可以快速計算 dlog 的 nn 還要同時符合 magic 的條件。

我解這題時使用的是 n=2p2n=2p^2 的形式，因為我從這邊看到這是其中一種 cyclic group 的形式，才能找到一個能完整覆蓋整個 group 的 generator。其中 p−1p-1 用爆破去試的直到它夠 smooth 為止。

之後 d1d_1 就取 generator 的任意次方，然後開炸 dlog 找出合適的就行了。

from pwn import remote
from Crypto.Util.number import *
from hashlib import *

LEN = 17
shift = 384 - LEN * 8


def init():
    io = remote("35.72.139.70", 31337)
    io.recvuntil(b"Magic: ")
    magic = int(io.recvlineS(), 16)
    return io, magic


while True:
    io, magic = init()
    p = next_prime(floor(sqrt((magic << shift) // 2)))
    print("try prime", p)
    if (2 * p * p >> shift) == magic and max(p for p, e in factor(p - 1)) < 2 ** 50:
        N = 2 * p * p
        phi = euler_phi(N)
        Z = Zmod(N)
        break
    io.close()


def find_order(x):
    o = phi
    while x ^ o == 1:
        o //= 2
    o *= 2
    return o


for i in range(3, 100):
    if find_order(Z(i)) == phi:
        g = Z(i)
        break


def rnd():
    d1 = ZZ(g ** randint(1, phi))
    d2 = ZZ(bytes_to_long(sha384(long_to_bytes(d1)).digest()))
    return d1, d2


while True:
    d1, d2 = rnd()
    if d2 > N:
        continue
    print("try dlog", d1)
    res = pari.znlog(Z(d2), Z(d1))
    if len(res) == 0:
        continue
    e = ZZ(res)
    if power_mod(d1, e, N) == d2:
        break


print("found")
print(d1)
print(d2)
print(e)

io.sendlineafter(b"N:>", str(N).encode())
io.sendlineafter(b"E:>", str(e).encode())
io.sendlineafter(b"data:>", long_to_bytes(d1).hex().encode())
io.interactive()

# hitcon{Did_you@solve!this_with_smoooothness?}

magic dlog

import os
from Crypto.Util.number import *
from hashlib import *
from binascii import unhexlify

LEN = 17
magic = os.urandom(LEN)
print("Magic:", magic.hex())
print('Coud you use it to solve dlog?')

magic_num = bytes_to_long(magic)
try:
    P = int(input('P:>'))
    e = int(input('E:>'))
    data = unhexlify(input('data:>'))
    if P >> (384 - LEN*8) == magic_num and isPrime(P):
        data2 = sha384(data).digest()
        num1 = bytes_to_long(data)
        num2 = bytes_to_long(data2)
        if pow(num1, e, P) == num2:
            print(open('flag','r').read())
        else:
            print('try harder!!!')
    else:
        print('try harder!')
except Exception as e:
    print('invalid')

和前面一題幾乎一樣，只是這次要求是質數，所以就要想辦法找到 p−1p-1 是 smooth 且符合 p=2248magic+kp=2^{248}\mathit{magic}+k 的才行。

有找到 Finding Smooth Integers in Short Intervals Using CRT Decoding 這篇 paper，也有稍微 implement 看看了裡面的算法:

# mbits = 17 * 8
# shift = 384 - mbits
# magic = randint(1, 2 ^ mbits)
# m = magic << shift

shift = 50
target = product([p for p in primes_first_n(1000) if randint(0, 1) == 1])
m = (target >> shift) << shift

B = 2 ^ shift
a = 4
ap = 4
n = 1000
ps = primes_first_n(n)
P = product(ps)
# R = crt([-m] * n, ps)
R = -m % P
amp = lambda x: gcd(m + x, P)
PR = PolynomialRing(ZZ, "x", 1)
x = PR.gen()
gs = [P ^ (a - i) * (x - R) ^ i for i in range(a)]
hs = [(x - R) ^ a * x ^ i for i in range(ap)]
polys = Sequence([f.subs(x=B * x) for f in gs + hs])
L, v = polys.coefficient_matrix()
print("LLL", L.dimensions())
L = L.dense_matrix().LLL()
for w in L * vector(v):
    print(w.subs(x=x / B).roots())
print(target - m)

只是說我測試的時候發現它真的只能找非常 smooth 的數，若是 s-smooth\text{s-smooth} 中的 ss 稍微大了點，數字就會變很大使得 LLL 跑很久，所以就放棄了這個解法。

後來發現說取 k=1k=1 的時候 p−1=2248magicp-1=2^{248}\mathit{magic} 的 smooth 程度等價於 magic\mathit{magic}，所以就暴力炸 server 直到 magic\mathit{magic} 本身也夠 smooth 為止。之後就一樣炸 d1d_1 出來算 dlog 即可。

from pwn import remote
from Crypto.Util.number import *
from hashlib import *

LEN = 17
shift = 384 - LEN * 8


def init():
    io = remote("35.72.139.70", 31338)
    io.recvuntil(b"Magic: ")
    magic = int(io.recvlineS(), 16)
    return io, magic


while True:
    io, magic = init()
    p = (magic << shift) + 1
    print("try prime", p)
    if isPrime(p) and max(p for p, e in factor(p - 1)) < 2 ** 50:
        F = GF(p)
        break
    io.close()

g = F.multiplicative_generator()


def rnd():
    d1 = ZZ(g ** randint(1, p - 1))
    d2 = ZZ(bytes_to_long(sha384(long_to_bytes(d1)).digest()))
    return d1, d2


print(factor(p - 1))

while True:
    d1, d2 = rnd()
    if d2 > p:
        continue
    print("try dlog", d1)
    e = ZZ(discrete_log(F(d2), F(d1)))
    if power_mod(d1, e, p) == d2:
        print("found")
        break


print("found")
print(d1)
print(d2)
print(e)

io.sendlineafter(b"P:>", str(p).encode())
io.sendlineafter(b"E:>", str(e).encode())
io.sendlineafter(b"data:>", long_to_bytes(d1).hex().encode())
io.interactive()

# hitcon{Hoo@pe_you_can_solve_by_smoooothness_this_time!}

so easy but not rsa

from Crypto.Util.number import bytes_to_long as b2l
from Crypto.Util.number import long_to_bytes as l2b
import random

load('secretkey.sage')

Zx.<x> = ZZ[]
def convolution(f,g):
  return (f * g) % (x^n-1)

def balancedmod(f,q):
  g = list(((f[i] + q//2) % q) - q//2 for i in range(n))
  return Zx(g)  % (x^n-1)

def randomdpoly(d1, d2):
  result = d1*[1]+d2*[-1]+(n-d1-d2)*[0]
  random.shuffle(result)
  return Zx(result)

def invertmodprime(f,p):
  T = Zx.change_ring(Integers(p)).quotient(x^n-1)
  return Zx(lift(1 / T(f)))

def invertmodpowerof2(f,q):
  assert q.is_power_of(2)
  g = invertmodprime(f,2)
  while True:
    r = balancedmod(convolution(g,f),q)
    if r == 1: return g
    g = balancedmod(convolution(g,2 - r),q)

def keypair():
  while True:
    try:
      f = randomdpoly(61, 60)
      f3 = invertmodprime(f,3)
      fq = invertmodpowerof2(f,q)
      break
    except Exception as e:
      pass
  g = randomdpoly(20, 20)
  publickey = balancedmod(3 * convolution(fq,g),q)
  secretkey = f
  return publickey, secretkey, g

def encode(val):
    poly = 0
    for i in range(n):
        poly += ((val%3)-1) * (x^i)
        val //= 3
    return poly

def encrypt(message, publickey):
  r = randomdpoly(18, 18)
  return balancedmod(convolution(publickey,r) + encode(message), q)


n, q = 263, 128
publickey, _, _ = key # key = keypair()

flag = b2l(open('flag', 'rb').read())
print(encrypt(flag, publickey))
print(publickey)

# generate a lots of random data
data = [ random.getrandbits(240) for _ in range(200)]
for random_msg in data:
    print(l2b(random_msg).hex(), encrypt(random_msg, publickey))

這題是個標準的 NTRU implementation，且參數大小也都是正常的，沒辦法直接 LLL 找 private key。

弱點在於它的 random 是 python 內建的 MT19937，而它在最後面還有給 240×200>32×624240 \times 200 > 32 \times 624 的輸出，所以是足夠去重建 MT19937 的狀態的。

只是有個比較麻煩的地方是 240 不是 32 的倍數，不能直接拿一般的 MT19937 recover 腳本，因為那些通常都要求連續 624 個 32 bits 輸出才行。

我是拿之前在 Balsn CTF 的時候找到的 MT19937 Symbolic Execution and Solver 來解，它可以很快速的只用 top 4, 8, 16, 32 bits 去還原狀態。由於 2×240×200>32×6242 \times 240 \times 200 > 32 \times 624 還是成立的，所以把 240 bits 切割成 8 塊之後把 32 bits 的 7 塊都只留 top 16 bits 是可行的。丟進 solver 之後就能還原出 random 的狀態。

之後要去讀一下 python 的 random.shuffle 是怎麼實作的，然後回推適當的狀態數之後可以得到 rr，所以 c−rh mod q=mc-rh \bmod{q} = m 即可得到 flag。

from Crypto.Util.number import *
import sys
from tqdm import tqdm
from functools import partial

sys.path.append("./MT19937-Symbolic-Execution-and-Solver/source")

# Import symbolic execution
from MT19937 import MT19937, MT19937_symbolic

# Import XorSolver
from XorSolver import XorSolver

Zx.<x> = ZZ[]

with open("data") as f:
    ct = sage_eval(f.readline(), locals={"x": x})
    h = sage_eval(f.readline(), locals={"x": x})
    rnddata = []
    for line in f:
        rnd, poly = line.split(" ", 1)
        rnddata.append(bytes_to_long(bytes.fromhex(rnd)))


data = []
for bits in rnddata:
    for _ in range(7):
        data.append((bits >> 16) & 0xFFFF)
        bits >>= 32
    data.append(bits)
nbits = 16
cloned = MT19937(state_from_data=(data, nbits))


def clone(rng):
    return MT19937(state=list(rng.state))


def randbelow(n, getrandbits):
    k = int(n).bit_length()
    r = getrandbits(k)
    while r >= n:
        r = getrandbits(k)
    return r


def shuffle(x, randbelow):
    for i in reversed(range(1, len(x))):
        j = randbelow(i + 1)
        x[i], x[j] = x[j], x[i]


def randomdpoly(d1, d2, shuffle):
    result = d1 * [1] + d2 * [-1] + (n - d1 - d2) * [0]
    shuffle(result)
    return Zx(result)


def encode(val):
    poly = 0
    for i in range(n):
        poly += ((val % 3) - 1) * (x ^ i)
        val //= 3
    return poly


def decode(poly):
    return int("".join([str(int(c) + 1) for c in poly.list()][::-1]), 3)


n, q = 263, 128


def convolution(f, g):
    return (f * g) % (x ^ n - 1)


def balancedmod(f, q):
    g = list(((f[i] + q // 2) % q) - q // 2 for i in range(n))
    return Zx(g) % (x ^ n - 1)


for i in tqdm(range(500, 0, -1)):
    rng = clone(cloned)
    rng.reverse_states(i)
    rb = partial(randbelow, getrandbits=lambda k: rng() >> (32 - k))
    sh = partial(shuffle, randbelow=rb)
    r = randomdpoly(18, 18, sh)
    m = balancedmod(ct - convolution(h, r), q)
    if all(-1 <= x <= 1 for x in m.list()):
        print(i, long_to_bytes(decode(m)))
        break

# hitcon{ohno!secure_random_is_50_important!}

web

One-Bit Man

這題可以選擇對 wordpress:5.8.2-apache 之中 /var/www/html 中的任一一個檔案，選擇其中一個 byte 的一個 bit 去 flip。它是用額外的一個服務讓你選擇 path, byte 和 bit，然後動態用 docker 產生出新的 wordpress instance 的。

解法就是把 wp-includes/user.php 中第 174 行的 login check 改掉:

	if ( ! wp_check_password( $password, $user->user_pass, $user->ID ) ) {
		return new WP_Error(
			'incorrect_password',
			sprintf(
				/* translators: %s: User name. */
				__( '<strong>Error</strong>: The password you entered for the username %s is incorrect.' ),
				'<strong>' . $username . '</strong>'
			) .
			' <a href="' . wp_lostpassword_url() . '">' .
			__( 'Lost your password?' ) .
			'</a>'
		);
	}

由於 ! 和空白字元只差一個 bit，所以就把那個 ! 變成空白之後就能任意登入了。以 admin 登入後就在 plugin 上傳區隨便傳個 webshell 就能 RCE 拿 flag。

在這個版本的話是 path: /var/www/html/wp-includes/user.php byte: 5389 和 bit: 0。

另一個我覺得可能有戲的是 , 和 . 也是只差一個 bit，可能可以把一些傳參數的地方變成接字串，搞不好也有其他的玩法

W3rmup PHP

<?php
    if (!isset($_GET['mail']))
        highlight_file(__FILE__) && exit();

    $mail    = filter_var($_GET['mail'],           FILTER_VALIDATE_EMAIL);
    $addr    = filter_var($_SERVER['REMOTE_ADDR'], FILTER_VALIDATE_IP);
    $country = geoip_country_code_by_name($addr);
    
    if (!$addr    || strlen($addr)    == 0) die('bad addr');
    if (!$mail    || strlen($mail)    == 0) die('bad mail');
    if (!$country || strlen($country) == 0) die('bad country');

    $yaml = <<<EOF
    - echo          # cmd
    - $addr         # address
    - $country      # country
    - $mail         # mail
    EOF;
    $arr = yaml_parse($yaml);
    if (!$arr) die('bad yaml');

    for ($i=0; $i < count($arr); $i++) { 
        if (!$arr[$i]) {
            unset($arr[$i]);
            continue;
        }
        $arr[$i] = escapeshellarg($arr[$i]);
    }

    system(implode(" ", $arr));

整題 source code 很短，就把幾個參數放到 yaml 中 parse 之後做一些 escape，然後執行指令。

看到 yaml 和國碼第一個讓我想到的就是 The Norway Problem: NO 在 yaml 中代表 false，而挪威的國碼也是 NO，所以在 yaml 中如果沒把國碼用 quote 包起來的話遇到挪威就會出問題。

所以只要用個挪威 vpn 就能讓 $arr 的第 2 個 element 變成 false，這邊在下面的迴圈會進入那個 if，unset($arr[2]) 之後 continue，但是 unset 之後 count($arr) 也會變化，這就造成了 $mail 不會被 escape 的問題。

剩下就想辦法利用能通過 FILTER_VALIDATE_EMAIL 的 payload 去 command injection 即可，一個 payload 如下:

http://18.181.228.241/?mail=a`/readflag`@a.tw

之所以要多加一個 a 是因為也要能讓它通過 yaml parsing

misc

FBI WARNING

這題有個類似 2ch 的 imageboard，只是發文功能都被關閉了。目標是要找出頁面上唯一一個留言者 Ωrange 的 ip，flag format 為 hitcon{<ip-address-of-Ωrange>}。

這方面用日文搜尋比較容易能找到相關資訊，可以在 2ch 的 スクリプト ダウンロード 看到它有提供背後的 futaba.php 下載。

review 一下它的 source code 可以知道它有個 ID 是由以下程式碼生成的:

substr(crypt(md5($_SERVER["REMOTE_ADDR"].IDSEED.gmdate("Ymd", $time+9*60*60)),'id'),-8);

其中 IDSEED 是一開始所定義的一個常數:

define("IDSEED", 'idの種');		//idの種

假定說這題的 IDSEED 沒被改過，只要知道時間的話就能直接暴力找所有的 ipv4 address 看看哪個符合目標 id (ueyUrcwA)。

繼續讀可以在函數 regist 看到下方的 code:

  // 時間
  $time = time();
  $tim = $time.substr(microtime(),2,3);

  // アップロード処理
  if($upfile&&file_exists($upfile)){
    $dest = $path.$tim.'.tmp';
    move_uploaded_file($upfile, $dest);

所以可以知道上傳的檔名是由當前時間 $time 和 substr(microtime(),2,3) 做 concat 而成的。很剛好的，Ωrange 的留言正好也有上傳一張圖片，內容是 FBI Warning 且檔名為 1638537259302.jpg，所以可以知道它發文當下的時間是 1638537259。

之後就寫個 php 腳本用這些算法直接開炸 2322^{32} 種 ipv4 address，不過後來 Orange 有多加個提示說 ip 是 219 開頭的，這樣可以把搜尋範圍壓到 1/256:

<?php
define("IDSEED", 'idの種');
$time = 1638537259; // 302 is from microtime
$target = 'ueyUrcwA';
$st = ip2long("219.0.0.0");
$ed = ip2long("219.255.255.255");

for($i=$st;$i<$ed;$i++){
    if($i % 65536 === 0){
        echo ($i/65536)."\n";
    }
    $ip = long2ip($i);
    $h = substr(crypt(md5($ip.IDSEED.gmdate("Ymd", $time+9*60*60)),'id'),-8);
    if($target === $h){
        echo $ip."\n";
        break;
    }
}

原本我還想說因為 futaba.php 本身是以 Shift-JIS 儲存的，所以我也把暴搜的腳本存成 Shift-JIS 使得 IDSEED 相同再去炸 ip。只是後來發現說還是要存 UTF-8 才能成功炸出 ip