三顺七的笔记
0%

2023-0CTF-Crypto-WP

发表于 更新于 分类于 Valine：

打不动，也看不懂

有两道还是能理解，看得懂的，其他题就有点反人类了，这里就简单记录一下。

RSA 0：

题目：

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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
#!/usr/bin/env python3

import random
import signal
import socketserver
import string
from Crypto.Util.number import *
from hashlib import sha256
from secret import FLAG
from os import urandom

P_BITS = 512
E_BITS = int(P_BITS * 2 * 0.292) + 30
CNT_MAX = 7

class LCG:
    def __init__(self):
        self.init()

    def next(self):
        out = self.s[0]
        self.s = self.s[1: ] + [(sum([i * j for (i, j) in zip(self.a, self.s)]) + self.b) % self.p]
        return out

    def init(self):
        while True:
            p = getPrime(2 * P_BITS)
            if p.bit_length() == 2 * P_BITS:
                self.p = p
                break
        self.b = getRandomRange(1, self.p)
        self.a = [getRandomRange(1, self.p) for _ in range(6)]
        self.s = [getRandomRange(1, self.p) for _ in range(6)]

class RSA:
    def __init__(self, l, p = 0, q = 0):
        self.l = l
        if not p:
            while True:
                p = getPrime(P_BITS)
                if p.bit_length() == P_BITS:
                    self.p = p
                    break
            while True:
                p = getPrime(P_BITS)
                if p.bit_length() == P_BITS:
                    self.q = p
                    break
        else:
            self.p = abs(p)
            self.q = abs(q)
        self.e = getPrime(E_BITS)
        self.check()

    def enc(self, m):
        return pow(m, self.e, self.n)

    def noisy_enc(self, m, r = 1):
        if r:
            self.refresh()
        return pow(m, self.e ^ self.l.next(), self.n)

    def dec(self, c):
        return pow(c, self.d, self.n)
        
    def check(self):
        assert self.p.bit_length() == P_BITS
        assert self.q.bit_length() == P_BITS
        self.n = self.p * self.q
        self.phi = (self.p - 1) * (self.q - 1)
        assert self.e.bit_length() >= E_BITS
        assert self.e < self.phi
        assert GCD(self.e, self.phi) == 1
        self.d = inverse(self.e, self.phi)
        assert self.d.bit_length() >= E_BITS
        for _ in range(20):
            x = self.l.next() % self.n
            assert self.dec(self.enc(x)) == x

    def refresh(self):
        self.e = (self.e ^ self.l.next()) % (2**E_BITS)

class Task(socketserver.BaseRequestHandler):
    def __init__(self, *args, **kargs):
        super().__init__(*args, **kargs)

    def proof_of_work(self):
        random.seed(urandom(16))
        proof = ''.join([random.choice(string.ascii_letters + string.digits) for _ in range(20)])
        digest = sha256(proof.encode()).hexdigest()
        self.dosend('sha256(XXXX + {}) == {}'.format(proof[4: ], digest))
        self.dosend('Give me XXXX:')
        x = self.request.recv(10)
        x = x.strip().decode('latin-1')
        if len(x) != 4 or sha256((x + proof[4: ]).encode()).hexdigest() != digest:
            return False
        return True

    def dosend(self, msg):
        try:
            self.request.sendall(msg.encode('latin-1') + b'\n')
        except:
            pass
    
    def timeout_handler(self, signum, frame):
        raise TimeoutError

    def recvn(self, sz):
        r = sz
        res = b''
        while r > 0:
            res += self.request.recv(r)
            if res.endswith(b'\n'):
                r = 0
            else:
                r = sz - len(res)
        res = res.strip()
        return res

    def recv_hex(self, l):
        return int(self.recvn(l + 1), 16)

    def handle(self):
        try:
            '''
            signal.signal(signal.SIGALRM, self.timeout_handler)
            signal.alarm(60)
            if not self.proof_of_work():
                self.dosend('You must pass the PoW!')
                return

            signal.alarm(20)
            '''
            
            self.dosend('Give me your RSA key plz.')
            pq = [self.recv_hex(P_BITS // 4) for _ in range(2)]
            lcg = LCG()
            alice = RSA(lcg)
            bob = RSA(lcg, *pq)
            secrets = getRandomNBitInteger(P_BITS // 8)
            secrets_ct = alice.enc(secrets)
            self.dosend('{}\n{}'.format(alice.e, alice.n))
            self.dosend('{}\n{}\n{}\n{}'.format(lcg.p, lcg.a, lcg.b, lcg.s))
            
            CNT = 0
            while CNT < CNT_MAX:
                self.dosend('pt: ')
                pt = self.recv_hex(P_BITS // 2)
                if pt == 0:
                    break
                ct = alice.noisy_enc(pt)
                ct = bob.noisy_enc(ct)
                self.dosend('ct: ' + hex(ct))
                CNT += 1
            print(secrets_ct)
            secrets_ct = bob.noisy_enc(secrets_ct)
            self.dosend('secrets_ct: ' + hex(secrets_ct))
            lcg.init()

            bob = RSA(lcg, *pq)
            self.dosend('{}\n{}\n{}\n{}'.format(lcg.p, lcg.a, lcg.b, lcg.s))

            seen = set()
            while CNT < CNT_MAX:
                self.dosend('ct: ')
                ct = self.recv_hex(P_BITS // 2)
                if ct == 0:
                    break
                pt = alice.dec(ct)
                if pt in seen:
                    self.dosend('You can only decrypt each ciphertext once.')
                    self.request.close()
                else:
                    seen.add(pt)
                pt = bob.noisy_enc(pt)
                self.dosend('pt: ' + hex(pt))
                CNT += 1            
            
            guess = self.recv_hex(P_BITS // 4)
            if guess == secrets:
                self.dosend('Wow, how do you know that?')
                self.dosend('Here is the flag: ' + FLAG)
            else:
                self.dosend('Wrong!')
        except TimeoutError:
            self.dosend('Timeout!')
        except:
            self.dosend('GG')
        self.request.close()

class ThreadedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass

if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 10000
    server = ThreadedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    server.serve_forever()

分析：

代码流程很长，NC上去之后也看不太懂，还是启动一下源审：

first:

在进入主要流程之前，先来梳理一下可以用的功能，和怎么利用这两点。

主要有两个元件：RSA和LCG(线性同余随机数生成器)

LCG部分：

该LCG在每次输出随机数之后，都会对自身的末位再生成一个新的状态位，公式如下：

主要的参数有四个：a,b,s,p \s_6=\sum_{i=0}^{n=5}{a_{i}*s_{i}}+b\ \ (modp)

一个很简单的道理就是：如果能拿到生成器的参数，那么这个预测就很简单了。

RSA：

限制了模数的因子q,p的位数为512位，公钥e大概为344位，大部分和常规的RSA加密系统一样，有一个特别的函数noise_enc()，重点解析一下这个函数的流程：

  • 调用函数之后，先用LCG的输出，更新一遍自身的公钥e。
  • 用更新后的e再与LCG的下一位输出异或，参与RSA加密。
  • 数学表达如下：

f(m)=(m)^{e\bigoplus L_{i}\bigoplus L_{i+1}}\equiv c\ \ (modN)

值得注意的是，第一次刷新会更新自身的状态位，第二次刷新才用于加密。

回到主流程：

第一阶段：

  • 首先Bob的模数由我们提供，Alice的公钥由服务器提供。
  • 服务器再提供LCG的所有参数。
  • 接下来我们可以输入任意明文，获取到如下输出：

接下来为了方便，\我采用f’{B}(m)表示Bob的扰动加密，f’{A}(m)表示Alice的扰动加密\ ct \equiv f’{B}(f’{A}(pt))

  • 最后提供：

secret_ct=f’{B}(f{A}(secret))

第二阶段：

  • Bob的原公钥刷新一次。
  • LCG状态刷新一次
  • 服务器提供LCG的所有参数。
  • 接下来我们可以输入任意密文，获取到如下输出：

f’{B}(f{A}^{-1}(ct))=output

就这些，就完了。代码挺长看着蛮哈人的，审完流程之后，仔细想想就知道问题出在哪里了：

我们先来整理一下，自身有什么信息：

  • 两趟LCG的状态，意味着可以任意预测随机数的生成。
  • Bob模数的因子，意味着在拥有公钥的情况下可以任意解密。
  • Alice的公钥，意味着我们可以任意伪造密文。

一个很质朴的想法就是，把第一阶段的密文丢到第二阶段去给服务器解密就完了。这道题就是那么简单，那么我们就得把Bob这部分的影响消去，只要求出Bob的公钥就完了。

How to do?——DLP，构造p-1光滑数，在CRT回去就完了。

其他部分的参数稍微预测一下改回去就行，那么攻击流程如下：

第一阶段：在任意明文输入的时候，把Bob的公钥算出来，求出secret_ct。

第二阶段：在任意密文输入的时候，把Bob的公钥再算一次，求出secret就完了

那么最终Solution如下:

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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
from pwn import *
import itertools
import hashlib 
import string
from Crypto.Util.number import *
context(log_level = 'debug')
from gmpy2 import invert
P_BITS = 512
E_BITS = int(P_BITS * 2 * 0.292) + 30

def proof(io):
     io.recvuntil(b"XXXX + ")
     suffix = io.recv(16).decode("utf8")
     io.recvuntil(b"== ")
     cipher = io.recvline().strip().decode("utf8")
     for i in itertools.product(string.ascii_letters+string.digits, repeat=4):
         x = f"{i[0]}{i[1]}{i[2]}{i[3]}"
         proof=hashlib.sha256((x+suffix).encode()).hexdigest()
         if proof == cipher: break
     print(x)
     io.sendlineafter(b"XXXX:",x.encode())

class LCG:
    def __init__(self,a=None,b=None,s=None,p=None):
        self.a = a
        self.b = b
        self.s = s
        self.p = p
        if self.a == None or self.b == None or self.p ==None:self.init()
        self.count = 0
    def next(self):
        self.count += 1
        out = self.s[0]
        self.s = self.s[1: ] + [(sum([i * j for (i, j) in zip(self.a, self.s)]) + self.b) % self.p]
        return out

    def init(self):
        while True:
            p = getPrime(2 * P_BITS)
            if p.bit_length() == 2 * P_BITS:
                self.p = p
                break
        self.b = getRandomRange(1, self.p)
        self.a = [getRandomRange(1, self.p) for _ in range(6)]
        self.s = [getRandomRange(1, self.p) for _ in range(6)]

def attack():
    io = remote('chall.ctf.0ops.sjtu.cn',int(32226))
    #io = remote('115.159.221.202',int(10004))
    #io = process(['python3','task.py'])
    proof(io)
    #print(io.recvline())
    Bob_q = 13376855652894019412358024612099844415413836050979835768784889437961140034682908016344033711102957594157827340675230392915983921929015951210569440046731259
    Bob_p = 12459679084081170608028294687886983079242987755931480502386371754786544026455886080639726278817241233708653169055414948669151783119861900601774233568181639

    io.recvuntil(b'key plz.\n')
    q = (long_to_bytes(Bob_q).hex()).encode()
    p = (long_to_bytes(Bob_p).hex()).encode()
    q_primes = [98377, 52379, 68539, 49993, 57467, 62581, 9547, 2153, 24481, 69991, 3083, 34673, 60217, 74201, 63761, 16139, 1777, 24799, 14683, 22877, 47609, 2473, 95219, 46273, 98047, 19319, 23857, 11941, 3391, 30893, 15901, 28837, 65899, 25667, 13499]
    p_primes = [100559, 26479, 10529, 66343, 6703, 34759, 97001, 36637, 13537, 17341, 9587, 101921, 2137, 102913, 22171, 43793, 38791, 102593, 38197, 10909, 36269, 73091, 29027, 46489, 23993, 32359, 39383, 10859, 54559, 91529, 91459, 86111, 40939, 27583]

    io.sendline(q)
    io.sendline(p)

    alice_e_ = eval(io.recvline().decode())
    alice_n = eval(io.recvline().decode())

    p = eval(io.recvline().decode())
    a = eval(io.recvline().decode())
    b = eval(io.recvline().decode())
    s = eval(io.recvline().decode())
    lcg = LCG(a,b,s,p)

    ct_ =[]

    io.recvuntil(b'pt: \n')
    io.sendline(str(3).encode())
    io.recvuntil(b'ct: ')
    ct_.append(eval(io.recvline()[:-1]))

    io.recvuntil(b'pt: \n')
    io.sendline(str(0).encode())

    io.recvuntil(b'secrets_ct: ')
    secrets_ct = eval(io.recvline()) #换成数字形式
    
    alice_e = (alice_e_^^lcg.next()) % (2**E_BITS)
    alice_e = lcg.next()^^alice_e

    alice_first_enc = pow(3,alice_e,alice_n)
    bob_first_output = ct_[0]

    print(f'alice_e = {alice_e}')

    #要么对，要么没有

    #得到bob_e
    n = Bob_p*Bob_q
    dlog  = []
    dlog_ = []
    p_ = (discrete_log(mod(bob_first_output,Bob_p),mod(alice_first_enc,Bob_p)))
    q_ = (discrete_log(mod(bob_first_output,Bob_q),mod(alice_first_enc,Bob_q)))
    bob_e = crt([q_,p_],[Bob_q-1,Bob_p-1])
    print(f'bob_e={bob_e}')


    #直接求出原bob_e
    t1 = lcg.next()
    t2 = lcg.next()

    bob_e1_ = t2^^bob_e
    bob_e2 = (bob_e1_^^lcg.next()) % (2**E_BITS)
    bob_e2 = lcg.next()^^bob_e2

    print(f'bob_e2={bob_e2}')


    #解密：
    Bob_N = Bob_q*Bob_p
    phi = (Bob_q-1)*(Bob_p-1)
    d = invert(bob_e2,phi)
    m_ = pow(secrets_ct,d,Bob_N)
    print(f'secrets_ct: {m_}')

    p = eval(io.recvline().decode())
    a = eval(io.recvline().decode())
    b = eval(io.recvline().decode())
    s = eval(io.recvline().decode())
    lcg = LCG(a,b,s,p)


    pt_new = pow(2,alice_e_,alice_n)

    pt_ = []
    io.recvuntil(b'ct: \n')
    io.sendline((long_to_bytes(pt_new).hex()).encode())
    io.recvuntil(b'pt: ')
    pt_.append(eval(io.recvline()[:-1]))


    p_ = (discrete_log(mod(pt_[0],Bob_p),mod(2,Bob_p)))
    q_ = (discrete_log(mod(pt_[0],Bob_q),mod(2,Bob_q)))
    bob_e = crt([q_,p_],[Bob_q-1,Bob_p-1])

    io.recvuntil(b'ct: \n')
    io.sendline((long_to_bytes(m_).hex()).encode())
    io.recvuntil(b'pt: ')
    enc = (eval(io.recvline()[:-1]))
    #print(f'enc={enc}')

    #从这里再得到一次Bob_e
    print(f'bob_e={bob_e}')
    t1 = lcg.next()
    t2 = lcg.next()

    bob_e1_ = t2^^bob_e
    bob_e2 = (bob_e1_^^lcg.next()) % (2**E_BITS)
    bob_e2 = lcg.next()^^bob_e2


    d = invert(bob_e2,phi)
    m = pow(enc,d,Bob_N)

    flag = (long_to_bytes(m).hex()).encode()


    io.recvuntil(b'ct: \n')
    io.sendline(str(0).encode())
    io.sendline(flag)
    print(f'flag={m}')
    print(f'Bob_e = {bob_e2}')
    io.interactive()
    '''
    res = []
    res.append(io.recvline())
    res.append(io.recvline())
    return res
    '''

attack()
'''
Wow, how do you know that?
Here is the flag: flag{All_Crypto_challenges_in_0CTF/TCTF2023_are_solvable_on_laptop_good_luck_and_have_fun}
'''

debug最痛苦的一集。不确定求得参数对不对的话，在自己服务器上面再开一个环境输出调试就行。

*RSA 1:

题目：

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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
#!/usr/bin/env python3

import random
import signal
import socketserver
import string
from Crypto.Util.number import *
from hashlib import sha256
from secret import FLAG
from os import urandom

P_BITS = 512
E_BITS = int(P_BITS * 2 * 0.292) + 30
CNT_MAX = 70

class LCG:
    def __init__(self):
        self.init()

    def next(self):
        out = self.s[0]
        self.s = self.s[1: ] + [(sum([i * j for (i, j) in zip(self.a, self.s)]) + self.b) % self.p]
        return out

    def init(self):
        while True:
            p = getPrime(P_BITS)
            if p.bit_length() == P_BITS:
                self.p = p
                break
        self.b = getRandomRange(1, self.p)
        self.a = [getRandomRange(1, self.p) for _ in range(6)]
        self.s = [getRandomRange(1, self.p) for _ in range(6)]

class RSA:
    def __init__(self, l, p = 0, q = 0):
        self.l = l
        if not p:
            while True:
                p = getPrime(P_BITS)
                if p.bit_length() == P_BITS:
                    self.p = p
                    break
            while True:
                p = getPrime(P_BITS)
                if p.bit_length() == P_BITS:
                    self.q = p
                    break
        else:
            self.p = abs(p)
            self.q = abs(q)
        self.e = getPrime(E_BITS)
        self.check()

    def enc(self, m):
        return pow(m, self.e, self.n)

    def noisy_enc(self, m, r = 1):
        if r:
            self.refresh()
        return pow(m, self.e ^ self.l.next(), self.n)

    def dec(self, c):
        return pow(c, self.d, self.n)
        
    def check(self):
        assert self.p.bit_length() == P_BITS
        assert self.q.bit_length() == P_BITS
        self.n = self.p * self.q
        self.phi = (self.p - 1) * (self.q - 1)
        assert self.e.bit_length() >= E_BITS
        assert self.e < self.phi
        assert GCD(self.e, self.phi) == 1
        self.d = inverse(self.e, self.phi)
        assert self.d.bit_length() >= E_BITS
        for _ in range(20):
            x = self.l.next() % self.n
            assert self.dec(self.enc(x)) == x

    def refresh(self):
        self.e = (self.e ^ self.l.next()) % (2**E_BITS)

class Task(socketserver.BaseRequestHandler):
    def __init__(self, *args, **kargs):
        super().__init__(*args, **kargs)

    def proof_of_work(self):
        random.seed(urandom(16))
        proof = ''.join([random.choice(string.ascii_letters + string.digits) for _ in range(20)])
        digest = sha256(proof.encode()).hexdigest()
        self.dosend('sha256(XXXX + {}) == {}'.format(proof[4: ], digest))
        self.dosend('Give me XXXX:')
        x = self.request.recv(10)
        x = x.strip().decode('latin-1')
        if len(x) != 4 or sha256((x + proof[4: ]).encode()).hexdigest() != digest:
            return False
        return True

    def dosend(self, msg):
        try:
            self.request.sendall(msg.encode('latin-1') + b'\n')
        except:
            pass
    
    def timeout_handler(self, signum, frame):
        raise TimeoutError

    def recvn(self, sz):
        r = sz
        res = b''
        while r > 0:
            res += self.request.recv(r)
            if res.endswith(b'\n'):
                r = 0
            else:
                r = sz - len(res)
        res = res.strip()
        return res

    def recv_hex(self, l):
        return int(self.recvn(l + 1), 16)

    def handle(self):
        try:
            signal.signal(signal.SIGALRM, self.timeout_handler)
            signal.alarm(60)
            if not self.proof_of_work():
                self.dosend('You must pass the PoW!')
                return

            signal.alarm(20)
            self.dosend('Give me your RSA key plz.')
            pq = [self.recv_hex(P_BITS // 4) for _ in range(2)]
            lcg = LCG()
            alice = RSA(lcg)
            bob = RSA(lcg, *pq)
            secrets = getRandomNBitInteger(P_BITS // 8)
            secrets_ct = alice.enc(secrets)
            self.dosend('{}\n{}\n{}'.format(lcg.p, lcg.a, lcg.b))
            
            CNT = 0
            while CNT < CNT_MAX:
                self.dosend('pt: ')
                pt = self.recv_hex(P_BITS // 2)
                if pt == 0:
                    break
                ct = alice.noisy_enc(pt)
                ct = bob.noisy_enc(ct)
                self.dosend('ct: ' + hex(ct))
                CNT += 1

            secrets_ct = bob.noisy_enc(secrets_ct)
            self.dosend('secrets_ct: ' + hex(secrets_ct))
            lcg.init()
            bob = RSA(lcg, *pq)

            seen = set()
            while CNT < CNT_MAX:
                self.dosend('ct: ')
                ct = self.recv_hex(P_BITS // 2)
                if ct == 0:
                    break
                pt = alice.dec(ct)
                if pt in seen:
                    self.dosend('You can only decrypt each ciphertext once.')
                    self.request.close()
                else:
                    seen.add(pt)
                pt = bob.noisy_enc(pt)
                self.dosend('pt: ' + hex(pt))
                CNT += 1            
            
            guess = self.recv_hex(P_BITS // 4)
            if guess == secrets:
                self.dosend('Wow, how do you know that?')
                self.dosend('Here is the flag: ' + FLAG)
            else:
                self.dosend('Wrong!')
        except TimeoutError:
            self.dosend('Timeout!')
        except:
            self.dosend('GG')
        self.request.close()

class ThreadedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass

if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 32225
    server = ThreadedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    server.serve_forever()

分析:

  • 大致流程与RSA 0一样，不再赘述。
  • 我们在第一阶段缺少LCG的完整状态，alice的公钥。
  • 二阶段的LCG状态也位置。

赛事期间没做出来，真的哈哈哈了，实际上想得到输入明文的构造这题就不算太难。

因为前面分析过了怎么去操作得到secret，这里流程也一样，照着上面的思路走就行，问题在于怎么泄露LCG的状态，怎么拿到alice,bob的公钥，针对这个问题：

在输入明文阶段，我们选择输入: -1,\ 使得：f’{B}(f’{A}(-1))=ct\ 展开：f’{B}((-1){e’_{A}}mod(N_{A}))\=f’_{B}(N_{A}-1)\=(N_{A}-1){e’{B}}modN_{B}

emmmm还是有点不太理解，暂时放弃，贴一下大哥的wp：

img

Blocky 4.5_lite:

题目：

task:

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
#!/usr/bin/env python3

import random
import signal
import socketserver
import string
from Cipher import BlockCipher
from hashlib import sha256
from os import urandom
from secret import FLAG

MENU = """
[1] Encrypt
[2] Decrypt
[3] Guess"""

def get_key():
    key = b''
    while len(key) < 9:
        b = urandom(1)
        if b[0] < 243:
            key += b
    return key

class Task(socketserver.BaseRequestHandler):
    def __init__(self, *args, **kargs):
        super().__init__(*args, **kargs)

    def proof_of_work(self):
        random.seed(urandom(16))
        proof = ''.join([random.choice(string.ascii_letters + string.digits) for _ in range(20)])
        digest = sha256(proof.encode()).hexdigest()
        self.dosend('sha256(XXXX + {}) == {}'.format(proof[4: ], digest))
        self.dosend('Give me XXXX:')
        x = self.request.recv(10)
        x = x.strip().decode('latin-1')
        if len(x) != 4 or sha256((x + proof[4: ]).encode()).hexdigest() != digest:
            return False
        return True

    def dosend(self, msg):
        try:
            self.request.sendall(msg.encode('latin-1') + b'\n')
        except:
            pass

    def timeout_handler(self, signum, frame):
        raise TimeoutError

    def recvn(self, sz):
        r = sz
        res = b''
        while r > 0:
            res += self.request.recv(r)
            if res.endswith(b'\n'):
                r = 0
            else:
                r = sz - len(res)
        res = res.strip()
        return res

    def handle(self):
        try:
            signal.signal(signal.SIGALRM, self.timeout_handler)
            signal.alarm(60)
            if not self.proof_of_work():
                self.dosend('You must pass the PoW!')
                return

            signal.alarm(int(337.1))
            key = get_key()
            cipher = BlockCipher(key, 5)

            self.dosend(MENU)
            for _ in range(int(133.7)):
                op = int(self.recvn(2))
                if op == 1:
                    self.dosend('pt: ')
                    pt = bytes.fromhex(self.recvn(19).decode())
                    assert all(bb < 243 for bb in pt)
                    ct = cipher.encrypt(pt)
                    self.dosend('ct: ' + ct.hex())
                elif op == 2:
                    self.dosend('ct: ')
                    ct = bytes.fromhex(self.recvn(19).decode())
                    assert all(bb < 243 for bb in ct)
                    pt = cipher.decrypt(ct)
                    self.dosend('pt: ' + pt.hex())
                elif op == 3:
                    guess = bytes.fromhex(self.recvn(19).decode())
                    if guess == key:
                        self.dosend('Wow, how do you know that?')
                        self.dosend('Here is the flag: ' + FLAG)
                    else:
                        self.dosend('Wrong!')
                    break
                else:
                    break
        except TimeoutError:
            self.dosend('Timeout!')
        except:
            self.dosend('GG')
        self.request.close()

class ThreadedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass

if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 31338
    server = ThreadedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    server.serve_forever()

GF:

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
class GF:
    def __init__(self, value):
        if type(value) == int:
            self.value = [(value // (3 ** i)) % 3 for i in range(5)]
            print(self.value)
        elif type(value) == list and len(value) == 5:
            self.value = value
        else:
            assert False, "Wrong input to the constructor"

    def __str__(self):
        return f"GF({self.to_int()})"

    def __repr__(self):
        return str(self)

    def __hash__(self):
        return hash(tuple(self.value))

    def __eq__(self, other):
        assert type(other) == GF
        return self.value == other.value
    
    def __add__(self, other):
        assert type(other) == GF
        return GF([(x + y) % 3 for x, y in zip(self.value, other.value)])
    
    def __sub__(self, other):
        assert type(other) == GF
        return GF([(x - y) % 3 for x, y in zip(self.value, other.value)])
    
    def __mul__(self, other):
        assert type(other) == GF

        arr = [0 for _ in range(9)]
        for i in range(5):
            for j in range(5):
                arr[i + j] = (arr[i + j] + self.value[i] * other.value[j]) % 3
        
        # Modulus: x^5 + 2*x + 1
        for i in range(8, 4, -1):
            arr[i - 4] = (arr[i - 4] - 2 * arr[i]) % 3
            arr[i - 5] = (arr[i - 5] - arr[i]) % 3
        
        return GF(arr[:5])
    
    def __pow__(self, other):
        assert type(other) == int
        base, ret = self, GF(1)
        while other > 0:
            if other & 1:
                ret = ret * base
            other >>= 1
            base = base * base
        return ret

    def inverse(self):
        return self ** 241

    def __div__(self, other):
        assert type(other) == GF
        return self * other.inverse()
    
    def to_int(self):
        return sum([self.value[i] * (3 ** i) for i in range(5)])

if __name__ == "__main__":
    print(GF(2)*GF(2))
    '''
    assert GF(3) * GF(3) == GF(9)
    assert GF(9) * GF(27) == GF(5)
    assert GF(5).inverse() == GF(240)
    '''

cipher:

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
from GF import GF

SBOX, INV_SBOX = dict(), dict()
for i in range(3 ** 5):
    v = GF(23) + (GF(0) if i == 0 else GF(i).inverse())
    SBOX[GF(i)] = v
    INV_SBOX[v] = GF(i)

class BlockCipher:
    def __init__(self, key: bytes, rnd: int):
        assert len(key) == 9
        sks = [GF(b) for b in key]
        for i in range(rnd * 9):
            sks.append(sks[-1] + SBOX[sks[-9]])
        self.subkeys = [sks[i:i+9] for i in range(0, (rnd + 1) * 9, 9)]
        self.rnd = rnd

    def _add_key(self, l1, l2):
        return [x + y for x, y in zip(l1, l2)]

    def _sub_key(self, l1, l2):
        return [x - y for x, y in zip(l1, l2)]
    
    def _sub(self, l):
        return [SBOX[x] for x in l]

    def _sub_inv(self, l):
        return [INV_SBOX[x] for x in l]
    
    def _shift(self, b):
        return [
            b[0], b[1], b[2],
            b[4], b[5], b[3],
            b[8], b[6], b[7]
        ]
    
    def _shift_inv(self, b):
        return [
            b[0], b[1], b[2],
            b[5], b[3], b[4],
            b[7], b[8], b[6]
        ]
    
    def _mix(self, b):
        b = b[:] # Copy
        for i in range(3):
            x = GF(7) * b[i] + GF(2) * b[3 + i] + b[6 + i]
            y = GF(2) * b[i] + b[3 + i] + GF(7) * b[6 + i]
            z = b[i] + GF(7) * b[3 + i] + GF(2) * b[6 + i]
            b[i], b[3 + i], b[6 + i] = x, y, z
        return b
    
    def _mix_inv(self, b):
        b = b[:] # Copy
        for i in range(3):
            x = GF(86) * b[i] + GF(222) * b[3 + i] + GF(148) * b[6 + i]
            y = GF(222) * b[i] + GF(148) * b[3 + i] + GF(86) * b[6 + i]
            z = GF(148) * b[i] + GF(86) * b[3 + i] + GF(222) * b[6 + i]
            b[i], b[3 + i], b[6 + i] = x, y, z
        return b
    
    def encrypt(self, inp: bytes):
        assert len(inp) == 9
        b = [GF(x) for x in inp]
        
        b = self._add_key(b, self.subkeys[0])
        for i in range(self.rnd):
            b = self._sub(b)
            b = self._shift(b)
            if i < self.rnd - 2:
                b = self._mix(b)
            b = self._add_key(b, self.subkeys[i + 1])
        
        return bytes([x.to_int() for x in b])
    
    def decrypt(self, inp: bytes):
        assert len(inp) == 9
        b = [GF(x) for x in inp]

        for i in reversed(range(self.rnd)):
            b = self._sub_key(b, self.subkeys[i + 1])
            if i < self.rnd - 2:
                b = self._mix_inv(b)
            b = self._shift_inv(b)
            b = self._sub_inv(b)
        b = self._sub_key(b, self.subkeys[0])
        
        return bytes([x.to_int() for x in b])

if __name__ == "__main__":
    import random
    key = bytes(random.randint(0, 242) for i in range(9))
    cipher = BlockCipher(key, 5)
    for _ in range(100):
        pt = bytes(random.randint(0, 242) for i in range(9))
        ct = cipher.encrypt(pt)
        pt_ = cipher.decrypt(ct)
        assert pt == pt_

分析：

块长度为9，有限域为GF(3^5)下的AES加密，只有五轮。可能是square attack，但是值得注意的一点是：(如果不会square attack，建议看看春哥的文章)

  • square attack要构造一个A集，使得前一个状态的和值为0。
  • 构造一个A集需要3^5次交互，这里确实是不满足的。

借用队里师傅的分析：

12643db7-ac9c-4876-b966-15d39ac06981.png

主要思路就是square attack，task.py给出的选择明文/密文均可。该题的特殊点在于：

  1. 最后两轮均没有列混淆
  2. 给出的数据量D远小于常规square attack所需的单块遍历量（本例为3^5=243）

第二点限制本题不能用常规的A，B，C去刻画，于是我们采用了如下的定义方法：

A = {i|i\in|D’|,\forall i,j,i\neq j }\ B = Unkown\ C = {i|i = c}

其中|D’|为我们所能获得的最大明文量。此时，我们所关注的中间量从全B状态变成了现在的全A状态。图中红色部分为全A所能保持到的最远位置。

同时，由于选择明文时，最后的两轮均无法保证A集的构造，因此我们需要枚举最后两轮的相关密钥；而选择密文时，前两轮并不会对结构体造成影响，因此我们采用选择密文攻击。

由于对我们关注的A矩阵中某一字节来说，其状态只与三个初始轮密钥字节有关，因此我们每次只遍历三个字节即可。时间复杂度O(D’)=(243^3)*3。简单地说就是构造后面的B集，使得没有重复的情况存在。

总结一下流程：

我们需要获得某一轮的子秘钥，而在对称分析当中，理所应当的去构造差分集对吧，

现在情况就到了怎么找这个差分特征上面，根据春哥的文章可以知道，常规的square attack是需要满足密文前面某轮所有集合的差分和为0，但这题不能这样构造，退而求次，我们要构造另外的delta集使得没有重复的特征存在。

那么最终的爆破solution如下：

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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
from pwn import *
import itertools
import hashlib 
import string
from GF import GF
context.log_level = 'debug'
io = remote('chall.ctf.0ops.sjtu.cn',31338)

def proof(io):
     io.recvuntil(b"XXXX + ")
     suffix = io.recv(16).decode("utf8")
     io.recvuntil(b"== ")
     cipher = io.recvline().strip().decode("utf8")
     for i in itertools.product(string.ascii_letters+string.digits, repeat=4):
         x = f"{i[0]}{i[1]}{i[2]}{i[3]}"
         proof=hashlib.sha256((x+suffix).encode()).hexdigest()
         if proof == cipher: break
     print(x)
     io.sendlineafter(b"XXXX:",x.encode())

proof(io)
io.recvuntil(b'[3] Guess\n')
io.sendline(b'1')
io.recvline()
io.sendline(b'00'*9)
tmp = io.recvline()[6:-1]
print(tmp)
p_raw = []
f = open("b.txt",'w+')
for i in range(0x00,110):
    te = hex(i)[2:].zfill(2) + tmp.decode()
    io.sendline(b'2')
    io.recvline()
    io.sendline(te.encode())
    x = io.recvline()[4:]
    p_raw.append(x)
    f.write(x.decode())
print(p_raw)
f.close()

import subprocess
proc = subprocess.Popen("solve", stdout=subprocess.PIPE)
output = proc.communicate()[0]
io.sendline(b'3')
io.sendline(output)
io.recvline()
print(io.recvline())
#include<cstdio>
#include"GF.h"
#include<algorithm>
#include<mingw.thread.h>
using namespace std;

GF_243 p[200][9];
char p0[20];

int hex_to_int(char x){
    if(x <= '9') return x - '0';
    else return x - 'a' + 10;
}

int inv_Sbox[243] = {115,142,80,57,60,217,104,200,70,154,178,50,30,33,110,194,221,40,120,150,83,1,2,0,210,240,163,
140,136,149,29,117,183,21,143,114,229,202,207,88,172,106,103,24,198,218,62,20,98,37,235,58,216,19,
12,179,153,101,167,176,161,134,144,193,15,219,234,55,96,191,196,214,108,35,11,74,184,119,31,109,10,
118,28,72,186,111,169,170,113,182,45,165,100,105,64,89,49,13,155,46,99,175,212,6,241,188,180,112,
204,233,127,97,54,38,211,162,7,201,68,208,123,157,129,238,205,126,16,192,39,59,18,61,84,95,92,
164,242,8,203,228,66,190,42,197,209,67,230,25,102,69,128,232,239,17,41,220,44,215,195,213,43,189,
26,71,199,47,174,166,87,63,173,223,85,91,222,93,86,56,236,36,90,94,224,3,151,122,171,65,107,
131,226,124,177,14,48,53,145,133,75,137,139,132,160,51,121,82,4,77,147,135,148,76,138,79,22,116,
158,125,225,206,237,231,52,159,146,81,152,5,27,185,73,130,156,227,187,168,181,9,34,32,141,23,78};

int table_0[9] = {0, 1, 2, 4, 5, 3, 8, 6, 7};
int table_1[9] = {0, 1, 2, 5, 3, 4, 7, 8, 6};

void hex_init(int i){
    // printf("%s\n",p0);
    for(int j = 0; j < 9; j ++){
        p[i][j] = GF_init((hex_to_int(p0[table_0[j]*2]) << 4) + hex_to_int(p0[table_0[j]*2+1]));
        // printf("%02x",(hex_to_int(p0[table[j]*2]) << 4) + hex_to_int(p0[table[j]*2+1]));
    }
    // printf("\n");
    return ;
}

GF_243 mix_inv(GF_243* tmp){
    return GF_add(GF_add(GF_mul(GF_init(7), tmp[0]), GF_mul(GF_init(2), tmp[1])), tmp[2]);
}

bool comp(GF_243 a, GF_243 b){
    for(int i = 0; i < 5; i++){
        if(a.value[i] < b.value[i]) return 0;
        if(a.value[i] > b.value[i]) return 1;
    }
    return 0;
}

int data_len = 90;

int k[9];

void solve(int b,int k30){
    GF_243 tmp[3];
    GF_243 l[200];
    int n = 243;
    bool flag;
    for(int k0 = k30*9; k0 < k30*9+9; k0++){
        // printf("%d\n",k0-k30*9);
        for(int k1 = 0; k1 < n; k1 ++){
            for(int k2 = 0; k2 < n; k2 ++){
                for(int i = 0; i < data_len; i++){
                    tmp[0] = GF_init(inv_Sbox[GF_int(GF_sub(p[i][b  ], GF_init(k0)))]);
                    tmp[1] = GF_init(inv_Sbox[GF_int(GF_sub(p[i][b+3], GF_init(k1)))]);
                    tmp[2] = GF_init(inv_Sbox[GF_int(GF_sub(p[i][b+6], GF_init(k2)))]);
                    l[i] = mix_inv(tmp);
                }
                sort(l, l+data_len, comp);
                flag = 1;
                for(int i = 0; i < data_len-1; i++){
                    if(GF_int(l[i]) == GF_int(l[i+1])) flag = 0;
                    // printf("%d ",GF_int(l[i]));
                }
                // printf("\n");
                if(flag){
                    // printf("%d %d %d\n",k0,k1,k2);
                    // printf("%d\n",k2);
                    // return ;
                    k[b  ] = k0;
                    k[b+3] = k1;
                    k[b+6] = k2;           
                }
            }
        }
    }
    // printf("%d is END.\n",k30);
    return ;
}

int table_3[243] = {16, 15, 17, 13, 12, 14, 10, 9, 11, 7, 6, 8, 4, 3, 5, 1, 0, 2, 25, 24, 26, 22, 21, 23, 19, 18, 20, 70, 69, 71, 67, 66, 68, 64, 63, 65, 61, 60, 62, 58, 57, 59, 55, 54, 56, 79, 78, 80, 76, 75, 77, 73, 72, 74, 43, 42, 44, 40, 39, 41, 37, 36, 38, 34, 33, 35, 31, 30, 32, 28, 27, 29, 52, 51, 53, 49, 48, 50, 46, 45, 47, 178, 177, 179, 175, 174, 176, 172, 171, 173, 169, 168, 170, 166, 165, 167, 163, 162, 164, 187, 186, 188, 184, 183, 185, 181, 180, 182, 232, 231, 233, 229, 228, 230, 226, 225, 227, 223, 222, 224, 220, 219, 221, 217, 216, 218, 241, 240, 242, 238, 237, 239, 235, 234, 236, 205, 204, 206, 202, 201, 203, 199, 198, 200, 196, 195, 197, 193, 192, 194, 190, 189, 191, 214, 213, 215, 211, 210, 212, 208, 207, 209, 97, 96, 98, 94, 93, 95, 91, 90, 92, 88, 87, 89, 85, 84, 86, 82, 81, 83, 106, 105, 107, 103, 102, 104, 100, 99, 101, 151, 150, 152, 148, 147, 149, 145, 144, 146, 142, 141, 143, 139, 138, 140, 136, 135, 137, 160, 159, 161, 157, 156, 158, 154, 153, 155, 124, 123, 125, 121, 120, 122, 118, 117, 119, 115, 114, 116, 112, 111, 113, 109, 108, 110, 133, 132, 134, 130, 129, 131, 127, 126, 128};

int main(){
    freopen("b.txt","r",stdin);
    for(int i = 0; i < data_len; i++){
        scanf("%s",p0);
        hex_init(i);
    }

    thread thread_arr[27];
    for (int i = 0; i < 27; i++) {
        thread_arr[i] = thread(solve,0,i);
    }
    for (int i = 0; i < 27; i++) {
        thread_arr[i].join();
    }
    for (int i = 0; i < 27; i++) {
        thread_arr[i] = thread(solve,1,i);
    }
    for (int i = 0; i < 27; i++) {
        thread_arr[i].join();
    }
    for (int i = 0; i < 27; i++) {
        thread_arr[i] = thread(solve,2,i);
    }
    for (int i = 0; i < 27; i++) {
        thread_arr[i].join();
    }

    for(int i = 0; i < 9; i++){
        printf("%02x",table_3[k[table_1[i]]]);
    }
    return 0;
}
#include"GF.h"
#include<cstdio>
using namespace std;

struct GF_243 GF_init(int value){
    int mo = 1;
    struct GF_243 res;
    for(int i = 0; i < 5; i++){
        res.value[i] = (value/mo) % 3;
        mo *= 3;
    }
    return res;
}

struct GF_243 GF_add(GF_243 a, GF_243 b){
    struct GF_243 res;
    for(int i = 0; i < 5; i++){
        res.value[i] = (a.value[i] + b.value[i]) % 3;
    }
    return res;
}

struct GF_243 GF_sub(GF_243 a, GF_243 b){
    struct GF_243 res;
    for(int i = 0; i < 5; i++){
        res.value[i] = (a.value[i] + 3 - b.value[i]) % 3;
    }
    return res;
}

struct GF_243 GF_mul(GF_243 a, GF_243 b){
    struct GF_243 res;
    uint8_t arr[9] = {0,0,0,0,0,0,0,0,0};
    for(int i = 0; i < 5; i++){
        for(int j = 0 ; j < 5; j++){
            arr[i + j] = (arr[i + j] + a.value[i] * b.value[j]) % 3;
        }
    }
    for(int i = 8; i > 4; i--){
        arr[i - 4] = (arr[i - 4] + 9 - 2 * arr[i]) % 3;
        arr[i - 5] = (arr[i - 5] + 9 - arr[i]) % 3;
    }
    for(int i = 0; i < 5; i++){
        res.value[i] = arr[i];
        // printf("%d ",arr[i]);
    }
    // printf("\n");
    return res;
}

int GF_int(GF_243 a){
    int mo = 1;
    int res = 0;
    for(int i = 0; i < 5; i++){
        res += mo * a.value[i];
        mo *= 3;
    }
    return res;
}
#include<stdint.h>

struct GF_243{
    uint8_t value[5];
};

struct GF_243 GF_init(int value);

struct GF_243 GF_add(GF_243 a, GF_243 b);

struct GF_243 GF_sub(GF_243 a, GF_243 b);

struct GF_243 GF_mul(GF_243 a, GF_243 b);

int GF_int(GF_243 a);