20211107-陇原战“疫”-CryptoSecWriteUp

Posted on Edited on In , Views: Symbols count in article: 6.9k Reading time ≈ 6 mins.

 

Crypto

mostlycommon

共模再开个方

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import gmpy2
from Crypto.Util.number import *

e1 = 65536 // 2
e2 = 270270 // 2

n = 122031686138696619599914690767764286094562842112088225311503826014006886039069083192974599712685027825111684852235230039182216245029714786480541087105081895339251403738703369399551593882931896392500832061070414483233029067117410952499655482160104027730462740497347212752269589526267504100262707367020244613503
c1 = 39449016403735405892343507200740098477581039605979603484774347714381635211925585924812727991400278031892391996192354880233130336052873275920425836986816735715003772614138146640312241166362203750473990403841789871473337067450727600486330723461100602952736232306602481565348834811292749547240619400084712149673
c2 = 43941404835820273964142098782061043522125350280729366116311943171108689108114444447295511969090107129530187119024651382804933594308335681000311125969011096172605146903018110328309963467134604392943061014968838406604211996322468276744714063735786505249416708394394169324315945145477883438003569372460172268277

get_tuple = gmpy2.gcdext(e1, e2)        # return (g,s,t)   g = gcd(e1,e2) and g = e1*s + e2*t

r = -get_tuple[1]
s = get_tuple[2]

a = gmpy2.powmod(gmpy2.invert(c1, n), r, n)
b = gmpy2.powmod(c2, s, n)

m = gmpy2.f_mod(gmpy2.mul(a,b),n)
print(gmpy2.iroot(m, 2))
print(long_to_bytes(gmpy2.iroot(m, 2)[0]))

easytask

虽然r是完全可以爆破的，但是要3个小时才能跑完，比赛中没有出

没做出来的原因总结一下几点

  1. 遍历所有的r不慢，但是不精明的操作（在循环中生成AES解密）会导致空间复杂度很大，导致程序非常慢
  2. 赛后问尚师傅，其实真正的r开头是-3 -2（应该是刻意为之），所以尽管空间复杂度很大，但是比赛中还是遍历到了，判断机制写得不对
  3. 综上，判断机制不是非得是flag.starswith(b'flag')，求出来的m很有特征的；可以学尚师傅，先自己定个r，然后用脚本跑一遍（处理大数据，样本方法
  4. 比赛中先算出r保存在内存里，再开始遍历

调整后的脚本快多了

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
#!/usr/bin/env sage
# -*- coding: utf-8 -*-
import hashlib
from Crypto.Cipher import AES
import re
from itertools import product

c = '1070260d8986d5e3c4b7e672a6f1ef2c185c7fff682f99cc4a8e49cfce168aa0'
c = bytes.fromhex(c)
ct_e = '[151991736758354 115130361237591  58905390613532 130965235357066  74614897867998  48099459442369  45894485782943   7933340009592     25794185638]'
ct_W = '''[-10150241248 -11679953514  -8802490385 -12260198788 -10290571893   -334269043 -11669932300  -2158827458     -7021995]
[ 52255960212  48054224859  28230779201  43264260760  20836572799   8191198018  14000400181   4370731005     14251110]
[  2274129180  -1678741826  -1009050115   1858488045    978763435   4717368685   -561197285  -1999440633     -6540190]
[ 45454841384  34351838833  19058600591  39744104894  21481706222  14785555279  13193105539   2306952916      7501297]
[-16804706629 -13041485360  -8292982763 -16801260566  -9211427035  -4808377155  -6530124040  -2572433293     -8393737]
[ 28223439540  19293284310   5217202426  27179839904  23182044384  10788207024  18495479452   4007452688     13046387]
[   968256091  -1507028552   1677187853   8685590653   9696793863   2942265602  10534454095   2668834317      8694828]
[ 33556338459  26577210571  16558795385  28327066095  10684900266   9113388576   2446282316   -173705548      -577070]
[ 35404775180  32321129676  15071970630  24947264815  14402999486   5857384379  10620159241   2408185012      7841686]'''

e = []
for i in re.findall(r"\d+", ct_e):
    e.append(int(i))
e = matrix(e)

W = [[0 for _ in range(9)] for j in range(9)]
ct_W = re.findall(r'-?\d+', ct_W)
for i in range(len(ct_W)):
    W[i // 9][i % 9] = int(ct_W[i])
W = matrix(W)
inv_W = W.inverse()

table = [_ for _ in range(-3, 4)]
r = product(table, repeat=9)

for ri in r:
    rx = matrix(ri)
    m = (e - rx) * inv_W
    if 0 < m[0][0] < 1024:
        M = list(m[0])
        key = hashlib.sha256(str(M).encode()).digest()
        cipher = AES.new(key, AES.MODE_ECB)
        flag = cipher.decrypt(c)
        if flag.startswith(b'flag') or flag.startswith(b'SET'):
            print(r)
            print(flag)
            break

让我看看之前的脚本为啥不能出

我们自己写一个r，就[-3,-3,-3,-3,-3,-3]吧，然后走一遍，我知道了，是这个问题

1
M = list(m[0])

sage矩阵转列表的时候要多取一个，差不多是这么一个意思吧

image-20211108072631010

竟然是非预期，做的时候也想着用格来做，但直接爆破还是太诱人了，原题

https://hxp.io/blog/26/VolgaCTF-2016-Quals-crypto300-XXY-writeup/

经过一番搜索后发现原来这是GHH加密

Civet cat for Prince

目的，已知IV，可以获得输入name+'a_cat_permission'的密文，可以有最多两次自己输入IV和密文进行解密，求输入name+'Princepermission'的密文，注意最后这里我们可以自己定义IV

重点是最后一句话，这就是利用点，复现的时候我一个上午都没注意到，以为是要用它的IV；然后下午看到，那就比较简单了

一个小思路，假设获取的name_cipher$c$分成前半段$c_1,\ c_2$，密文构造成
$$
c_1\oplus a_cat_permission\ \oplus Princepermission + c_2\notag
$$
这样第二段密文解密出来就是Princepermission

然后利用一次解密的机会，将上面这个密文的前半段和系统的IV丢进去，得到的结果记为$m_1$，求
$$
m_1\oplus IV \oplus Princepermission\notag
$$
这样解密出来的第一段就是Princepermission，其实name无所谓什么都可以

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
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
import hashlib
from pwn import *
from itertools import product
import string

context.log_level = 'debug'
table = string.ascii_letters + string.digits


class Solve:
    def __init__(self):
        # self.sh = remote('192.168.56.1', 10005)
        self.sh = remote('node4.buuoj.cn', 29129)
        self._Princepermission = b'Princepermission'
        self._a_cat_permission = b'a_cat_permission'
        self.iv = b''
        self.cipher_name = b''
        self.payload_cipher = b''
        self.payload_iv = b''

    def proof_of_work(self):
        """
        [+] sha256(XXXX+Q3kqSv2c) == e9ded46c9d0dbcf14d8c36852678fe59daec43b1025c282738a81e7ea9f395f9
        [+] Give Me XXXX :
        """
        proof = self.sh.recvline()
        tail = proof[16:24].decode()
        HASH = proof[29:93].decode()
        for i in product(table, repeat=4):
            head = ''.join(i)
            t = hashlib.sha256((head + tail).encode()).hexdigest()
            if t == HASH:
                self.sh.recvuntil(b'[+] Give Me XXXX :')
                self.sh.sendline(head.encode())
                break

    def solve_BANNER(self, _name):
        self.sh.sendlineafter(b'[-]', b'1')
        self.sh.sendlineafter(b'[-]', _name)
        self.sh.recvline()
        self.sh.recvline()
        self.sh.recvuntil(b'Miao~ ')
        self.iv = self.sh.recvuntil(b"I'm a")[:-6]
        print(len(self.iv))

    def solve_NAME(self):
        self.sh.sendlineafter(b'[-]', b'1')
        self.sh.recvuntil(b'Permission:')
        self.cipher_name = self.sh.recvuntil(b"I'm a")[:-6]
        self.cipher_name = self.cipher_name
        self.payload_cipher = xor(xor(self.cipher_name[:16], self._a_cat_permission),
                                  self._Princepermission) + self.cipher_name[16:32]

    def solve_Princepermission(self):
        self.sh.sendlineafter(b'[-]', b'2')
        self.sh.sendlineafter(b'[-]', self.payload_cipher[:16])
        self.sh.sendlineafter(b'[-]', self.iv)
        self.sh.recvuntil(b'The message is ')
        self.payload_iv = xor(xor(self.sh.recvuntil(b'1.getpermission')[:16], self.iv), self._Princepermission)

    def solve_flag(self):
        self.sh.sendlineafter(b'[-]', self.payload_cipher)
        self.sh.sendlineafter(b'[-]', self.payload_iv)
        self.sh.recvuntil(b'The prince asked me to tell you this:\n')
        flag = self.sh.recvline()
        print(flag)

    def solve(self):
        self.proof_of_work()
        self.solve_BANNER(self._Princepermission)

        # get cipher_name
        # chance ====> 2
        self.solve_NAME()

        # get cipher_Princepermission
        # chance ====> 1
        self.solve_Princepermission()

        # chance ====> 0
        self.sh.sendlineafter(b'[-]', b'3')
        
        # get flag
        self.solve_flag()


if __name__ == '__main__':
    solution = Solve()
    solution.solve()

image-20211108161217066

好一个狸猫换太子

Re

EasyRe

反编译失败，查了好久，尝试平衡栈，手动修无果，然后想起一开始看到一串32位的字符串没用到，随便搜了下竟然是hello world的md5，抱着试一试的心态丢进去就对了

image-20211107141510771