2022 BalsnCTF Crypto Writeup

2022-09-05

字数统计: 2.1k字 | 阅读时长≈ 13分

A high quality competition, at least for crypto challenges. NeSE got the first place and here are some of the crypto writeups by tl2cents.

Yet another RSA with hint, 32 solves, 192 pts

I got the first blood in 30 minutes. It’s about the interesting properties about digit sum. Taking p-digit sum into consideration, for any x in form of p-digit: $x_tx_{t-1}...x_1x_0$ , we take x modulo p-1: $x \equiv \sum^t_0x_i*p^i \equiv \sum_o^tx_i \mod (p-1) = digitSum(x) \mod (p-1)$ . Hence, the hint numbers leak p%n where n= 1,2,…,199. Using the CRT method, we obtain about 286 bits information about p and that’s enough to apply the coppersmith method: construct $f = x*lcm([1\ to\ 199]) + leak$ and find f’s small root.

exp

# sage 9.2
n = 69769370315605399620499157110259161770226204413410714287546175640222894393734656823609842094208000324903785445480970937467772043771047139468214623293799193606693151204028152125827120312591965423568920046988483517193159267137262989786922993050699199470525597334312901558499603311835177928669168435353736304603
e = 65537
c = 44629586340631092032969036077439025547731549046317830052768219747251144452428756243443530079705365300095620187777995163429306743725384004785137984724398460770780400852341911649904759816676765406154144761671142475150796245779492784073799771022568183264838096756108860913879311490014711507384458820460700533977
hint = [250, 305, 371, 421, 519, 569, 583, 621, 746, 679, 787, 821, 880, 919, 899, 1021, 1038, 1151, 1133, 1229, 1157, 1205, 1237, 1301, 1399, 1335, 1574, 1549, 1495, 1469, 1564, 1709, 1634, 1633, 1759, 1673, 1794, 1817, 1790, 1989, 1971, 2081, 2058, 2041, 2114, 2065, 2239, 2381, 2193, 2199, 2432, 2297, 2500, 2519, 2459, 2501, 2558, 2597, 2647, 2609, 2750, 2711, 2627, 2765, 2609, 3053, 2931, 3333, 2939, 2809, 2843, 2789, 3002, 3089, 2924, 3185, 3306, 3389, 3169, 2989, 3302, 3201, 3153, 3089, 2874, 3305, 3554, 3493, 3822, 3419, 3467, 3261, 3548, 3461, 3679, 3533, 3420, 4251, 4274, 4249, 3967, 4013, 4172, 4117, 3824, 4461, 3707, 4193, 3585, 4109, 4532, 4237, 4009, 4439, 4089, 4917, 3896, 4181, 4370, 3989, 4032, 4641, 4841, 4509, 4324, 4643, 4379, 4685, 4595, 5079, 4437, 5165, 5161, 4271, 5624, 4557, 4570, 4871, 5191, 5189, 4871, 4689, 4923, 5597, 4859, 4973, 5084, 5457, 5196, 5099, 4855, 5541, 5237, 5077, 5284, 5729, 5468, 5539, 5468, 5709, 5308, 5813, 6201, 6317, 5264, 4979, 6540, 5693, 5885, 5679, 5921, 5713, 6086, 6425, 5574, 6221, 5774, 6581, 6422, 6209, 6324, 5651, 6227, 6021, 6789, 6617, 6155, 6657, 6218, 6719, 5820, 6221, 6026, 6815, 6509, 6113, 6731, 7343]

m = list(range(2-1, 200-1))
p_low = crt(hint,m)
M = lcm(m)

# k*M + p_low
# n = (k*M + p_low)*q
PR.<x> = PolynomialRing(Zmod(n))
f = x*M + p_low
roots = f.monic().small_roots(X=2**222,beta=0.4)
print(roots)
# [5784150875484499037995939504927189783710817356645353949424936206149]
k = 5784150875484499037995939504927189783710817356645353949424936206149
p = (k*M + p_low)
q = n//p
assert n==p*q

print(long_to_bytes(int(pow(c,inverse(65537,(p-1)*(q-1)),n))))

VSS, 9 Solves, 369 pts

This challenge can be decomposed into two subproblems. Denote the data we receive from the server as $p_1,a,b,c,p_2,g,Y$ , a quick observation is that since $p_2$ is chosen randomly, we can compute the discrete logarithm in its subgroup with small order. That is to say, $\{g,Y\}$ leaks $y \mod n$ where n is a small divisor of $p_2-1$ . With this leakage, we now can transform the challenge to a hidden number problem (HNP) with two unknown values and this is the second subproblem we need to handle.

Subgroup discrete logarithm.

In this section, we focus on recovering as much information about $y$ as possible from the data $Y,g$ , where $g^y \equiv Y \mod p_2$ . Since $p_2-1$ is not a strong prime, with high probability there are small factors of $p_2-1$ . We can brute force all the small factors less than $2^{25}$ or use the factdb (pip install factordb-pycli) interface to obtain more small factors. Denote the lcm of all the factors as $n$ . After this, we aim to find its max subgroup order which means some of the factors are useless for discrete logarithm (for example: $g = g_0^{p_1*p_2*k}$ , where $g_0$ is the generator for $GF(p_2)$ ， then $p_1,p_2$ is useless). Then use the Pohlig—Hellman algorithm to solve the subgroup discrete logarithm.

# sage 9.2
def get_factor_list_with_exponent(n):
    if isPrime(n):
        return {n: 1}
    for _ in range(10):
        factor = FactorDB(n)
        factor.connect()
        factor_list = list(factor.get_factor_list())
        if len(factor_list) > 1:
            break
    factor_list_with_exponent = {}
    for factor in factor_list:
        if factor not in factor_list_with_exponent.keys():
            factor_list_with_exponent[factor] = 1
        else:
            factor_list_with_exponent[factor] += 1
    return factor_list_with_exponent

# use factDB
def find_small_factors(p, B = 2**25):
    factor_list = get_factor_list_with_exponent(p-1)
    fl = []
    for factor in factor_list.keys():
        if factor < B:
            fl.append(factor ** factor_list[factor])
    return fl

# brute force
def find_small_factors(p, B = 2**25):
    fl  = []
    ps = primes(B)
    for f in ps:
        if (p-1)%f!=0:
            continue
        g = f
        while (p-1)%g == 0:
            g*=f
        fl.append(g//f)
    return fl

def find_max_subgroup(small_facts, g, p):
    small_fact = lcm(small_facts)
    big_fact = (p - 1) // small_fact
    all_sf = divisors(small_fact)
    y = pow(g, big_fact, p)
    if y == 1:
        print("Bad")
        return
    for sf in all_sf:
        if pow(y, sf, p) == 1:
            return sf
# how to leak
p1, a, b, c, p2, g, Y = get_data()
fl = find_small_factors(p2)
n = find_max_subgroup(fl, g, p2)
g_bar = pow(g, (p2 - 1) // lcm(fl), p2)
Y_bar = pow(Y, (p2 - 1) // lcm(fl), p2)
leak_x = discrete_log(Y_bar, g_bar, ord=n)
leak = n.nbits()
print("[+] subgroup order bits", leak)
print("[+] leak x  ", leak_x)

Hidden number problem with two unknown values

Now, we get an oralce as follows:

$leak : \quad ((a+b*k_1+c*k_2) \mod p) \mod n \ \rightarrow denoted \ as \ x \\ unknown : k_1,k_2 \\ expand \ the \ mod: x + n*u \equiv a+b*k_1+c*k_2 \mod p\\ \iff (a-x)*n^{-1}+k_1*(n^{-1}b)+k_2*(n^{-1}*c) \equiv u \mod p \\ \iff \bar{a}+k_1*\bar{b}+k_2*\bar{c} \equiv u \mod p$

Denote $\alpha = n.nbit()$ , the upper bound of $u$ is : $B =2^{512-\alpha}$ , therefore we can construct a lattice to solve this problem with enough samples and large $\alpha$ . The basic lattice I use is as follows:

$M=\begin{bmatrix} \bar{a_1} & \bar{a_2} &... & \bar{a_t} & B & 0 & 0\\ \bar{b_1} & \bar{b_2} &... & \bar{b_t} & 0 & \frac{B}{2^{512}} & 0\\ \bar{c_1} & \bar{c_2} &... & \bar{c_t} & 0 & 0 & \frac{B}{2^{512}}\\ p_1 & 0 &... & 0 & 0 & 0 & 0 \\ 0 & p_2 &... & 0 & 0 & 0 & 0 \\ . & . &... & . & . & . & . \\ 0 & 0 &... & p_t & 0 & 0 & 0 \end{bmatrix} \\ \implies short \ vector : \vec{U}=(u_1,u_2,...,u_t,B,\frac{k_1B}{2^{512}},\frac{k_2B}{2^{512}})$

With enough data samples, we can obtain the secret $k_1,k_2$ by LLL reduction on the above lattice. In my local test, let the lower bound of leak bits be $\alpha = 25$ , we need at least $t=46$ data sets. So far, we have solved this challenge. But for the remote solver, we may need extra optimization. One way is to increase the bound of small factors in the subgroup problem (such as $2^{50}$ ). Here I’ll introduce two ways to optimize the above lattice.

Observe that the $n$ varies a lot, the max n can be 70-bit long. Therefore, the above lattice doesn’t make the most of leaked information. Denote $n_i.nbits()= \alpha_i$ and replace B in M with $\bar{B} =(\sum_1^tn_i)/t$ , I’ll explain two methods to make the above lattice more effective.

Using the CVP method: let $\vec{V} = (2^{512-\alpha_1},2^{512-\alpha_2},...,2^{512-\alpha_t}, \bar{B},\frac{k_1\bar{B}}{2^{512}},\frac{k_2\bar{B}}{2^{512}})$ be the target vector, we can run Baiba algorithm to solve the CVP. Hopefully, we can can get $\vec{U}$ .
Using the adjustment multiplier: multiply every column of M by $2^{\alpha_i-\alpha}$ . After this operation, we enlarge the row vectors’ length and doesn’t change the short vector $\vec{U}$ . Therefore, we can find the short vector with higher probability by the LLL theorem. (My teammate Lord Riot implemented this method)

# sage 9.2
import telnetlib
from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import os
import random
from hashlib import sha256
from factordb.factordb import FactorDB


def get_factor_list_with_exponent(n):
    if isPrime(n):
        return {n: 1}
    for _ in range(10):
        factor = FactorDB(n)
        factor.connect()
        factor_list = list(factor.get_factor_list())
        if len(factor_list) > 1:
            break
    factor_list_with_exponent = {}
    for factor in factor_list:
        if factor not in factor_list_with_exponent.keys():
            factor_list_with_exponent[factor] = 1
        else:
            factor_list_with_exponent[factor] += 1
    return factor_list_with_exponent


class ShareScheme:
    def __init__(self, key: bytes):
        assert len(key) == 128
        self.key1 = bytes_to_long(key[:64])
        self.key2 = bytes_to_long(key[64:])

    def getShare(self):
        p = getPrime(512)
        a = random.randint(2, p - 1)
        b = random.randint(2, p - 1)
        c = random.randint(2, p - 1)
        y = (a + self.key1 * b + self.key2 * c) % p
        return p, a, b, c, y


def commit(val: int):
    p = getPrime(512)
    g = random.randint(2, p - 1)
    return p, g, pow(g, val, p)


def readline():
    return io.read_until(b"\n")


def writeline(l):
    io.write(l + b"\n")


def find_small_factors(p, B = 2**25):
    factor_list = get_factor_list_with_exponent(p-1)
    fl = []
    for factor in factor_list.keys():
        if factor < B:
            fl.append(factor ** factor_list[factor])
    return fl


def find_max_subgroup(small_facts, g, p):
    small_fact = lcm(small_facts)
    big_fact = (p - 1) // small_fact
    all_sf = divisors(small_fact)
    y = pow(g, big_fact, p)
    if y == 1:
        print("Bad")
        return
    for sf in all_sf:
        if pow(y, sf, p) == 1:
            return sf


io = telnetlib.Telnet('vss.balsnctf.com', '9876')
encflag = readline()
enc = bytes.fromhex(encflag.strip(b"\n").split(b" ")[-1].decode())
print(encflag)


def Get_data():
    if local:
        p1, a, b, c, y = ss.getShare()
        p2, g, Y = commit(y)
        return p1, a, b, c, p2, g, Y

    io.read_until(b"Option: ")
    writeline(b"1")
    p1 = int(readline().strip(b"\n").split(b" ")[-1])
    a = int(readline().strip(b"\n").split(b" ")[-1])
    b = int(readline().strip(b"\n").split(b" ")[-1])
    c = int(readline().strip(b"\n").split(b" ")[-1])
    p2, g, Y = [int(i) for i in readline().strip(b"\n").split(b" ")[1:]]
    return p1, a, b, c, p2, g, Y


a_bars = []
b_bars = []
c_bars = []
p_s = []
n_bars = []
t = 35
leak_bits = 25

data_ls = []
for _ in range(1000):
    try:
        data_ls.append(Get_data())
    except:
        print("[+] Get data sets: ", len(data_ls))
        break

for data in data_ls:
    print("[+] samples number = ", len(p_s))
    if len(p_s) > t:
        break
    p1, a, b, c, p2, g, Y = data
    fl = find_small_factors(p2)
    n = find_max_subgroup(fl, g, p2)
    if n is None:
        continue
    g_bar = pow(g, (p2 - 1) // lcm(fl), p2)
    Y_bar = pow(Y, (p2 - 1) // lcm(fl), p2)
    leak_x = discrete_log(Y_bar, g_bar, ord=n)
    leak = n.nbits()
    print("[+] subgroup order bits", leak)
    print("[+] leak x  ", leak_x)

    if leak >= leak_bits:
        n_inv = inverse(n, p1)
        a_bar = (a - leak_x) * n_inv % p1
        b_bar = b * n_inv % p1
        c_bar = c * n_inv % p1
        a_bars.append(a_bar)
        b_bars.append(b_bar)
        c_bars.append(c_bar)
        n_bars.append(n)
        p_s.append(p1)
    else:
        continue

print("[+] Start to build matrix")
Bounds = 2 ^ (512 - leak_bits)
adjust = [2 ^ (ZZ(ni).nbits() - leak_bits) for ni in n_bars]
t = len(p_s)
M1 = matrix(QQ, [[a_bars[i] * adjust[i] for i in range(t)],
                 [b_bars[i] * adjust[i] for i in range(t)],
                 [c_bars[i] * adjust[i] for i in range(t)]])
M2 = matrix.identity(QQ, t)
for i in range(t):
    M2[i, i] = p_s[i] * adjust[i]
A = block_matrix([[M1], [M2]], nrows=2)

B = zero_matrix(QQ, t + 3, 3)
B[0, 0] = Bounds
B[1, 1] = Bounds / 2 ** 512
B[2, 2] = Bounds / 2 ** 512


M = block_matrix([A, B], nrows=1)
print("[+] Start to LLL")
L = M.LLL()
print("[+] LLL done")

k1 = int(L[0][-2] * 2 ** 512 / Bounds)
k2 = int(L[0][-1] * 2 ** 512 / Bounds)

key = long_to_bytes(k1) + long_to_bytes(k2)
real_key = sha256(key).digest()[:16]
cipher = AES.new(real_key, AES.MODE_ECB)
flag = cipher.decrypt(enc)
print(f"[+] flag: {flag}")

Old but gold, 4 solves, 438 pts

Another teammate of mine solved this challenge, but it requires hard work on reversing the binary file compiled by go. I didn’t do much work on this. The solution is oracle attack about CFB mode. The server will provide the information about whether the token is valid json bytes by its structure like “{…}” or “ space,\t,\n,\r”. The padding is unsecure, too. The server takes only the last byte of decrypted token as padding length and then unpads the decrypted token. Using the above oracle, we can control the blocks’ plaintext and thus we can forge the following token:

1	target = b'{"Type":"admin","ID":"aaaaaaaa-bbbb-cccc-dddd-ffffffffffff","Mail":"admin"}'

All done. Exp is not written by me, so I don’t upload it.