2019SUCTF Crypto&&Reverse writeup

Posted on

SUCTF Crypto&&Reverse

Crypto AK指南

DSA

共r攻击得到x，对消息签名得到flag

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
#coding=utf8
from Crypto.PublicKey import DSA
from hashlib import sha1
import gmpy2
y = 59998964422720567410971392247588610270838161207397035632002275213137280191832120978879710500476700732252657163883040778110433361229025561528932261647267356601327288870079034283219825305854917122470476263679775684658309724956217086373271094822923565839520323861656876204763501285315938099749485745556365977385
g = 43389854742161278437795219923942481775415347045657754950101547258603126039442015413837081119910836292884272763216819814465391926154918568052023904893455646228551404626313275513364910490826315111525183581985725183125157061116286909065516135519389601010524077855226671936609315614619488171104373006393843535936
p = 89884656743115797306463115781658547652701352914216992134724261350662138610779037881598639133132443399775174755349212745086191371006305803101408979382417949745858915745624526163699132112106657340987225858815360563806509539737133045727525608405157417768282568991275850018080217110159142086149521127066321887933
q = 947518380736106120979020081716052995250920349441
m3 = 307693878875281197163704550997724119116
m4 = 27650803417371457807064002936379775828
s3 = 204284014447639360127701931752666127662919593553
s4 = 807037783913314060221428202522519970102697802927
r = 107149838461499022506747607203457736319293892939
ds = s4 - s3
dm = m4 - m3
k = gmpy2.mul(dm, gmpy2.invert(ds, q))
k = gmpy2.f_mod(k, q)
tmp = gmpy2.mul(k, s3) - m3
x = tmp * gmpy2.invert(r, q)
x = gmpy2.f_mod(x, q)
print(x)
print(k)
mes = 334436397493699539473999398012751306876
r1 = gmpy2.powmod(g,k,p)
r1 = r1 % q
s1 = (gmpy2.invert(k,q)*(mes+x*r))%q
print('k',k)
print('x',x)
print('(%d, %d)'%(r1,s1))
# (1070334240122464358241089769633029668974770861682L, 1222791079228374886029529242891467967573428488490L)

MT

angr或z3求解

Prime

nc过去得到四组数据n1、n2、n3、n4，c1、c2、c3、c4

其中 c = powmod(m,n,n) ，要求求出m1、m2、m3、m4

发现n1、n2、n3、n4两两共因子，所以每个n都可以分解为诸如

n = p * qp * qqp * qqq 的形式，由费马小定理求出phi，而后求逆元d，就可得到m

m = powmod(c,n,n)

代码写得比较丑，将就看吧

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
import gmpy2
from Crypto.Util import number

c0 = 0x2e3413f85b4037231cf93b9c0a0e8d94535679b29747911dd1f189ac5e7b8358974b1f139f3af0e94024c5df6feb1f1f9e6494ae6aa6e99d14a83615e9893e3d8df5fe578b3fc3fb3888c34eb0da25ff8df62612830c21a9324c6738667cfd5e26096912aca966fd875e8fbd2c4e13bbc1979ffe4bda1c098c31033e80bbd086938eb1c9fe09ce5b7a10f7dd397deeb7d7be5e0cf6e1146218fd2ba1a9795c691005768dee8d21f5b888aca0660dcc14695ce9245a9b02dd69a722c9ba81966469b058776fdd439ab5a3b07d20ca9219e6573798401a44e04abc2ad362f54187b3e8ce6310d0c629fd5b89a8fb386ec21a1e18abe5f7d3c60bef510e9cc224
c1 = 0xb42983a2937314541bf7f31f00d3492eba055b974d2d27800490f2922faccce4982f7a9b1dc51a993bdc4ec1c6d2ce4dac9a1fe6a814bf3647ef2053b760411c8c05d93adb579aa4c6a2b0978f2db8e4ec64ee45849391a13a326926257999006e4f859122a3db531fbd3e71ff4654bf75572d41a5c96c2016dbdf2ddd0a7ab7526ed44b026075d48f983ecbddf6f4bab2cc33b89670cf0cc535073f063f762ce371b7c42906dfb0a06f51e28d7144d3e5769f30b69ded7cfb582296a9df23e91b13b35f7fa3220072fc5f9e4189a3c8aef8a47ef4a5a370f6e5967796d031b6e00a29505b69f6afd6e6ba0a6184a274b8ec912700c987cd356dffdf389ba1
c2 = 0x3b8950457e4232268b1b6cb44d6f0545eec55784054e551b7dc14db9bcba18b6271a6612e919cc0bbbb2028de47ec4e3e6d1add29ba59fd5c657da34efa20fec0858d5d717a9adb81f66b4a3f6e12bdb7dcca5f44b160d45674943ff10c55a9eb07adf65c310f208686de9da11618dd28fe0a370b4947428a27eea357571bbaf793ccbd1a671315a993da1d4c39239eda774d8c6a53249acd51c38c88aca166f172ca0447c7afeb82bda0f3fc0a3970d731971c1947ec50f00698c53c05bf5f90e2af15340c15bdfcb79f48b10a9320841069ed9448969dc1aaa8b09205279c1b93e296ffc5f5d4d7379bbb5536aba44f1c3c9b6499a14f45bfd761ebe10bf43
c3 = 0x183403f54b8a16fc6b9ba1b034c34991f1799df7416b03ec342d0f79d74b3ea329f983d4d5fc76f29908d3376b5e1d10b90ec6562c114962a758aad15e27e6b3086cdc9e9434f5de2f339f5038335d64845f5371d89a43e31fc098bdb022c989faf46bd5705d84b0b4b2b5de28556505c73cfe17e9b2cea83125852e494394ba3df8022c470d15295c2ac1b0b359e6b6072b5d4ce6324829429cbdd8639c72ed503cf0572607b2796da933e3152a2ae0895e999720e9e31445dde5e1d3042a53e85a2a32eb395742f3d4f643938ba9cb92da430ca154b0d7cfad07076e9d5d927ae80deaff1573b13343bf8e5c378b89cc6764d567984ab9b8a010a134efe6b

n0 = 0x16657186baf7838afac2496d178767b436f72eb3404f42230c69e2490f4623db38ba480b1b9a087fe2ce8eb6cdd5d8889f821cab6a903cc5d1db83ea996bc62e3146e557f91d2119bc62573e9afea867c5f3dd870a93169dbfee02f4f3a6b527e1ff30b6441456a4cd0ece51d0fcd1ac94945b7e10d7f537ce2597e32d1bb2d3468416328110d3e1b36e42c90e08446263854b357b8b2adce43cf6c8ecc5e05a96ad32317cdf4576c0d959072493cf96f99d6509581b8375796510937e8cddc87575c5bf02c6af18261eaab2a5bfe9b3e51909095aef351426b2e473ebe58bc2899d25fd31ceb2407e993afd0c0acbb9306313018f9e89fdcd7b9ad299f6015
n1 = 0xbae5ec9f4ef1c80612ec6980670bec41674eedcfbe8bfc389a9eff4e0558a52b97bb502e7550c715aaec555db9cf9d77557bbfa4ac7af5f624a5d29b9e7b527bd869cd07a58647f7a5af2ba1cbca566c89b6b362c696bcee414bae1bd4b351f71b451a989603ac3ed9591aa216feee60404ea60ea3f80ac46fab2ae2509a684ea189c8fd162254f36a2fd76e152260accdbfee3f9b8b3fa5246a66c86b03a72fc1a47eb5947ccd68faf8336ad55a9367d84d23b9e797c0be62f372891aade7adf5c940f0f0028875c52692f5aab57adbc4096de0cb774d070571dac490aa266407c9c82f39102cc6a00cb16cdc8ffe2eaa879126460a29634259d4bf4f99bd
n2 = 0x44290f36dd89d87461aae4a10f9f42054239c91e6faa94c30011b1f1b783a13d2fe61adf081ac8be829dd636bb9c7027aa79d20b16c2268dea978765ddc50187349c64afe98ad91f35fa7321e2db264e65e306c743e9e14e77e69a0f3db3dbbcb9d912f1c583071e650dd88f3a120457756140aa3feef2d4dd2249c8ac904d3825ae93ca96908c7d913bebd7a3c6d18e704f7df493a65fc39ae04af1c0a577b96ec284b8ab8b859372334a148b3dc0e000302622b25e8d1439a4d3d369bcffab7f279a2ace742fc5685f168a7caa487a55c4907456c30b1087c3f484180da55346bff2d095b95d1b708b36f199752eff06029af1676ea0128160b64477aef8d9
n3 = 0x25e93a809158fd8e8230441691867e95c53fee2052f1e4f3c0a383b5eeb2ef2ba54958941848e313b1bdbfc1843d254cd624ca25f9aac303ece3945ebd3c492e2ea06573f78c9de6d69ff176719671dacc51300a0cbc53ed942dd59f2edfbf5ba90a341a501c1c6754457263cddf34e401362c0655b3cafbd989dc6a632c5ee4698ef9b8d2f50c5c76ea0540506eee65b4faa80245b0b02b51e5304b7071cfe771a646a50d2721e04f1babcc1c66f79ccb748950dbae61d4eda6056ce28f12142a02a611c51bf6cb54c3465d6459da94536c92e29e27d07386bc39ba306608b9eb79520a5ad1533069ac272b9ba86142ff0632319256eb2fac0ff37d82e02c5

p01 = gmpy2.gcd(n0,n1)
p02 = gmpy2.gcd(n0,n2)
p03 = gmpy2.gcd(n0,n3)
p12 = gmpy2.gcd(n1,n2)
p13 = gmpy2.gcd(n1,n3)
p23 = gmpy2.gcd(n2,n3)

def funs(n0,p01,p02,p03,c0):
    q0 = n0//p01
    q1 = n0//p02
    q2 = n0//p03

    qq1 = gmpy2.gcd(q0,q1)
    qq2 = gmpy2.gcd(q0,q2)

    qp1=q0//qq1

    qpq = gmpy2.gcd(qq1,qq2)

    qpp = qq1//qpq

    phi  = (qpq-1)*(qpp-1)*(qp1-1)*(p01-1)
    # print(phi)
    d = int(gmpy2.invert(n0,phi))
    m = hex(pow(c0,d,n0))[2:-1]
    print(m)


funs(n0,p01,p02,p03,c0)
funs(n1,p01,p12,p13,c1)
funs(n2,p02,p12,p23,c2)
funs(n3,p13,p03,p23,c3)


# flag{H0W_c1EV3R_Y0u_AR3_C0ngRatu1at10n5}

RSA

Least Significant Bit Oracle Attack

注意因为整除的缘故最后得到的值与实际值有一定偏差

exp

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
from pwn import *
from string import hexdigits
from hashlib import md5
import gmpy2
import re
import time

def hash(salt,part_hash):
    for i in range(0xffffff):
        s = str(i)
        if(md5(s + salt).hexdigest()[:5] == part_hash):
            return s;
            break;
            
io=remote('47.111.59.243',9421)
t = time.clock()
line = io.recvline()
salt = line[40:44]
part_hash = line[54:59]
s = hash(salt,part_hash)
io.sendline(s)
for i in range(3):
    l = io.recvuntil('Please input your option:',drop =True )
    pattern = re.compile(r'(?<=n = )\d+\.?\d*')
    print(l)
    n = int(pattern.findall(l)[0])
    pattern = re.compile(r'(?<=e = )\d+\.?\d*')
    e = int(pattern.findall(l)[0])
    pattern = re.compile(r'(?<=c = )\d+\.?\d*')
    c = int(pattern.findall(l)[0])
    u = n
    l = 0
    d = gmpy2.powmod(2,e,n)
    m = c
    i = 0
    while u - l > 1:
        m = (m*d)%n
        io.sendline('D')
        io.send(str(m)+'\n')
        res = io.recvuntil('!',drop = True)
        if 'even' in res:
            u = (u+l)/2
        else:
            l = (u+l)/2

    ans = 0
    for i in range(-1024,1025):
        m = u + i
        if pow(m,e,n) == c:
            ans = m
            break
    io.sendline('G')
    io.send((str(ans)).strip('L')+'\n')
    res = io.recvuntil('!',drop = True)
    print(res)
    res = io.recvline()
    print(res)
    res = io.recvline()
    print(res)
    print('bye')
print('[!]Timer:',round((time.clock()-t),2),'s')
io.close()

Reverse

SignIn

签到题，n可分解，直接求出明文

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
__int64 __fastcall main(__int64 a1, char **a2, char **a3)
{
  char v4; // [rsp+0h] [rbp-4A0h]
  char v5; // [rsp+10h] [rbp-490h]
  char v6; // [rsp+20h] [rbp-480h]
  char v7; // [rsp+30h] [rbp-470h]
  char v8; // [rsp+40h] [rbp-460h]
  char v9; // [rsp+B0h] [rbp-3F0h]
  unsigned __int64 v10; // [rsp+498h] [rbp-8h]

  v10 = __readfsqword(0x28u);
  puts("[sign in]");
  printf("[input your flag]: ", a2);
  __isoc99_scanf("%99s", &v8);
  sub_96A(&v8, &v9);
  __gmpz_init_set_str(&v7, "ad939ff59f6e70bcbfad406f2494993757eee98b91bc244184a377520d06fc35", 16LL);
  __gmpz_init_set_str(&v6, &v9, 16LL);
  __gmpz_init_set_str(&v4, "103461035900816914121390101299049044413950405173712170434161686539878160984549", 10LL);
  __gmpz_init_set_str(&v5, "65537", 10LL);
  __gmpz_powm(&v6, &v6, &v5, &v4);
  if ( (unsigned int)__gmpz_cmp(&v6, &v7) )
    puts("GG!");
  else
    puts("TTTTTTTTTTql!");
  return 0LL;
}

exp

1
2
3
4
5
6
7
8
9
10
import gmpy2
from binascii import unhexlify

p = 282164587459512124844245113950593348271
q = 366669102002966856876605669837014229419
e = 65537
c = 0xad939ff59f6e70bcbfad406f2494993757eee98b91bc244184a377520d06fc35
d = gmpy2.invert(e,(p-1)*(q-1))
m = gmpy2.powmod(c,d,p*q)
print('flag:',unhexlify(hex(m).encode()[2:]).decode())

flag 为 suctf{Pwn_@_hundred_years}

hardCPP

ollvm混淆的题目，还有个简单的时间反调，但是F5之后可以直接看到关键的处理区域

1
2
3
4
5
6
7
8
9
10
11
12
13
v35 = v38 ^ s[v36];
v34 = main::$_0::operator() const(&v44, (unsigned int)v35);
v33 = main::$_1::operator() const(&v42, (unsigned int)s[v38 - 1 + v36]);
v24 = main::$_1::operator() const(char)::{lambda(int)#1}::operator() const(&v33, 7LL);
v35 = main::$_0::operator() const(char)::{lambda(char)#1}::operator() const(&v34, (unsigned int)v24);
v32 = main::$_2::operator() const(&v45, (unsigned int)v35);
v31 = main::$_2::operator() const(&v45, (unsigned int)s[v38 - 1 + v36]);
v25 = main::$_2::operator() const(char)::{lambda(char)#1}::operator() const(&v31, 18LL);
v30 = main::$_3::operator() const(&v43, (unsigned int)v25);
v26 = main::$_3::operator() const(char)::{lambda(char)#1}::operator() const(&v30, 3LL);
v29 = main::$_0::operator() const(&v44, (unsigned int)v26);
v27 = main::$_0::operator() const(char)::{lambda(char)#1}::operator() const(&v29, 2LL);
v35 = main::$_2::operator() const(char)::{lambda(char)#1}::operator() const(&v32, (unsigned int)v27);

对算法进行逆向，可以得到

1
2
for i in range(0x20):
	flag[i+1]+(flag[i]%7)^(flag[i]^18)*3+2 == enc[i]

很容易就可以得到输入为#flag{mY-CurR1ed_Fns}

flag为 flag{mY-CurR1ed_Fns}

0%