发布于 

mtctf WP

好气啊！

赛事复盘

这次比赛应该是HASH-TEAM迄今为止合作最为优良的一次，虽然大三PWN爷因ddl没有打，大二misc哥神秘消失，只剩我们几个大一狗（和从隔壁院拉来玩的misc哥哥），排除那个辣鸡密码最后一题的干扰的话，进前二十还是有很大希望的。

以下是密码学部分的WP。

WP

easy_rsa

真的很easy，第一步是一个rsa的padding 攻击，第二步是一次一密的manytimespad 攻击。

padding攻击的推导学习如下：

附原文：rsa_padding_attack

脚本如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from gmpy2 import *
print('m1=m+p1')
print('m2=m+p2')
n=int(input("n(hex):")[2:],16)
c1=int(input("c1(hex):")[2:],16)
p1=int(input("p1(hex):")[2:],16)
c2=int(input("c2(hex):")[2:],16)
p2=int(input("p2(hex):")[2:],16)
print('m1=a*m2+p1-p2')
a=int(input("a(hex):")[2:],16)
b=p1-p2
m=((3*b*((a**3)*c2-b**3)*invert(c1-c2*(a**3)+2*(b**3),n)+b)*invert(a,n)-p2)%n
from binascii import *
print(unhexlify(hex(m)[2:]))

manytimespad经典脚本，丢在这里。

需要注意的是，由于manytimespad是概率算法，需要对某些位进行人工校对。

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
ciphertexts=[
'280316470206017f5f163a3460100b111b2c254e103715600f13',
'091b0f471d05153811122c70340c0111053a394e0b39500f0a18',
'4638080a1e49243e55531a3e23161d411a362e4044111f374409',
'0e0d15470206017f59122935601405421d3a244e10371560140f',
'031a08080e1a540d62327f242517101d4e2b2807177f13280511',
'0a090f001e491d2c111d3024601405431a36231b083e022c1d',
'16000406080c543854077f24280144451c2a254e093a0333051a',
'02050701120a01334553393f32441d5e1b716027107f19334417',
'131f15470800192f5d167f352e0716481e2b29010a7139600c12',
'1609411e141c543c501d7f232f0812544e2b2807177f00320b1f',
'0a090c470a1c1d3c5a1f2670210a0011093a344e103715600712',
'141e04040f49153142043a22601711520d3a331d0826'
]
NUM_CIPHER = len(ciphertexts) #NUM_CIPHER=11
THRESHOLD_VALUE = 8 

def strxor(a, b):
    if len(a) > len(b):
        return "".join([chr(ord(x) ^ ord(y)) for (x, y) in zip(a[:len(b)], b)])
    else:
        return "".join([chr(ord(x) ^ ord(y)) for (x, y) in zip(a, b[:len(a)])])

def letter_position(s):
    position = []
    for idx in range(len(s)):
        if (s[idx] >= 'A' and s[idx] <= 'Z') or (s[idx] >= 'a' and s[idx] <= 'z') or s[idx] == chr(0):
            position.append(idx)
    return position

def find_space(cipher):
    space_position = {}
    space_possible = {}
    for cipher_idx_1 in range(NUM_CIPHER):
        space_xor = []
        c = ''.join([chr(int(d, 16)) for d in [cipher[cipher_idx_1][i:i + 2] for i in range(0, len(cipher[cipher_idx_1]), 2)]])
        for cipher_idx_2 in range(NUM_CIPHER):
            e = ''.join([chr(int(d, 16)) for d in [cipher[cipher_idx_2][i:i+2] for i in range(0, len(cipher[cipher_idx_2]), 2)]])
            plain_xor = strxor(c, e)
            if cipher_idx_2 != cipher_idx_1:
                space_xor.append(letter_position(plain_xor))
        space_possible[cipher_idx_1] = space_xor  

    for cipher_idx_1 in range(NUM_CIPHER):
        spa = []
        for position in range(400):
            count = 0
            for cipher_idx_2 in range(NUM_CIPHER - 1):
                if position in space_possible[cipher_idx_1][cipher_idx_2]:
                    count += 1
            if count > THRESHOLD_VALUE:  
                spa.append(position)
        space_position[cipher_idx_1] = spa  
    return space_position


def calculate_key(cipher):
    key = [29] * 200  
    space = find_space(cipher)
    
    for cipher_idx_1 in range(NUM_CIPHER):
        for position in range(len(space[cipher_idx_1])):
            idx = space[cipher_idx_1][position] * 2 
            a = cipher[cipher_idx_1][idx] + cipher[cipher_idx_1][idx + 1]
            key[space[cipher_idx_1][position]] = int(a ,16) ^ ord(' ') 

    key_str = ""
    for k in key:
        key_str += chr(k)
    return key_str  

result = ""
key = calculate_key(ciphertexts)
key_hex =''.join([hex(ord(c)).replace('0x', '')+' ' for c in key])
print("key=\n"+key)
print("key_hex=\n"+key_hex)
print(ord(key[0]))

#key="flag{it_1s_P@dd1n_@nd_p@d}"
print(key)
for t in range(len(ciphertexts)):
    f = ''.join([chr(int(d, 16)) for d in [ciphertexts[t][i:i+2] for i in range(0, len(ciphertexts[t]), 2)]])

    for letter in strxor(f,key):
             if (letter>=' ' and letter<='}'):
                 result+=letter
             else:
                 result+='0'
    print(result)
    result=''

random

这个题直接连靶场，第一段是一个已知ed与n，求解pq并签名的过程，这里需要通过分解ed暴力枚举哪个是合适的私钥进行加密，直接上脚本。

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
from pwn import *
p=[3,47,97,157,1601,21851, 56277292709098311733, 842863003249682472366877119627791407784227212205826369770241241624102599233623894956515489038200231882823515796275720517565796868777565634050439841286136730958498908985484216812390745790379384069380694859486312946676748208469080046559332149394110283426861163444586148612461696703]
e=[0]*256
for i in range(2**8):
    t='0'*(8-len(bin(i)[2:]))+bin(i)[2:]
    print(t)
    s=1
    for j in range(len(t)):
        if (t[j]=='1'):
            s*=p[j]
    e[i]=s

p=10980405508174271259925333166343579553719061316941945190323939083665489902286168861229664589365210026388298173482496757264697996404794685064674668272479771
q=9473016801951797771267846445459738473973421588058140695253031511700407533935872397264731631901174665159278878658035094231228063878480145556088206641042779
m=2977586969238177688788136343510734253831840749969343604581
ed=3563225736483105767663757964850895939437686773696002911178487096580796031415653965179057012630692344510786639289764837381745729106408000203666201724099978695932368871885604099587719393152976934607128732108404042096355012051169236089620505421627586309618317607971836222910097506025923742035914623661579380093911361
from gmpy2 import *
for i in range(256):
    if(e[i]*invert(e[i],(p-1)*(q-1))!=ed):
        continue
    d=invert(e[i],(p-1)*(q-1))
    pr=remote('47.105.112.9',1123)
    pr.recvuntil('enter sign:')
    print(i)
    pr.sendline(str(powmod(m,d,q)))
    s=pr.recv()
    s=pr.recv()
    if(b'error' not in s):
        print(s)
        pr.interactive()

print('wrong')

这里有一个点是，如何进行暴力枚举，这次采用的手法是生成01背包串然后按位选取，方便计算复杂度，也相对容易实现。

然后是一个LCG生成随机数，没想学，就找了个脚本魔改。

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
from Crypto.Util.number import *
def gcd(a,b): 
    if(b==0): 
        return a 
    else: 
        return gcd(b,a%b) 
s = [3732074616716238200873760199583586585380050413464247806581164994328669362805685831589304096519259751316788496505512 , 8890204100026432347745955525310288219105398478787537287650267015873395979318988753693294398552098138526129849364748 , 3443072315415198209807083608377973177101709911155814986883368551162572889369288798755476092593196361644768257296318 , 4505278089908633319897964655164810526240982406502790229247008099600376661475710376587203809096899113787029887577355 , 9059646273291099175955371969413555591934318289156802314967132195752692549263532407952697867959054045527470269661073 , 3085024063381648326788677294168591675423302286026271441848856369032582049512915465082428729187341510738008226870900 , 8296028984288559154928442622341616376293205834716507766500770482261973424044111061163369828951815135486853862929166 , 2258750259954363171426415561145579135511127336142626306021868972064434742092392644953647611210700787749996466767026 , 4382123130034944542655156575000710851078842295367353943199512878514639434770161602326115915913531417058547954936492 , 1098293359822342785200547274854337991360189639864781168096457916133912890897651117338289654910429603148324390094392]
t = []
for i in range(9):
    t.append(s[i]-s[i-1]) 
all_n = []
for i in range(7):
    all_n.append(gcd((t[i+1]*t[i-1]-t[i]*t[i]), (t[i+2]*t[i]-t[i+1]*t[i+1]))) 

MMI = lambda A, n,s=1,t=0,N=0: (n < 2 and t%N or MMI(n, A%n, t, s-A//n*t, N or n),-1)[n<1] #逆元计算
for n in all_n:
    n=abs(n)
    if n==1:
        continue
    a=(s[2]-s[1])*MMI((s[1]-s[0]),n)%n
    ani=MMI(a,n)
    b=(s[1]-a*s[0])%n
    seed = (ani*(s[0]-b))%n
    plaintext=seed
    print(long_to_bytes(plaintext))

附原文：LCG

RSA_sig

第一步工作证明，直接爆破sha224.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from hashlib import sha224
from base64 import *
s='ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'
m0=input('XXX+?:')
a=input("ans:")
for i in range(64):
    for j in range(64):
        for k in range(64):
            t=s[i]+s[j]+s[k]
            m=t+m0
            p=sha224()
            p.update(m.encode("UTF-8"))
            d=p.hexdigest()
            if a in d:
                print(t)

连上之后发现就是一个公钥签名体系，众所周知，对于RSA，“签名我”和“解密我”等价，所以求了flag再搞签名就行。

random1

这个题随意到跟题目一样【……】

第一步是lsfr，因为有mask，可以直接n位解决。需要注意，加密脚本里掩码少两个f。

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
#python2.7
import libnum
from binascii import *
def LFSR_inv(R,mask):
    str=bin(R)[2:].zfill(32)
    new=str[-1:]+str[:-1]
    new=int(new,2)                   
    i = (new & mask) & 0xffffffff
    lastbit = 0
    while i != 0:
        lastbit ^= (i & 1)
        i = i >> 1
    return R>>1 | lastbit<<31      
def lfsr(R,mask):
    output = (R << 1) & 0xffffffff
    i=(R&mask)&0xffffffff
    lastbit=0
    while i!=0: 
        lastbit^=(i&1)
        i=i>>1
    output^=lastbit
    return (output,lastbit)
mask = 0b10100100000010000000100010010001
data=open('change2').read()
data1=data[:4]
c=libnum.s2n(data1)                   
for _ in range(32):
    c=LFSR_inv(c,mask)
print(hex(c))
key1=c
c=''
for i in range(100):
    tmp=0
    for j in range(8):
        (key1,out)=lfsr(key1,mask)
        tmp=(tmp<<1)^out
    c+=chr(tmp)

print(c)
print(data)
print(c==data)

然后是魔改RC4

这里的密钥是上文密钥的字节串【……】（临门一脚orz）

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
# coding=utf-8
from base64 import b64encode
#from flag import flag,key_read
from Crypto.Util.number import *
global x,N
N=100
x=16*16
#assert len(bin(key_read)[2:])==32
#assert key_read.startwith("0x")

def lfsr(R,mask):
    output = (R << 1) & 0xffffff
    i=(R&mask)&0xffffff
    lastbit=0
    while i!=0: 
        lastbit^=(i&1)
        i=i>>1
    output^=lastbit
    return (output,lastbit)


def s_box_a():
    s=[]
    for i in range(x):
        s.append(i)
    return s

def key_padding(key):
    k=[0]*x
    for i in range(x):
        k[i]=key[(i)% len(key)]
    return k

def s_box(s,key):
    j=0
    for i in range(x):
        j=(j+s[i]+key[i])%x
        s[j],s[i]=s[i],s[j]
    return s
from base64 import *
def main():
    key1=b'0x1afea246'
    cm=128834039630569249954916947026853954267142833779669
    cm=hex(cm)[2:]
    cm=b64decode("WCbeI/BfRYydhk43yF1MIdOk4zPV")
    print(len(cm))
    print(cm)   
    mask=0b10100100000010000000100010010001
    key=[]
    for i in range(len(key1)):
        key.append(key1[i])
    key=key_padding(key)
    sbox=s_box(s_box_a(),key)
    i=j=0
    
    c=""
    print(sbox)
    print()    
    for k in range(len(cm)):
        i = (i+1)%x
        j = (j+sbox[i])%x
        sbox[i],sbox[j]=sbox[j],sbox[i]
        t=(sbox[i]+sbox[j])%(x//2)
        c+=chr(cm[k]^sbox[t])
    print(c)

if __name__=='__main__':
    main()
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

本站由 [@Zuni](http://example.com/) 创建，使用 Stellar 作为主题。