廢文集中區

HITCON CTF 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 .

Participated in HITCON CTF 2021 with Goburin' and got 10th place, second in Taiwan. This time I mainly solved a few crypto and web challenges, and only slightly helped with misc and reverse. Unfortunately, I couldn't solve the NTRU crypto challenge because I had to take a Japanese exam halfway through the competition.

  Scoreboard Screenshot

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)

The pp and qq in RSA are generated using an LCG. The method of generating primes is straightforward: it checks if a number is prime, and if not, it moves to the next one. Thus, pp and qq have a polynomial relationship: q=f(p)q=f(p), where f(x)f(x) is an unknown degree LCG iteration.

By conducting some experiments, we can determine that pp and qq are approximately within 600 iterations of each other. Therefore, we can brute force the number of iterations to find the polynomial f(x)f(x). Then, using p⋅f(p)≡N(modM)p \cdot f(p) \equiv N \pmod{M}, we can solve for 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)))

Although this challenge was easy, I didn't expect to get the 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))

This challenge involves an unbalanced RSA where d=pd=p. Thus, en≡epq≡q(modφ(n))en \equiv epq \equiv q \pmod{\varphi(n)}, so 2en≡2q(modn)2^{en} \equiv 2^q \pmod{n}. We can reduce this modulo qq, and by Fermat's Little Theorem, 2en≡2q≡2(modq)2^{en} \equiv 2^q \equiv 2 \pmod{q}. Therefore, gcd⁡(2en−2,n)\gcd(2^{en}-2,n) is a nontrivial factor qq of nn.

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

The interesting part of this challenge is that the flag mentions Coppersmith. The intended solution probably involves using men≡m(modq)m^{en} \equiv m \pmod{q}, then taking c′=men(modn)c' = m^{en} \pmod{n} and using Coppersmith to find the small root mm of f(x)=x−c′f(x)=x-c'. (The flag is short enough to satisfy m<n0.752m<n^{0.75^2})

To restrict the solution to this method, the author might need to remove ee as well.

I had a similar idea before, but I didn't use unbalanced RSA. I tried it out for 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')

The goal is to choose n,en,e such that n >> 248 == magic, and then find d1e≡SHA384⁡(d1)(modn)d_1^e \equiv \operatorname{SHA384}(d_1) \pmod{n}.

Although the challenge title says RSA, it's clearly a dlog problem. The goal is to find an nn that allows for fast dlog computation and also satisfies the magic condition.

I solved this challenge using n=2p2n=2p^2 because I found here that this is one form of a cyclic group, allowing us to find a generator that covers the entire group. I brute-forced p−1p-1 until it was smooth enough.

Then, I took any power of the generator as d1d_1 and used dlog to find a suitable one.

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

This challenge is almost the same as the previous one, but this time it requires a prime number. So, we need to find a p−1p-1 that is smooth and satisfies p=2248magic+kp=2^{248}\mathit{magic}+k.

I found the paper Finding Smooth Integers in Short Intervals Using CRT Decoding and implemented the algorithm:

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

However, I found that it only works for very smooth numbers. If the ss in s-smooth\text{s-smooth} is slightly larger, the numbers become too large, causing LLL to run for a long time. So, I abandoned this method.

Later, I realized that when k=1k=1, the smoothness of p−1=2248magicp-1=2^{248}\mathit{magic} is equivalent to magic\mathit{magic}. So, I brute-forced the server until magic\mathit{magic} itself was smooth enough. Then, I used the same method to find d1d_1 and compute 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))

This challenge is a standard NTRU implementation with normal parameter sizes, so we can't directly use LLL to find the private key.

The weakness lies in the fact that random uses Python's built-in MT19937, and it provides more than 240×200>32×624240 \times 200 > 32 \times 624 outputs, which is enough to reconstruct the state of MT19937.

The tricky part is that 240 is not a multiple of 32, so we can't use the usual MT19937 recovery scripts that require 624 consecutive 32-bit outputs.

I used the MT19937 Symbolic Execution and Solver I found during Balsn CTF. It can quickly recover the state using only the top 4, 8, 16, or 32 bits. Since 2×240×200>32×6242 \times 240 \times 200 > 32 \times 624 still holds, we can split the 240 bits into 8 parts and keep only the top 16 bits of 7 parts. Feeding this into the solver allows us to recover the state of random.

Then, we need to read how Python's random.shuffle is implemented and backtrack the appropriate state numbers to get rr. Thus, c−rh mod q=mc-rh \bmod{q} = m gives us the 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

In this challenge, you can choose any file in /var/www/html of wordpress:5.8.2-apache and flip one bit of one byte. An additional service allows you to select the path, byte, and bit, and dynamically generates a new WordPress instance using Docker.

The solution is to modify the login check on line 174 of wp-includes/user.php:

	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>'
		);
	}

Since ! and a space character differ by only one bit, changing the ! to a space allows arbitrary login. After logging in as admin, you can upload a webshell in the plugin upload area to achieve RCE and get the flag.

In this version, the path is /var/www/html/wp-includes/user.php, byte: 5389, and bit: 0.

Another potential approach is that , and . also differ by one bit, which might allow some parameter passing to be converted to string, possibly enabling other exploits.

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

The source code for this challenge is very short. It places several parameters into YAML, parses them, performs some escaping, and then executes a command.

Seeing YAML and country codes immediately reminded me of The Norway Problem: NO in YAML represents false, and Norway's country code is also NO. So, if the country code is not quoted in YAML, it will cause issues when encountering Norway.

Using a Norwegian VPN changes the second element of $arr to false. In the loop below, it enters the if statement, unset($arr[2]), and continues. However, after unset, count($arr) changes, causing $mail to not be escaped.

The remaining task is to use a payload that passes FILTER_VALIDATE_EMAIL for command injection. One such payload is:

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

The extra a is added to ensure it passes YAML parsing.

misc

FBI WARNING

This challenge involves an imageboard similar to 2ch, but the posting function is disabled. The goal is to find the IP address of the only commenter, Ωrange, with the flag format hitcon{<ip-address-of-Ωrange>}.

Searching in Japanese makes it easier to find relevant information. On 2ch's スクリプト ダウンロード, you can find the futaba.php script.

Reviewing the source code, we see that the ID is generated by the following code:

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

Where IDSEED is a constant defined at the beginning:

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

Assuming the IDSEED hasn't been changed, knowing the time allows us to brute force all IPv4 addresses to find the one that matches the target ID (ueyUrcwA).

Continuing to read, we see the following code in the regist function:

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

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

So, the uploaded file name is formed by concatenating the current time $time and substr(microtime(),2,3). Conveniently, Ωrange's comment includes an uploaded image with the filename 1638537259302.jpg, indicating the posting time was 1638537259.

We can write a PHP script to brute force the 2322^{32} IPv4 addresses. Later, Orange provided a hint that the IP starts with 219, reducing the search space to 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;
    }
}

Initially, I thought the futaba.php script was stored in Shift-JIS, so I saved the brute force script in Shift-JIS to match the IDSEED. However, I later found that saving it in UTF-8 was necessary to successfully find the IP.