VNCTF2024

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 2.8k 阅读时长 ≈ 10 分钟

记录2024VNCTF——Crypto部分题解

basiccry

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
import random 
from Crypto.Util.number import *
flag = b'********************************'
m = bytes_to_long(flag)

rr = matrix(ZZ,[random_vector(ZZ,256,0,2) for _ in range(256)])
mm = matrix(GF(2),[list(bin(m)[2:].rjust(256,'0'))]*256)
cc = mm+rr
ii = vector(ZZ,input("Undoubtedly, this is a backdoor left for you: ").split(","))
dd = rr*ii

print(cc)
print(dd)

我的解法

rr是个$256\times 256$的矩阵，其元素只有0和1

我这里用的是一个不太聪明的方式，分析如下：

假如我们要求m的第一位，只需令

此时

这样我们可以求得$r_{1,1}$，又因$cc$已知，便可求得$m_1 = c_{1,1} - r_{1,1}$

同理，因为flag是不会变的，一次nc确定一个m的值，只需要256次nc即可完成求解

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
from pwn import *
from tqdm import *
from Crypto.Util.number import *

context.log_level = 'debug'

m = []
for i in trange(256):
    sh = remote("manqiu.top",port)
    sh.recvuntil(b"Undoubtedly, this is a backdoor left for you:")
    print("Ok")
    msg = "0," * i + "1," + "0," * (254-i) + "0"
    sh.sendline(msg.encode())
    cc = []
    for j in range(256):
        c = sh.recvline().decode().strip().split(" ")
        cc.append(c)
    dd = eval(sh.recvline().decode())
    
    if "1" in cc[i][i]:
        mm = 1 ^ int(dd[i])
        m.append(str(mm))
        print(m)
    if "0" in cc[i][i]:
        mm = 0 ^ int(dd[i])
        m.append(str(mm))
        print(m)
        
print(m)
tmp = "".join(m)
flag = int(tmp,2)
print(long_to_bytes(flag))

我的预期是一次脚本就能把flag打出来，不过实际情况是脚本运行一段时间会出现卡顿，而且不运行下去，所以我分了几次跑。

然后把m拼接起来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import libnum
a = ['0', '1', '0', '1', '0', '1', '1', '0', '0', '1', '0', '0', '1', '1', '1', '0', '0', '1', '0', '0', '0', '0', '1', '1', '0']
b = ['1', '0', '1', '0', '1', '0', '0', '0', '1', '0', '0', '0', '1', '1', '0']
c = ['0', '1', '1', '1', '1', '0', '1', '1', '0', '1']
d = ['0', '0', '1', '0', '0', '0', '0', '0', '1', '1', '0', '1', '0', '0', '0', '1', '0', '1', '1', '1', '1', '1', '0', '1', '0', '1', '1', '1', '1', '1', '0', '0', '1', '1', '0', '0', '0', '1', '0', '1', '1', '0', '1', '1', '1', '0', '0', '1', '1', '0', '0', '1', '1', '1', '0', '1', '1', '1']
e = ['0', '1', '1', '1', '0', '1', '0', '1', '1', '1', '1', '1', '0', '1', '0', '1', '1', '1', '1', '1', '0', '1', '1', '0', '0']
f = ['1', '1', '1', '0', '1', '1', '0', '1', '0', '0', '0', '0', '1', '1', '1']
g = ['0', '1', '0', '0', '0', '1', '0', '1', '1', '1', '1', '1', '0', '1', '1', '1', '0', '0', '1', '1', '0', '1', '1', '0', '1']
h = ['0', '0', '1', '0', '1', '1', '0', '1', '1', '0', '1', '0', '1', '1', '1', '0', '0', '0', '0', '0', '0', '1', '1', '0', '0', '0', '0', '0', '1', '0', '1', '1', '1', '1', '1', '0', '1', '0', '1', '1', '1', '1', '1', '0', '0', '1', '1', '0', '1', '0', '0', '0', '1', '1']
i = ['0', '1', '1', '1', '0', '0', '1', '1', '1', '0', '1']
j = ['0', '0', '0', '0', '1', '0', '0', '0', '0', '1', '0', '1', '1', '1', '1', '1', '0']

m = a + b + c + d + e + f + g + h + i + j
mm = "".join(m) + "1"                 # 前面是255位的m,最后一位是0或1

mm = int(mm,2)
print(libnum.n2s(mm))
# VNCTF{H4__1ngw__ght_simp0__4nt!}

其他解法

因为对$ii$没有数值上的限制，可以输入一个超递增序列，然后解背包密码把$rr$求出来，再通过$cc$求解m

因没有复现环境，我自己跑了一组数据如下

输入ii

1
1396, 4208, 9033, 18993, 49667, 105450, 330619, 593253, 1876818, 3550691, 9529612, 28591711, 51988472, 132843784, 320774929, 598312683, 2181437722, 4514448112, 11033914127, 24717468900, 57170894226, 109232241484, 217765824089, 669361628365, 1537769405756, 5238736260364, 11517060106926, 33274554775748, 52987052874846, 200874642992442, 440036893056103, 1279532450657230, 2525383946646219, 6487425614066993, 18090859843634092, 33581802921810381, 67951262646090810, 236029764230241520, 371434770115377698, 1257356244869475435, 3256303138070771505, 7067073561936850474, 24127867434321267748, 60985644584045221455, 119966599001522700855, 323715115282447495963, 563638038251886152718, 1562758955137275436637, 4366897987962052857035, 10931883236137883071726, 22686730558819138388996, 68605157560030178338054, 147917636495124746879227, 439116283382708998463813, 1197370602526820848441882, 3526401183696005886706582, 9780886784726593647258031, 23108659457238292179141175, 50733650552337768257690350, 114047294672048167498357666, 343008530546716755443530729, 883065601710941166781920126, 1951735126256282162170890480, 3549294884090502286274162644, 12599090863023551555481356271, 22998501751026727274146362616, 75978819003210302788599527890, 184548098836386683631848249076, 362344598107921025881522365102, 1014540318649307346637507848227, 1724457743393683313892130153903, 3752021494648065847971667929160, 8751622531619676588802561141481, 21977521599899609397641556442745, 56967704655700565063507079582980, 130371146527115144972409118267261, 243940139195902064533590252835795, 504570175577858094170375658937401, 1724511362392632498069058434711317, 3175099681336126602307008601348384, 10766204612360101724080196876607024, 16852475506881520590161083280762900, 53627091171327834847005188824109238, 103561772296183675403952616457563989, 280026711851882808277765000086222626, 832910897579720658130004851924081363, 2023056473488121160945235651347869598, 5140555576735963362065957728276228493, 12645261191963611409256836348958880872, 38970952821426753891922880457616419362, 112842641108831754496521607659053791991, 226059631047279992651963964581729383372, 499628479648525277160451012145684475364, 1634950128476283254658756732538710073958, 4980395749000950620147743331684852327696, 10335453136180383147726205775759422895057, 19581332191317789908858753007087798921746, 39271215750319956436652373144379930411091, 100299643665664037163864768482253817359309, 246711383907850112229895867306471360562125, 659085788316744039471630164044941884580361, 1342383412223478867109569635929355655178877, 3183564035353894971423498947298281425469680, 6768961673865891723895059730064281706558792, 22140899671677402725807155257971240138886647, 65025814347530831297856724241218445844606709, 158626562691102593573919802703303965966900008, 405703178014513779902935604939052476404166632, 889783655242092473917914007377236047753162753, 2524771500590706096628247117655643561807433001, 4809685812091056451551423022288481965312117348, 13239034685098667988749044271345583171496780850, 27524985564892165868433157488875597649623380634, 58181836477172146276129852254435214620092584903, 110776737127202123072986976555115993410791454009, 254644089079357270019337865768698383189822043875, 623407507890594787639116324870725343406891807320, 1148793984731041978118136713837698836327882770797, 4087525652629843896766642135369600318893283784390, 9501068493863263682124944114777688508233668273420, 16629817170684466595505142295834036764908800859591, 40585163068514106417601809718068965504666394607912, 73617772169671271835826702629619993340070531996911, 224287533751078360583119827295823831400613980935009, 675454501297081806472980735293175693673331409583101, 1948424009539449362634985284321716255713031696809208, 5165924169549103078633555828696318421669501467077712, 15085526245609282031296558421648059435097206092412006, 27742725389037350446063660700423871789119957993662659, 74545054727451665407298035339270062917448215715381213, 201095158143046025148091208858720669100329869164722374, 517408115941707826996333553183210762099301710953203258, 1215860628641208373263960554358961852408725204335705656, 2654463570394906727196918545888042969753893082657862533, 7681022079627192503711156508760941066966325378185006591, 23013409522283546253799760953566246670119241043617591148, 63041022340388791607715952422971788763103966600404960549, 136118404665740917095029813853107313081064638944700649213, 444587265193875538344927650738980799534360182304040710333, 1094357761377718955537119975880349183873280543277596462260, 3450240054956124129710703405499009396656007378839062390091, 10209891896332339356030894124220861278668982815714128714576, 23064629583679521046483284866922804816353086304919998046346, 53800485907674446517137155096176902419153156507895442316580, 94938091647480556185173978850115238563185984992821915703136, 237018569884986183368856854061219384846573933420773970547637, 657034639440607458278193394927064207219732424874893288946723, 1986409584362267803630879282886865794904809854213270814598743, 5479555994470480976655157200378064978168240516967450342380270, 14028289842392460609314835100170682639027408282271967503501170, 43299640894866943409276932020279268246939906817298689024656187, 112008650531795992470538743246931031660469521104648058970172838, 256841167436075244654255600143138251703821673576743531259082198, 807502397701618218228927970764211170260611798959823551585216424, 1553548649694472662683768574008307685427817581266197612771248890, 3871581519809598477383461773083798139959661282123587280598568006, 12306372113499020019461392592648561836400035980327794522853142395, 35164787142454221307678561232946811153556210708112634293927580891, 99676752887622990620803966887696014281729180914435363186928642600, 187274443220683244592106305274818083316587901975054486960973190867, 514672460820049425594272397215632274315262932047802767310996194025, 1451445287606709203239645683797393286278494416348034514239761447758, 4545237132890480594199888930545580064256717464472819684566374839712, 8733806927824923268179548705169906162124844033045353745867314131106, 23508327099213710924374118129318034691079620574420355572642602563248, 64169484233107273069687718622993735689816613698275669061856648326812, 193800286160324528275217968716492996741953713190592244227245650275713, 300693933233365189914578527501457407617219233866651809346379549364496, 1063692878425981962862003278851844320614814486100147670662991626073163, 3292764323071081008157348761943500422582760458919351272862564755514328, 9854898053603986628900471050355061693018463464318902078969263841629827, 19491277392284263583409282556242664211492528273443441864516484522489692, 42162033947673464764591511766088777801599677413566738002708480129807895, 117999083106948001841902855986345682211441130802669968220017482276329843, 267400499515132937974019379180832975171764571483833779552598959217700363, 665929477975355057167044016795735252545506257497524808919475243048916946, 2090265018279850066893555555683226002631179739039566523724006893262704831, 4380087119828936820064940449726495597566358411993944860249066588467634367, 9302772118294473595467871339398001259659494520163782913777854350975309626, 26810270108999858670097631542384173452068118719038918882231114077750545199, 82956705039684723262478108973218126268564917814839345960860172000348283107, 244314689464730976405103973869640517259192834792012055610290496112844352498, 486946039289592872270110838236870768011124178185680401559097863527462677328, 1524403572056072758875269541786470760119425031226712991652119922056919068541, 4717693348968875808558416616339444736664394879149393002760222774379876534080, 11811210065385332505005018217011752947179752457845768841304402707275070095153, 27674815416990001674722330071247357021158950065804890901937999613928921000169, 50600450228729208399023812649812702084226012934974690643941648555360964450337, 129135076350773962562831284743064485820923981895676857107786633133662015256732, 385474108830013063399724503223968643774996980466866050045934726372989436094211, 1073972775376973890291287147158782007940781800239412873205529623243947084487382, 3026321900735861551530643076273790317430346518004598316273739400250714755501102, 8808564708245806164185386459205693876352822962950029860675920124403460619481586, 21289361469159862801975921997929932314917063196567060982169728918595911920233584, 47593454785239361287636766853909821738834509731779740290602137534795617625380899, 107885966877928840772362801611407770126627207379093998531699586813951970512624095, 378006145797383163113741497647226878741296952446150101884957466609041441843730839, 735064477320058688010077904642464696633772745609861205097851177824811247543089119, 2173701545664788939097738002795355418607061668801393448437527697449425013057958027, 4426369577763864454657195263581632901587082282230018877966226883085072371325380531, 8086290890753394233187420309155944807521331215862173116193314619137727050931542177, 29025484571612755829340179010324615354578730414170724617438437314481184648375434752, 68721970782980336031223510741560622708217861440769986855749119465893825242134835757, 210118953599975274542117334084644221761792428382746913795949244646643512249388789354, 341729432791517123058656497058849546221427854445130775789931806169747086970907339633, 1255087084927522350008153229778246395721935482770603157086138211580281326245476235990, 2910886948077374071828254513295256573141216006128492235842622692597630336642708036664, 5819709449653395387173177865277316829587268289729382133990571422055782023763084680074, 18254288327325259155322113251694714398772626025792186547988234845006979267833759150404, 47900867400302605970375108164796962168695967591150236707628531516665424493129807082999, 77479987551980516509148040996692980612342453310720546569524540637809930194632408285543, 215094201979798150057609162626301120613027396324513287451395995543336126054101845633335, 401482490482526700923662992856593321572433811088603437487229414577110166778430218795974, 925301165625120168237218861455924995228312429172102811427042815975954214474015923942520, 3148982916163888486282415722374034486491027540163958513646321893155595906794358605307100, 8821925580810847345434287808119040402476588923988279141485232087798468043870869756293984, 22287448826612734381691104388114834082235100246468068115293984158933011989430113965631581, 70521924884046115262927097999519900944065523742602182831538063628409845107584704690586721, 144168655507996893750155308590356882707304622671545211428519603955672901605857074956406444, 483058856835537827927931455385081967380016118669386876103186899775565293760859099805249905, 1341758243389282450564430609835244876417265065258116251706032604712069420703915539866503806, 3191585461364311155937948405492435654646188894504373173479750878809188276967084113157942064, 8080827103226255730867511151238940132016248515119779639367372683825316390906397691681252028, 14733797313773801107633302751046108842926907396956387202332906587432311010045391191440705047, 28249946931132442734053968790198383016123430769118179369226132446794741094309169329994088093, 110105345663043725619892519261685449301606107473014230647951487191656799936162697287654779735, 259462666625865005417224160166433604159955676990653598791590003920881950294125908527924810003, 612687669170439357514289486254557289422883445734024106079932208517446227751779248458773360366, 1044561566609347331288934270150898902117799451069900947736335685270484166967434778016851014695, 3354961827318183563311602181813482186826501088510635678604778441854371725525755277821822993113, 7447079969782857166270843577833420896010891504666715192507902492956138657545322594176456416288, 17415859995221030134437801673466872940040033560375759220564957965900090585941609157615031285960, 36794796189628198177255130676172787332671551579150458960096924052241835364171040295310097898386, 107915668472647429714078206951122028724413330893805539866211772445531289491217740346972368961342, 313170344771157987231360749803058023402820894866005664625571056064040966958520921094369827624879, 761903295933749580741175398799385249548884372898754366263986856072054166167795327827049210299870, 1489770819349942046462718373796175558687478047222486034991716709317867333143368368934483330500043, 3746520279068929145998035845012213721541817054513208351365961296449805613463288472802093110963411, 7628307216832111145743761091788686434244051331261674356745689279142162301727207887604921225836494, 17779792434338331127100610651545265266672124709811778812631206298698893300225618961624384999294089, 49223547532685765294266665604894143417978409709111181507034393546688099522581051555263869480661466, 145993621650016470176185717460995956637537560987740522007226097824863166935930645037806402817459156, 379042096053773104431459351467030516955004685593877345564046362472678091749403392570157167654902788, 775386004206754322768735188408655495305399839236379875401863294138521727184489354109718388734229925, 1612181488198834206052286261825139194705918604267063574527541202511977052400119461497482113730803754, 3131570630599143164695483580944133657516138814366996188560018659079192612390844819594441303570021961, 6633304058164339372805722801608656708308578253080137862393089792251234187799766578644149183173964996, 15379894142120235873858473283800206923249528144468195240123051080299809067158007207213425564563672003, 46529957385169040318484505470831327645925221683432207134836677670262087316702164483452826481084968963, 124271370153616999150303585449283172789342840531703923694368156547437372371315582173540280582373615233, 384349915889731767580323409780622332557978896828472100639132827842554723219721099958143122535428571545, 865761204863099789471062207889443517360907444794670718829686071526294635593738795906513498863423287846, 1715311138716981034265475755284384343633723979133320734721525157971729225130115014114455413341793483582, 5563392198988884145093813185808371687596040932844400119615411076776375727765194364480006126887585784032, 9487867567222420578180315147593921763707326987309974561205930341626893787368890376233824638621964232460, 27292067536638309915878711259377268785797442758770179990797733185545584229834829696415309714227221857723

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

flag = b"VNCTF{H4__1ngw__ght_simp0__4nt!}"
m = bytes_to_long(flag)

rr = matrix(ZZ,[random_vector(ZZ,256,0,2) for _ in range(256)])
mm = matrix(GF(2),[list(bin(m)[2:].rjust(256,'0'))]*256)
cc = mm+rr
ii = vector(ZZ,input("Undoubtedly, this is a backdoor left for you: ").split(","))
dd = rr*ii

# 以下是求解过程
key = list(ii)	#手动输
def get_rr(S):
    m = []
    for i in reversed(key):
        if S > i:
            m.append(1)
            S -= i
        else:
            m.append(0)
    return m

rr = get_rr(int(dd[0]))

rr = vector(ZZ,rr[::-1])
mm = cc[0] - rr

m = ""
for i in mm:
    m += str(i)
print(long_to_bytes(int(m,2)))
# \xd6NCTF{H4__1ngw__ght_simp0__4nt!}

有点瑕疵不知道为什么头不对

SignAhead

task.py

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
from hashlib import md5
from secret import flag
from secrets import token_bytes


ROUNDS = 100

successful_forge = 0

for i in range(ROUNDS):
    print(f'Round {i}')

    key = token_bytes(32)

    msg = token_bytes(64)

    sign = md5(key + msg).hexdigest()

    print('msg:', msg.hex())
    print('sign:', sign)

    print('FORGE ME!!!!')
    
    newmsg = bytes.fromhex(input('msg: '))
    newsign = input('sign: ').strip()

    assert msg != newmsg

    if md5(key + newmsg).hexdigest() == newsign:
        print('GREAT JOB')
        successful_forge += 1
    else:
        print('you failed!')

if successful_forge == ROUNDS:
    print('Here is your reward:', flag)
else:
    print('try harder next time !')

考点是哈希扩展长度攻击，哈希（Hash）长度扩展攻击_哈希长度拓展攻击-CSDN博客

MD5哈希碰撞之哈希长度拓展攻击 - 知乎 (zhihu.com)

攻击者只需要知道msg + key + msg的哈希值 + key的长度，即可完成攻击

网上找脚本

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
import hashlib
import math
from typing import Any, Dict, List
from pwn import *

rotate_amounts = [7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22,
                  5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20,
                  4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23,
                  6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21]

constants = [int(abs(math.sin(i + 1)) * 2 ** 32) & 0xFFFFFFFF for i in range(64)]

functions = 16 * [lambda b, c, d: (b & c) | (~b & d)] + \
            16 * [lambda b, c, d: (d & b) | (~d & c)] + \
            16 * [lambda b, c, d: b ^ c ^ d] + \
            16 * [lambda b, c, d: c ^ (b | ~d)]

index_functions = 16 * [lambda i: i] + \
                  16 * [lambda i: (5 * i + 1) % 16] + \
                  16 * [lambda i: (3 * i + 5) % 16] + \
                  16 * [lambda i: (7 * i) % 16]


def get_init_values(A: int = 0x67452301, B: int = 0xefcdab89, C: int = 0x98badcfe, D: int = 0x10325476) -> List[int]:
    return [A, B, C, D]


def left_rotate(x, amount):
    x &= 0xFFFFFFFF
    return ((x << amount) | (x >> (32 - amount))) & 0xFFFFFFFF


def padding_message(msg: bytes) -> bytes:
    """
    在MD5算法中，首先需要对输入信息进行填充，使其位长对512求余的结果等于448，并且填充必须进行，即使其位长对512求余的结果等于448。
    因此，信息的位长（Bits Length）将被扩展至N*512+448，N为一个非负整数，N可以是零。
    填充的方法如下：
        1) 在信息的后面填充一个1和无数个0，直到满足上面的条件时才停止用0对信息的填充。
        2) 在这个结果后面附加一个以64位二进制表示的填充前信息长度（单位为Bit），如果二进制表示的填充前信息长度超过64位，则取低64位。
    经过这两步的处理，信息的位长=N*512+448+64=(N+1）*512，即长度恰好是512的整数倍。这样做的原因是为满足后面处理中对信息长度的要求。
    """
    orig_len_in_bits = (8 * len(msg)) & 0xffffffffffffffff
    msg += bytes([0x80])
    while len(msg) % 64 != 56:
        msg += bytes([0x00])
    msg += orig_len_in_bits.to_bytes(8, byteorder = 'little')
    return msg


def md5(message: bytes, A: int = 0x67452301, B: int = 0xefcdab89, C: int = 0x98badcfe, D: int = 0x10325476) -> int:
    message = padding_message(message)
    hash_pieces = get_init_values(A, B, C, D)[:]
    for chunk_ofst in range(0, len(message), 64):
        a, b, c, d = hash_pieces
        chunk = message[chunk_ofst:chunk_ofst + 64]
        for i in range(64):
            f = functions[i](b, c, d)
            g = index_functions[i](i)
            to_rotate = a + f + constants[i] + int.from_bytes(chunk[4 * g:4 * g + 4], byteorder = 'little')
            new_b = (b + left_rotate(to_rotate, rotate_amounts[i])) & 0xFFFFFFFF
            a, b, c, d = d, new_b, b, c
        for i, val in enumerate([a, b, c, d]):
            hash_pieces[i] += val
            hash_pieces[i] &= 0xFFFFFFFF
    
    return sum(x << (32 * i) for i, x in enumerate(hash_pieces))


def md5_to_hex(digest: int) -> str:
    raw = digest.to_bytes(16, byteorder = 'little')
    return '{:032x}'.format(int.from_bytes(raw, byteorder = 'big'))


def get_md5(message: bytes, A: int = 0x67452301, B: int = 0xefcdab89, C: int = 0x98badcfe, D: int = 0x10325476) -> str:
    return md5_to_hex(md5(message, A, B, C, D))


def md5_attack(message: bytes, A: int = 0x67452301, B: int = 0xefcdab89, C: int = 0x98badcfe,
               D: int = 0x10325476) -> int:
    hash_pieces = get_init_values(A, B, C, D)[:]
    for chunk_ofst in range(0, len(message), 64):
        a, b, c, d = hash_pieces
        chunk = message[chunk_ofst:chunk_ofst + 64]
        for i in range(64):
            f = functions[i](b, c, d)
            g = index_functions[i](i)
            to_rotate = a + f + constants[i] + int.from_bytes(chunk[4 * g:4 * g + 4], byteorder = 'little')
            new_b = (b + left_rotate(to_rotate, rotate_amounts[i])) & 0xFFFFFFFF
            a, b, c, d = d, new_b, b, c
        for i, val in enumerate([a, b, c, d]):
            hash_pieces[i] += val
            hash_pieces[i] &= 0xFFFFFFFF
    
    return sum(x << (32 * i) for i, x in enumerate(hash_pieces))


def get_init_values_from_hash_str(real_hash: str) -> List[int]:
    """
    
    Args:
        real_hash: 真实的hash结算结果

    Returns: 哈希初始化值[A, B, C, D]

    """
    str_list: List[str] = [real_hash[i * 8:(i + 1) * 8] for i in range(4)]
    # 先按照小端字节序将十六进制字符串转换成整数，然后按照大端字节序重新读取这个数字
    return [int.from_bytes(int('0x' + s, 16).to_bytes(4, byteorder = 'little'), byteorder = 'big') for s in str_list]


def get_md5_attack_materials(origin_msg: bytes, key_len: int, real_hash: str, append_data: bytes) -> Dict[str, Any]:
    """
    
    Args:
        origin_msg: 原始的消息字节流
        key_len: 原始密钥（盐）的长度
        real_hash: 计算出的真实的hash值
        append_data: 需要添加的攻击数据

    Returns: 发起攻击需要的物料信息
        {
            'attack_fake_msg': bytes([...]),
            'attack_hash_value': str(a1b2c3d4...)
        }

    """
    init_values = get_init_values_from_hash_str(real_hash)
    # print(['{:08x}'.format(x) for x in init_values])
    # 只知道key的长度，不知道key的具体内容时，任意填充key的内容
    fake_key: bytes = bytes([0xff for _ in range(key_len)])
    # 计算出加了append_data后的真实填充数据
    finally_padded_attack_data = padding_message(padding_message(fake_key + origin_msg) + append_data)
    # 攻击者提前计算添加了攻击数据的哈希
    attack_hash_value = md5_to_hex(md5_attack(finally_padded_attack_data[len(padding_message(fake_key + origin_msg)):],
                                              A = init_values[0],
                                              B = init_values[1],
                                              C = init_values[2],
                                              D = init_values[3]))
    fake_padding_data = padding_message(fake_key + origin_msg)[len(fake_key + origin_msg):]
    attack_fake_msg = origin_msg + fake_padding_data + append_data
    return {'attack_fake_msg': attack_fake_msg, 'attack_hash_value': attack_hash_value}


sh = remote("manqiu.top",21535)
for i in range(100):
    sh.recvuntil(b"msg:")
    msg = bytes.fromhex(sh.recvline().strip().decode())
    sh.recvuntil(b"sign:")
    sign = sh.recvline().strip().decode()
    attack_data = b"attack data"
    
    attack_materials = get_md5_attack_materials(msg,32,sign,attack_data)
    newmsg = attack_materials['attack_fake_msg']
    newsign = attack_materials['attack_hash_value']
    sh.sendlineafter(b"msg:",newmsg.hex().encode())
    sh.sendlineafter(b"sign:",newsign.encode())
    
sh.interactive()
# VNCTF{append_key_instead_of_message#6603db4e}

利用的是get_md5_attack_materials()函数

msg代表服务器给的msg

32是key的长度

sign是服务器给出md5(key + msg)

attack_data是攻击者希望newmsg中包含这个字符(可以随便取)

basiclog

task.py

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
import signal
import os
import sys
import random
flag = "************************"

def timeout(*args):
    sys.exit(0)


q = 11769445852166501942131444325164359907623906505859865854871085543754710159882777389890225783970170353153967463136054852998337865848469266919651006863215539
p = 23538891704333003884262888650328719815247813011719731709742171087509420319765554779780451567940340706307934926272109705996675731696938533839302013726431079
g = 2

signal.signal(signal.SIGALRM, timeout)
signal.alarm(1800)

x = random.getrandbits(48)
y = pow(g, pow(g, x, q), p)
print(y)

try:
	_x = int(input('> '))
	if x == _x:
		print(flag)
	else:
		print("Error...")
except:
	exit(0)

题目要求在1800s内求解离散对数

直接用sagemath自带的函数是没那么快解出来的

从鸡块师傅那里学到一个方法：

在一般情况下，求解$g^{x} \equiv c \mod p$，假设这里x是48bit的数。

先令$x = a\times 2^{24} + b$

要求解$g^x \equiv c \mod p$，就是求解$g^{as + b}\equiv c \mod p$，$s = 2^{24}$

两边同时乘上$g^{-b}$得，$g^{as} \equiv c\times g^{-b} \mod p$

此时，我们把所有a和$g^{as}$这样一对值建立为字典。这里推荐像这样建立字典{$g^{as}$ : a}

这里a从0取值到$2^{24}$

然后b从$0$遍历到$2^{24}$，求$c\times g^{-b}$的值，如果这里的值能在上面建立的字典中找到，说明我们就有了$a,b$，也就有了x，即求解完成

对于这题，我们需要求解$y \equiv g^{g^x \mod q} \mod p$

令$x = as + b$，即$y \equiv g^{g^{as+b}\mod q} \mod p$

两边同时乘方$g^{-b}$得到

$y^{g^{-b}}\equiv g^{g^{as} \mod q} \mod p$

建立的字典即{$g^{g^{as \mod q}} \mod p$ : a}

随后爆破b

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
from tqdm import *
from gmpy2 import powmod,invert
from pwn import *
import random

table = {}

q = 11769445852166501942131444325164359907623906505859865854871085543754710159882777389890225783970170353153967463136054852998337865848469266919651006863215539
p = 23538891704333003884262888650328719815247813011719731709742171087509420319765554779780451567940340706307934926272109705996675731696938533839302013726431079
g = 2
s = 2**24

for a in trange(2**24):
    key = powmod(g,powmod(g,a*s,q),p)
    value = a
    table[key] = value

sh = remote(host,port)
y = int(sh.recvline().strip().decode())

for b in trange(1,2**24):
    temp = powmod(y,powmod(g,-b,q),p)
    if temp in table.keys():
        a = table[temp]
        x = a*s + b
        print(f"x = {x}")
        sh.sendline(str(x).encode())
        sh.interactive()
        # VNCTF{BSGS_1s_a_BaSIc_AlGOrIThM_and_NeeD_S0mE_OPTIm1ZAT1ON}

在计算key的时候用powmod会比pow快不少，大概20分钟能把字典建立完。

这边建议先把字典建立完之后再nc。

-------------已经到底啦！-------------