ImaginaryCTF Round 53 - modjail series
I found some interesting crypto challenges in Imaginary CTF round 53. Among those, the modjail series drew most of my attention due to its cleverly hidden problem. This post will cover my writeup of the series.
modjail#
Source Code#
#!/usr/bin/python3
from Crypto.Util.number import getPrime, long_to_bytes
from secret import flag
from secrets import randbelow
p = getPrime(1024)
r = randbelow(p)
print(f'{r} mod {p}')
n = int(input())
if n%p != r:
print('no')
exit()
print(eval(long_to_bytes(n)))
Challenge Analysis#
- In this series, we have to find a number $n$ with 2 constraints:
- Satisfy an equation modulo a given prime $p$,
print(eval(long_to_bytes(n)))will somehow give us the flag.
- The objective is to recover the flag.
Solution#
As this a jail challenge, there are multiple solutions to the second condition. But since the output of eval is printed out and the first condition might make the long_to_bytes(n) contains lots of gibberish bytes. Therefore to make it align to Python syntax, I chose the payload of this form: flag# [S]. With #, most of the gibberish values will not be considered when passing to eval.
A constraint for S is that it must not contain \x00 and \x0a bytes. The first one is prohibited by default when using with eval, and the second one will break out of the comment, thus causing syntax error.
In the challenge, we are given 2 values $p$ and $r$ upon the connection. The first condition can now be expressed as: Find a number $n$ such that $n \equiv r \pmod{p}$.
Let’s denote $n_0 = $ long_to_bytes(b'flag# ' + S), then we can find the nearest multiples of $p$ and add $r$ to find such $n$. I only need the final payload has flag# as the prefix, so I can craft S very big compared to $r$ and $p$ (e.g. 2048 bits), therefore only LSBs are affected when $n$ in constructed in such way.
Solve Script#
from Crypto.Util.number import long_to_bytes, bytes_to_long
from pwnlib.tubes.remote import remote
original = b'flag#'
io = remote("155.248.210.243", 42114)
r, p = map(int, io.recvline().decode().strip().split(' mod '))
original = b'flag#' + b'\x01' * 128
for i in range(1024):
tmp = original + i * b'\x01'
k = bytes_to_long(tmp) // p + 1
payload = long_to_bytes(k * p + r)
if b'\x00' not in payload and b'\n' not in payload:
io.sendline(str(bytes_to_long(payload)).encode())
io.interactive()
break
modjail2#
Source Code#
#!/usr/bin/python3
from Crypto.Util.number import getPrime, long_to_bytes
from secret import flag
from secrets import randbelow
from time import sleep
p = getPrime(256)
r = randbelow(p)
print(f'{r} mod {p}')
n = int(input())
if n%p != r:
print('no')
exit()
m = long_to_bytes(n).decode()
strikes = 0 # 3 and you're out!
for c in m:
sleep(0.01)
if not (ord('a') <= ord(c) <= ord('z')):
strikes += 1
print(f'strike {strikes}{"!"*strikes}')
if strikes >= 3: exit()
print(eval(m))
Solution#
This challenge adds 1 more constraint: long_to_bytes(n) can only contains AT MOST 2 non-lowercase bytes. I continued to use the format 'flag#' + [S], so now our S can contains lowercase characters a-z and 1 arbitrary bytes.
Let $M = \overline{c_{l-1}c_{l-2}..c_1c_0} $ be a bytestream of length $l$ then its numerical expression $BTL(M)$:
$$BTL(M) = \sum_{i = 0}^{l - 1}256^ic_i$$
Applying the equation to my chosen format with $m_0 = BTL(flag\#)$ and $l$ is the length of S, I have:
$$n = 256^{l}m_0 + \sum_{i = 0}^{l - 1}256^ic_i$$
$$\Rightarrow 256^lm_0 + \sum_{i = 0}^{l - 1}256^ic_i \equiv r \pmod{p}$$
$$\Rightarrow \sum_{i = 0}^{l - 1}256^cc_i \equiv r - 256^lm_0 \pmod{p}$$
Now the problem is to solve the modular equation to find small roots $c_i \in [97, 122]$. This can be done via the LLL algorithm. As LLL will try to find roots as close to 0 as possible, I balance out the expected vectors to make the range of its entries has 0 as center. This can be done by defining $d_i = c_i - 109 \Rightarrow d_i \in [-12, 13]$, then I have:
$$\sum_{i = 0}^{l - 1}256^i(d_i + 109) \equiv r - 256^lm_0\pmod{p}$$
$$\Rightarrow 256^0d_0 + 256^1d_1 + … + 256^{l - 1}d_{l - 1} \equiv r - 256^lm_0 -109\sum_{i = 0}^{l - 1}256^i\pmod{p}$$
Let $s =r - 256^lm_0 -109\sum_{i = 0}^{l - 1}256^i$, then define matrix $M$ as follow:
$$
\begin{align}
M = \left(
\begin{array}{cccccc}
1 & 0 & \dots & 0 & 0 & 256^0 \\
0 & 1 & \dots & 0 & 0 & 256^1 \\
\vdots & \vdots & \vdots & \vdots & 0 & \vdots \\
0 & 0 & \dots & 1 & 0 & 256^{l - 1} \\
0 & 0 & \dots & 0 & 1 & s \\
0 & 0 & \dots & 0 & 0 & p
\end{array}
\right)
\end{align}
$$
which has a short vector $v = [d_0, d_1, …, d_{l - 1}, -1, 0]$.
Then I only need to bruteforce $l$, find the row in which last 2 entries are $[-1, 0]$ and the rest in range $[-12, 13]$, calculate $n$ and send it to the server.
Solve Script#
from sage.all import *
from Crypto.Util.number import bytes_to_long
from pwnlib.tubes.remote import remote
W = 1
original = b'flag#'
io = remote("155.248.210.243", 42115)
r, p = map(int, io.recvline().decode().strip().split(' mod '))
for length in range(70, 200):
print(f'{length = }')
m0 = bytes_to_long(original + b'\x00' * length)
col = [pow(256, i, p) for i in range(length)]
target = (r - m0 - 109 * sum(col)) % p
col = col + [target]
L = block_matrix(ZZ, [
[identity_matrix(len(col)), column_matrix(col)],
[0, p]
])
L = L.LLL()
for row in L:
if row[-1] != 0 or row[-2] != -1:
continue
if any(not(-12 <= x <= 13) for x in row[:-2]):
continue
row = [109 + x for x in row[:-2]][::-1]
password = original + bytes(row)
if bytes_to_long(password) % p != r:
continue
print(f'Found {password = }')
io.sendline(str(bytes_to_long(password)).encode())
io.interactive()
break
modjail3#
Solution#
There is a new function called wild, which is defined as follow:
def wild(n):
return bytes_to_long(repr(n).encode()) == p
Basically, wild convert each digit in $n$ to its ASCII value (0 -> 48, 1 -> 49, …) then treat those ASCII values as a bytestream and convert it to corresponding integer.
$n$ now has to satisfy the following property: $n \equiv wild(n) \pmod{p}$
Finding $n$ such that $n \equiv wild(n) \pmod{p}$#
Let $n = \overline{a_{l - 1}a_{l - 2}..a_1a_0}$ where $a_i \in [0, 9]$, so I have:
$$n = \sum_{i = 0}^{l - 1}10^ia_i$$
$$wild(n) = \sum_{i = 0}^{l - 1}256^i(a_i + 48) = \sum_{i = 0}^{l - 1}256^ia_i + 48\sum_{i = 0}^{l - 1}256^i$$
$$ \Rightarrow \sum_{i = 0}^{l - 1}10^ia_i \equiv \sum_{i = 0}^{l - 1}256^ia_i + 48\sum_{i = 0}^{l - 1}256^i \pmod{p}$$
$$\Rightarrow \sum_{i = 0}^{l - 1}(10^i - 256^i)a_i \equiv 48\sum_{i = 0}^{l - 1}256^i \pmod{p}$$
But Zayn, where does 48 come from? Indeed, the action of converting a digit $a_i$ into its ASCII value can be expressed as $f(a_i) = a_i + 48$. So 0 is 48, 1 is 49, 2 is 50 and so on.
The problem of finding $n$ is now similar too modjail2 and I can solve it with LLL. Since $a_i \in [0, 9]$ is not centered around 0, I define $b_i = a_i - 5 \Rightarrow b_i \in [-5, 4]$. Let $s = 48\sum_{i = 0}^{l - 1}256^i - 5\sum_{i = 0}^{l - 1}(10^i - 256^i)$, the following matrix $M$ will have $v = [b_1, …, b_{l - 1}, -1, 0]$ as a short vector:
$$
\begin{align}
M = \left(
\begin{array}{cccccc}
1 & 0 & \dots & 0 & 0 & 10^1 - 256^1 \\
0 & 1 & \dots & 0 & 0 & 10^2 - 256^2 \\
\vdots & \vdots & \vdots & \vdots & 0 & \vdots \\
0 & 0 & \dots & 1 & 0 & 10^{l - 1} - 256^{l - 1} \\
0 & 0 & \dots & 0 & 1 & s \\
0 & 0 & \dots & 0 & 0 & p
\end{array}
\right)
\end{align}
$$
Craft $n$ to have flag# as prefix#
The problem with $n$ found by the previous section is that its bytes form only contains gibberish values instead of following my selected format ('flag#' + [S]). At first, I hope that by increasing $l$, there is a chance that $n$ obtained from above approach has flag# when converting to bytes. However this did not work out according to my experiment for $l \le 180$
Therefore, I tried new idea: If I fix some most-significant (MS) digits of $n$, then can I find the rest digits to make it satisfy the condition? Turn out the answer is yes.
For a random number $n$, the 5 MS bytes of $LTB(n)$ (the $LTB$ function converts a number into bytes) is determined by $n / 256^{l - 5}$ where $l$ is the length of $LTB(n)$. Or in short, MS digits determine MS bytes. For example, the following numbers all have 1645879958137 as the prefix and their $LTB$s have flag# as a prefix too.
1645879958137 18622250011390837678245756542061662962959919673933 flag#\xb5\x8b\xc6J0\x83\x10j\xb5y\xd5-\xdf\x9a'\xdf\t\xe2\xd4\xf2M
1645879958137 54797919548001321220014467010580692716798274751696 flag#\xceLcjHB\xc5~m\xa9q\x19\x8aEb\x99\xbeV\xec\xcc\xd0
1645879958137 04370019905726608943316373149044356675622662460717 flag#\xab\xcbR0L\xf1`\xc1iRX5\xaa\xab\xc7>\x8d\xda&U-
After found the desired MS digits $n_{M}$, the goal is to find the rest digits $n_{L}$ of $n$ such that $n \equiv wild(n) \pmod{p}$. I solved this by first rewrite $n = 10^k \times n_{M} + n_{L} \Rightarrow wild(n) = wild(10^k \times n_{M} * + n_{L})$
First, let’s try to express $n$, $n_M$ and $n_L$ in digits:
Therefore, the outputs of applying $wild$ function on those numbers are:
$$ \displaylines{wild(10^k \times n_M) = \sum_{i = k}^{l_1 + k - 1}256^ia_i + 48\sum_{i = 0}^{l_1 + k - 1}256^i \\ wild(n_L) = \sum_{i = 0}^{l_2 - 1}256^ib_i + 48\sum_{i = 0}^{l_2 - 1}256^i \\ wild(n) = \sum_{i = k}^{l_1 + k - 1}256^ia_i + \sum_{i = 0}^{l_2 - 1}256^ib_i + 48\sum_{i = 0}^{l_1 + k - 1}256^i \\ \Rightarrow wild(n) = wild(10^k \times n_M) + wild(n_L) - 48\sum_{i = 0}^{l_2 - 1}256^i } $$
Combine this with the original condition, i.e. $n \equiv wild(n) \pmod{p}$: $$\displaylines{ n \equiv wild(10^k \times n_M) + wild(n_L) - 48\sum_{i = 0}^{l_2 - 1}256^i \pmod{p} \\ \Rightarrow 10^k \times n_M + n_L \equiv wild(10^k \times n_M) + wild(n_L) - 48\sum_{i = 0}^{l_2 - 1}256^ i\pmod{p} \\ \Rightarrow n_L \equiv wild(n_L) + m_0 \pmod{p} } $$ with $m_0 = wild(10^k \times n_M) - 48\sum_{i = 0}^{l_2 - 1}256^i - 10^k \times n_M$
Now this problem is find $n_L$ such that $n_L \equiv wild(n_L) + m_0 \pmod{p}$ where $m_0$ is a known value. Therefore I can adjust the lattice in previous section to solve for $n_L$, send it to the server and grab the flag.
Solve Script#
from sage.all import *
from Crypto.Util.number import long_to_bytes, bytes_to_long
from pwnlib.tubes.remote import remote
from subprocess import run as subprocess_run
from re import findall
flatter_path = "/usr/local/bin/"
flag = 123
def flatter(M):
z = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]"
ret = subprocess_run(flatter_path + "flatter", input=z.encode(), cwd=flatter_path, capture_output=True)
if ret.returncode != 0:
print(ret.stderr)
raise ValueError(f"LLL failed with return code {ret.returncode}")
ret = ret.stdout
return matrix(ZZ, M.nrows(), M.ncols(), map(int, findall(b"-?\\d+", ret)))
def wild(num):
return bytes_to_long(repr(num).encode()) % p
io = remote('155.248.210.243', 42111)
p = int(io.recvline().decode().strip())
print(f'{p = }')
for length in range(10, 60):
print(f'{length = }')
v10 = [pow(10, i, p) for i in range(1, length)]
v256 = [pow(256, i, p) for i in range(1, length)]
col = [(a - b) % p for a, b in zip(v10, v256)]
target = (48 * (sum(v10) + 1) - 53 * sum(col) - 48 * (sum(v256) + 1)) % p
base = bytes_to_long(b'flag#' + b'\7f\x7f' + (length + 1) * b'\x00')
digits = str(base)
for i in range(1, len(digits)):
tmp = int(digits[:i] + '0' * (len(digits) -i))
if long_to_bytes(tmp)[:5] != b'flag#':
continue
print(f'Found {tmp = }')
base = tmp
target = (target - base + wild(base) % p)
break
col += [target]
L = block_matrix(ZZ, [
[identity_matrix(len(col)), column_matrix(col)],
[0, p]
])
L = flatter(L)
for row in L:
if row[-1] != 0 or row[-2] != -1:
continue
if any(not(-5 <= x <= 4) for x in row[:-2]):
continue
num = ''.join(str(x + 5) for x in row[:-2])
num2 = int(num[::-1] + '0')
val = base + num2
print(long_to_bytes(val))
if b'\x00' in long_to_bytes(val) or b'\n' in long_to_bytes(val):
continue
try:
print(eval(long_to_bytes(val)))
except SyntaxError:
continue
io.sendline(str(val).encode())
io.interactive()
exit()