天翼杯

发表于 分类于 阅读次数： Waline： 本文字数： 1.4k 阅读时长 ≈ 1 分钟

赛后问了别的师傅复盘一下，好的东西需要记录

babypack

这一题真牛啊，考了很多考点，而且没有很偏的，很考验能力。nalrw👴想出来了

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
from random import getrandbits, randint
from Crypto.Util.number import getPrime
from functools import reduce
from secret import flag
import sys
import signal

signal.alarm(90)

N = 512
def egcd(a, b):
    if 0 == b:
        return 1, 0, a
    x, y, q = egcd(b, a % b)
    x, y = y, (x - a // b * y)
    return x, y, q

def chinese_remainder(pairs):
    mod_list, remainder_list = [p[0] for p in pairs], [p[1] for p in pairs]
    mod_product = reduce(lambda x, y: x * y, mod_list)
    mi_list = [mod_product//x for x in mod_list]
    mi_inverse = [egcd(mi_list[i], mod_list[i])[0] for i in range(len(mi_list))]
    x = 0
    for i in range(len(remainder_list)):
        x += mi_list[i] * mi_inverse[i] * remainder_list[i]
        x %= mod_product
    return x

def keygen():
    U = [getrandbits(N)for i in range(N)]
    V = []
    for i in range(N):
        v = U[i] - pow(2, N-i-1)
        V.append(v)

    s1 = sum(U)
    while True:
        p = getPrime(s1.bit_length() + 1)
        if p > s1:
            break
    s1 = 0
    s2 = 0
    for i in V:
        if i < 0:
            s2 += i
        else:
            s1 += i

    tmp = max(s1, -s2)
    while True:
        q = getPrime(tmp.bit_length() + 1)
        if q > tmp:
            break

    A = []
    for i, j in zip(U, V):
        A.append(chinese_remainder([(p, i), (q, j)]))
    return A, U, V, p, q

def check(m, n):#比较高位
    mbin = bin(m)[2:]
    nbin = bin(n)[2:]
    count = 0
    for i, j in zip(mbin, nbin):
        if i == j:
            count += 1
    return count

def encrypt(msg, pub):#背包加密
    s = 0
    for i, j in zip(msg, pub):
        s += i * j
    return s


A, U, V, p, q = keygen()


n = p * q
print("your pubkey:")
print(A)
print(U[0] + V[0])
print(U[0] * V[0])
Menu = '''
1.hint
2.get flag'''
for i in range(500):
    print(Menu)
    op = int(input(">").strip())
    if op == 1:
        m = int(input(">").strip())
        print(check(m, n))
    elif op == 2:
        msg = [randint(0, 1) for i in range(N)]
        ct = encrypt(msg, A)
        print("secret:")
        print(ct)
        secret = int(input(">").strip())
        ans = int("".join(list(map(str, msg))), 2)
        if ans == secret:
            print(flag)
        else:
            print("wrong")
            sys.exit(0)
    else:
        sys.exit(0)



分析代码

  • 首先使用getrandbits函数生成512个512比特的列表U，再生成列表V，有\[ V_i=U_i-2^{511-i}\]
  • 然后生成p,q，两个大概都是520位上下
  • 使用CRT生成A，满足

\[ A_i=U_i\;mod\;p\\ A_i=V_i\;mod\;q \]

  • 最后用randint(0, 1)生成01背包msg与A合成得到ct，最后我们要传入的结果就是仅含0和1的msg

这一题我们有的能拿到的数据有:\[A,U_0+V_0,U_0*V_0,ct\]

我们在这一题能与oracle进行一个交互，传入一个数x，oracle将比较x和n二进制的较高位，并返回位相等的个数。

思路

首先看到01背包很难不想到造格子，但是实际操作后发现512阶的矩阵连造都造不出来。并且，再仔细想，就算分解n拿到pq，接着拿到UV，对求解01的msg没有任何帮助，所以放弃造格子这一套。

观察到msg是用512次randint(0, 1)生成的，再加上前面生成U时用的是getrandbits，这两个函数的算法逻辑都是MT19937，这种伪随机数生成是可以破解的，只需要624个32比特的数。又由A和UV存在同余关系，如果拿到pq就能拿到UV，所以接下来要思考如何factor。

本题给出了\[A,U_0+V_0,U_0*V_0\]，我们很容易能够拿到单独的\[U_0、V_0\]

由UV和A的关系h我们可以知道： \[ p|A_0-U_0\\ q|A_0-v_0\\ ∴n=pq|(A_0-U_0)(A_0-v_0) \] 观察到，右边是已知条件，n待求，我们可以获取n的高多少多少位！

因此可以转换到Coppersmith Method已知p高位的情况！！

但是，由于我们最多只能和Oracle交互500次，由生成可知n大概为1040位，如果每次只爆一位，我们最多只能获得500位，这个条件是不足以使用coppersmith的。

这里就很考验智商了，我只能说nalrw yyds，我们可以采取一次爆破两位的方法，那么3次内就一定能爆破出两位，所以相当于0.75次爆破一位，那么前499次交互就能获取n的前499*3/2位，这足够用来求解了。这里需要知道n一共有多少位（因为要知道n缺失了多少低位），所以还是需要测试才知道n的位数范围，算是个小细节

之后使用gcd就能够分解出p和q，接下来就能求得U和V，然后使用调包randcrack破解MT19937。这里也有个小细节，由于randcrack只能预测连续的伪随机数，所以得取U最后624个32位数据，也比较麻烦。

代码可以参考春哥写的：春乎

总结

回顾一下整个流程：n高位——copper——gcd——randcrack，算是比较综合的一道题了，但是每一个单独的板块都是常规题（怎么有种做高考题的感觉，比较有意思

TryHash

加密部分myHash是Tea加密，逆向中经常出到的。队里的师傅也写过TEA，XTEA，XXTEA加密算法概要 | Tardis's blog (taardisaa.github.io)

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
import SocketServer
import signal,os,random,string
from hashlib import sha256

from secret import flag
from ctypes import c_uint32 as uint32
from struct import pack, unpack

class Task(SocketServer.BaseRequestHandler):
    def proof_of_work(self):
        random.seed(os.urandom(8))
        proof = ''.join([random.choice(string.ascii_letters+string.digits) for _ in xrange(20)])
        digest = sha256(proof).hexdigest()
        self.request.send("sha256(XXXX+%s) == %s\n" % (proof[4:],digest))
        self.request.send('Give me XXXX:')
        x = self.request.recv(10)
        x = x.strip()
        if len(x) != 4 or sha256(x+proof[4:]).hexdigest() != digest: 
            return False
        return True

    def dorecv(self,sz):
        try:
            return self.request.recv(sz).strip()
        except:
            return 0

    def dosend(self, msg):
        try:
            self.request.sendall(msg)
        except:
            pass

    def myhash(self,msg,identification):
        delta=0x9E3779B9
        v0, v1 = map(uint32, unpack('>2I', msg))
        k0, k1, k2, k3 = map(uint32, unpack('>4I', identification))
        sm, delta = uint32(0), uint32(delta)

        for i in range(32):
            sm.value += delta.value
            v0.value += ((v1.value << 4) + k0.value) ^ (v1.value + sm.value) ^ ((v1.value >> 5) + k1.value)
            v1.value += ((v0.value << 4) + k2.value) ^ (v0.value + sm.value) ^ ((v0.value >> 5) + k3.value)

        return pack('>2I', v0.value, v1.value)

    def handle(self):
        signal.alarm(200)
        if not self.proof_of_work():
            return
        nounce = os.urandom(8)
        self.dosend("Welcome to the Auth System.")
        self.dosend('If you are admin, I will give you the flag.\n')   
        adminpass = 'Iamthesuperadmin'
        adminhash = self.myhash(nounce,adminpass)
        for i in range(5):
            self.dosend('Choice:\n')
            choice = int(self.dorecv(8))
            if choice == 0:
                self.dosend('I can hash for you')
                user = self.dorecv(32)   
                if len(user)!=16:
                    self.request.close()
                    return
                if user == adminpass:
                    self.request.close()
                    return
                userhash = self.myhash(nounce,user)
                self.dosend(userhash+'\n')
            elif choice == 1:
                self.dosend('Are you admin?')
                userhash = self.dorecv(48)
                if userhash == adminhash:
                    self.dosend(flag+'\n')
                    self.request.close()
                    return
                else:
                    self.dosend('You are not admin!\n')
                    self.request.close()
                    return
            else:
                pass       
        
        self.request.close()


class ForkingServer(SocketServer.ForkingTCPServer, SocketServer.TCPServer):
    pass


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

我们可以先用我们给定的密钥加密，然后拿到密文，再通过密文解出nounce，然后再用已知密钥加密拿到userhash，就出了。

第一次见到Tea加密算法，加解密函数如下：

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
from ctypes import *

def encrypt(v, k):
    v0 = c_uint32(v[0])
    v1 = c_uint32(v[1])
    summ = c_uint32(0)
    delta = 0x9e3779b9

    k0, k1, k2, k3 = c_uint32(k[0]), c_uint32(k[1]), c_uint32(k[2]), c_uint32(k[3])
    
    print("%#x %#x" % (v0.value, v1.value))
    print("%#x %#x %#x %#x" % (k0.value, k1.value, k2.value, k3.value))

    w = [0,0]
    for i in range(32):
        summ.value += delta
        v0.value += ((v1.value << 4) + k0.value) ^ (v1.value + summ.value) ^ ((v1.value >> 5) + k1.value)
        v1.value += ((v0.value << 4) + k2.value) ^ (v0.value + summ.value) ^ ((v0.value >> 5) + k3.value)
    w[0], w[1] = v0, v1
    return w

def decrypt(v, k):
    v0 = c_uint32(v[0])
    v1 = c_uint32(v[1])
    summ = c_uint32(0xC6EF3720)
    delta = 0x9e3779b9

    k0, k1, k2, k3 = c_uint32(k[0]), c_uint32(k[1]), c_uint32(k[2]), c_uint32(k[3])
    
    print("%#x %#x" % (v0.value, v1.value))
    print("%#x %#x %#x %#x" % (k0.value, k1.value, k2.value, k3.value))

    w = [0,0]
    for i in range(32):
        v1.value -= ((v0.value << 4) + k2.value) ^ (v0.value + summ.value) ^ ((v0.value >> 5) + k3.value)
        v0.value -= ((v1.value << 4) + k0.value) ^ (v1.value + summ.value) ^ ((v1.value >> 5) + k1.value)
        summ.value -= delta
    w[0], w[1] = v0, v1
    return w

MyCipher

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
import SocketServer
import signal,os,random,string
from hashlib import sha256

from secret import flag
from struct import pack, unpack

class Task(SocketServer.BaseRequestHandler):
    def proof_of_work(self):
        random.seed(os.urandom(8))
        proof = ''.join([random.choice(string.ascii_letters+string.digits) for _ in xrange(20)])
        digest = sha256(proof).hexdigest()
        self.request.send("sha256(XXXX+%s) == %s\n" % (proof[4:],digest))
        self.request.send('Give me XXXX:')
        x = self.request.recv(10)
        x = x.strip()
        if len(x) != 4 or sha256(x+proof[4:]).hexdigest() != digest: 
            return False
        return True

    def dorecv(self,sz):
        try:
            return self.request.recv(sz).strip()
        except:
            return 0

    def dosend(self, msg):
        try:
            self.request.sendall(msg)
        except:
            pass

    def g(self,v1,v2,x):
        value = (v1+v2+x)%256
        value = ((value<<3) | (value>>5)) &0xff
        return value

    def f(self,value):
        v1,v2 = unpack('>2B',pack('>H',value))
        v2 = self.g(v1,v2,1)
        v1 = self.g(v1,v2,0)
        value = unpack('>H',pack('>2B',v1,v2))
        return value[0]

    def encrypt_ecb(self,msg,key):
        l = len(msg)
        if l%4 !=0:
            msg = msg+'\x00'*(4-(l%4))
        cipher = ''
        for i in range(0,len(msg),4):
            cipher += self.encrypt(msg[i:i+4],key)
        return cipher


    def encrypt(self,msg,key):
        subkeys = unpack('>4H',key)
        left,right = unpack('>2H',msg)
        right = right^subkeys[3]
        for i in range(3):
            tmp = left^self.f(subkeys[i]^right) 
            left = right
            right = tmp
        left = right^left
        return pack('>2H', left, right)

    def handle(self):
        signal.alarm(200)
        if not self.proof_of_work():
            return
        key = os.urandom(8)
        self.dosend('Encrypted flag is:')
        self.dosend(self.encrypt_ecb(flag,key)+'\n')
        self.dosend('Here is your chance:')
        data = self.dorecv(160)
        self.dosend(self.encrypt_ecb(data,key))

        self.request.close()


class ForkingServer(SocketServer.ForkingTCPServer, SocketServer.TCPServer):
    pass


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