rot727#

aeg{at_imuf_nussqd_zgynqd_paqezf_yqmz_yadq_eqogdq}

As the title mentioned, we can see that ROT727 is almost similar to ROT13. So we can put that in some decoder to brute-force the ROT, and the flag is encrypted in ROT14.

Flag: osu{oh_wait_bigger_number_doesnt_mean_more_secure}

beyond-wood#

1
from PIL import Image
2
import random
3

4
FLAG = Image.open("flag.png")
5
width, height = FLAG.size
6

7
key = [random.randrange(0, 256) for _ in range(width+height+3)]
8

9
out = FLAG.copy()
10
for i in range(width):
11
    for j in range(height):
12
        pixel = FLAG.getpixel((i, j))
13
        pixel = tuple(x ^ k for x, k in zip(pixel, key))
14
        newi, newj = (2134266 + i * 727) % width, (4501511 + j * 727) % height
15
        out.putpixel((newi, newj), pixel)
16

17
out.save("output.png")

key is built with random bytes of length width + height + 3. For each (i, j) it XORS the pixel channels with key starting from key[0]. Meaning that XOR key takes the first 3 bytes of key, and it’s constant per channel (one byte for R, one byte for G and one byte for B).

Then it write that XORed pixel to a new permuted location.

1
newi = (2134266 + i * 727) % width
2
newj = (4501511 + j * 727) % height

This is a linear (affine) permutation on each axis, so it’s reversible.

To solve this challenge, we first invert the permutation, by using the formula, and place it at the original pixel.

1
inv_i[(2134266 + i * 727) % width] = i
2
inv_j[(4501511 + j * 727) % height] = j

Then recover the 3 key bytes. Because XOR key is global, so that we can use some frequency assumptions such as black (0, 0, 0) or white (255, 255, 255), to XOR the unshuffled image with the recovered key to get the original.

1
from PIL import Image
2
from collections import Counter
3

4
def build_inverse_map(length, offset, mult):
5
    inv = [None] * length
6
    for i in range(length):
7
        new = (offset + i * mult) % length
8
        inv[new] = i
9
    return inv
10

11
def unshuffle(img):
12
    width, height = img.size
13
    inv_i = build_inverse_map(width, 2134266, 727)
14
    inv_j = build_inverse_map(height, 4501511, 727)
15
    out = Image.new(img.mode, (width, height))
16
    src = img.load()
17
    dst = out.load()
18
    for x in range(width):
19
        for y in range(height):
20
            dst[inv_i[x], inv_j[y]] = src[x, y]
21
    return out
22

23
def xor_pixel(pixel, key):
24
    return tuple(p ^ k for p, k in zip(pixel, key))
25

26
def apply_key(img, key):
27
    width, height = img.size
28
    out = Image.new(img.mode, (width, height))
29
    src = img.load()
30
    dst = out.load()
31
    for x in range(width):
32
        for y in range(height):
33
            dst[x, y] = xor_pixel(src[x, y], key)
34
    return out
35

36
def main():
37
    img = Image.open("output.png").convert("RGB")
38
    width, height = img.size
39
    unshuffled = unshuffle(img)
40

41
    for bg in [(0,0,0), (255,255,255)]:
42
        key = tuple(mc[i] ^ bg[i] for i in range(3))
43
        print(f"Recovering {bg}, key = {key}")
44
        recovered = apply_key(unshuffled, key)
45
        recovered.save(f"recovered_{bg[0]}_{bg[1]}_{bg[2]}.png")
46

47
if __name__ == "__main__":
48
    main()

Flag: osu{h1_05u_d351gn_t34m}

xnor-xnor-xnor#

1
import os
2
flag = open("flag.txt", "rb").read()
3

4
def xnor_gate(a, b):
5
    if a == 0 and b == 0:
6
        return 1
7
    elif a == 0 and b == 1:
8
        return 0
9
    elif a == 1 and b == 0:
10
        return 0
11
    else:
12
        return 1
13

14
def str_to_bits(s):
15
    bits = []
16
    for x in s:
17
        bits += [(x >> i) & 1 for i in range(8)][::-1]
18
    return bits
19

20
def bits_to_str(bits):
21
    return bytes([sum(x * 2 ** j for j, x in enumerate(bits[i:i+8][::-1])) for i in range(0, len(bits), 8)])
22

23
def xnor(pt_bits, key_bits):
24
    return [xnor_gate(pt_bit, key_bit) for pt_bit, key_bit in zip(pt_bits, key_bits)]
25

26
key = os.urandom(4) * (1 + len(flag) // 4)
27
key_bits = str_to_bits(key)
28
flag_bits = str_to_bits(flag)
29
enc_flag = xnor(xnor(xnor(flag_bits, key_bits), key_bits), key_bits)
30

31
print(bits_to_str(enc_flag).hex())
32
# 7e5fa0f2731fb9b9671fb1d62254b6e5645fe4ff2273b8f04e4ee6e5215ae6ed6c

We have XNOR(a, b) = 1 - (a XOR b), so if we have t = XNOR(XNOR(XNOR(a, k), k), k), meaning that if k = 1 then t = a, and k = 0 then t = NOT a. Therefore the whole triple-XNOR is just a bitwise XOR with the bitwise complement of the key. In bytes:

1
mask_byte = 0xff - key_byte
2
cipher = plaintext XOR mask
3
plaintext = cipher XOR mask

Because key is os.urandom(4) repeated, mask repeats every 4 bytes. So if we know the what the plaintext is, it’s reversible.

We know the flag format is osu{, it’s 0x6f 0x73 0x75 0x7b. Calculate the first 4 mask bytes:

1
mask0 = 0x7e XOR 0x6f = 0x11
2
mask1 = 0x5f XOR 0x73 = 0x2c
3
mask2 = 0xa0 XOR 0x75 = 0xd5
4
mask3 = 0xf2 XOR 0x7b = 0x89

We have the 4-byte repeated mask as 0x11 0x2c 0xd5 0x89, so the key is 0xff - mask_byte, meaning 0xee 0xd3 0x2a 0x76. XOR it with the cipher text, and we have the flag.

1
c = bytes.fromhex("7e5fa0f2731fb9b9671fb1d62254b6e5645fe4ff2273b8f04e4ee6e5215ae6ed6c")
2
known = b"osu{"
3
mask = [c[i] ^ known[i] for i in range(4)]
4
t = bytes(c[i] ^ mask[i % 4] for i in range(len(c)))
5
print(t.decode())

Flag: osu{b3l0v3d_3xclus1v3_my_b3l0v3d}

pls-nominate#

1
from Crypto.Util.number import *
2
FLAG = open("flag.txt", "rb").read()
3
message = bytes_to_long( b"hello there can you pls nominate my map https://osu.ppy.sh/beatmapsets/2436259 :steamhappy: i can bribe you with a flag if you do: " + FLAG )
4

5
ns = [getPrime(727) * getPrime(727) for _ in range(5)]
6
e = 5
7
print(len(FLAG))
8
print(ns)
9
print([pow(message, e, n) for n in ns])

This challenge is a simple Hastad-style broadcast RSA with e = 5. So we just need to combine 5 ciphertexts with the Chinese Remainder Theorem and search for the small multiple k so that M_e + k * N is a perfect 5th power.

1
ns = [...]
2
ciphers = [...]
3
e = 5
4

5
def prod(a):
6
    p = 1
7
    for x in a: p *= x
8
    return p
9

10
def ith_root(x, n):
11
    if x < 2: return x, True
12
    lo, hi = 0, 1 << ((x.bit_length() + n - 1) // n + 1)
13
    while lo + 1 < hi:
14
        m = (lo + hi) // 2
15
        if m ** n == x: return m, True
16
        if m ** n < x: lo = m
17
        else: hi = m
18
    return (lo, lo ** n == x)
19

20
# CRT
21
N = prod(ns)
22
Me = 0
23
for n, c in zip(ns, ciphers):
24
    Ni = N // n
25
    inv = pow(Ni, -1, n)
26
    Me += c * Ni * inv
27
Me %= N
28

29
# Search small k
30
r, exact = ith_root(Me, e)
31
if not exact:
32
    for k in range(0, 500000):
33
        r, exact = ith_root(Me + k*N, e)
34
        if exact:
35
            break
36

37
m = r
38
b = m.to_bytes((m.bit_length() + 7) // 8, 'big')
39
i = b.find(b"osu{")
40
print(b[i:i + 200].decode() if i != -1 else b[:200])

Flag: osu{pr3tty_pl3453_w1th_4_ch3rry_0n_t0p!?:pleading:}

linear-feedback#

1
from secrets import randbits
2
from math import floor
3
from hashlib import sha256
4

5
class LFSR:
6
    def __init__(self, key, taps, format):
7
        self.key = key
8
        self.taps = taps
9
        self.state = list(map(int, list(format.format(key))))
10

11
    def _clock(self):
12
        ob = self.state[0]
13
        self.state = self.state[1:] + [sum([self.state[t] for t in self.taps]) % 2]
14
        return ob
15

16
def xnor_gate(a, b):
17
    if a == 0 and b == 0: return 1
18
    elif a == 0 and b == 1: return 0
19
    elif a == 1 and b == 0: return 0
20
    else: return 1
21

22
key1 = randbits(21)
23
key2 = randbits(29)
24
L1 = LFSR(key1, [2, 4, 5, 1, 7, 9, 8], "{:021b}")
25
L2 = LFSR(key2, [5, 3, 5, 5, 9, 9, 7], "{:029b}")
26

27
bits = [xnor_gate(L1._clock(), L2._clock()) for _ in range(floor(72.7))]
28
print(bits)
29

30
FLAG = open("flag.txt", "rb").read()
31
keystream = sha256((str(key1) + str(key2)).encode()).digest() * 2
32
print(bytes([b1 ^ b2 for b1, b2 in zip(FLAG, keystream)]).hex())

This is the challenge where turning the LFSRs into a linear system over GF(2) and solving the initial register bits.

The two LFSRs are linear over GF(2), where each output bit at t is a linear function of the initial state bits.
The program prints bits = xnor(L1._clock(), L2._clock()). Since xnor(a, b) = 1 when a == b, we have: L1_t XOR L2_t = 1 ^ bits_t.
Build coefficient vectors for each LFSR output as linear combinations of their initial state bits, for every observed time step. That gives a linear system with 50 unknowns (21 + 29 initial bits) and 72 equations (observed outputs).
Solve the GF(2) linear system (Gaussian elimination). The system had 2 free variables; try 4 assignments, check which produces ASCII flag when decrypting the provided ciphertext.

Based on these steps, we can have the recovered values as:

1
key1 = 776071    #binary 10111101101001000111 as a 21-bit string
2
key2 = 340835109 #binary 0101000100010010101100010110101 as a 29-bit string

Flag: osu{th1s_hr1_i5_th3_m0st_fun_m4p_3v3r_1n_0wc}

ssss#

1
#!/usr/local/bin/python3
2
from Crypto.Util.number import *
3
import random
4

5
p = 2**255 - 19
6
k = 15
7
SECRET = random.randrange(0, p)
8

9
def lcg(x, a, b, p):
10
    return (a * x + b) % p
11

12
a = random.randrange(0, p)
13
b = random.randrange(0, p)
14
poly = [SECRET]
15
while len(poly) != k: poly.append(lcg(poly[-1], a, b, p))
16

17
def evaluate_poly(f, x):
18
    return sum(c * pow(x, i, p) for i, c in enumerate(f)) % p
19

20
print("welcome to ssss", flush=True)
21
for _ in range(k - 1):
22
    x = int(input())
23
    assert 0 < x < p, "no cheating!"
24
    print(evaluate_poly(poly, x), flush=True)
25

26
if int(input("secret? ")) == SECRET:
27
    FLAG = open("flag.txt").read()
28
    print(FLAG, flush=True)

Server returns $y = \sum_{i=0}^{k-1} c_i x^i$ with $c_{i+1} = ac_i + b, c_0 = SECRET$ .
Because $c_i = C_1a^i + C_2$ , then $y(x) = C_1S(x, a) + C_2U(x)$

where $S(x, a) = \frac{1 - (ax)^k}{1 - ax}$ and $U(x) = \frac{1 - x^k}{1 - x}$

Send 3 values x (e.x. 2, 3, 5), receive 3 values y and calculate 3 nonlinear system for $a, C_1, C_2$ .
Eliminate $C_1, C_2$ to get one polynomial equation in $a$ , solve it modulo $p$ , then recover $C_1, C_2$ by linear solve.
Compute $SECRET = C_1 + C_2 \pmod{b}$ , send this SECRET to the server to receive the flag.

1
import socket, re, sys, time
2
from sympy import symbols, together, expand, Poly, factor_list, Integer
3
from Crypto.Util.number import inverse, long_to_bytes
4

5
HOST = "ssss.challs.sekai.team"
6
PORT = 1337
7

8
p = 2**255 - 19
9
k = 15
10
xs_to_send = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43]  # length 14
11

12
def recv_line(sock, timeout=10):
13
    sock.settimeout(timeout)
14
    data = b""
15
    try:
16
        while True:
17
            ch = sock.recv(1)
18
            if not ch:
19
                break
20
            data += ch
21
            if ch == b"\n":
22
                break
23
    except socket.timeout:
24
        pass
25
    return data
26

27
def extract_last_int_from_bytes(b: bytes):
28
    m = re.search(rb"(-?\d+)\s*$", b.strip())
29
    if not m:
30
        return None
31
    return int(m.group(1))
32

33
def query_server_and_get_results(host, port, xs):
34
    s = socket.create_connection((host, port))
35
    s.settimeout(5)
36
    for _ in range(4):
37
        line = recv_line(s, timeout=0.5)
38
        if not line:
39
            break
40

41
    outputs = []
42
    for x in xs:
43
        # send x
44
        s.sendall(f"{x}\n".encode())
45
        val = None
46
        start = time.time()
47
        while True:
48
            line = recv_line(s, timeout=5)
49
            if not line:
50
                break
51
            val = extract_last_int_from_bytes(line)
52
            if val is not None:
53
                break
54
            if time.time() - start > 8:
55
                break
56
        if val is None:
57
            remaining = line.decode(errors='ignore') if line else "<no data>"
58
            print(remaining)
59
            s.close()
60
            sys.exit(1)
61
        outputs.append((x, val))
62
    return s, outputs
63

64
def recover_secret_from_three_pairs(pairs):
65
    (x1, y1), (x2, y2), (x3, y3) = pairs
66
    a = symbols('a')
67
    def S_sym(x):
68
        return (1 - (a * Integer(x))**k) / (1 - a * Integer(x))
69
    def U_sym(x):
70
        xI = Integer(x)
71
        return (1 - xI**k) / (1 - xI)
72
    S1, S2, S3 = S_sym(x1), S_sym(x2), S_sym(x3)
73
    U1, U2, U3 = U_sym(x1), U_sym(x2), U_sym(x3)
74
    Y1, Y2, Y3 = map(Integer, [y1, y2, y3])
75
    expr = (Y1 * U2 - Y2 * U1) * S3 + (-Y1 * S2 + Y2 * S1) * U3 - Y3 * (S1 * U2 - S2 * U1)
76
    expr_s = together(expr)
77
    num, den = expr_s.as_numer_denom()
78
    poly_expr = expand(num)
79
    P = Poly(poly_expr, a)
80
    print("[*] Integer polynomial degree:", P.degree())
81
    coeffs_mod_p = [int(c % p) for c in P.all_coeffs()]
82
    Pp = Poly(coeffs_mod_p, a, modulus=p)
83
    print("[*] Degree over GF(p):", Pp.degree())
84
    print("[*] Factoring polynomial mod p (may take a moment)...")
85
    try:
86
        fact = factor_list(Pp.as_expr(), modulus=p)
87
        factors = fact[1]
88
    except Exception as e:
89
        print("[!] factor_list failed:", e)
90
        factors = []
91

92
    candidates = set()
93
    for fpol, mult in factors:
94
        fpoly = Poly(fpol, a, modulus=p)
95
        if fpoly.degree() == 1:
96
            coefs = fpoly.all_coeffs()
97
            Acoef, Bcoef = int(coefs[0]) % p, int(coefs[1]) % p
98
            root = (-Bcoef * inverse(Acoef, p)) % p
99
            candidates.add(root)
100

101
    if not candidates:
102
        print("[*] No linear factors found")
103
        for guess in range(0, 200000):
104
            if Pp.eval(guess) % p == 0:
105
                candidates.add(guess)
106
                print("[*] Found a by scanning:", guess)
107
                break
108

109
    if not candidates:
110
        raise RuntimeError("No candidate 'a' found.")
111

112
    def compute_S_num(x, a_val):
113
        ax = (a_val * x) % p
114
        if (1 - ax) % p == 0:
115
            return None
116
        num = (1 - pow(ax, k, p)) % p
117
        den = (1 - ax) % p
118
        return (num * inverse(den, p)) % p
119

120
    def compute_U_num(x):
121
        if (1 - x) % p == 0:
122
            return None
123
        num = (1 - pow(x, k, p)) % p
124
        den = (1 - x) % p
125
        return (num * inverse(den, p)) % p
126

127
    for a_cand in candidates:
128
        S1v = compute_S_num(x1, a_cand)
129
        S2v = compute_S_num(x2, a_cand)
130
        S3v = compute_S_num(x3, a_cand)
131
        U1v = compute_U_num(x1)
132
        U2v = compute_U_num(x2)
133
        U3v = compute_U_num(x3)
134
        if None in (S1v, S2v, S3v, U1v, U2v, U3v):
135
            continue
136
        det = (S1v * U2v - S2v * U1v) % p
137
        if det == 0:
138
            continue
139
        inv_det = inverse(det, p)
140
        C1 = ((Integer(y1) * U2v - Integer(y2) * U1v) * inv_det) % p
141
        C2 = ((-Integer(y1) * S2v + Integer(y2) * S1v) * inv_det) % p
142
        y3calc = (C1 * S3v + C2 * U3v) % p
143
        if y3calc == Integer(y3) % p:
144
            SECRET = int((C1 + C2) % p)
145
            return a_cand, SECRET
146
    raise RuntimeError("No candidate 'a' produced valid C1/C2.")
147

148
def send_secret_and_get_flag(sock, secret):
149
    sock.sendall(f"{secret}\n".encode())
150
    data = b""
151
    try:
152
        while True:
153
            chunk = sock.recv(4096)
154
            if not chunk:
155
                break
156
            data += chunk
157
    except socket.timeout:
158
        pass
159
    return data.decode(errors='ignore')
160

161
def main():
162
    print("Connecting server")
163
    s, outputs = query_server_and_get_results(HOST, PORT, xs_to_send)
164
    print("Queried pairs:", outputs[:3], "... (total returned {})".format(len(outputs)))
165
    three = outputs[:3]
166
    try:
167
        a_val, secret = recover_secret_from_three_pairs(three)
168
    except Exception as e:
169
        print("Recovery failed:", e)
170
        s.close()
171
        sys.exit(1)
172

173
    print("Recovered a =", a_val)
174
    print("Recovered SECRET (int):", secret)
175
    try:
176
        print("SECRET (bytes):", long_to_bytes(secret))
177
    except Exception:
178
        pass
179

180
    print("Sending secret")
181
    flag_text = send_secret_and_get_flag(s, secret)
182
    s.close()
183
    print("---- SERVER OUTPUT ----")
184
    print(flag_text)
185
    print("-----------------------")
186

187
if __name__ == "__main__":
188
    main()

Flag: osu{0n3_hundr3d_p3rc3nt_4ccur4cy!}