a ctfer on the load

1
n1=144193923737869044259998596038292537217126517072587407189785154961344425600188709243733103713567903690926695626210849582322575275021963176688615503362430255878068025864333805901831356111202249176714839010151878345993886718863579928588098080351940561045688931786378656665718140998014299097023143181095121810219
2

3
e1=65537
4

5
d1=12574092103116126584156918631595005114605155027996964036950457918490065036621732354668884564796078087090438462300608898225025828108557296714458055780952572974382089675780912070693778415852291145766476219909978391880801604060224785419022793121117332853938170749724540897211958251465747669952580590146500249193
6

7
e2=6767671
8

9
c=31703515320997441500407462163885912085193988887521686491271883832485018463764003313655377418478488372329742364292629844576532415828605994734718987367062694340608380583593689052813716395874850039382743513756381017287371000882358341440383454299152364807346068866304481227367259672607408256375720022838698292966

1
from Crypto.Util.number import long_to_bytes
2
from random import randint
3
from math import gcd
4

5
n1=
6
e1=65537
7
d1=
8

9
e2=6767671
10
c=
11

12
solution_not_found = True
13

14
while solution_not_found:
15
    k = d1 * e1 - 1
16
    g = randint(2, n1 - 1)
17
    t = k
18

19
    while t % 2 == 0:
20
        t = t // 2
21
        x = pow(g, t, n1)
22

23
        if x > 1 and gcd(x - 1, n1) > 1:
24
            p = gcd(x - 1, n1)
25
            q = n1 // p
26
            solution_not_found = False
27
            break
28

29
phi = (p-1)*(q-1)
30

31
d2 = pow(e2, -1, phi)
32

33
p = pow(c, d2, n1)
34

35
print(long_to_bytes(p))

1
import random
2
from datetime import datetime
3
import hashlib
4
import hmac
5

6
class DiceGame():
7
    def __init__(self):
8
        self.balance = 800
9
        self.client_seed = "1337awesome"
10
        self.nonce = 0
11
        self.running = True
12
        with open("./serverseed", 'r') as f:
13
            random.seed(f.read())
14

15
    def roll_dice(self) -> int:
16
        self.server_seed = random.getrandbits(32)
17
        nonce_client_msg = f"{self.client_seed}-{self.nonce}".encode()
18
        sig = hmac.new(str(self.server_seed).encode(), nonce_client_msg, hashlib.sha256).hexdigest()
19
        index = 0
20
        lucky = int(sig[index*5:index*5+5], 16)
21
        while (lucky >= 1e6):
22
            index += 1
23
            lucky = int(sig[index * 5:index * 5 + 5], 16)
24
            if (index * 5 + 5 > 129):
25
                lucky = 9999
26
                break
27
        return round((lucky % 1e4) * 1e-2)
28

29
    def show_starting_banner(self) -> None:
30
        print(f"Balance: {self.balance}")
31
        print("options: ")
32
        print(" a) view shop ")
33
        print(" b) gamble ")
34
        print(" c) set own seed ")
35
        print(" d) exit ")
36

37
    def gamble_game(self) -> None:
38
        print("ULTIMATE BET WIN BIG MONEY!!!")
39
        wager = float(input(f"Wager per game (min-wager is {self.balance/800}): "))
40
        if (wager < self.balance/800 or wager > self.balance):
41
            print("Wager not in range!")
42
            return
43
        games = int(input("Number of games (int): "))
44
        greed = float(input("Enter your number higher or equal to the roll between 2-98 (prize improves with lower numbers): ")) # win if number is between 0 and n
45
        if (greed < 2 or greed > 98):
46
            print("Greed not in range!")
47
            return
48
        confirm = input("Do you wish to proceed? (Y/N)")
49
        if confirm == "Y":
50
            for i in range(games):
51
                if (self.balance - wager >= 0):
52
                    roll = self.roll_dice()
53
                    multiplier = (100-1)/(greed)
54
                    self.balance -= wager
55
                    reward_value = 0
56
                    if (greed >= roll):
57
                        reward_value = wager * multiplier
58
                    print(f"Game {i:05}: Roll: {roll:02}, Reward: {reward_value}, Nonce: {self.nonce}, Client-Seed: {self.client_seed}, Server-Seed: {self.server_seed}")
59
                    self.nonce+=1
60
                    self.balance += reward_value
61
                else:
62
                    print(f"Out of Balance...")
63
                    break
64
            print(f"Final Balance: {self.balance}")
65

66
    def game(self) -> None:
67
        while self.running:
68
                self.show_starting_banner()
69
                option = input("> ")
70
                match option:
71
                    case "a":
72
                        print("-- SHOP --")
73
                        print("a) buy flag : $10000")
74
                        print("b) exit")
75
                        choice = input("> ")
76
                        if (choice == "a") and (self.balance >= 10000):
77
                            with open("./flag", 'r') as f:
78
                                print(f.read())
79
                    case "b":
80
                        try:
81
                            self.gamble_game()
82
                        except Exception as e:
83
                            print("Error: ", e)
84
                    case "c":
85
                        print(f"current seed: {self.client_seed}")
86
                        self.client_seed = input("Set custom seed: ")
87
                    case "d":
88
                        self.running = False
89
                        break
90
                    case _:
91
                        print("unknown command..")
92

93
dicegame : DiceGame = DiceGame()
94
dicegame.game()

1
import hashlib
2
import hmac
3
import re
4

5
from randcrack import RandCrack
6

7
from pwn import *
8

9
# 配置连接信息
10
HOST = '34.162.20.138'
11
PORT = 5000
12

13
# 本地模拟服务端的 roll_dice 逻辑
14
def get_predicted_roll(server_seed, client_seed, nonce):
15
    nonce_client_msg = f"{client_seed}-{nonce}".encode()
16
    # 计算 HMAC
17
    sig = hmac.new(str(server_seed).encode(), nonce_client_msg, hashlib.sha256).hexdigest()
18

19
    index = 0
20
    lucky = int(sig[index*5:index*5+5], 16)
21
    while (lucky >= 1e6):
22
        index += 1
23
        lucky = int(sig[index * 5:index * 5 + 5], 16)
24
        if (index * 5 + 5 > 129):
25
            lucky = 9999
26
            break
27
    return round((lucky % 1e4) * 1e-2)
28

29
def solve():
30
    # context.log_level = 'debug' # 如果需要调试可以取消注释
31
    io = remote(HOST, PORT)
32
    rc = RandCrack()
33

34
    client_seed = "1337awesome"
35
    current_nonce = 0
36

37
    print("[*] Connected via Pwntools")
38

39
    # === 第一阶段：收集 624 个 Server Seeds ===
40
    print("[*] Phase 1: Harvesting 624 server seeds to recover PRNG state...")
41

42
    # 进入 Gamble 模式
43
    io.sendlineafter(b'> ', b'b')
44

45
    # 赌注: 1 (最小), 局数: 624, Greed: 90 (为了稍微回点血保持余额，虽然输赢无所谓)
46
    io.sendlineafter(b'Wager per game', b'1')
47
    io.sendlineafter(b'Number of games', b'624')
48
    io.sendlineafter(b'Enter your number', b'90')
49
    io.sendlineafter(b'Do you wish to proceed? (Y/N)', b'Y')
50

51
    # 接收并解析输出
52
    for i in range(624):
53
        line = io.recvline().decode().strip()
54
        # 解析 Server-Seed
55
        match = re.search(r'Server-Seed: (\d+)', line)
56
        if match:
57
            seed_val = int(match.group(1))
58
            rc.submit(seed_val)
59
            current_nonce += 1
60
        else:
61
            print(f"Error parsing line: {line}")
62

63
    print("[+] State recovered! Engine is now synchronized.")
64

65
    # 解析当前余额
66
    final_balance_line = io.recvline().decode() # "Final Balance: xxx"
67
    current_balance = float(final_balance_line.split(":")[1].strip())
68
    print(f"[*] Current Balance: {current_balance}")
69

70
    # === 第二阶段：预测并赢取资金 ===
71
    print("[*] Phase 2: Exploiting via prediction...")
72

73
    while current_balance < 10000:
74
        # 1. 预测下一个 Server Seed
75
        predicted_server_seed = rc.predict_getrandbits(32)
76

77
        # 2. 本地计算结果
78
        predicted_roll = get_predicted_roll(predicted_server_seed, client_seed, current_nonce)
79

80
        # 3. 制定策略
81
        # 我们需要 greed >= roll 才能赢。赔率是 (100-1)/greed。
82
        # 为了最大化收益，greed 应该尽可能小，但必须 >= roll。
83
        # 游戏限制 greed 范围 2-98。
84

85
        target_greed = max(2, predicted_roll)
86

87
        # 如果预测结果是 99 (极其罕见)，greed 最大只能 98，必输。
88
        # 或者如果我们非常有信心，可以直接梭哈。
89

90
        wager = current_balance
91

92
        # 如果必输 (roll > 98)，只下最小注烧掉这个随机数
93
        if predicted_roll > 98:
94
            print(f"[-] Predicted bad roll ({predicted_roll}). Skipping with min bet.")
95
            wager = max(1, current_balance / 800) # 保持最小下注
96
            target_greed = 98
97
        else:
98
            print(f"[+] Predicted Roll: {predicted_roll}. Betting ALL-IN with Greed: {target_greed}")
99

100
        # 发起单局游戏
101
        io.sendlineafter(b'> ', b'b')
102
        io.sendlineafter(b'Wager per game', str(wager).encode())
103
        io.sendlineafter(b'Number of games', b'1')
104
        io.sendlineafter(b'Enter your number', str(target_greed).encode())
105
        io.sendlineafter(b'Do you wish to proceed? (Y/N)', b'Y')
106

107
        # 读取结果
108
        result_line = io.recvline().decode()
109
        if "Reward" in result_line:
110
            print(f"   -> Result: {result_line.strip()}")
111
            current_nonce += 1
112

113
        balance_line = io.recvline().decode()
114
        current_balance = float(balance_line.split(":")[1].strip())
115
        print(f"   -> New Balance: {current_balance}")
116

117
    # === 第三阶段：购买 Flag ===
118
    print("[*] Phase 3: Buying Flag...")
119
    io.sendlineafter(b'> ', b'a') # Enter shop
120
    io.sendlineafter(b'> ', b'a') # Buy flag
121
    io.interactive()
122
if __name__ == "__main__":
123
    solve()

1
import itertools
2

3
# WG-style transformation ANF on 7 variables (x0..x6).
4
WG_ANF_TERMS = [
5
    (1, 2, 3, 4, 5, 6),
6
    (0, 1, 2, 3, 5),
7
    (0, 1, 2, 4, 5),
8
    (0, 1, 3, 4, 5),
9
    (1, 2, 3, 4, 5),
10
    (0, 1, 2, 4, 6),
11
    (0, 2, 3, 4, 6),
12
    (1, 2, 3, 4, 6),
13
    (0, 1, 2, 5, 6),
14
    (0, 2, 3, 5, 6),
15
    (1, 2, 3, 5, 6),
16
    (0, 3, 4, 5, 6),
17
    (1, 3, 4, 5, 6),
18
    (0, 1, 2, 4),
19
    (0, 1, 2, 5),
20
    (1, 2, 3, 5),
21
    (0, 1, 4, 5),
22
    (1, 3, 4, 5),
23
    (2, 3, 4, 5),
24
    (1, 2, 3, 6),
25
    (0, 1, 4, 6),
26
    (1, 2, 4, 6),
27
    (0, 3, 4, 6),
28
    (1, 3, 4, 6),
29
    (1, 2, 5, 6),
30
    (0, 3, 5, 6),
31
    (1, 4, 5, 6),
32
    (2, 4, 5, 6),
33
    (3, 4, 5, 6),
34
    (0, 1, 2),
35
    (0, 1, 4),
36
    (0, 2, 4),
37
    (1, 2, 4),
38
    (0, 1, 5),
39
    (0, 3, 5),
40
    (1, 3, 5),
41
    (2, 3, 5),
42
    (3, 4, 5),
43
    (0, 1, 6),
44
    (0, 3, 6),
45
    (2, 3, 6),
46
    (3, 4, 6),
47
    (0, 5, 6),
48
    (2, 5, 6),
49
    (4, 5, 6),
50
    (2, 3),
51
    (3, 4),
52
    (0, 5),
53
    (3, 5),
54
    (1, 6),
55
    (3, 6),
56
    (4, 6),
57
    (0,),
58
    (3,),
59
    (5,),
60
    (6,),
61
]
62

63

64
def eval_anf(bits, terms):
65
    """Evaluate ANF given bits (tuple/list of 0/1) and list of monomial tuples."""
66
    acc = 0
67
    for mon in terms:
68
        prod = 1
69
        for idx in mon:
70
            prod &= bits[idx]
71
            if prod == 0:
72
                break
73
        acc ^= prod
74
    return acc
75

76

77
class NLFFilterCipher:
78
    """
79
    Bit-level LFSR with nonlinear filter function.
80
    state[0] is the newest bit; shift inserts feedback at position 0 and drops the last bit.
81
    """
82

83
    def __init__(self, feedback_taps, filter_taps, state_bits):
84
        self.feedback_taps = tuple(feedback_taps)
85
        self.filter_taps = tuple(filter_taps)
86
        self.L = len(state_bits)
87
        self.state = list(state_bits)
88

89
    def clock(self):
90
        """Clock once, update state, and return keystream bit."""
91
        taps = [self.state[i] for i in self.filter_taps]
92
        z = eval_anf(taps, WG_ANF_TERMS)
93
        fb = 0
94
        for idx in self.feedback_taps:
95
            fb ^= self.state[idx]
96
        self.state = [fb] + self.state[:-1]
97
        return z
98

99
    def keystream(self, n):
100
        return [self.clock() for _ in range(n)]

1
import os
2
from cryptography.hazmat.primitives.ciphers.aead import ChaCha20Poly1305
3
from cryptography.hazmat.primitives.kdf.hkdf import HKDF
4
from cryptography.hazmat.primitives import hashes
5

6

7
def derive_key(state_bits, length=32):
8
    data = bytes(state_bits)
9
    hkdf = HKDF(algorithm=hashes.SHA256(), length=length, salt=None, info=b"nlfg-ctf")
10
    return hkdf.derive(data)
11

12

13
def encrypt(flag: bytes, state_bits):
14
    key = derive_key(state_bits, length=32)
15
    nonce = os.urandom(12)
16
    aead = ChaCha20Poly1305(key)
17
    ct = aead.encrypt(nonce, flag, associated_data=None)
18
    return nonce, ct
19

20

21
def decrypt(nonce, ct, state_bits):
22
    key = derive_key(state_bits, length=32)
23
    aead = ChaCha20Poly1305(key)
24
    return aead.decrypt(nonce, ct, associated_data=None)

1
"""
2
solver.
3

4
It does four steps:
5
1) Read public data (taps, keystream, filter ANF).
6
2) Build one small annihilator polynomial for z=0 and z=1 (degree <= 3).
7
3) Encode the LFSR + annihilator equations to CNF and solve with SAT.
8
4) Derive the key from the recovered 48-bit state and decrypt.
9
"""
10

11
import json
12
from itertools import combinations
13
from pathlib import Path
14
from pysat.formula import CNF, IDPool
15
from pysat.solvers import Glucose4
16
import crypto
17

18

19
def eval_anf(bits, terms):
20
    """Evaluate the filter ANF on a 7-bit vector."""
21
    acc = 0
22
    for mon in terms:
23
        prod = 1
24
        for i in mon:
25
            prod &= bits[i]
26
            if not prod:
27
                break
28
        acc ^= prod
29
    return acc
30

31

32
def build_annihilator(filter_terms, target_side):
33
    """
34
    Return one degree<=3 annihilator polynomial for the 7-bit filter.
35
    target_side=1: polynomial vanishes when f=1 (use with z=1)
36
    target_side=0: polynomial vanishes when f=0 (use with z=0)
37
    """
38
    mons = [()]
39
    for d in range(1, 4):
40
        mons += list(combinations(range(7), d))
41

42
    # truth table of f
43
    f_tt = []
44
    for mask in range(1 << 7):
45
        bits = [(mask >> i) & 1 for i in range(7)]
46
        f_tt.append(eval_anf(bits, filter_terms))
47

48
    # Build rows (bitmasks of monomials that evaluate to 1) where f == target_side.
49
    rows = []
50
    for mask, val in enumerate(f_tt):
51
        if val != target_side:
52
            continue
53
        bits = [(mask >> i) & 1 for i in range(7)]
54
        row = 0
55
        for j, mon in enumerate(mons):
56
            v = 1
57
            for i in mon:
58
                v &= bits[i]
59
                if not v:
60
                    break
61
            if v:
62
                row |= 1 << j
63
        rows.append(row)
64

65
    def nullspace_basis(rows, ncols):
66
        """Simple GF(2) row reduction to get a basis of the nullspace."""
67
        rows = rows[:]
68
        pivots = {}
69
        r = 0
70
        for c in range(ncols):
71
            pr = next((i for i in range(r, len(rows)) if (rows[i] >> c) & 1), None)
72
            if pr is None:
73
                continue
74
            rows[r], rows[pr] = rows[pr], rows[r]
75
            pivot_row = rows[r]
76
            pivots[c] = pivot_row
77
            for i in range(len(rows)):
78
                if i != r and ((rows[i] >> c) & 1):
79
                    rows[i] ^= pivot_row
80
            r += 1
81
            if r == len(rows):
82
                break
83

84
        pivot_cols = set(pivots.keys())
85
        free_cols = [c for c in range(ncols) if c not in pivot_cols]
86
        pivot_items = sorted(pivots.items(), reverse=True)
87

88
        basis = []
89
        for fcol in free_cols:
90
            vec = 1 << fcol
91
            for c, row in pivot_items:
92
                other = row & ~(1 << c)
93
                parity = (other & vec).bit_count() % 2
94
                if parity:
95
                    vec |= 1 << c
96
                else:
97
                    vec &= ~(1 << c)
98
            basis.append(vec)
99
        return basis, mons
100

101
    basis, mons = nullspace_basis(rows, len(mons))
102
    vec = basis[0]
103
    poly = [mons[i] for i in range(len(mons)) if (vec >> i) & 1]
104
    return poly
105

106

107
def solve_instance(data):
108
    L = data["L"]
109
    fb = data["feedback_taps"]
110
    ftaps = data["filter_taps"]
111
    terms = [tuple(t) for t in data["filter_terms"]]
112
    ks = data["keystream"]
113

114
    # Single annihilator per side (degree <=3).
115
    ann_f = build_annihilator(terms, target_side=1)
116
    ann_f1 = build_annihilator(terms, target_side=0)
117

118
    pool = IDPool(start_from=L + 1)
119
    cnf = CNF()
120

121
    # b[t]: state[0]=b[t], state[1]=b[t-1], ...
122
    tmin, tmax = - (L - 1), len(ks)
123
    b = {t: pool.id() for t in range(tmin, tmax + 1)}
124

125
    def and2(a, bvar):
126
        # o = a AND bvar
127
        o = pool.id()
128
        cnf.extend([[-a, -bvar, o], [a, -o], [bvar, -o]])
129
        return o
130

131
    def xor2(a, bvar):
132
        # o = a XOR bvar
133
        o = pool.id()
134
        cnf.extend([[-a, -bvar, -o], [-a, bvar, o], [a, -bvar, o], [a, bvar, -o]])
135
        return o
136

137
    def xor_chain(vs):
138
        if len(vs) == 1:
139
            return vs[0]
140
        cur = vs[0]
141
        for v in vs[1:]:
142
            cur = xor2(cur, v)
143
        return cur
144

145
    # LFSR recurrence: b[t+1] = xor(feedback taps)
146
    for t in range(0, len(ks)):
147
        taps = [b[t - off] for off in fb]
148
        eq = xor_chain([b[t + 1]] + taps)
149
        cnf.append([-eq])  # XOR(...) == 0
150

151
    # Annihilator equations per timestep (pick annihilator based on keystream bit)
152
    for t, z in enumerate(ks):
153
        taps = [b[t - off] for off in ftaps]
154
        poly = ann_f if z == 1 else ann_f1
155
        rhs = 0
156
        mon_vars = []
157
        for mon in poly:
158
            if len(mon) == 0:
159
                rhs ^= 1
160
            elif len(mon) == 1:
161
                mon_vars.append(taps[mon[0]])
162
            else:
163
                cur = taps[mon[0]]
164
                for idx in mon[1:]:
165
                    cur = and2(cur, taps[idx])
166
                mon_vars.append(cur)
167
        eq = xor_chain(mon_vars)
168
        cnf.append([eq] if rhs else [-eq])
169

170
    # Direct keystream checks to prune spurious solutions.
171
    check_count = min(40, len(ks))
172
    for t in range(check_count):
173
        taps = [b[t - off] for off in ftaps]
174
        rhs = 0
175
        mon_vars = []
176
        for mon in terms:
177
            if len(mon) == 0:
178
                rhs ^= 1
179
            elif len(mon) == 1:
180
                mon_vars.append(taps[mon[0]])
181
            else:
182
                cur = taps[mon[0]]
183
                for idx in mon[1:]:
184
                    cur = and2(cur, taps[idx])
185
                mon_vars.append(cur)
186
        zvar = xor_chain(mon_vars)
187
        want = ks[t] ^ rhs
188
        cnf.append([zvar] if want else [-zvar])
189

190
    solver = Glucose4(bootstrap_with=cnf.clauses)
191
    assert solver.solve()
192
    model = set(solver.get_model())
193

194
    def val(var):
195
        return 1 if var in model else 0
196

197
    state_bits = [val(b[-i]) for i in range(0, L)]
198
    return state_bits
199

200

201
def main():
202
    data = json.load(open("challenge.json"))
203
    state_bits = solve_instance(data)
204
    pt = crypto.decrypt(bytes.fromhex(data["nonce"]), bytes.fromhex(data["ct"]), state_bits)
205
    print(pt.decode())
206

207

208
if __name__ == "__main__":
209
    main()

1
import numpy as np
2
import galois
3
from secret import gen_commuting_matrix
4
from Crypto.Util.number import *
5
from Crypto.Random import random
6
GF = galois.GF(202184226278391025014930169562408816719)
7

8

9
A = GF([])
10

11
FLAG = b'uoftctf{fake_flag}'
12

13
bits = bin(bytes_to_long(FLAG))[2:].zfill(8*len(FLAG))
14

15
for b in bits:
16
    if b=='0':
17
        print(gen_commuting_matrix(A))
18
    else:
19
        print(np.linalg.matrix_power(A, random.randrange(202184226278391025014930169562408816719**12-1)))

1
import re
2
from Crypto.Util.number import *
3
import tqdm
4

5
p = 202184226278391025014930169562408816719
6
F = GF(p)
7

8
V = VectorSpace(F, 12)
9

10
A = Matrix(F, [])
11

12
K = GF(p^12, modulus=A.characteristic_polynomial(), name='x')
13

14
x = K.gen()
15

16
v = vector(F, (1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0))
17

18
basis = [v]
19
for i in range(1, 12):
20
    basis.append(A*basis[-1])
21

22
Binv = Matrix(basis).transpose().inverse()
23

24
# generated with AI because I do NOT want to parse my own creations myself.
25
def parse_pretty_matrix(s):
26
    """
27
    Parse a matrix written in the Sage/NumPy pretty format:
28

29
    [[ a b c
30
       d e f ]
31
     [ g h i ]]
32

33
    Returns a Sage Matrix over ZZ.
34
    """
35

36
    # Remove outer whitespace
37
    s = s.strip()
38

39
    # Sanity check
40
    if not (s.startswith("[[") and s.endswith("]]")):
41
        raise ValueError("Input does not look like a matrix")
42

43
    # Extract row blocks: anything between [ ... ]
44
    # but not the outermost brackets
45
    row_strings = re.findall(r"\[([^\[\]]+)\]", s)
46

47
    rows = []
48
    for row in row_strings:
49
        # Split on whitespace and parse integers
50
        entries = [ZZ(x) for x in row.split()]
51
        rows.append(entries)
52

53
    # Check rectangularity
54
    ncols = len(rows[0])
55
    for r in rows:
56
        if len(r) != ncols:
57
            raise ValueError("Non-rectangular matrix")
58

59
    return Matrix(ZZ, rows).change_ring(F)
60

61
def parse_all_pretty_matrices(s):
62
    """
63
    Parse multiple pretty-printed matrices back-to-back.
64

65
    Returns a list of Matrix(ZZ).
66
    """
67

68
    mats = []
69
    i = 0
70
    n = len(s)
71

72
    while i < n:
73
        # Find start of matrix
74
        start = s.find("[[", i)
75
        if start == -1:
76
            break
77

78
        depth = 0
79
        j = start
80

81
        # Find matching closing brackets
82
        while j < n:
83
            if s[j:j+2] == "[[":
84
                depth += 1
85
                j += 2
86
            elif s[j:j+2] == "]]":
87
                depth -= 1
88
                j += 2
89
                if depth == 0:
90
                    break
91
            else:
92
                j += 1
93

94
        block = s[start:j]
95

96
        mats.append(parse_pretty_matrix(block))
97
        i = j
98

99
    return mats
100

101
with open("../dist/output.txt") as f:
102
    data = f.read()
103

104
Ms = parse_all_pretty_matrices(data)
105
# The rest is written by me, not the clanker.
106
print("Parsed matrices")
107
bits = []
108

109

110
# Technically you could just do this all in the matrix field but that's just unecessarily expensive...
111
o = p^12-1
112
small_primes = []
113
for d in Primes()[:100]:
114
    if o%d==0:
115
        small_primes.append(d)
116

117
fac = 1
118
for d in small_primes:
119
    while o%d==0:
120
        if x^(o//d)==1:
121
            o//=d
122
        else:
123
            break
124

125
print(x^o)
126

127
for M in tqdm.tqdm(Ms):
128
    P = Binv*(M*v)
129
    #print(Polynomial(P)(A)==M)
130
    y = K(P)
131
    if (y^o)==1:
132
        bits.append(1)
133
    else:
134
        bits.append(0)
135

136
print(long_to_bytes(int(''.join(map(str, bits)), 2)))

1
#!/usr/bin/env python3
2
import os, sys, base64
3
from Crypto.Cipher import AES
4
from Crypto.Random import get_random_bytes
5

6
BS=16
7
FLAG=open("flag.txt","rb").read().strip()
8
M=256
9
L=1024
10

11
def pad(m):
12
    p=BS-(len(m)%BS)
13
    return m+bytes([p])*p
14

15
class O:
16
    def __init__(self):
17
        self.k=get_random_bytes(16)
18
        self.pl=int.from_bytes(os.urandom(1),"big")%97
19
        n=L//BS+1
20
        self.n=n
21
        self.q=list(range(n))
22
        for i in range(n-1,0,-1):
23
            j=int.from_bytes(os.urandom(2),"big")%(i+1)
24
            self.q[i],self.q[j]=self.q[j],self.q[i]
25

26
    def e(self, idx, u):
27
        if idx<0 or idx>=self.n:
28
            return None
29
        u=u[:M]
30
        p=os.urandom(self.pl)
31
        m=p+u+FLAG
32
        if len(m)>L:
33
            m=m[:L]
34
        else:
35
            m+=os.urandom(L-len(m))
36
        c=AES.new(self.k,AES.MODE_ECB).encrypt(pad(m))
37
        b=[c[i:i+BS] for i in range(0,len(c),BS)]
38
        out=[b[i] for i in self.q]
39
        return out[idx]
40

41
o=O()
42

43
while True:
44
    sys.stdout.write("> ")
45
    sys.stdout.flush()
46
    l=sys.stdin.readline()
47
    if not l:
48
        break
49
    l=l.strip()
50
    if not l:
51
        print("error")
52
        continue
53
    if l.lower() == "exit":
54
        break
55
    if ":" in l:
56
        a,h=l.split(":",1)
57
    else:
58
        parts=l.split(None,1)
59
        if len(parts)==1:
60
            a,h=parts[0],""
61
        else:
62
            a,h=parts[0],parts[1]
63
    try:
64
        idx=int(a,10)
65
        u=bytes.fromhex(h) if h else b""
66
    except Exception:
67
        print("error")
68
        continue
69
    blk=o.e(idx,u)
70
    if blk is None:
71
        print("error")
72
    else:
73
        print(base64.b64encode(blk).decode())

1
#!/usr/bin/env python3
2
from pwn import *
3
import base64, os, re
4
from collections import Counter
5

6
context.log_level = "error"
7

8
HOST, PORT = "34.186.247.84", 5000
9
BS = 16
10
FLAG_RE = re.compile(rb"uoftctf\{[^}]+\}")
11

12
def oracle_connect():
13
    r = remote(HOST, PORT)
14
    r.recvuntil(b"> ")
15
    return r
16

17
def q(r, idx: int, data: bytes) -> bytes | None:
18
    line = f"{idx}:{data.hex()}".encode()
19
    r.sendline(line)
20
    resp = r.recvline().strip()
21
    r.recvuntil(b"> ")
22
    if resp == b"error":
23
        return None
24
    return base64.b64decode(resp)
25

26
def discover_nblocks(r, limit=256) -> int:
27
    for i in range(limit):
28
        if q(r, i, b"") is None:
29
            return i
30
    raise Exception("failed to discover nblocks")
31

32
def get_all_blocks(r, nblocks: int, data: bytes):
33
    return [q(r, i, data) for i in range(nblocks)]
34

35
def find_align_pad(r, nblocks: int) -> int:
36
    for pad in range(BS):
37
        pt = b"C"*pad + b"A"*(3*BS) + b"D"*BS
38
        bl = get_all_blocks(r, nblocks, pt)
39
        c = Counter(bl)
40
        if any(v >= 3 for v in c.values()):
41
            return pad
42
    raise Exception("align_pad not found")
43

44
def find_marker_ct(r, nblocks: int, align_pad: int, marker=b"Z"*BS) -> bytes:
45
    pt = b"C"*align_pad + marker + os.urandom(BS) + marker + os.urandom(BS)
46
    bl = get_all_blocks(r, nblocks, pt)
47
    c = Counter(bl)
48
    dups = [b for b, v in c.items() if v >= 2]
49
    if not dups:
50
        raise Exception("marker_ct not found")
51
    dups.sort(key=lambda x: c[x], reverse=True)
52
    return dups[0]
53

54
def find_out_index_for_t(r, nblocks: int, align_pad: int, marker_ct: bytes, t: int, marker=b"Z"*BS) -> int:
55
    pt = b"C"*align_pad + os.urandom(BS*t) + marker + os.urandom(BS*2)
56
    for i in range(nblocks):
57
        b = q(r, i, pt)
58
        if b == marker_ct:
59
            return i
60
    raise Exception("failed to locate marker output index")
61

62
def solve():
63
    r = oracle_connect()
64
    nblocks = discover_nblocks(r)
65
    align_pad = find_align_pad(r, nblocks)
66
    marker_ct = find_marker_ct(r, nblocks, align_pad)
67

68
    pos_cache = {}
69
    recovered = b""
70
    i = 0
71

72
    while True:
73
        fill = BS - 1 - (i % BS)
74
        t = (fill + i) // BS
75

76
        if t not in pos_cache:
77
            pos_cache[t] = find_out_index_for_t(r, nblocks, align_pad, marker_ct, t)
78
        idx = pos_cache[t]
79

80
        target = q(r, idx, b"C"*align_pad + b"A"*fill)
81
        if target is None:
82
            raise Exception("unexpected error on probe")
83

84
        base = b"C"*align_pad + b"A"*fill + recovered
85
        found = None
86
        for g in range(256):
87
            b = q(r, idx, base + bytes([g]))
88
            if b == target:
89
                found = g
90
                break
91

92
        if found is None:
93
            raise Exception(f"dictionary miss at byte {i}")
94

95
        recovered += bytes([found])
96
        i += 1
97

98
        print(f"Recovered {i} bytes: {recovered!r}")
99

100
        m = FLAG_RE.search(recovered)
101
        if m:
102
            print(m.group(0).decode())
103
            return
104

105
if __name__ == "__main__":
106
    solve()