Pwnhub & Always be with U & Writeup

 

前言

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

 

Happy Tree Friends

题目概述

拿到题目

#!/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值的三个字符的下标)，检查是否是有效匹配。可以将查找过程理解为一个查字典的过程，只不过这个字典的条目也是处理过程中逐渐生成、逐渐抛弃的。
我们编写测试脚本可以发现

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位匹配，寻找长度为最短值的字符即可

题目测试

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

flag
496f7e60ae407bb1020fc5d97898270cec9c8495cf0ca52d93d3dd74d4ae8cb0732dd45736a79ec8f921cd9cc893c08eb250f54ca27c1bf5e74b69fdcfef7ba4

flag{
bfe7b29ddccb4d0b4e538f224247801fdc9d8a518070cc38527152f1237cb6b96f22d30de1d7658bd71513bf1fcc58c950114a5c1c25907087d599fd83ef7a83

flag{a
b8c5ce562800a8209ddc31527a76758a50568cd51d256730be9ba0850cdaeae092656f305a92d1ff6bea09ea25745067aa27e16003acdf9e8a599f296d43b4b8d326ac1a9176be5ebc2866f8eb75ab56

flag{b
6a2b03216022caa3d7958767a86ef304858e9bf3e7303df3d27deaad6a9ddfa2603ee16dfe9b6b967805a527dd944a508d81b56a1bf32e4ea770b1334b17b6e17b93d95badb2429bf0f1a591c7cd914d

flag{c
ebfd61a158e220ce16fd53b31c1e4e67df928a883b187c66c98be71f11cf43df1abe6cfd3365da603c92beaa8e30c23cb94d420c8d392fa6b457369263e35bb0847a116cb31135ea57e6bcf18a083e42

flag{d
aef61242ad1cf6f7b645b73c486df9d9a8985eeb38c7c4e16d71c19b9ed05cf6def29c3c236ed126af90f2c467507a3a3b4fecdb4129f257bf567935f43e2b84

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

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

但发现跑完只得到

flag{de12473b-

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

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

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

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

flag{de12473b-

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

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

发现长度明显不同

于是将脚本进行改进。

payload

编写出如下脚本

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

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

 

Farewell

题目概述

拿到题目后

#!/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，以及在流量包中有如下值

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;
其中值得注意的是

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

即

k=k*

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

g^x mod p

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

r^x mod p

计算出共享密钥k

私钥计算

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

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为

406518553680923303810998357867089986872597384625428296032382082223605988123574210841218447069934463869653305779972123070300843700243223695683842745570568684988254542730892443975304109337441724302279618874884331668884226985266615045139866948788642830842298877192435129229769098933982345569684722762310667192130392534911466160274059969529107046199350538396064656112295906250939672478159817378079309441784880287725371781211748012877184256920210313871719115362010515515110891402855431658223334353873593303525395667978618326801978550187994124468270924013873572498432067645518118093443435418639520888364353499167897138949530744479663644999699224624773483099925521628862586180232198687320947503864600545302221833421275377235509032523457368609815918585758902481553859663387458618816129349463449419087862341088098652933968194993618037910771065808327330647298288575310835586890815804579122178907612697859270737899965594281906994558485264432034470368606167998120003373267066108968891036101743283670490035545481631859464049676062374641157466906693289719168834606604591256752463984131731185528958907446384032245887743211357901745111407737140995225229516243384229267475225313252051953270472323465728081856951111786989858395543299883339743470874543998207949716754885646487861907213598041410526482071904355862055436218492748770410795259787330776539666787777384878258553459788559880593421515430755132522925521857946949333624821971975459183239317332938414550857334189671635116967802683106640

getflag

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

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

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

 

后记

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