sky's blog

2019 Pwnhub-Always be with U-Writeup

字数统计: 1,955阅读时长: 9 min
2019/03/29 Share

前言

正逢pwnhub有比赛,于是做了一下题目,以下是题解

Happy Tree Friends

题目概述

拿到题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#!/usr/bin/env python3

import zlib
from Crypto.Cipher import AES
import sys
import os
from hashlib import md5

flag = open("flag.txt").read()
while True:
data = input()
data = "message: %s, flag: %s" % (data, flag)
compressed = zlib.compress(data.encode())
if len(compressed) % 16:
compressed += b"\x00" * (16 - len(compressed) % 16)
encrypted = AES.new(
md5(flag.encode()).digest(), AES.MODE_CBC, os.urandom(16)
).encrypt(compressed)
print(encrypted.hex())

发现有如下操作
1.接收输入的值
2.将输入值和flag放在一起
3.使用zlib进行压缩
4.将压缩结果进行padding
5.使用AES加密
6.返回加密值

漏洞点分析

本想对AES进行攻击,但只可控明文,还要经过zlib压缩,应该不太靠谱,于是往zlib压缩算法上考虑
查阅资料得知
zlib应该是参考了Rabin–Karp字符串查找算法,即使用hash方法来确定一个字符串是否在前面出现过。zlib压缩过程中会维护一个比较大的hash值数组,这个数组存储了数据流中每3个字符组成的字符串的hash值,例如4、5、6号字符计算一个hash值,5、6、7号字符也计算一个hash值。
计算出的hash值作为下标,用来在hash值数组里存储当前三字字符串的下标。当数据流中出现一个新字符时,和之前的两个字符组成一个字符串,计算hash值,看在hash数组里该值的位置是否已经有值,有的话就取出这个值(上一次得到这个hash值的三个字符的下标),检查是否是有效匹配。可以将查找过程理解为一个查字典的过程,只不过这个字典的条目也是处理过程中逐渐生成、逐渐抛弃的。
我们编写测试脚本可以发现

1
2
3
4
5
6
7
8
import zlib
flag = 'flag{148731984637}'
data1 = 'fla'
data1 = "message: %s, flag: %s" % (data1, flag)
data2 = 'dfa'
data2 = "message: %s, flag: %s" % (data2, flag)
print len(zlib.compress(data1.encode()))
print len(zlib.compress(data2.encode()))


由于压缩算法:
data1字符串中存在2次flag,如果data中有fla存在,则fla存在3次,压缩结果最短
而data2字符串中除了fla外,任意3种字符串,压缩后都没有data1压缩长度短
那么我们可以利用这种方式,通过长度进行侧信道,进行flag碰撞爆破,一旦出现flag中的字符,则加密结果明显变短
同时我们发现

当我们已知前几位后,后面爆破的结果,一旦匹配,则长度始终为最短值,即39
这样,如果开头是flag{,那么我们即可1位1位匹配,寻找长度为最短值的字符即可

题目测试

知道原理后,我们测试题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
flag
496f7e60ae407bb1020fc5d97898270cec9c8495cf0ca52d93d3dd74d4ae8cb0732dd45736a79ec8f921cd9cc893c08eb250f54ca27c1bf5e74b69fdcfef7ba4

flag{
bfe7b29ddccb4d0b4e538f224247801fdc9d8a518070cc38527152f1237cb6b96f22d30de1d7658bd71513bf1fcc58c950114a5c1c25907087d599fd83ef7a83

flag{a
b8c5ce562800a8209ddc31527a76758a50568cd51d256730be9ba0850cdaeae092656f305a92d1ff6bea09ea25745067aa27e16003acdf9e8a599f296d43b4b8d326ac1a9176be5ebc2866f8eb75ab56

flag{b
6a2b03216022caa3d7958767a86ef304858e9bf3e7303df3d27deaad6a9ddfa2603ee16dfe9b6b967805a527dd944a508d81b56a1bf32e4ea770b1334b17b6e17b93d95badb2429bf0f1a591c7cd914d

flag{c
ebfd61a158e220ce16fd53b31c1e4e67df928a883b187c66c98be71f11cf43df1abe6cfd3365da603c92beaa8e30c23cb94d420c8d392fa6b457369263e35bb0847a116cb31135ea57e6bcf18a083e42

flag{d
aef61242ad1cf6f7b645b73c486df9d9a8985eeb38c7c4e16d71c19b9ed05cf6def29c3c236ed126af90f2c467507a3a3b4fecdb4129f257bf567935f43e2b84

发现如果是flag的格式,并与flag一致,则长度为129,其余都为161,于是可以按位爆破,写出脚本如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from pwn import *
import itertools
import string

dic = string.digits + 'abcdef-'
s = remote("40.73.22.31", "2333")
flag = 'flag{de12473b-'
while True:
for i in dic:
tmp = flag+i
print tmp
s.sendline(tmp)
res = s.recvline()
print len(res)
if len(res)==129:
flag +=i
print flag
break

但发现跑完只得到

1
flag{de12473b-

后面字母跑出来,长度都是161,思考一下
发现这里还有AES,如果我输入的太长,就算原文被压缩,长度变短后,加密后还是会变长
所以并不能带这么一长串进行攻击,需要几个几个一爆。
同时发现

flag和de12虽然都在flag{}里出现,但是flag时候明显短
估计是因为消息如下

1
data = "message: %s, flag: %s" % (data, flag)

填充flag后,flag出现了3次,而de12只有2次,所以对zlib来说flag出现3次,压缩的更短,导致AES加密后只有128,即分了8组,而其他时候分了10组
同时,在原文足够长的时候

1
flag{de12473b-

无论是否压缩,压缩后结果都比较长,经过AES后依旧会分10组
这时候,我决定找到一个de1经过压缩会加密分组会变短,而de2经过压缩会加密分组不变的垃圾数据
(因为flag不太靠谱,出现过3次,不具有普遍意义)
垃圾数据填充到

1
2
~!@#$%^&*()_+{}SKYISC(4&^@)#%^de1
~!@#$%^&*()_+{}SKYISC(4&^@)#%^de2

发现长度明显不同

于是将脚本进行改进。

payload

编写出如下脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from pwn import *
import itertools
import string

dic = string.digits + 'abcdef-{}'
s = remote("40.73.22.31", "2333")
flag = 'flag{de12473b-'
padd = '~!@#$%^&*()_+{}SKYISC(4&^@)#%^'
while True:
now = flag[-2:]
for i in dic:
tmp = now+i
s.sendline(padd+tmp)
res = s.recvline()
if len(res)<224:
flag +=i
print flag
break

运行后可以得到flag

1
flag{de12473b-7105-4f6e-981c-1e4672e7a4b5}

Farewell

题目概述

拿到题目后

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

import sys
import socket
import secrets
from Crypto.Cipher import AES
from hashlib import sha256

p = 449703347709287328982446812318870158230369688625894307953604074502413258045265502496365998383562119915565080518077360839705004058211784369656486678307007348691991136610142919372779782779111507129101110674559235388392082113417306002050124215904803026894400155194275424834577942500150410440057660679460918645357376095613079720172148302097893734034788458122333816759162605888879531594217661921547293164281934920669935417080156833072528358511807757748554348615957977663784762124746554638152693469580761002437793837094101338408017407251986116589240523625340964025531357446706263871843489143068620501020284421781243879675292060268876353250854369189182926055204229002568224846436918153245720514450234433170717311083868591477186061896282790880850797471658321324127334704438430354844770131980049668516350774939625369909869906362174015628078258039638111064842324979997867746404806457329528690722757322373158670827203350590809390932986616805533168714686834174965211242863201076482127152571774960580915318022303418111346406295217571564155573765371519749325922145875128395909112254242027512400564855444101325427710643212690768272048881411988830011985059218048684311349415764441760364762942692722834850287985399559042457470942580456516395188637916303814055777357738894264037988945951468416861647204658893837753361851667573185920779272635885127149348845064478121843462789367112698673780005436144393573832498203659056909233757206537514290993810628872250841862059672570704733990716282248839
g = 2

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)

if sys.argv[1] == 's': # server
s.bind(('127.0.0.1', 23333))
s.listen()
s, _ = s.accept()
elif sys.argv[1] == 'c': # client
s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('127.0.0.1', 23333))

x = secrets.randbelow(p)
s.send(str(pow(g, x, p)).encode())
r = int(s.recv(2048))
key = pow(r, x, p)
aes = AES.new(sha256(str(key).encode()).digest())

if sys.argv[1] == 's':
flag = open('flag.txt').read()
flag += ' ' * (32 - len(flag) % 32)
s.send(aes.encrypt(flag))
elif sys.argv[1] == 'c':
print(aes.decrypt(s.recv(2048)))

发现题目是一个Diffle-Hellman密钥交换算法,同时题目用共享密钥key作为AES的密钥加密了flag
题目给出了p和g,以及在流量包中有如下值

1
2
3
str(pow(g, x, p)).encode()
r
aes.encrypt(flag)

所以题目思路比较清晰,即利用题目泄露的信息,计算出共享密钥,然后解密密文

Diffle-Hellman密钥交换算法

该交换算法原理如下
1.Alice和Bob先说好一个大素数p和它的原始根g
2.Alice随机产生一个数x, 计算C1=g^x mod p,然后把C1发给Bob;
3.Bob随机产生一个数y,计算C2=g^y mod p,然后把C2发给Alice;
4.Alice计算k=C2^x mod p;
5.Bob计算k*=C1^y mod p;
其中值得注意的是

1
k= C2^x mod p= (g^y)^x mod p = (g^x)^y mod p = C1^y mod p = k*


1
k=k*

那么在该题里,我们有p和g的值
同时有g^x mod pr的值
只要我们能通过

1
g^x mod p

计算出x,那么就可以利用

1
r^x mod p

计算出共享密钥k

私钥计算

这里我们知道Diffle-Hellman密钥交换算法的安全性建立于有限域上计算离散对数非常困难,但由于这里的g非常小,所以我们可以利用如下脚本进行计算

1
2
3
4
5
6
7
8
p=449703347709287328982446812318870158230369688625894307953604074502413258045265502496365998383562119915565080518077360839705004058211784369656486678307007348691991136610142919372779782779111507129101110674559235388392082113417306002050124215904803026894400155194275424834577942500150410440057660679460918645357376095613079720172148302097893734034788458122333816759162605888879531594217661921547293164281934920669935417080156833072528358511807757748554348615957977663784762124746554638152693469580761002437793837094101338408017407251986116589240523625340964025531357446706263871843489143068620501020284421781243879675292060268876353250854369189182926055204229002568224846436918153245720514450234433170717311083868591477186061896282790880850797471658321324127334704438430354844770131980049668516350774939625369909869906362174015628078258039638111064842324979997867746404806457329528690722757322373158670827203350590809390932986616805533168714686834174965211242863201076482127152571774960580915318022303418111346406295217571564155573765371519749325922145875128395909112254242027512400564855444101325427710643212690768272048881411988830011985059218048684311349415764441760364762942692722834850287985399559042457470942580456516395188637916303814055777357738894264037988945951468416861647204658893837753361851667573185920779272635885127149348845064478121843462789367112698673780005436144393573832498203659056909233757206537514290993810628872250841862059672570704733990716282248839
g=2
po = 312827656920665019052154527973062873164155435750834364099549354276600246039780808375717193869518770295806958147314654770520680676883270457649459743668787722703852223185610468575274145823739097462833932263058142549857140269637619269087411010174206045061016542198959480305747562269639856888526630582754886085323913120581662775122656234745332568520238838445916214100660745696922469287938919295619254972946705975683751437282135292172658670815955803075584269128554697234601952297591311295087027674743379383960411103043466786182497597866061129442701995358254124186369249520035589323173168805824570833282035445498782643378768358700682376307190201843700760320696872165065894961224809252051704551991788222733119953751476970741723581723530792919118911052397510799833080000512103966726938986113045128903532639271674853108472379556253636897190191182797552815462576549308131710191832665640046277651599574046021255652154555206626299039923531695289748325251163391286522402130644593746350983380447169395283756146065786333043918764637244487399476582803660120363329563190678655408546077633121456889790401760376550560489115040487451522266237283633048382172370079943143410743342217597309023634940063326550917247604702902550215759784529552401298569555386076473292117763682664669364246320241134117049920406912330431288119412796087737646208534116711021629494365386501930451907402808159838174943862279362834677757884050584093448170667659133693515258906880458166511868847468784977428190810086167564
I = Integers(p)
base =I(g)
power = I(po)
x = discrete_log(power,base,I.order()-1)
print x

可以计算出x为

1
406518553680923303810998357867089986872597384625428296032382082223605988123574210841218447069934463869653305779972123070300843700243223695683842745570568684988254542730892443975304109337441724302279618874884331668884226985266615045139866948788642830842298877192435129229769098933982345569684722762310667192130392534911466160274059969529107046199350538396064656112295906250939672478159817378079309441784880287725371781211748012877184256920210313871719115362010515515110891402855431658223334353873593303525395667978618326801978550187994124468270924013873572498432067645518118093443435418639520888364353499167897138949530744479663644999699224624773483099925521628862586180232198687320947503864600545302221833421275377235509032523457368609815918585758902481553859663387458618816129349463449419087862341088098652933968194993618037910771065808327330647298288575310835586890815804579122178907612697859270737899965594281906994558485264432034470368606167998120003373267066108968891036101743283670490035545481631859464049676062374641157466906693289719168834606604591256752463984131731185528958907446384032245887743211357901745111407737140995225229516243384229267475225313252051953270472323465728081856951111786989858395543299883339743470874543998207949716754885646487861907213598041410526482071904355862055436218492748770410795259787330776539666787777384878258553459788559880593421515430755132522925521857946949333624821971975459183239317332938414550857334189671635116967802683106640

getflag

得到私钥后,就是计算共享密钥再解密AES了,可以写出如下脚本

1
2
3
4
5
6
7
8
9
10
11
12
from Crypto.Cipher import AES
from hashlib import sha256

r=78087120192506798185304785534036220490682295457985899593552286015760906515956977310718106026282702809422711635619435917331518767851766791450692341186817654392039937276866732823290900777821010247327671241243643650412880368150333211471395035297424887127204256326908722464623917394462679939630749446410387197599335390520467029069728074767246541966424633680601615773218990609115018202108293891151991011803340952544552635132188415103709705346657970777043221314746732187471928545207308547177553542327264672520940226251888781036654093770411265925735389942610651694464713219676594471860313120475954809929673190737166098124441789345848214708040517022155838996124293848907006907419888109057810382829316850548709211468528812150512419577354250048007280565757975359757844819724279701194952271971968109182400983285949430466403580176579808358235196432047919412166611978194160383972820803839428543781819223102375217858138264186633827564726154084918862464617886404527934356701470162555172341817057875835953741671717748853387699781466740938591750994343486592410583776852328678921121336669128939343468165354791232165526407821586702774092562342825423846314736479769371630140795341485570538796652969642206321722350767458962990861456051369560315789943007263349872724565868324293287652102593428824637171300666426843580254096051705945897970157438347228211952956498549949387040740580715926063683264912465718505170513257955773741351861008670710537188992538116637590461265650926502662281478520940158
x=406518553680923303810998357867089986872597384625428296032382082223605988123574210841218447069934463869653305779972123070300843700243223695683842745570568684988254542730892443975304109337441724302279618874884331668884226985266615045139866948788642830842298877192435129229769098933982345569684722762310667192130392534911466160274059969529107046199350538396064656112295906250939672478159817378079309441784880287725371781211748012877184256920210313871719115362010515515110891402855431658223334353873593303525395667978618326801978550187994124468270924013873572498432067645518118093443435418639520888364353499167897138949530744479663644999699224624773483099925521628862586180232198687320947503864600545302221833421275377235509032523457368609815918585758902481553859663387458618816129349463449419087862341088098652933968194993618037910771065808327330647298288575310835586890815804579122178907612697859270737899965594281906994558485264432034470368606167998120003373267066108968891036101743283670490035545481631859464049676062374641157466906693289719168834606604591256752463984131731185528958907446384032245887743211357901745111407737140995225229516243384229267475225313252051953270472323465728081856951111786989858395543299883339743470874543998207949716754885646487861907213598041410526482071904355862055436218492748770410795259787330776539666787777384878258553459788559880593421515430755132522925521857946949333624821971975459183239317332938414550857334189671635116967802683106640
p=449703347709287328982446812318870158230369688625894307953604074502413258045265502496365998383562119915565080518077360839705004058211784369656486678307007348691991136610142919372779782779111507129101110674559235388392082113417306002050124215904803026894400155194275424834577942500150410440057660679460918645357376095613079720172148302097893734034788458122333816759162605888879531594217661921547293164281934920669935417080156833072528358511807757748554348615957977663784762124746554638152693469580761002437793837094101338408017407251986116589240523625340964025531357446706263871843489143068620501020284421781243879675292060268876353250854369189182926055204229002568224846436918153245720514450234433170717311083868591477186061896282790880850797471658321324127334704438430354844770131980049668516350774939625369909869906362174015628078258039638111064842324979997867746404806457329528690722757322373158670827203350590809390932986616805533168714686834174965211242863201076482127152571774960580915318022303418111346406295217571564155573765371519749325922145875128395909112254242027512400564855444101325427710643212690768272048881411988830011985059218048684311349415764441760364762942692722834850287985399559042457470942580456516395188637916303814055777357738894264037988945951468416861647204658893837753361851667573185920779272635885127149348845064478121843462789367112698673780005436144393573832498203659056909233757206537514290993810628872250841862059672570704733990716282248839
g=2
po=312827656920665019052154527973062873164155435750834364099549354276600246039780808375717193869518770295806958147314654770520680676883270457649459743668787722703852223185610468575274145823739097462833932263058142549857140269637619269087411010174206045061016542198959480305747562269639856888526630582754886085323913120581662775122656234745332568520238838445916214100660745696922469287938919295619254972946705975683751437282135292172658670815955803075584269128554697234601952297591311295087027674743379383960411103043466786182497597866061129442701995358254124186369249520035589323173168805824570833282035445498782643378768358700682376307190201843700760320696872165065894961224809252051704551991788222733119953751476970741723581723530792919118911052397510799833080000512103966726938986113045128903532639271674853108472379556253636897190191182797552815462576549308131710191832665640046277651599574046021255652154555206626299039923531695289748325251163391286522402130644593746350983380447169395283756146065786333043918764637244487399476582803660120363329563190678655408546077633121456889790401760376550560489115040487451522266237283633048382172370079943143410743342217597309023634940063326550917247604702902550215759784529552401298569555386076473292117763682664669364246320241134117049920406912330431288119412796087737646208534116711021629494365386501930451907402808159838174943862279362834677757884050584093448170667659133693515258906880458166511868847468784977428190810086167564
key = pow(r,x,p)
c = '0e10f06cc8a34a8b93d2f5afd2a32109413fc6c1bdf3985fa55a7427f5befb215afe920b4c9f1c5fd7cd8621eccbce74842474de9eab381535ca5a3d0d21d37a'
aes = AES.new(sha256(str(key).encode()).digest())
print aes.decrypt(c.decode('hex'))

运行后可得到flag

1
flag{2D7A22A4-68C9-46A9-A209-E5623917A864}

后记

这次pwnhub的crypto比以往简单不少……做完后甚至有点不敢相信……

1
文章首发于安全客
点击赞赏二维码,您的支持将鼓励我继续创作!
CATALOG
  1. 1. 前言
  2. 2. Happy Tree Friends
    1. 2.1. 题目概述
    2. 2.2. 漏洞点分析
    3. 2.3. 题目测试
    4. 2.4. payload
  3. 3. Farewell
    1. 3.1. 题目概述
    2. 3.2. Diffle-Hellman密钥交换算法
    3. 3.3. 私钥计算
    4. 3.4. getflag
  4. 4. 后记