Srdnlen CTF 2025 - Crypto Writeups

srdnlen_crypto

Confusion

Description:

Looks like our cryptographers had one too many glasses of mirto! Can you sober up their sloppy AES scheme, or will the confusion keep you spinning?

This is a remote challenge, you can connect to the service with: nc confusion.challs.srdnlen.it 1338

Challenge File:

1
#!/usr/bin/env python3
2

3
from Crypto.Cipher import AES
4
from Crypto.Util.Padding import pad, unpad
5
import os
6

7
# Local imports
8
FLAG = os.getenv("FLAG", "srdnlen{REDACTED}").encode()
9

10
# Server encryption function
11
def encrypt(msg, key):
12
    pad_msg = pad(msg, 16)
13
    blocks = [os.urandom(16)] + [pad_msg[i:i + 16] for i in range(0, len(pad_msg), 16)]
14

15
    b = [blocks[0]]
16
    for i in range(len(blocks) - 1):
17
        tmp = AES.new(key, AES.MODE_ECB).encrypt(blocks[i + 1])
18
        b += [bytes(j ^ k for j, k in zip(tmp, blocks[i]))]
19

20
    c = [blocks[0]]
21
    for i in range(len(blocks) - 1):
22
        c += [AES.new(key, AES.MODE_ECB).decrypt(b[i + 1])]
23

24
    ct = [blocks[0]]
25
    for i in range(len(blocks) - 1):
26
        tmp = AES.new(key, AES.MODE_ECB).encrypt(c[i + 1])
27
        ct += [bytes(j ^ k for j, k in zip(tmp, c[i]))]
28

29
    return b"".join(ct)
30

31

32
KEY = os.urandom(32)
33

34
print("Let's try to make it confusing")
35
flag = encrypt(FLAG, KEY).hex()
36
print(f"|\n|    flag = {flag}")
37

38
while True:
39
    print("|\n|  ~ Want to encrypt something?")
40
    msg = bytes.fromhex(input("|\n|    > (hex) "))
41

42
    plaintext = pad(msg + FLAG, 16)
43
    ciphertext = encrypt(plaintext, KEY)
44

45
    print("|\n|  ~ Here is your encryption:")
46
    print(f"|\n|   {ciphertext.hex()}")

Solution:

The challenge implemented a custom mode of AES. We were given an encryption oracle and the flag is appended to our plaintext. The target is to recover the flag. Denote $Enc(M)$ and $Dec(M)$ as the AES-ECB encryption on plaintext $M$ . As the key is the same among the encryption and decryption, I’ll omit it. Let the plaintext $M$ be the composition of 16-bytes block, i.e.: $M = [M_0, M_1, ..., M_n]$ , the encryption function $F$ of custom mode can be expressed as follow:

F(M) = [IV, Enc(M_0), \\Enc(M_1) \oplus M_0 \oplus Dec(M_0 \oplus IV), \\ ... \\Enc(M_n) \oplus M_{n-1} \oplus Dec(M_{n-1} \oplus M_{n-2})]

Since the plaintext is double padded, the last block is always 16 bytes \x10. If we know the value of $Enc(M_n)$ and $M_{n-1}$ then we can extract value $Dec(M_{n-1} \oplus M_{n-2})$ . After that, we send it to the oracle to obtain $M_{n-1} \oplus M_{n-2}$ since the second block of ciphertext is always $Enc(M_0)$ . Then we can recover $M_{n-2}$ by XOR it with known value $M_{n-1}$ . Repeat this until we recover the whole flag. To obtain $Enc(M_n)$ , we just need to send 16 bytes \x10 as plaintext. $M_{n-1}$ can be known by padding the plaintext to make it has the form }\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f due to the double padding.

1
from pwnlib.tubes.remote import remote
2
from Crypto.Cipher import AES
3
from Crypto.Util.Padding import pad
4
from pwnlib.util.fiddling import xor
5

6
def blockify(ct):
7
    return [ct[i:i + 16] for i in range(0, len(ct), 16)]
8

9
def oracle(pt):
10
    io.recvlines(3)
11
    io.sendlineafter(b'hex) ', pt.hex().encode())
12
    io.recvlines(3)
13
    ct = io.recvline().decode().strip().split()[-1]
14
    ct = blockify(bytes.fromhex(ct)[16:])
15
    return ct
16

17
io = remote("confusion.challs.srdnlen.it", 1338)
18
io.recvlines(2)
19

20
padded_enc = oracle(b'\x10' * 16)[0]
21
known = b''
22
payload = pad(bytes([ord('}')]), 16) + b'\x00' * 12
23
ct0 = oracle(payload)
24
expected = ct0[0]
25
new_payload = xor(ct0[-1], padded_enc, payload[:16])
26
ct1 = oracle(new_payload)[0]
27
flag2 = xor(ct1, expected)
28
print(f'{flag2 = }')
29

30
flag2_enc = oracle(flag2)[0]
31
new_payload = xor(ct0[-2], expected, flag2)
32
ct1 = oracle(new_payload)[0]
33
flag1 = xor(ct1, flag2_enc)
34
print(f'{flag1 = }')
35

36

37
flag1_enc = oracle(flag1)[0]
38
new_payload = xor(ct0[-3], flag2_enc, flag1)
39
ct1 = oracle(new_payload)[0]
40
flag0 = xor(ct1, flag1_enc)
41
print(f'{flag0 = }')
42

43
# srdnlen{I_h0p3_th15_Gl4ss_0f_M1rt0_w4rm3d_y0u_3n0ugh}

Chess

Description:

Look at this cool encoding, it’s made for chess lovers!! Man I love chess…

This is a remote challenge, you can connect to the service with: nc chess.challs.srdnlen.it 4012

Challenge File:

1
from src.encode_to_pgn_2bit import encode_to_pgn
2
from src.trivia import trivia
3
from src.pseudorandom import XorShift128
4
from src.decode_from_pgn_2bit import decode_from_pgn, input_and_parse_pgns
5
import secrets
6
SIZE = 64
7
MAX_STRING = 300
8

9
def main_menu():
10
    prng = XorShift128(secrets.randbits(SIZE), secrets.randbits(SIZE))
11

12
    while True:
13
            print("\nMain Menu")
14
            print("1. Encode a string to PGN")
15
            print("2. Decode a PGN to string")
16
            print("3. Play trivia")
17
            print("4. Exit")
18
            choice = input("Enter your choice (1/2/3/4): ")
19

20
            if choice == "1":
21
                while True:
22
                    string_to_encode = input(f"Enter the string to encode (max {MAX_STRING} characters): ")
23

24
                    if len(string_to_encode) <= MAX_STRING:
25
                        break
26
                    else:
27
                        print(f"String too long! Please enter a string with at most {MAX_STRING} characters.")
28

29
                results = [ pgn for pgn in encode_to_pgn(string_to_encode, prng)]
30

31
                print("encoded pgns:\n")
32
                for result in results:
33
                    print(result)
34

35
            if choice == "2":
36
                list_of_pgns = input_and_parse_pgns()
37

38
                print("decoded string:\n")
39
                print(decode_from_pgn(list_of_pgns))
40

41
            elif choice == "3":
42
                trivia(prng)
43
            elif choice == "4":
44
                print("Exiting...")
45
                break
46
            else:
47
                print("Invalid choice. Please try again.")
48

49
if __name__ == "__main__":
50
    main_menu()

Solution:

This challenge is centered around the XorShift128 PRNG. Following the writeup here, the PRNG is linear in its LSB, so we can break the PRNG if we can obtain the least significant bits of ~128 samples and then solve the corresponding system of equations.

We get access to PRNG outputs through a chess move selection system which uses the PRNG to generate an output and then reduces the output modulo the number of valid chess moves in a given state. For our purposes, we only require that the number of valid chess moves is even, so that the LSB of the reduced value and the LSB of the raw output is identical.

Given the above, we ask the server to encode a large random string, and then follow along locally with our own chessboard looking at the moves the server picks. If we reach a state where the number of possible moves is even then we can recover the LSB of a PRNG output from the server’s choice. Once we have enough samples, we can solve the system to recover the PRNG seeds, and from there predict the trivia game.

1
#!/usr/bin/env python3
2
import secrets
3
from src.pseudorandom import XorShift128 as XorShift128Real
4
from sage.all import *
5
from pwn import *
6
from Crypto.Util.number import bytes_to_long
7
import chess.pgn
8
from chess import Board, pgn
9
from src.trivia import players
10

11

12
def shift_left(var, n):
13
    return (var + [0] * n)[-64:]
14

15

16
def shift_right(var, n):
17
    return ([0] * n + var)[:64]
18

19

20
def xor(left, right):
21
    return [x + y for x, y in zip(left, right)]
22

23

24
def xorshift128(state0, state1):
25
    s1 = state0
26
    s0 = state1
27
    state0 = s0
28

29
    s1 = xor(s1, shift_left(s1, 23))
30

31
    s1 = xor(s1, shift_right(s1, 17))
32

33
    s1 = xor(s1, s0)
34

35
    s1 = xor(s1, shift_right(s0, 26))
36
    state1 = s1
37
    return state0, state1
38

39

40
class XorShift128:
41

42
    def __init__(self, state0, state1):
43
        self.state0 = state0
44
        self.state1 = state1
45

46
    def next(self):
47
        self.state0, self.state1 = xorshift128(self.state0, self.state1)
48
        return self.state0[-1] + self.state1[-1]
49

50

51
R = PolynomialRing(GF(2), [f"x_{i}" for i in range(64)] + [f"y_{i}" for i in range(64)])
52

53

54
def break_prng(outputs):
55
    state0, state1 = list(R.gens()[:64]), list(R.gens()[64:])
56
    prng = XorShift128(state0, state1)
57

58
    eqs = []
59
    for output, mod in outputs:
60
        if mod % 2 == 0:
61
            eqs.append(prng.next() - output)
62
        else:
63
            prng.next()
64
        if len(eqs) == 140:
65
            break
66

67
    A, mons = Sequence(eqs).coefficients_monomials()
68
    A, b = A[:, :-1], vector(-A[:, -1])
69
    assert A.rank() == 128
70
    x = A.solve_right(b)
71

72
    left = int("".join(map(str, x[:64])), 2)
73
    right = int("".join(map(str, x[64:])), 2)
74

75
    return left, right
76

77

78
def encode(conn, string):
79
    conn.sendlineafter(b"Enter your choice (1/2/3/4): ", b"1")
80
    conn.sendlineafter(b"characters): ", string.encode())
81
    conn.recvuntil(b"encoded pgns:\n\n")
82
    encoded_pgns = []
83
    data = conn.recvuntil(b"Invalid choice", drop=True)
84
    pgns = data.decode().split('[Event "?"]')
85
    out = []
86
    for pgn in pgns:
87
        if pgn:
88
            out.append(chess.pgn.read_game(io.StringIO(pgn)))
89
    return out
90

91

92
def string_to_bits(s):
93
    binary_string = bin(bytes_to_long(s.encode()))[2:]
94
    padding_length = (8 - len(binary_string) % 8) % 8
95
    padded_binary_string = binary_string.zfill(len(binary_string) + padding_length)
96
    return padded_binary_string
97

98

99
dic_tile_to_bits = {
100
    f"{chr(col + ord('a'))}{8 - row}": f"{row % 2}{col % 2}"
101
    for row in range(8)
102
    for col in range(8)
103
}
104

105
dic_bits_to_tile = defaultdict(list)
106
for k, v in dic_tile_to_bits.items():
107
    dic_bits_to_tile[v].append(k)
108
dic_bits_to_tile = dict(dic_bits_to_tile)
109

110

111
def iterate_moves(pgns):
112
    for pgn in pgns:
113
        for move in pgn.mainline_moves():
114
            yield move.uci()
115

116

117
def solve():
118
    # conn = process(["python", "main.py"])
119
    conn = connect("chess.challs.srdnlen.it", 4012)
120
    msg = "".join(random.choices(string.ascii_letters, k=300))
121
    pgns = encode(conn, msg)
122

123
    bits_to_encode = string_to_bits(msg)
124
    chess_board = Board()
125
    moves = iterate_moves(pgns)
126
    prng_outputs = []
127
    for i in range(len(bits_to_encode) // 2):
128
        current_2bits = bits_to_encode[i * 2 : i * 2 + 2]
129

130
        legal_moves = list(str(k) for k in chess_board.generate_legal_moves())
131
        possible_moves = dic_bits_to_tile[current_2bits]
132

133
        legal_possible_moves = [
134
            legal_move
135
            for legal_move in legal_moves
136
            if legal_move[2:4] in possible_moves
137
        ]
138
        if not legal_possible_moves:
139
            chess_board = Board()
140

141
            legal_moves = list(str(k) for k in chess_board.generate_legal_moves())
142
            possible_moves = dic_bits_to_tile[current_2bits]
143
            legal_possible_moves = [
144
                legal_move
145
                for legal_move in legal_moves
146
                if legal_move[2:4] in possible_moves
147
            ]
148

149
            mod = len(legal_possible_moves)
150
            chosen_move = next(moves)
151
            chess_board.push(chess.Move.from_uci(chosen_move))
152
            prng_outputs.append((legal_possible_moves.index(chosen_move), mod))
153
        else:
154
            mod = len(legal_possible_moves)
155
            chosen_move = next(moves)
156
            prng_outputs.append((legal_possible_moves.index(chosen_move), mod))
157
            chess_board.push(chess.Move.from_uci(chosen_move))
158

159
            if chess_board.is_insufficient_material() or chess_board.can_claim_draw():
160
                chess_board = Board()
161
    state0, state1 = break_prng(prng_outputs)
162
    prng = XorShift128Real(state0, state1)
163

164
    for _ in range(len(list(iterate_moves(pgns)))):
165
        prng.next()
166

167
    conn.sendlineafter(b"Enter your choice (1/2/3/4): ", b"3")
168
    for _ in range(50):
169
        conn.sendlineafter(
170
            "Which chess player am I thinking of?", prng.choice(players).encode()
171
        )
172
    conn.recvall()

Based sbox

Description:

ChatGPT cooked a story for us:

Once upon a time, after linear and differential cryptanalysis had revolutionized the cryptographic landscape, and before Rijndael was selected as the Advanced Encryption Standard (AES), the field of cryptography was in a unique state of flux. New cryptanalytic methods exposed vulnerabilities in many established ciphers, casting doubt on the long-term security of systems once thought to be invulnerable. In response, the U.S. National Institute of Standards and Technology (NIST) launched a competition to find a successor to the aging DES. In 2000, Rijndael was chosen, setting a new standard for secure encryption. But even as AES became widely adopted, new challenges, like quantum computing, loomed on the horizon.

This is a remote challenge, you can connect to the service with: nc basedsbox.challs.srdnlen.it 46173

Challenge File:

The challenge files can be found here: https://github.com/srdnlen/srdnlenctf-2025_public/tree/main/crypto_Based-sbox/src

Solution:

We are given 4 minutes to perform a key recovery attack on a 7 round Feistel cipher. The round function is an sbox which performs modular inversion followed by an addition in the field GF(2^64). This sbox is vulnerable to an interpolation attack.

By reimplementing the cipher symbolically, we can obtain an equation for the ciphertext as a rational function of the plaintext, with unknown key-dependent coefficients. Given enough plaintext/ciphertext pairs, we can interpolate this rational function and solve the linear system for the coefficients/round keys.

Unfortunately the number of unknowns gets too large for the amount of samples we have if we try to express the full action of the cipher symbolically, so we can alter the attack by using a meet in the middle approach to reduce the number of variables.

Using a meet in the middle approach we get a system of equations with 136 variables (linearised) and 46 equations. We can then run a Groebner basis algorithm to solve for the unknowns.

1
#!/usr/bin/env python3
2

3
from sage.all import *
4
from pwn import *
5
from functools import reduce
6

7
x = GF(2)["x"].gen()
8
K = GF(2**64, "y", modulus=1 + x + x**3 + x**4 + x**64)
9
e = -1
10
a1, a2 = K.from_integer(0x01D_5B), K.from_integer(0x_15_BA5ED)
11

12
sbox = lambda x: (K.from_integer(x) ** e + a1 + a2).to_integer()
13
sbox_sym = lambda x: x**e + a1 + a2
14
story = (  # ChatGPT cooked a story for us
15
    "Once upon a time, after linear and differential cryptanalysis had revolutionized the cryptographic landscape, "
16
    "and before Rijndael was selected as the Advanced Encryption Standard (AES), the field of cryptography was in a unique state of flux. "
17
    "New cryptanalytic methods exposed vulnerabilities in many established ciphers, casting doubt on the long-term security of systems "
18
    "once thought to be invulnerable. In response, the U.S. National Institute of Standards and Technology (NIST) "
19
    "launched a competition to find a successor to the aging DES. In 2000, Rijndael was chosen, setting a new standard for secure encryption. "
20
    "But even as AES became widely adopted, new challenges, like quantum computing, loomed on the horizon."
21
).encode()
22

23

24
class Feistel:
25
    def __init__(self, key, rounds=10, block_size=16):
26
        assert block_size % 2 == 0
27
        self._rounds = rounds
28
        self._block_size = block_size
29
        self._round_keys = key
30

31
    def _f(self, l, r, key):
32
        return l + sbox_sym(r + key)
33

34
    def _encrypt_block(self, pt, round_num=6):
35
        l, r = pt
36
        for i in range(self._rounds):
37
            l, r = r, self._f(l, r, self._round_keys[i])
38
            if i == round_num:
39
                break
40
        ct = [l, r]
41
        return ct
42

43
    def _decrypt_block(self, ct, round_num=6):
44
        l, r = ct
45
        for i in reversed(range(self._rounds)):
46
            l, r = self._f(r, l, self._round_keys[i]), l
47
            if i == round_num:
48
                break
49
        pt = [l, r]
50
        return pt
51

52
    def encrypt(self, pt, iv):
53
        ct = [K.from_integer(iv)]
54
        for i in range(0, len(pt)):
55
            ct.append(self._encrypt_block(pt[i] + ct[-1:]))
56
        return ct
57

58
    def decrypt(self, ct):
59
        pt = []
60
        for i in range(0, len(ct) - 1):
61
            pt.append(self._decrypt_block(ct[i + 1]) + ct[i])
62
        return pt
63

64

65
def get_ciphertext(conn):
66
    round_keys = []
67
    ct = bytes.fromhex(conn.recvline().decode())
68
    return round_keys, ct
69

70

71
def pad(m: bytes, n: int) -> bytes:
72
    x = n - len(m) % n
73
    return m + bytes([x] * x)
74

75

76
def undo_cbc(ct):
77
    pt = pad(story, 16)
78
    pt_out = []
79
    ct_out = []
80
    for i in range(0, len(pt), 16):
81
        pt_block = xor(pt[i : i + 16], ct[i : i + 16])
82
        ct_block = ct[i + 16 : i + 32]
83

84
        pt_l, pt_r = pt_block[:8], pt_block[8:]
85
        ct_l, ct_r = ct_block[:8], ct_block[8:]
86
        pt_block = (
87
            K.from_integer(int.from_bytes(pt_l)),
88
            K.from_integer(int.from_bytes(pt_r)),
89
        )
90
        ct_block = (
91
            K.from_integer(int.from_bytes(ct_l)),
92
            K.from_integer(int.from_bytes(ct_r)),
93
        )
94

95
        pt_out.append(pt_block)
96
        ct_out.append(ct_block)
97
    return pt_out, ct_out
98

99

100
def solve():
101
    P = PolynomialRing(K, 7, [f"rk_{i}" for i in range(7)])
102
    key = P.gens()
103
    P = PolynomialRing(P, 4, ["pt_l", "pt_r", "ct_l", "ct_r"])
104
    pt_l, pt_r, ct_l, ct_r = P.gens()
105

106
    cipher = Feistel(key, rounds=7, block_size=16)
107
    pt = [pt_l, pt_r]
108
    ct = [ct_l, ct_r]
109
    l_forwards, r_forwards = cipher._encrypt_block(pt, round_num=2)
110
    l_backwards, r_backwards = cipher._decrypt_block(ct, round_num=3)
111

112
    conn = connect("basedsbox.challs.srdnlen.it", 46173)
113
    round_keys, ct = get_ciphertext(conn)
114

115
    pt_blocks, ct_blocks = undo_cbc(ct)
116

117
    poly_left = (l_forwards - l_backwards).numerator()
118
    poly_right = (r_forwards - r_backwards).numerator()
119
    eqs = []
120
    eqs_left = []
121
    for pt_block, ct_block in zip(pt_blocks, ct_blocks):
122
        pt_l, pt_r = pt_block
123
        ct_l, ct_r = ct_block
124

125
        eqs.append(poly_right(pt_l, pt_r, ct_l, ct_r))
126
        eqs_left.append(poly_left(pt_l, pt_r, ct_l, ct_r))
127
    R = eqs[0].parent()
128
    I = R.ideal(eqs)
129
    set_verbose(10)
130
    G = I.groebner_basis()
131

132
    solutions = {}
133
    for g in G:
134
        assert g.degree() == 1
135
        mon = g.monomials()[0]
136
        sol = g.constant_coefficient()
137
        solutions[mon] = sol
138
    other = eqs_left[0].subs(solutions)
139
    assert other.degree() == 1
140
    mon = other.monomials()[0]
141
    sol = other.univariate_polynomial().roots()[0][0]
142
    solutions[mon] = sol
143

144
    round_keys_solved = [
145
        int("".join(map(str, solutions[mon].list()))[::-1], 2).to_bytes(8, "big")
146
        for mon in R.gens()
147
    ]
148

149
    key = xor(reduce(xor, round_keys_solved))
150

151
    conn.sendline(key.hex().encode())
152
    conn.recvall()