x3CTF 2025 (feat. mvm) Writeup

, , , ,

Before all

Rank: 27
Team: ICEDTEA
I participated in this cute CTF with ICEDTEA as my last CTF before chinese new year, and I almost AK all Crypto Challenges … (Except BabyRNG)
After all, I really love these cute challenges and they can also be a good piece of lecture to my junior teammates in ICEDTEA!

Writeup

Crypto

man-vs-matrix

challenge.py 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from sage.all import *
from Crypto.Util.number import bytes_to_long

class RNG:

    def __init__(self, seed):
        self.p = next_prime(2**24)
        self.F = GF(self.p)
        self.M = matrix(self.F, 3,3, [bytes_to_long(seed[i:i+3]) for i in range(0, len(seed), 3)])
        self.state = vector(self.F, map(ord, "Mvm"))
        self.gen = self.F(2)

    def get_random_num(self):
        out = self.M * self.state

        for i in range(len(self.state)):
            self.state[i] = self.gen**self.state[i]

        return out * self.state

flag = b"MVM{???????????????????????????}"
seed = flag[4:-1]

rng = RNG(seed)
samples = []

for i in range(9):
    samples.append(rng.get_random_num())

print(f"{samples = }")
# samples = [6192533, 82371, 86024, 4218430, 12259879, 16442850, 6736271, 7418630, 15483781]

This is a RNG with an initial state “Mvm” with every 3*3 matrix input (splitted from the flag with 3 chars a set).
It’s trivial that the state is always predictable in the 9 operations rng.get_random_num()(exponential), and the output value is actually a linear sum with the input matrix and old state*new state as paired parameters.
With 9 output values, the problem would become an easy linear equation (because there’re also 9 unknown variables).
exp.sage 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from Crypto.Util.number import long_to_bytes
samples=[6192533, 82371, 86024, 4218430, 12259879, 16442850, 6736271, 7418630, 15483781]
p=next_prime(2**24)
F=GF(p)
gen=F(2)
state = vector(F, map(ord, "Mvm"))
params=[]
def gen_params():
    for i in range(9):
        old_state=[_ for _ in state]
        cur=[]
        for j in range(len(state)):
            state[j]=gen**state[j]
        for j in range(3):
            for k in range(3):
                cur.append(state[j]*old_state[k])
        params.append(cur)

gen_params()
M=Matrix(F, params)
flag=''
for i in M.solve_right(samples):
    flag+=long_to_bytes(int(i)).decode()

print(flag)

sourceless-crypto

A black box crypto challenge…
First tested with ‘aaaaaa…’ and found out the key value is in some order(like increasing but not), also the max input size is 197 chars (256-len(flag)), so the key may be a permutation of ASCII chars.
Later tested with ‘abcdef…’ and obtained something like this: 

1
2
3
4
5
6
7
Welcome to sourceless-crypto, enjoy the pain
1 -> Show Flag
2 -> Encrypt Plaintext
3 -> exit
Operation: 2
Enter plaintext: abcdefghijklmnopqrstuvwxyz
Encrypted plaintext: b'KOOKK77;;??;;77++//++77;;?'

Cool, some repeated pairs of charaters appeared many times, maybe about bitwise operation…XOR?! (because of the LSB, and I guessed the key is in some kind of order)
To prove my concept, directly connected to the server two times with diffrent inputs, the xor value between the ciphertext and plaintext are all the same, tada~
Last, just observed that the key permutation is a change of order from 0123 to 0132 (same for other sets of numbers).
exp.py 

1
2
3
4
5
6
7
8
from pwn import xor
dataset='1032547698badcfe'
key=b''
for i in dataset:
    for j in dataset:
        key+=bytes.fromhex(i+j)

print(xor(enc, key))

This challenge should be renamed to GUESSY-crypto
Btw, I love this sense of humor!
image

curved-mvm

A signer based on fastecdsa.
Player have two operation chances and the operations are:

  1. Obtain a signed message.
  2. Sign a specify message back, check the value and get the flag if correct.

server.py 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
from sage.all import *

import os
from json import dumps
from secrets import randbits
from Crypto.Util.number import bytes_to_long
from hashlib import sha1

FLAG = os.getenv("FLAG", "MVM{f4ke_fl4g}")

# a wonderful curve
p = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF
a = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC
b = 0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B
Gx = 0x6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296
Gy = 0x4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5

F = GF(p)
EC = EllipticCurve(F, [a, b])
n = EC.order()

SECRET_KEY = bytes_to_long(os.urandom(69420)) % n
G = EC([Gx, Gy])
assert G in EC

Q = SECRET_KEY * G

FUNNY_CREDITS_FOR_FREE_TRIAL = 2

CHALL_NAME = "Curved MVM"

K_SIZE = 18
SAMPLE_MSG = "hardcoded cuz reasons"
REQUIRED_MSG = "mvm mvm mvm"


def sign_msg(msg: str):
    z = bytes_to_long(sha1(msg.encode()).digest()) % n
    k = (randbits(K_SIZE) + 2) % n
    R = k * G
    r = ZZ(R.x()) % n
    s = (k.inverse_mod(n) * (z + r * SECRET_KEY)) % n
    return {"r": hex(r), "s": hex(s)}


def sign_bogus():
    return sign_msg(SAMPLE_MSG)


def verify_signature(r, s, msg):
    z = bytes_to_long(sha1(msg.encode()).digest()) % n

    if r < 1 or r >= n or s < 1 or s >= n:
        return {"error": "funny user uwu"}

    w = s.inverse_mod(n)

    u1 = (z * w) % n
    u2 = (r * w) % n

    P = u1 * G + u2 * Q

    should_r = ZZ(P.x()) % n

    if should_r == r:
        return {"flag": FLAG}
    else:
        # user funny
        return {"error": "invalid signature"}


def mvm():
    r = prompt_integer("r")
    s = prompt_integer("s")
    try:
        return verify_signature(r, s, REQUIRED_MSG)
    except:
        return {"error": "funny user"}


operations = {
    "sign": sign_bogus,
    "mvm": mvm,
}


def prompt_operation():
    _prompt = "/".join(operations)
    prompt = f"({_prompt}): "

    try:
        recv = input(prompt)
    except Exception:
        print("user too funny, complaints will be ignored\n")

    if recv not in operations:
        print("funny operation\n")
        return prompt_operation()

    return operations[recv]


def prompt_integer(name: str):
    prompt = f"{name}: "
    try:
        recv = input(prompt)
    except:
        print("user too funny, complaints will be sent to /dev/null\n")
        return prompt_integer(name)

    try:
        number = int(recv, 16)
    except:
        print("user supplied number too funny, complaints will be ignored\n")
        return prompt_integer(name)

    if number <= 1:
        print("user supplied number funny.\n")
        return prompt_integer(name)

    return ZZ(number)


funny_credits = FUNNY_CREDITS_FOR_FREE_TRIAL

if __name__ == "__main__":
    print(f"Welcome to {CHALL_NAME!r}, enjoy the pain!\n")

    while True:
        print(
            f"You have {funny_credits} funny credit{'s' if funny_credits > 1 else ''}."
        )
        operation = prompt_operation()
        print(dumps(operation()))
        funny_credits -= 1

        if funny_credits == 0:
            print("ran out of funny credits, bye")
            exit()

        print()

Take a close look at function sign_msg

1
2
3
4
5
6
7
def sign_msg(msg: str):
    z = bytes_to_long(sha1(msg.encode()).digest()) % n
    k = (randbits(K_SIZE) + 2) % n
    R = k * G
    r = ZZ(R.x()) % n
    s = (k.inverse_mod(n) * (z + r * SECRET_KEY)) % n
    return {"r": hex(r), "s": hex(s)}

We would get the value of R, since the value of k is too small, it’s feasible to bruteforce/discrete_log on R and obtain the value of k.
After that, the value of k, z, r, n are all known so the value of SECRET_KEY would be leaked, just simply sign a message back and get flag!
exp.sage 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import os
from json import dumps
from secrets import randbits
from Crypto.Util.number import *
from hashlib import sha1

p = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF
a = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC
b = 0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B
Gx = 0x6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296
Gy = 0x4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5

K_SIZE = 18
SECRET_KEY = 0x7ea
F = GF(p)
EC = EllipticCurve(F, [a, b])
n = EC.order()

G = EC([Gx, Gy])
assert G in EC

def x2point(q_x):
    y_2 = (pow(q_x,3) + a*q_x + b) % p
    q_y = pow(y_2, (p+1)//4, p)
    Q = EC([q_x, q_y])
    return Q

def find_secret(r, s):
    z = bytes_to_long(sha1("hardcoded cuz reasons".encode()).digest()) % n
    R = x2point(r)
    randkey = discrete_log(x2point(r), G, G.order(), operation='+')
    secret_key = (randkey*s-z)*inverse(r, n)%n
    return secret_key

def sign_msg(msg: str):
    z = bytes_to_long(sha1(msg.encode()).digest()) % n
    k = (randbits(K_SIZE) + 2) % n
    R = k * G
    r = ZZ(R[0]) % n
    s = (k.inverse_mod(n) * (z + r * SECRET_KEY)) % n
    return {"r": hex(r), "s": hex(s)}

r = int(input("r >> "), 16)
s = int(input("s >> "), 16)
SECRET_KEY=find_secret(r, s)
print(sign_msg("mvm mvm mvm"))

With connection by hand.

fastcrypto

An RSA CRT service which it’s multiplication is based on NTT Algorithm.
chall.py 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#!/usr/bin/env python3

from Crypto.Util.number import getPrime, bytes_to_long as btl, inverse
from secrets import randbits
from nttmul import conv
from SECRET import FLAG
import signal

TIMEOUT = 30

B = 7639 # chosen by fair dice roll

def fromPoly(arr):
	num = 0
	for idx in reversed(range(len(arr))):
		num *= B
		num += arr[idx]
	
	return num

def toPoly(num):
	arr = []
	while num != 0:
		num, tmp = divmod(num, B)
		arr.append(tmp)

	return arr

def multiply(a: int, b: int) -> int:
	aPoly = toPoly(a)
	bPoly = toPoly(b)
	cPoly = conv(aPoly, bPoly)
	return fromPoly(cPoly)

def modpow(base: int, ex: int, mod: int) -> int:
	ret = 1
	while ex:
		if ex & 1 == 1:
			ret = multiply(ret, base)
			ret %= mod
		base = multiply(base, base)
		base %= mod
		ex >>= 1
	
	return ret

def encrypt(p: int, q: int, e: int, data: int) -> int:
	encp = modpow(data % p, e, p)
	encq = modpow(data % q, e, q)
	pInvQ = inverse(p, q)
	qInvP = inverse(q, p)

	return (encp * qInvP * q + encq * pInvQ * p) % (p * q)


if __name__ == '__main__':	
	p = getPrime(512)
	q = getPrime(512)
	N = p * q
	e = 0x10001
	FLAG = btl(FLAG)
	signal.alarm(TIMEOUT)
	print('### FASTCRYPTO ###')
	print(f'{N = }')
	while True:
		print('1. Get flag\n2. Encrypt data\n3. Exit')
		choice = input('choice: ')
		assert choice == '1' or choice == '2' or choice == '3'
		if choice == '1':
			data = randbits(1024)
			enc = encrypt(p, q, e, data)
			print(f'{enc = }')
			decryptedData = int(input('pt: '))
			assert data == decryptedData

			enc = encrypt(p, q, e, FLAG)
			print(f'{enc = }')
		elif choice == '2':
			data = randbits(1024)
			print(f'{data = }')
			enc = encrypt(p, q, e, data)
			print(f'{enc = }')
		else:
			exit()

Is suspecious of chosing a B value 7639, an uncommon prime which is quite too small and would have some bias while encountering higher coefficients.
So it’s probably feasible to do a RSA Fault Attack if the output value is wrong!
The exploit tells everything ⬇️.
exp.py 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
from pwn import *
import random
import math
from Crypto.Util.number import *
host='947b7890-af59-40d2-83c2-ac750bf0ac26.x3c.tf'
e=65537
def exploit():
    data=b''
    r=remote(host, 31337, ssl=True)
    r.recvline()
    predict=[]
    n=int(r.recvline().decode().split(' = ')[1])
    while True:
        r.recvuntil(b': ')
        r.sendline(b'2')
        cur_data=int(r.recvline().decode().split(' = ')[1])
        cur_enc=int(r.recvline().decode().split(' = ')[1])
        if pow(cur_data, e, n)!=cur_enc: # check if it has bias
            #return f"{cur_data=}\n{cur_enc=}\n{n}"
            break
    p=math.gcd(pow(cur_data, e, n)-cur_enc, n) # calculate the secret key value
    assert n%p==0 and isPrime(p)
    q=n//p
    d=inverse(e, (p-1)*(q-1))
    r.recvuntil(b': ')
    r.sendline(b'1')
    chal=int(r.recvline().decode().split(' = ')[1])
    r.sendline(str(pow(chal, d, n)).encode())
    print(f"{d=}\n{n=}")
    eflag=int(r.recvline().decode().split(' = ')[1])
    print(long_to_bytes(pow(eflag, d, n)))
#    r.interactive()

print(exploit())

rubiks-dsa

A cute cryptosystem based on rubiks cube ?!
Thanks for telling me there’re rubiks inside sage, I love this one!
chall.sage 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
from hashlib import sha256
from tqdm import tqdm

rubik_moves = "B' U  B' R  F2 "
P = Permutation(eval(open("permutation.txt").read())).to_permutation_group_element()
forbidden = [2, 27, 45, 56, 70, 86, 94, 138, 140, 167, 182, 232, 283, 284, 306, 308, 335, 348, 350, 363, 378, 423, 428, 446, 452, 506, 507, 536, 544, 560, 578, 579, 585, 587, 590, 592, 619, 642, 670, 675, 702, 731, 732, 738, 758, 760, 768, 770, 782, 783, 814, 830, 834, 843, 862, 867, 927, 936, 952, 980, 1010, 1038, 1091, 1119, 1148, 1150, 1152, 1170, 1174, 1175, 1188, 1190, 1204, 1206, 1222]
n = 641154303900

def spicy_rubik_pow(k):
    C = RubiksCube().move(rubik_moves * (k % 1260))
    
    return (P * C._state)**k

def hash_to_int(m):
    return int(sha256(m.encode()).hexdigest(), 16) % n

def sign(msg, d):
    k = n
    r_hash = n

    while gcd(k, n) != 1 or gcd(r_hash, n) != 1 or (k % 1260) in forbidden:
        k = randint(2, n - 1)
        r = spicy_rubik_pow(k)
        r_hash = hash_to_int(str(r))
    
    s = pow(k, -1, n) * (hash_to_int(msg) + r_hash*d) % n

    return r, s

flag = b"MVM{_fakemvmfakemvm_}"
flag = flag[4:-1]
privkeys = [randint(0, n) for i in range(32)]

assert len(flag) == 16

out = open("out.txt", "w")

for i in range(32):
    r,s = sign(f"mvm_{i}", privkeys[i])

    out.write(str(r) + "\n")
    out.write(str(s) + "\n")

for i in range(0, len(flag), 4):
    secret = vector([flag[i + j] for j in range(4)])
    ds = vector(privkeys[i:i+4])

    out.write(str(secret * ds) + "\n")

Take a look at the spicy_rubik_pow function: 

1
2
3
4
def spicy_rubik_pow(k):
    C = RubiksCube().move(rubik_moves * (k % 1260))
    
    return (P * C._state)**k

I would call it a base for every permutation group (P * C._state)**k, and there’re only 1185 bases.
After some trials, the order of those bases are quite small, so it’s DLP can be solved with discrete_log function …

Next is the signer: 

1
2
3
4
5
6
7
8
9
10
11
12
def sign(msg, d):
    k = n
    r_hash = n

    while gcd(k, n) != 1 or gcd(r_hash, n) != 1 or (k % 1260) in forbidden:
        k = randint(2, n - 1)
        r = spicy_rubik_pow(k)
        r_hash = hash_to_int(str(r))
    
    s = pow(k, -1, n) * (hash_to_int(msg) + r_hash*d) % n

    return r, s

After solving the value of k from discrete_log of r (brute force all bases and find the right one), the rest values like hash_to_int(msg), r_hash are trivial so that the value of d can be recovered (which is the secret key).

Finally is the encryption with those keys: 

1
2
3
4
5
for i in range(0, len(flag), 4):
    secret = vector([flag[i + j] for j in range(4)])
    ds = vector(privkeys[i:i+4])

    out.write(str(secret * ds) + "\n")

It’s a linear operation with the size of keys are much more larger than ASCII chars, which can simply calculated with LLL after obtained the keys.
Btw, 4 chars are actually able to brute-force

sol.sage 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
from hashlib import sha256
from tqdm import trange

rubik_moves="B' U  B' R  F2 "
P=Permutation(eval(open("permutation.txt").read())).to_permutation_group_element()
data=open('out.txt').read().split('\n')
forbidden=[2, 27, 45, 56, 70, 86, 94, 138, 140, 167, 182, 232, 283, 284, 306, 308, 335, 348, 350, 363, 378, 423, 428, 446, 452, 506, 507, 536, 544, 560, 578, 579, 585, 587, 590, 592, 619, 642, 670, 675, 702, 731, 732, 738, 758, 760, 768, 770, 782, 783, 814, 830, 834, 843, 862, 867, 927, 936, 952, 980, 1010, 1038, 1091, 1119, 1148, 1150, 1152, 1170, 1174, 1175, 1188, 1190, 1204, 1206, 1222]
n=641154303900
all_states=[]
int2id={}
enc_keys=[]
enc_flags=[]

keys=[]
flags=[]

def hash_to_int(m):
    return int(sha256(m.encode()).hexdigest(), 16) % n

def gen_all_states():
    cur_id=0
    for i in range(1260):
        if (i not in forbidden):
            int2id[i]=cur_id
            cur_id+=1
            C = RubiksCube().move(rubik_moves * i)
            all_states.append(P * C._state)

def parse_data():
    for i in range(32):
        enc_keys.append({'gp':PermutationGroupElement(data[i*2]), 'sign':int(data[i*2+1])})
    for i in range(4):
        enc_flags.append(int(data[64+i]))

def crack_key(id, gp, sign):
    for i in trange(len(all_states)):
        try:
            k=discrete_log(gp, all_states[i])
            print(f"[*] mvm_{id} trying {k}")
            r_hash=hash_to_int(str(gp))
            cur_key=((sign*k-hash_to_int(f"mvm_{id}"))*pow(r_hash, -1, n))%n
            keys.append(cur_key)
            print(f"[*] mvm_{id} secret cracked!")
        except Exception as e:
            print('', end='')

def get_flag(used_keys, out_int):
    global flags
    M=[[0]*6 for _ in range(5)]
    for i in range(4):
        M[i][0]=used_keys[i]
        M[i][i+1]=-1
    M[4][0]=out_int
    M[4][5]=2**1024
    M=Matrix(ZZ, M)
    A=M.LLL()
    for v in A:
        if v[0]==0 and v[-1]==2**1024:
            flags+=v[1:-1]

gen_all_states()
print('[*] Generated all States')
parse_data()
print('[*] Data Parsed!')
for i in range(len(enc_keys)):
    crack_key(i, enc_keys[i]['gp'], enc_keys[i]['sign'])


for i in range(4):
    get_flag(keys[i*4:i*4+4], enc_flags[i])

print(bytes(flags))

Web

submission

A web service that user are allowed to uploads .txt files, and they would be moved to /upload folder and: 

1
exec("chmod *");

The flag is also inside /upload folder.
Actually, it’s dangerous to use a wildcard parameter like * directly inside a command cuz it would probably leads to a wildcard injection vulnerability.

For example, if there’s a file named --help inside a folder and doing find *, a manual would pop out cause the --help file name were seen as a parameter passwd to find command
image

Next, there’s a --reference=<file name> option in chmod command which would change all files into the same permision as <file name>.

Exploit Step:

  1. upload a file named .txt (be shown as a hidden file in linux file system, won’t be listed in *)
  2. upload a file named --reference=.txt (change all files permission same as .txt, which would be readable)
  3. read flag~

Misc

Playing with the cert…

mvm

Change all M into 0 and V into 1, binary decode and got a piece of brainfuck code, solve them with online decoder.
image

trophy-plus

With the idea from challenge “mvm”, I found that there’re some tiny MVM aroung the cert, probably the same concept?
image
And the answer is … yep!
But tearing my eyes, actually …

trophy-plus64

Another Human-based OCR
image
There’s a REAL Certification on the stamp at the corner of the cert, after base decoded the first few lines a flag like string appeared … (Thanks a lot to my teammate wang for this).
After that, I just guessed the correct flag!
{mu5t_b3_feo_typ1ng_th1r_by_h4nd_1375105304248361} => {mu5t_b3_fun_typ1ng_th15_by_h4nd_1375105304248361}