SECT CTF crypto Gsh思路分享
SECT CTF crypto Gsh 思路分享
@(思路)[AES-ECB][hash forge][高斯消元]
题目描述：
About last night...
Service: nc 178.128.171.133 3333 | nc crypto.sect.ctf.rocks 3333
Download: gsh.tar.gz
Author: grocid
这道题是grocid出的，一直看着大佬的分享，在这谢谢大佬。
reddit.txt
Submitted 2 months ago by [deleted] to /r/infoleaks
I tried to login... was able to get a shell, but as a restricted user.
It seems horrendously badly configured. Which is what I would've expected.
Fortunately, I found a source code from an old unencrypted backup drive...
this one's particularly interesting...
class AESHash(object):
def __init__(self, key):
self.bs = 16
self.key = hashlib.sha256(key.encode()).digest()
def _pkcs7pad(self, s, blksize=16):
missing = abs(len(s) - (len(s) / blksize + 1) * blksize)
return s + (chr(missing) * missing)
def digest(self, user, password):
cipher = AES.new(self.key, AES.MODE_ECB)
q = 0
data = self._pkcs7pad(user + password)
for i in xrange(0, len(data), self.bs):
block = data[i:i + self.bs]
q ^= int(cipher.encrypt(block).encode("hex"), 0x10)
return q
Their authentication mechanism uses some weird keyed AES-based MAC -- I've
never seen anything like it before. I'd say it's insecure, but I don't know
how to exploit it. Also, it's written in Python. Really?
Since the HMAC combines credentials in the following way... it's kind of
moot to give it a try. I've learnt from one-oh-one that h(message | key) is
secure... I think. Motherf... I'll give up; it's late and I need to go to
sleep... over and out. For now.
-- JD
The revolution will not be televised.信息搜集
reddit上找了一通，没线索。那nc过去看看：
root@bin:/mnt/hgfs/CTF# nc 178.128.171.133 3333
Login (leave empty to create)
user:
Creating new user
user: 2
password:
IO error: cannot write 2:b5bbe950b1f52310ec0f986f4aeacbbb to /etc/shadow.
Logged in as 2
$ ls
-rw-r--r-- 1 admin staff 27 Sep 5 19:31 flag.txt
-rw------- 1 admin staff 27 Sep 5 19:31 invoice.xls
$ cat flag.txt
-[--->+<]>--.[->+++++++<]>.--.>-[--->+<]>-.--[-->+++<]>.-------.------------.[-->+<]>---.[--->++<]>---.++[->+++<]>.+[-->+<]>+.[--->++<]>---.++[->+++<]>.[--->+<]>---.>-[----->+<]>.+.++[->++<]>.-------------.+++++++.++++++.-----------.++++++.--------.+[-->+<]>+.-[->++<]>-.---------------.[--->+<]>++.--[->+++++<]>.[----->+<]>---.----.++++++++++.>-[----->+<]>.>--[-->+++<]>.
$ cat /etc/shadow
admin:8f643bbafa959617b12b591f3145e5c0brainfuck 得到flag:SECT{th1s_1s_r34l_flag_1_Pr0mis3}.喵喵喵？提交是fake flag。
分析
class AESHash(object):
def __init__(self, key):
self.bs = 16
self.key = hashlib.sha256(key.encode()).digest()
def _pkcs7pad(self, s, blksize=16):
missing = abs(len(s) - (len(s) / blksize + 1) * blksize)
return s + (chr(missing) * missing)
def digest(self, user, password):
cipher = AES.new(self.key, AES.MODE_ECB)
q = 0
data = self._pkcs7pad(user + password)
for i in xrange(0, len(data), self.bs):
block = data[i:i + self.bs]
q ^= int(cipher.encrypt(block).encode("hex"), 0x10)
return q
题目提供了加密的oracle,可以任意_pkcs7pad(username+password)的AES-ECB hash,我们的目的是伪造出hash为8f643bbafa959617b12b591f3145e5c0的一串字符。
密码是弱密码？
要不用rockyou.txt爆破试试？
爆破了一段时间，主办方检测到了，，提示：不必用admin登陆
AES-ECB, 我们能得到任意对plaintext-ciphertext.然后恢复出16byte的Key，目前计算能力还不可能,参考
那接着想...
q ^= int(cipher.encrypt(block).encode("hex"), 0x10)
我们可以得到一定长度(>=128)的list,则我们需要的8f643bbafa959617b12b591f3145e5c0一定在这个list的sublist的xor里,子串的空间远大于目标大小。
In [15]: a = 0
In [16]: b = 200
In [17]: for i in range(1,200):
...: a+=math.factorial(200)/(math.factorial(200-i)*math.factorial(i))
...:
...:
In [18]: print a
1606938044258990275541962092341162602522202993782792835301374
In [19]: a>n#n=0x8f643bbafa959617b12b591f3145e5c0
Out[19]: True
In [20]: a//n
Out[20]: 4722366482869645213695L
因为目标hash的长度为128bit,我们得到128对(plaintext-ciphertext)就能在ciphertext的子集里xor后得到目标hash.
这里想到了背包求解,构造着发现xor不能放入矩阵中，又不是超递增序列，xd,放弃。
换方向，要不是算法？
google看看
动态规划？
试了试，放弃了，空间换时间，但是需要的空间太大了。
bingo
128bit xor？高斯消元问题(我好菜啊)
转换成128个mod2的方程，生成方程脚本。
pubKey = [113602217935607289453201245405212005384L, 269903559201925776990330113614440744455L, 241565958944381636901648516767764106171L, 293672457538477642706410811981171228129L, 272079616170753890530117150285282929599L, 269802233640074548208254108223689761648L, 32133977644431573130477059196438070444L, 168481870008700738830294105175750796933L, 334922603314748487392344955780653300791L, 229414278903494832894227239178044704871L, 314703640767546154017347102168549516178L, 229972393494801775976797693407437555074L, 125452168836448551076922910806630459951L, 262636539008753216495347364077806328737L, 303348595956025858261652430594209650251L, 132672121569498985439667061816466777526L, 89476347243353865055927706682672438996L, 286115169586201751228609487648065866581L, 38893596458691279680158477802167839522L, 110805151320319006854019117500520175271L, 217194583637807804833392150804070536402L, 283037099573651336758040780021200142310L, 7196865238995195499778618888341499355L, 284856974763903941648686303990344767756L, 46821015876162010421748088382302560276L, 45388127152583280472844240800679060217L, 146834781513464544824789678632912373136L, 310644875230998320116732885820655222497L, 131576182487433797424666312540180389984L, 171632252297102443689664876555372193475L, 317207614102114190031478247173880580720L, 2019229043570815776979555681544956730L, 245332635870108819924360320160703080019L, 239746812010932291984386741568646528638L, 228150701255382534989917544119797599448L, 185329463144774238518171826187628783159L, 158422852548138928063071348282524371388L, 158047794225017117130631522128526938570L, 90002203713415179765155403291211983672L, 76183402577795977133563149834619010424L, 327033792199131907487376336916299010622L, 118110037947296269297522351912372815433L, 321331302318616639237472643742369122434L, 289871679349655287280426454891864460350L, 75896741940518641522389176253255931779L, 197528980393672022096646323382660721736L, 115267970274030551815131740534349838092L, 49128996804450313910781079594870471752L, 123453828800152009102665156279329464542L, 130762113187729390222390303095979243117L, 61962357689242046630039464984615623418L, 140348449816079277411275534159670289956L, 33935328799922823116297326841875084885L, 35446070094974416393317951914222282384L, 140292576835520415898099759285324407527L, 147146547617559489772915310720919332096L, 89646310806806036514713906069580365796L, 146874883014409295818531141503483994057L, 215437059004110248276750706046950925500L, 188221500525429520226503459794681179563L, 107972196836043571189384335713705530585L, 319718467664145050267908415211752615178L, 33790415791374444635822170504733312663L, 268800796979802432176455203809128526484L, 80514653928319629483719911526029943056L, 135353781885361716043230856191705908194L, 248180642408496061561454976433206893558L, 167655055161390482231544772656939164871L, 190331929667729623461110734835852719728L, 187872543812390919449231797787200390383L, 731101207891086255367024962539452869L, 331480993999803516069715352266054794594L, 85051118383149231027697337373798989241L, 47155605115554939334278125433372864400L, 121571815342736079022184219812503381803L, 263897155994150599327720693337921055396L, 54773392672203757877373626108902217120L, 138230004851931690176273198756282683622L, 283961092605567520993276283761367292625L, 287427965518330255286468485630091923645L, 46048869046414685264563278604990544304L, 243992658215021478151816473612407007169L, 338863296884167753624774150576543762901L, 249144433185189696822461918937843402675L, 174818984157084863003810504402963987843L, 49928437897272681604945166345382507316L, 169811917566691913816282203750125937825L, 248050233964070849706166860569612457954L, 1520258942159896323411963668751448396L, 333903589113355008603671520689640095324L, 337283667498635266986955607930131881010L, 197275029571731159274404014534356327324L, 129127001502279772254983153277368979360L, 177664913726081238004970583318541857889L, 85345496984135463087607716053977274319L, 91067168265864964696323804190072902614L, 192313254602131543459595847451029739619L, 112569030115633226287082881409522972259L, 150001238724700829259323667615673880452L, 78068730795594359467947320547021453088L, 164343369109346155112267741409523371420L, 228295673936931267244009383358414484278L, 66434581323900441939497595202767346873L, 312252109240210724403681095721447485886L, 179536901124859573787240720578905054392L, 265439400460700457940046726125324252004L, 241729208168572831927145640303669387214L, 224337267414262612853089595775967279611L, 211673272870623245856836660056154165887L, 88864449641825470063121187794230717364L, 73583051201515982281955717688769709645L, 260362752765785315958751287873241950198L, 52643190122666891387028838978738517195L, 154358808680938772019044733343352311407L, 196770985680500542539525268347680436167L, 328641879029504610590589570948678125864L, 24055869246749042499776225701332337057L, 38962078756404369905292170184025166626L, 170464594782261344004111979932874732922L, 232969215105220038515319207645195415802L, 208232609530347149967744742865898294226L, 275011224471984173494987769795990207177L, 308448887477339611643764297681803645311L, 39333230010553686835704431573974868722L, 280137539273739588435755948932899843402L, 253559907074997393930500823898473019197L, 125435856573771157299386612169553004907L, 115668627810610406030382750471801939809L, 23014601533775013085562579636743156201L, 11638513728055365905389210485318791555L,98597860941506298802187660394195423776L, 304512308993000256655319287612711900807L, 14613834564922699655380962015367927765L, 246925452458798984849277761651527906021L, 163938503868483016450886771295612831911L, 109796792849187331500478984080856610695L, 199759177923708969317747029879348989258L, 331339365629637604448480638753676331661L, 12422981147352332285955737972268754463L, 332030753925344401561153559659396583657L]
target = 0x8f643bbafa959617b12b591f3145e5c0
pubKey = pubKey[:128]
def _pkcs7pad(s, blksize=16):
missing = abs(len(s) - (len(s) / blksize + 1) * blksize)
return s + (chr(missing) * missing)
print len(pubKey)
for i in range(0,128):
txt = ""
for j in pubKey:
if bin(j)[2:].zfill(128)[i] =="1":
txt+="a"+str(pubKey.index(j))+"+"
txt= txt[:-1]+"=="+bin(target)[2:].zfill(128)[i]
print txt
这里我用wolfram mathematics求解(脚本见附件)
从结果可知，多解，C[1]为0，1均可，这里我取c[1]=0，得到了一组sublist :out = [2,4,5,9,10,11,12,13,16,17,22,24,27,28,30,31,32,35,36,38,40,43,45,47,48,49,51,52,54,57,59,62,63,64,68,71,73,75,79,80,81,87,89,90,92,93,94,97,98,99,101,103,105,106,111,115,116,117,118,120,121,122,123,124,126,127]
验证结果：
In [71]: print a
[0, 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, 35, 36, 38, 40, 43, 45, 47, 48, 49, 51, 52, 54, 57, 59, 62, 63, 64, 68, 71, 73, 75, 79, 80, 81, 87, 89, 90, 92, 93, 94, 97, 98, 99, 101, 103, 105, 106, 111, 115, 116, 117, 118, 120, 121, 122, 123, 124, 126, 127]
In [72]: a= [2,4,5,9,10,11,12,13,16,17,22,24,27,28,30,31,32,35,36,38,40,43,45,47
...: ,48,49,51,52,54,57,59,62,63,64,68,71,73,75,79,80,81,87,89,90,92,93,94,9
...: 7,98,99,101,103,105,106,111,115,116,117,118,120,121,122,123,124,126,127
...: ]
In [73]:
In [73]: txt=0
...: for i in a:
...: txt^=pubKey[i]
...:
In [74]:
In [74]: print hex(txt)
0x8f643bbafa959617b12b591f3145e5c0L
求解:
from pwn import *
context.log_level = "debug"
# f = open("rockyou.txt","rb").read().split("\n")[::-1]
test = []
def _pkcs7pad(s, blksize):
missing = abs(len(s) - (len(s) / blksize + 1) * blksize)
return s + (chr(missing) * missing)
out = [2,4,5,9,10,11,12,13,16,17,22,24,27,28,30,31,32,35,36,38,40,43,45,47,48,49,51,52,54,57,59,62,63,64,68,71,73,75,79,80,81,87,89,90,92,93,94,97,98,99,101,103,105,106,111,115,116,117,118,120,121,122,123,124,126,127]
aeshash = ""
for i in out[:-1]:
aeshash+=_pkcs7pad(str(i),16)
aeshash+=str(out[-1])
print len(aeshash)
print repr(aeshash)
for i in range(130,140):
io = remote("178.128.171.133", 3333)
io.recvuntil("user: ")
# io.sendline()
# io.recvuntil("user: ")
io.sendline(aeshash)
io.recvuntil("password: ")
io.sendline()
data = io.recvuntil("Logged in as")
io.interactive()
# $ cat invoice.xls
[DEBUG] Sent 0x10 bytes:
'cat invoice.xls\n'
[DEBUG] Received 0x24 bytes:
'SECT{...1_w4s_ly1ng_0f_c0urse_LuLz}\n'
SECT{...1_w4s_ly1ng_0f_c0urse_LuLz}
[DEBUG] Received 0x2 bytes:
'# '
# $
总结: 算法需要加强，怼题不能放弃，不要以分数为目的而不停的换题做。
gsh-solve.zip
(0.012 MB) 下载附件