pwnhub crypto学习

Twings师傅给本菜鸡推荐了Pwnhub的两道Crypto，于是本菜鸡去研究了一下

题目一

题目很短，如下：

#!/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())

解读一下源码就是，接收用户输入的值，将输入值与flag放在一起使用zlib进行压缩，对压缩结果进行padding，再进行AES加密然后返回加密结果。

一开始以为是单纯的AES，想着对其进行攻击，但是只可控明文，不太靠谱，于是考虑zlib压缩算法

zlib压缩算法详情：https://blog.csdn.net/wtyqm/article/details/7294242

文章重点是：

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{ajfh9409248}'
data1 = 'flag'
data1 = "message: %s, flag: %s" % (data1, flag)
data2 = 'jklj'
data2 = "message: %s, flag: %s" % (data2, flag)
print len(zlib.compress(data1.encode()))
print len(zlib.compress(data2.encode()))

也就是说当输入的值中存在与flag相同的字符时，压缩结果将会变短，这就存在一种叫做侧信道攻击的方法：

https://www.sjoerdlangkemper.nl/2016/08/23/compression-side-channel-attacks/

import zlib
flag = 'flag{ajfh9409248}'
data1 = 'flag'
data1 = "message: %s, flag: %s" % (data1, flag)
data2 = 'flag{ajfh'
data2 = "message: %s, flag: %s" % (data2, flag)
data3 = 'flag{ajfh94092'
data3 = "message: %s, flag: %s" % (data3, flag)
print len(zlib.compress(data1.encode()))
print len(zlib.compress(data2.encode()))
print len(zlib.compress(data3.encode()))

但是同时我们发现，当我们知道前面的字符的时候，当后面的字符一旦匹配，长度始终为最小值，即38。这样的话，如果flag的开头为flag{，那我们就可以一个一个匹配，寻找长度为最短值的字符

测试题目

发现如果是与flag一致的话，则长度为129，否则为161，脚本如下：

from pwn import *
import string

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

但是跑完只得到

flag{de12473b-

由于有aes，输入得太长，压缩变短后再加密也会变长，后面的字母跑出来长度都是161，所以得三个三个一起爆，同时发现flag和de12返回的结果不一样，尽管两个字符串都属于flag，但是在data中flag出现的次数多了一次，因此这里需要构造一个padding

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

改进脚本：

from pwn import *
import string

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

题目二

这个题目也很短，如下：

#!/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，同时，在流量包中发现了如下值：

str(pow(g, x, p)).encode()

312827656920665019052154527973062873164155435750834364099549354276600246039780808375717193869518770295806958147314654770520680676883270457649459743668787722703852223185610468575274145823739097462833932263058142549857140269637619269087411010174206045061016542198959480305747562269639856888526630582754886085323913120581662775122656234745332568520238838445916214100660745696922469287938919295619254972946705975683751437282135292172658670815955803075584269128554697234601952297591311295087027674743379383960411103043466786182497597866061129442701995358254124186369249520035589323173168805824570833282035445498782643378768358700682376307190201843700760320696872165065894961224809252051704551991788222733119953751476970741723581723530792919118911052397510799833080000512103966726938986113045128903532639271674853108472379556253636897190191182797552815462576549308131710191832665640046277651599574046021255652154555206626299039923531695289748325251163391286522402130644593746350983380447169395283756146065786333043918764637244487399476582803660120363329563190678655408546077633121456889790401760376550560489115040487451522266237283633048382172370079943143410743342217597309023634940063326550917247604702902550215759784529552401298569555386076473292117763682664669364246320241134117049920406912330431288119412796087737646208534116711021629494365386501930451907402808159838174943862279362834677757884050584093448170667659133693515258906880458166511868847468784977428190810086167564

r

78087120192506798185304785534036220490682295457985899593552286015760906515956977310718106026282702809422711635619435917331518767851766791450692341186817654392039937276866732823290900777821010247327671241243643650412880368150333211471395035297424887127204256326908722464623917394462679939630749446410387197599335390520467029069728074767246541966424633680601615773218990609115018202108293891151991011803340952544552635132188415103709705346657970777043221314746732187471928545207308547177553542327264672520940226251888781036654093770411265925735389942610651694464713219676594471860313120475954809929673190737166098124441789345848214708040517022155838996124293848907006907419888109057810382829316850548709211468528812150512419577354250048007280565757975359757844819724279701194952271971968109182400983285949430466403580176579808358235196432047919412166611978194160383972820803839428543781819223102375217858138264186633827564726154084918862464617886404527934356701470162555172341817057875835953741671717748853387699781466740938591750994343486592410583776852328678921121336669128939343468165354791232165526407821586702774092562342825423846314736479769371630140795341485570538796652969642206321722350767458962990861456051369560315789943007263349872724565868324293287652102593428824637171300666426843580254096051705945897970157438347228211952956498549949387040740580715926063683264912465718505170513257955773741351861008670710537188992538116637590461265650926502662281478520940158

aes.encrypt(flag)

0e10f06cc8a34a8b93d2f5afd2a32109413fc6c1bdf3985fa55a7427f5befb215afe920b4c9f1c5fd7cd8621eccbce74842474de9eab381535ca5a3d0d21d37a

Diffle-Hellman密钥交换算法

原理：

• Alice和Bob先对p 和g达成一致，而且公开出来
• Alice取一个私密的整数x，发给Bob 计算结果：C1 = g ^ x mod p
• Bob 取一私密的整数y，发给Alice计算结果：C2 = g ^ y mod p
• Alice计算S = C2 ^ x mod p = (g ^ y) ^ a mod p = g ^ (x * y) mod p
• Bob计算S1 = C1 ^ y mod p = (g ^ z) ^ y mod p = g ^ (x * y) mod p

即S = S1

这里我们知道p、g的值，同时知道了g ^ x mod p的值和r的值，只要我们通过g ^ x mod p计算出x，就可以利用r ^ x mod p得到key

计算x

#!/usr/bin/env sage
# coding=utf-8
from sage.all import *

p = 449703347709287328982446812318870158230369688625894307953604074502413258045265502496365998383562119915565080518077360839705004058211784369656486678307007348691991136610142919372779782779111507129101110674559235388392082113417306002050124215904803026894400155194275424834577942500150410440057660679460918645357376095613079720172148302097893734034788458122333816759162605888879531594217661921547293164281934920669935417080156833072528358511807757748554348615957977663784762124746554638152693469580761002437793837094101338408017407251986116589240523625340964025531357446706263871843489143068620501020284421781243879675292060268876353250854369189182926055204229002568224846436918153245720514450234433170717311083868591477186061896282790880850797471658321324127334704438430354844770131980049668516350774939625369909869906362174015628078258039638111064842324979997867746404806457329528690722757322373158670827203350590809390932986616805533168714686834174965211242863201076482127152571774960580915318022303418111346406295217571564155573765371519749325922145875128395909112254242027512400564855444101325427710643212690768272048881411988830011985059218048684311349415764441760364762942692722834850287985399559042457470942580456516395188637916303814055777357738894264037988945951468416861647204658893837753361851667573185920779272635885127149348845064478121843462789367112698673780005436144393573832498203659056909233757206537514290993810628872250841862059672570704733990716282248839
g = 2
y = 312827656920665019052154527973062873164155435750834364099549354276600246039780808375717193869518770295806958147314654770520680676883270457649459743668787722703852223185610468575274145823739097462833932263058142549857140269637619269087411010174206045061016542198959480305747562269639856888526630582754886085323913120581662775122656234745332568520238838445916214100660745696922469287938919295619254972946705975683751437282135292172658670815955803075584269128554697234601952297591311295087027674743379383960411103043466786182497597866061129442701995358254124186369249520035589323173168805824570833282035445498782643378768358700682376307190201843700760320696872165065894961224809252051704551991788222733119953751476970741723581723530792919118911052397510799833080000512103966726938986113045128903532639271674853108472379556253636897190191182797552815462576549308131710191832665640046277651599574046021255652154555206626299039923531695289748325251163391286522402130644593746350983380447169395283756146065786333043918764637244487399476582803660120363329563190678655408546077633121456889790401760376550560489115040487451522266237283633048382172370079943143410743342217597309023634940063326550917247604702902550215759784529552401298569555386076473292117763682664669364246320241134117049920406912330431288119412796087737646208534116711021629494365386501930451907402808159838174943862279362834677757884050584093448170667659133693515258906880458166511868847468784977428190810086167564

I = Integers(p)
base =I(g)
power = I(y)
x = discrete_log(power,base,I.order()-1)
print x

得到x

406518553680923303810998357867089986872597384625428296032382082223605988123574210841218447069934463869653305779972123070300843700243223695683842745570568684988254542730892443975304109337441724302279618874884331668884226985266615045139866948788642830842298877192435129229769098933982345569684722762310667192130392534911466160274059969529107046199350538396064656112295906250939672478159817378079309441784880287725371781211748012877184256920210313871719115362010515515110891402855431658223334353873593303525395667978618326801978550187994124468270924013873572498432067645518118093443435418639520888364353499167897138949530744479663644999699224624773483099925521628862586180232198687320947503864600545302221833421275377235509032523457368609815918585758902481553859663387458618816129349463449419087862341088098652933968194993618037910771065808327330647298288575310835586890815804579122178907612697859270737899965594281906994558485264432034470368606167998120003373267066108968891036101743283670490035545481631859464049676062374641157466906693289719168834606604591256752463984131731185528958907446384032245887743211357901745111407737140995225229516243384229267475225313252051953270472323465728081856951111786989858395543299883339743470874543998207949716754885646487861907213598041410526482071904355862055436218492748770410795259787330776539666787777384878258553459788559880593421515430755132522925521857946949333624821971975459183239317332938414550857334189671635116967802683106640

getflag，decode.py

#!/usr/bin/env python

from Crypto.Cipher import AES
from hashlib import sha256

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