XYCTF2025

发表于 更新于

时间过的真快啊，没想到距离XYCTF2024已经过去1年了

前言

说实话，其实我这次出的挺烂的。确实最近没有啥好的idea加上准备挺匆忙的，所以出现了一些非预期，还有些抽象的题目。希望大家轻点喷。

Misc

sins

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from secret import flag

print('For there are three that bear record in heaven, the Father, the Word, and the Holy Ghost')
print('But here we have four cases bearing witness')


def i_pow(n):
    if n % 4 == 0: # as the 40 days of flood
        return '1'
    elif n % 4 == 1: # as the 1 true God
        return 'i'
    elif n % 4 == 2: # as the 2 tablets of stone
        return '-1'
    elif n % 4 == 3: # as the 3 days in the tomb
        return '-i'

inp = input("wash away your sins: ")
assert all(i in "i0123456789+-*%/^=<>~&|:()[]'" for i in inp), "invalid char"
assert len(inp) < 16, "too long"
R = eval(f"lambda i: {inp}", {}, {})
assert all(R(i) == i_pow(i) for i in range(int.from_bytes(b'The_adwa_shall_forgive_thee') // 2**195))
print(flag)

呃，这个题其实就是之前codegolf打多了，莫名想出来的一个题目。其实挺简单的，也就是对 python 一些语法的使用的考察

我本人给出了两个做法

1
2
f = lambda i:'1i--'[i%4::-2]
f = lambda i:'--1i'[i-2::2]

如果还有啥更好的欢迎来讨论

Crypto

choice

题目

1
2
3
4
5
6
7
8
9
10
11
from Crypto.Util.number import bytes_to_long
from random import Random
from secret import flag

assert flag.startswith(b'XYCTF{') and flag.endswith(b'}')
flag = flag[6:-1]

msg = bytes_to_long(flag)
rand = Random()
test = bytes([i for i in range(255, -1, -1)])
open('output.py', 'w').write(f'enc = {msg ^ rand.getrandbits(msg.bit_length())}\nr = {[rand.choice(test) for _ in range(2496)]}')

其中对random.py改了246行，变成了k = n.bit_length() - 1

不过似乎我直接给一个 random.py 大家都没有看出来改了一点点东西，所以有点锅了。其实加了这个 -1 的话这个题目才可以做，不然调用choice的话就相当于是getrandbits(9)然后输出8bits的值，然后弃掉剩下的以至于无法进行回推。而有了-1就是getrandbits(8)了直接找个wheel就好了 。

Complex_signin

题目

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
from Crypto.Util.number import *
from Crypto.Cipher import ChaCha20
import hashlib
from secret import flag


class Complex:
    def __init__(self, re, im):
        self.re = re
        self.im = im

    def __mul__(self, c):
        re_ = self.re * c.re - self.im * c.im
        im_ = self.re * c.im + self.im * c.re
        return Complex(re_, im_)

    def __eq__(self, c):
        return self.re == c.re and self.im == c.im

    def __rshift__(self, m):
        return Complex(self.re >> m, self.im >> m)

    def __lshift__(self, m):
        return Complex(self.re << m, self.im << m)

    def __str__(self):
        if self.im == 0:
            return str(self.re)
        elif self.re == 0:
            if abs(self.im) == 1:
                return f"{'-' if self.im < 0 else ''}i"
            else:
                return f"{self.im}i"
        else:
            return f"{self.re} {'+' if self.im > 0 else '-'} {abs(self.im)}i"

    def tolist(self):
        return [self.re, self.im]


def complex_pow(c, exp, n):
    result = Complex(1, 0)
    while exp > 0:
        if exp & 1:
            result = result * c
            result.re = result.re % n
            result.im = result.im % n
        c = c * c
        c.re = c.re % n
        c.im = c.im % n
        exp >>= 1
    return result

bits = 128
p = getPrime(1024)
q = getPrime(1024)
n = p * q
m = Complex(getRandomRange(1, n), getRandomRange(1, n))
e = 3
c = complex_pow(m, e, n)
print(f"n = {n}")
print(f"mh = {(m >> bits << bits).tolist()}")
print(f"C = {c.tolist()}")
print(f"enc = {ChaCha20.new(key=hashlib.sha256(str(m.re + m.im).encode()).digest(), nonce=b'Pr3d1ctmyxjj').encrypt(flag)}")

'''
n = 24240993137357567658677097076762157882987659874601064738608971893024559525024581362454897599976003248892339463673241756118600994494150721789525924054960470762499808771760690211841936903839232109208099640507210141111314563007924046946402216384360405445595854947145800754365717704762310092558089455516189533635318084532202438477871458797287721022389909953190113597425964395222426700352859740293834121123138183367554858896124509695602915312917886769066254219381427385100688110915129283949340133524365403188753735534290512113201932620106585043122707355381551006014647469884010069878477179147719913280272028376706421104753
mh = [3960604425233637243960750976884707892473356737965752732899783806146911898367312949419828751012380013933993271701949681295313483782313836179989146607655230162315784541236731368582965456428944524621026385297377746108440938677401125816586119588080150103855075450874206012903009942468340296995700270449643148025957527925452034647677446705198250167222150181312718642480834399766134519333316989347221448685711220842032010517045985044813674426104295710015607450682205211098779229647334749706043180512861889295899050427257721209370423421046811102682648967375219936664246584194224745761842962418864084904820764122207293014016, 15053801146135239412812153100772352976861411085516247673065559201085791622602365389885455357620354025972053252939439247746724492130435830816513505615952791448705492885525709421224584364037704802923497222819113629874137050874966691886390837364018702981146413066712287361010611405028353728676772998972695270707666289161746024725705731676511793934556785324668045957177856807914741189938780850108643929261692799397326838812262009873072175627051209104209229233754715491428364039564130435227582042666464866336424773552304555244949976525797616679252470574006820212465924134763386213550360175810288209936288398862565142167552]
C = [5300743174999795329371527870190100703154639960450575575101738225528814331152637733729613419201898994386548816504858409726318742419169717222702404409496156167283354163362729304279553214510160589336672463972767842604886866159600567533436626931810981418193227593758688610512556391129176234307448758534506432755113432411099690991453452199653214054901093242337700880661006486138424743085527911347931571730473582051987520447237586885119205422668971876488684708196255266536680083835972668749902212285032756286424244284136941767752754078598830317271949981378674176685159516777247305970365843616105513456452993199192823148760, 21112179095014976702043514329117175747825140730885731533311755299178008997398851800028751416090265195760178867626233456642594578588007570838933135396672730765007160135908314028300141127837769297682479678972455077606519053977383739500664851033908924293990399261838079993207621314584108891814038236135637105408310569002463379136544773406496600396931819980400197333039720344346032547489037834427091233045574086625061748398991041014394602237400713218611015436866842699640680804906008370869021545517947588322083793581852529192500912579560094015867120212711242523672548392160514345774299568940390940653232489808850407256752]
enc = b'\x9c\xc4n\x8dF\xd9\x9e\xf4\x05\x82!\xde\xfe\x012$\xd0\x8c\xaf\xfb\rEb(\x04)\xa1\xa6\xbaI2J\xd2\xb2\x898\x11\xe6x\xa9\x19\x00pn\xf6rs- \xd2\xd1\xbe\xc7\xf51.\xd4\xd2 \xe7\xc6\xca\xe5\x19\xbe'
'''

预期是希望用结式将多变量变成单变量打copper的，不过看起来多元copper也是可以打出来的。比较简单的签到题，解数也是预期的。

reed

题目

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
import string
import random
from secret import flag

assert flag.startswith('XYCTF{') and flag.endswith('}')
flag = flag.rstrip('}').lstrip('XYCTF{')

table = string.ascii_letters + string.digits
assert all(i in table for i in flag)
r = random.Random()

class PRNG:
    def __init__(self, seed):
        self.a = 1145140
        self.b = 19198100
        random.seed(seed)

    def next(self):
        x = random.randint(self.a, self.b)
        random.seed(x ** 2 + 1)
        return x
    
    def round(self, k):
        for _ in range(k):
            x = self.next()
        return x

def encrypt(msg, a, b):
    c = [(a * table.index(m) + b) % 19198111 for m in msg]
    return c

seed = int(input('give me seed: '))
prng = PRNG(seed)
a = prng.round(r.randrange(2**16))
b = prng.round(r.randrange(2**16))
enc = encrypt(flag, a, b)
print(enc)

最背大锅的题目了/(ㄒoㄒ)/~~，当时脑子糊了在后面套了个仿射。以至于可以直接打仿射拿到flag。

实际上这题希望打的是prng，因为它的输出范围很小，我们可以考虑枚举seed找到一个周期很小的输出。然后这里可以找到一个周期为2的seed，这样子我们就可以直接枚举a和b来计算flag了。

prng_xxxx

题目

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
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from hashlib import md5
from secret import flag, b, seed

class LCG:
    def __init__(self, seed, a, b):
        self.seed = seed
        self.a = a
        self.b = b
        self.m = 2**128

    def next(self):
        self.seed = (self.seed * self.a + self.b) % self.m
        return (self.seed >> 64) ^ (self.seed % 2**64)

class lfsr:
    # 我被裁了/(ㄒoㄒ)/~~
    pass

a = 47026247687942121848144207491837523525
assert b < 2**128 and seed < 2**128
lcg = LCG(seed, a, b)
print([lcg.next() for _ in [0] * 64])
print(AES.new(key=md5(str(seed).encode()).digest(), mode=AES.MODE_ECB).encrypt(pad(flag, 16)))
# [17861431650111939539, 15632044669542972472, 18085804805519111109, 11630394250634164303, 10914687109985225138, 7348450425255618214, 10796029302647050328, 14267824433700366397, 9363967587530173835, 8995382728269798714, 3504283765121786984, 1312349325731613524, 10716889342831891752, 12298317818779713512, 8701992888199838445, 7261196699430834071, 4670657923849978944, 9833942603152121381, 18304734854303383637, 15945503654626665549, 6509330987395005461, 223169047706410182, 12990946817252956584, 3884858487227858459, 6366350447244638553, 10326924732676590049, 12989931141522347344, 9197940263960765675, 2481604167192102429, 1409946688030505107, 9263229900540161832, 266892958530212020, 14298569012977896930, 17318088100106133211, 4224045753426648494, 650161332435727275, 9488449142549049042, 8916910451165068139, 10116136382602356010, 6604992256480748513, 7375827593997920567, 1661095751967623288, 4143230452547340203, 4145435984742575053, 10465207027576409947, 16146447204594626029, 2807803679403346199, 10857432394281592897, 1494771564147200381, 2085795265418108023, 11756240132299985418, 13802520243518071455, 1191829597542202169, 16603089856395516862, 12517247819572559598, 14148806699104849454, 8174845389550768121, 15565523852832475714, 10046639095828632930, 15353735627107824646, 7003433641698461961, 11217699328913391211, 6392630836483027655, 7918524192972397836]
# b'l\x8bd,\xa3\xe7\x87*\xca\n\xd7\x11\xd6n=\xeaS`\xa4w\x94(\xb9\xf9\xb9\xc6\xe3\xc2\xfb\xdb\x80\xf6\x9f\xc7\xd1F"`{;V\xa7}Z\xc0\xc0\xf6<'

好吧，这个是单纯的整烂活XD。预期exp大概要跑1h左右确实挺慢的，其实当时准备用64bits的参数来出的，但是感觉好像可以硬爆出来所以改成128bits了。

其实这题是基于一个 Q&A，具体可以看Attacks on LCG with "self-XOR" output function?

做法如下

首先我们要找到一组 ∣wi∣<W|w_i|<W (越小越好) 使得

∑i=1mwiAi≡0mod  2n/2+k\sum^m_{i=1}w_iA^i\equiv 0\mod 2^{n/2+k}

其中 kk 是一个小数(就是后面我们要猜的bits数)，然后我们可以做一个背包格来得到 wiw_i，这里建议用 BKZ 然后 block_size 取大点，这样子规约的值稳定可以在 [−1,1][-1,1] 以内。然后 ww 的界大概是满足 mlog⁡2(W)≈n2+km\log_2(W) \approx \frac{n}{2}+k 这个式子的。

然后后面我们就要去猜测 X0X_0 和 CC 的低位了，然后如果看过直接蜀道山CTF的 prng_lfsr 的话，其实后面的 XiX_i 的低位也是可以求出来的(因为都是满足模 2l2^l)。然后我们可以和输出进行异或拿到对应的高位的位置(这和蜀道山CTF的 prng_lfsr 也是一致的)。然后我们可以用 Xi∗X_i^* 来表示猜测的值乘上 2n/22^{n/2} 即 Xi∗=2n/2×guessX_i^*=2^{n/2}×guess。

然后我们注意到这么一个东西

∑i=1mwi(Xi+1−Xi)=∑i=1mwi(AiX0+C∑k=0i−1Ak−Ai−1X0−C∑k=0i−2Ak)≡∑i=1mwiAi≡0mod  2n/2+k\sum^m_{i=1}w_i(X_{i+1}-X_i)\\=\sum^m_{i=1}w_i(A^iX_0+C\sum^{i-1}_{k=0}A^k-A^{i-1}X_0-C\sum^{i-2}_{k=0}A^k)\\\equiv\sum^m_{i=1}w_iA^i\\\equiv 0\mod 2^{n/2+k}

这时候我们可以考虑通过用 Xi∗X_i^* 来近似这个和以判断 kk 是否是对的

我们令

Z=∑i=1mwi(Xi+1∗−Xi∗)mod  2n/2+kZ=\sum^m_{i=1}w_i(X^*_{i+1}-X^*_i)\mod 2^{n/2+k}

然后这个 Q&A 说让 Δ\Delta 为 ZZ 和 00 或者 2n/2+k2^{n/2+k} 的差值中的最小值。然后如果这个 Δ\Delta 小于 2mW×2n/22mW×2n/2，那么就有 1−2mW×2−k1-2mW×2^{-k} 的概率是对的。正常来说，这个时候就有剪枝的思路了，但是你直接剪的话是不可能的，因为条件并不是很够，以至于后面DFS的时候数据还是非常的多。

然后 Q&A 这时候就提出了用滑动窗口的方式来进行操作，就是多用几组 YiY_i 来进行条件判断，这样子最后的可能性就大大减少了，大约1h左右就可以跑出来了。