BUAACTF2023 Crypto WP

admin
admin
admin
137432
文章
113
评论
2024年8月15日16:27:37评论23 views字数 23102阅读77分0秒阅读模式

BUAACTF2023 Crypto WP

ASR

from sage.all import *
from Crypto.Util.number import *
from gmpy2 import iroot
from libnum import *
from random import *
# 下面获取flag1
n = 22435848699656439430048260540176288030655042508109245348203445122056847876996607608611892056743501586488889168983607278397416470209194916985023908893310155270591748740126867248701139828665276853343163829939990987331026735495951912477601815131279382932153740508597542224648089775796802134745882144397328618204142989152751641372904445512671873582920538213880923397228305140234250303290009967109582828057519833587016281762379014389003814474573177719458550439800992452142920397237367310205204735952714220809997458836826342346730887267026568707643698737124998719830204084696971082358216392528426050106025032379139014423321
d = 20354412116269121510293104896444513282005945339570286117350965660612526671760792060149535621835144680437831770002273112374629994999457819337059141393701114761393145922236289855875677570566105500947768981625176573702001333986589568805832548629673255421091601642011486973263101325101577385857213692790105959115036385282675843417550399809724681031192529462528642112438295398315448676494393444923898200165689737396930202324686274876268952582257404549544075682059970937186448224276371016928222330204265425683795781628651310585874703339472767170154876297183452730676130031932279053647967819682281776997897365217554415144033
e = 8545970560619293415863869061629533131353052726527575105498824066096173134202176407771698168891393791901508803718121936403456285176580496345915728675609872087314945931309067503425183949923543095686689494879877359916226960617400586139116144067054907570518268413146641607525379529898998165978606786256497
c = 17208039537612825516747747878451966796120839641453197811745943450387215029980143252298866765386258366964704956107202728668453189436311383104017230316824503104192120754592188140860077450499901758898311008990707821123572736111805013388976133948732183654932878173674813982349517829145629555764948009535371050231553730823883215738704410561544672350728718269759703288288480665118982616042097028169710775672403103646694081696142297008847942639335715629545722107760119795737487838136067725445300808857250119963001634053526259681138127266703659084123296950022775198691600472211227341298838458948960470823254499392585524087918
k=d*e-1
temp = 0
while True:
    g=randint(n//10,n-1)
    k1=k
    while k1%2==0:
        k1 = k1 // 2
        x=pow(g,k1,n)
        p = math.gcd(x-1,n) %n
        if x>1 and p>1:
            q=n//p
            temp = 1
            break
    if temp==1:
        break
print(p)
print(q)
d = invmod(e, (p-1)*(q-1))
flag1 = n2s(pow(c, d, n))
print(flag1)

#下面获取flag2
e = 3
c = 574808471478635333245317783955856232370563895750738178995495491244722220578259862014622258456002771074212202993749856311345778504
n = 132275218780270789276875142391448867650895270629670759900527027384204094378702805212980599389161642078516147410438758869570165283020546983219261613517162232406493853982513805637479563931664593533545755290425758761320070903155316315225168568823850902007487296420757650976479888059670760410374801967212927224977
print(n2s(iroot(c, 3)[0]))

# 下面获取flag3
c = 95995020771266284668771773954095383926073034180948646028969032401939359632605448469918019304830962431504319950829514957438851980885420908331400633412921367641226567936331249173469086850004952349859327253487176970823999803143210342915194996505332578787985234930535548547834345641331406894553696409553432127676252530117997529863647389804169829603847371009965333521992075291993986519143392110820521102789536579717013822114100961105599532067858175576407477678474343
hint = 331827959959669362980903675700579680333727515633777861628619061160155873334438387426601431102578757478220073973755314614841843834177072237961383958721650387302854513037804229759753543773380647137880844819226502619093178213699654143169541320688758073525229779021778299681565211604935016493932946601713080358152349008389888320122977378245126603180345245359431242722391116674672049868497727142316387043599105147729557199319037013456439001531544933422509782305382177
n = 617084232354634109322171875468612900428229667931513848806770839434059627069484990725607996303673918867720768751727135179953407336155782580734284839136278190669702346600358059275099682118093888920038165877388324627028766987891732872124755908892972046287450095353992961045719531391795505441739616388353911919212662674941754442327213528963862921107314349391130370460483255191809581325731848910365215670220922837774417042794328874852028405333599359662323013152032901
e = 0x10001
tmp = pow(e, e, n)
p = GCD((hint * tmp) % n - 1, n)
print(p)
q = n // (p * p)
d = inverse(e, p * (p-1) * (q-1))
flag3 = long_to_bytes(pow(c, d, n))
print(flag3)

# 下面获取flag4
d = 242618035035163469434322293327938405750017912799190107714591368086742881522661519860077104080961
c = 742481710491632202304950326079681148354035306250917295914498846416723687179474088162312486652622
e = 65537
kphi = e * d - 1
print("[+]kphi =", kphi)
divisor = divisors(kphi)
for pm1 in divisor:
p = pm1 + 1
# print("[+]Try p =", p)
if isPrime(p) and int(p).bit_length() == 160:
for k in range(1, e):
if kphi % k != 0:
continue
q = (kphi // k // pm1) + 1
# print("[+]Try q =", q)
if isPrime(q) and int(q).bit_length() == 160:
print("[+]p =", p)
print("[+]q =", q)
n = p * q
m = pow(c, d, n)
msg = long_to_bytes(int(m))
print(b"msg = " + msg)

# BUAACTF{th1s_15_4n_really_ez_RSA_for_a1l_kind4_Of_attack_especially_for_known_e_and_d}

Block Cipher

分组密码,看懂加密，写解密即可。

from functools import reduce
import operator
def xor(a, b):
    assert len(a) == len(b)
    return bytes(map(operator.xor, a, b))

def decrypt(iv, key, parts):
result = []
for index, part in enumerate(parts):
result.append(reduce(xor, [part, iv if index == 0 else parts[index - 1], key]))
return b''.join(result)

iv = b'xba=yxa3xc6)xcfxf7'
key = b'}6Exeb(x91x08xa0'
parts = [b'x85^}txadxecx81,', b'xbax04Wxa1xee"xeaxc5', b'xb7ZWx18x99x82xd6:', b'x99x03}x9cxde|xb1xc5', b'xa1Tk.x8bxeexbaf']
print(decrypt(iv, key, parts))

# BUAACTF{BloCk_cIphER_14_Soooooo_EaSY}

KeyExchange

考点: LCG密钥交换恢复、数学推导、二分法

考点其实很基础，不过很好的解释了为什么plainLCG不能用来设计密钥交换算法。 LCG的和内置参数已知。定义：

 

 

假设A与B要利用这个基础的LCG，共享密钥，二者商定一个基础的公共值，满足小于即可。 此时A生成一个小于的随机数作为私钥，计算公钥；B生成一个小于的随机数作为私钥，计算公钥。A和B把公钥和公开至共享信道，随后A计算，B计算，由于定义函数满足性质：

 

 

故有：

 

 

此时二者完成密钥共享，。 由于和都非常大，因此在CTF环境下无法采取暴力破解的手段计算二者的私钥，但是可以发现这个过程存在一个最大的问题：LCG采用的线性算法具有同构性。

 

 

可以发现，迭代n次函数得到的结果仍可以写成的形式，如果我们定义一个内置参数为、的LCG，及其相关的计算函数，则有：

 

 

其中，。 从以上推导回到LCG密钥交换问题，可以发现：

 

 

同理可知：

 

 

此时可以破解共享密钥：

 

 

或者：

 

 

题中给出了、和、，在求解共享密钥时还需分解得到和。

本题中给出了一个，可用这个泄漏值来分解。由于，可以看出函数对是单调递增的（为常数），而题里又给出、均为512位，因此在内二分找一下即可分解。

被用作AES-CBC中的key加密flag，iv已知，解密一下即可。

exp:
from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from hashlib import sha256
from random import randint
from libnum import invmod, n2s

p = 110045941581246566163852236169863726493322518614291259738650243772537777220447239564993293840178002270803358414801874876416861655681706091960526864981702297311975108477231430850046449802619712390151394990272883738498246287828012579651055043742174921894177086628278972268977919519134723993840866617728971125501
s = 103083435269546339253719292770367969157635923310796947624819807524514689714230038488629636887588073083408362510426148038690685619752778205013088349018307009939108678198113606930036410404549808586987764543060403391315169316818289657581541763263327670573813529568272160960214773113382466107788108424376942305179
pk_a = 104249886397359747249273092453488313866919664956033370839273165940023672119280749446507600277914299719461300855987124305389892009846065290488788845690592952592538823773157304003987554741970547804984472643400001801640946933980112156093413786073659705669257814748840719625590155866880068232234070029543099326008
pk_b = 73943176009325878591909652784371325868093784459904155452171082544674415915957790552228923092972996591011414909913381038800791214834557764389213534028507829053436031472854955231610581309098048200856194242071844838535785588222371659431886892907007805510914868507217421041100993332508303713741693778352086616092

leak = 29040777564893836055576935754958349303880224434489606637225123765874859084299305072404829973337935904266301029232783978449958360875461566254630838251549934932706914467564998782070045758886430608783726619661530870388938391442492043731894115397400015449950051951769344001061013880264004181568996494392695873947102851715933737547680797285706746028093745905399081868517548754953070086517995947839613006470389399208171194194504365074914947024889949570680226668773867669172700292722732348438746947857754535156207414199788546164281701388891687436649862876851080136461979528906440369488791240780833837652254029174364644864043838626162283607643013213942931346399529512644954169730170267869381208558883655869400666658812252861841021468606579935712846111089021383151894750921351386

left = 2 ** 511
right = 2 ** 512
mid = (left + right) // 2
while (mid ** 5 - ((s ** 3) // (mid ** 3))) != leak:
if (mid ** 5 - ((s ** 3) // (mid ** 3))) > leak:
right = mid
mid = (left + right) // 2
else:
left = mid
mid = (left + right) // 2

a = mid
b = s // mid

iv = long_to_bytes(0xe759b23de290a6d4ea11dab4b0c306f3)
c = b"xa8x83x8b,x14x1adxfbxfdx12xc6xc1=xa0+kx05xc7xc9xedxdexca>x04xe1;xccxc1xb6x9a+xe66dxcfx9bxfftpx81xabxbf(x02xcdx0bxa4xc0Lpgx83Fx82lxad2xdcIx1abx08x88n"

m = (invmod((a-1) * s + b, p) * (pk_b * (a-1) + b)) % p
k = (invmod((a-1) * s + b, p) * (pk_a * (a-1) + b)) % p
shared1 = (m * pk_a + invmod(a-1, p) * (m-1) * b) % p
shared2 = (k * pk_b + invmod(a-1, p) * (k-1) * b) % p
assert shared1 == shared2

key = sha256(str(shared1 + s).encode()).digest()[:16]
cipher = AES.new(key, AES.MODE_CBC, iv=iv)
print(cipher.decrypt(c))

# BUAACTF{Uns@fe_Xch4nq3__c0nsTruct1oN_u51ng_lcg!!!}

 

Math

考点：通过关系构造二次方程并解出+简单数学推导

参考exp，前两关通过关系构造二次方程并解出，最后一关经推导不难发现为p+q（信息安全数学基础课后题），用方程解出即可。

from Crypto.Util.number import *
from z3 import *

e = 65537
c = 112603855258130214477579025724347852348654764350616283814228948696384649423509219700593580927436981131009253539258926656199553162798353424478456071312399854016855769730451167219095385224786982617931318336289395411790738746409786626741975659380781585117554886308860499453339049544449101737359477485341756095685
n = 156554201159196482703626229456180336082601822691986590744780894650795965611900555514134060137082990473725887830010623065818450185823730822009287525836754951877076875771488298693374835052451569073414980813577454117535462658662205409616157954907990248587384015512293862003341283487632375295475440935688094002617
leak = 3118625448174043604744529027319786605170955560813558072118277982181159822887603847530258597519488281509287189431662221215460717933909531417536796929018210
tmp = (leak - 2) // 2
p, q = Int('p'), Int('q')
solver = Solver()
solver.add(p * q == n, p - q == tmp, p > 0, q > 0)
if solver.check() == sat:
m = solver.model()
p, q = m

.as_long(), m[q].as_long()
assert p * q == n
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = int(pow(c, d, n))
print(long_to_bytes(m)[:14].decode(), end="")

e = 65537
c = 93978686378293828086191790122529919325716419332933686245770487684123528049983735994708527178252488091788860014057317894385773677231842636035334795883708882974841442069339023354766426009980023194357039539192634379156228433248998982297141837057318199779573613425738350307108121215320184191104501916977179892819
n = 113314208967522806109377775391344774798246647245609527530250842162998260734597302913497036905918762468707747032503484781341144969937434755205814353751104297147933894782213419095409180897649121217538219106453769844032495640631837946695496195968385913896925163019434775707488581307013382934251169925612458912701
leak = 92227188008859636551571172271384433717034261725865660741125015972908284264524691925307008950647919630793901680894279288364099880089609034246812387558747800115003457695305687069115350786189814893940014083795308121668729848809030525554558177868795576913946290045467615215700823448216007469394406486122762340799
tmp = e * leak - 1
k = tmp // n
tmp -= k * (n+1)
tmp = tmp // (e - k)
phi = n + 1 - tmp
d = inverse(e, phi)
m = int(pow(c, d, n))
print(long_to_bytes(m)[:14].decode(), end="")

e = 65537
c = 57267353578218922590866753594427040157686249506833227002343780474377875165575891892094097781872920937467859618146840876344931100376140310307914367629844308420600760564342032844568436492313668901310573464694813393787808054157639041836407430313117254669011492042858846089516806744148324079065759777653798065470
n = 72559362705546768966148503007933634888094434921837745715507408562619698919824091078235194244259688366819227638823888641073251820477424150670604138979273724058577742415825092468613527614237094273848230891355347434776123637086037409586867384122532873818945115846995272181542565199089210266795364142054521432969
leak = 17238032591075070541888189318082997841936669281409415876040204774279914799918723435203750385624612322410269658410156575528112867456120069790169980041169270
phi = n + 1 - leak
d = inverse(e, phi)
m = int(pow(c, d, n))
print(long_to_bytes(m)[:14].decode())
# flag{512_b1t3_R5A_15_n0_l0n63r_53cur3!!!!}

 

Hidden

考点：二次剩余+线性方程组+工具使用

出题思路：紧紧围绕二次剩余性质。

容易观察到flag二进制位值会影响到二次剩余性质，可以构造模2线性方程组，不难发现独立方程数量极大概率大于未知量个数，使用任意解方程工具解出。

参考exp，列方程解方程即可得，主要关注随机数r为非二次剩余的情况构造有效方程即可。

参考：

https://en.wikipedia.org/wiki/Quadratic_residue

System of linear equations

2020年工业互联网决赛Crypto

from sage.all import *
from Crypto.Util.number import *
def add(a,p):
    if pow(a,(p-1) // 2,p) == 1:
        return 0
    else:
        return 1

f = open("C:/Users/lenovo/Desktop/attachments/output.txt",'rb')
q = 210767327475911131359308665806489575328083
out = eval(f.read())

A = Matrix(GF(2), len(out))
v = vector(GF(2), len(out))
for i in range(len(out)):
t1, t2 = out[i]
for j in range(len(t1)):
A[i,j] = add(t1[j], q)
v[i] = add(t2, q)

m = A.solve_right(v)[:len(t1)]
m = ''.join(map(str, m))
print(long_to_bytes(int(m, 2)))
# flag{H1dd3n_Rul3s_4r3_7h3_K3y_70_Unl0ck_Cryp70_C0d3s!}

Factor

考点：FAC问题的算法、复杂度及相关工具的使用

此题是一个经过巧妙选择参数构造的FAC问题，组合ECM方法和任意一种筛法即可解决。

相关论文，维基百科链接：

https://www.sciencedirect.com/science/article/pii/S2213020916300210

https://en.wikipedia.org/wiki/Integer_factorization

https://github.com/bbuhrow/yafu

https://en.wikipedia.org/wiki/Lenstra_elliptic-curve_factorization

https://en.wikipedia.org/wiki/Quadratic_sieve

https://en.wikipedia.org/wiki/General_number_field_sieve

分解工具有CADO-NFS、msieve、yafu等很多，自己手写实现一个也没有任何问题。

FAC问题在素数选取不存在漏洞的情况下，分解主要有如下方法：

  • Lenstra elliptic curve factorization（ECM）方法，时间复杂度与最小质因数大小有关。
  • 各种筛法，时间复杂度与待分解数大小有关。

对目前家用级CPU（R23万分量级）和一般实现而言，ECM方法最多分解出45-55十进制位数，对于更大的数，时间开销迅速增加到不可接受的量级。

不同筛法有自身的优势区间，一般而言，小于75十进制位数选择SNFS（特殊数域筛法），75-130十进制位数选择SIQS（二次筛法），更大的数选择GNFS（通用数域筛法）。

对于本题目而言，应先用ECM方法分解出155二进制位的小质因数，再用任意一种筛法分解剩下的172*172二进制位数。

这里以yafu为例，介绍分解工具使用。

yafu可以通过yafu.ini文件调整配置，比较重要的有以下参数:threads，pretest_ratio，xover，snfs_xover，plan，work。

threads默认为1，速度很慢，可以根据处理器线程数设置。

pretest_ratio，xover，snfs_xover，plan，work这些参数可以参照yafu注释设置，决定了yafu使用哪些分解方法。

gnfs库在yafu项目里默认没有提供，如果要使用gnfs的话，推荐使用ggnfs。

对于本题，将threads拉满，调整pretest_ratio、plan和work先使用ECM分解，再调整snfs_xover使用SIQS分解即可解出。

flag{Cr4ck1ng_RSA_Thr0ugh_Pr1m3_Fact0r_M4st3ry}

Can_Your_Noggin_Survive

考点：离散数学完全集+信息论纠错码

出题思路：想考考大家纠错码，为了让题目变得有趣加了一点点离散数学表皮。

解题思路：经过试验发现love符号是或非，对离散数学知识敏感的人可以知道或非构成完全集，之后选用任意一种满足（15，7）纠两位错和（31，16）纠三位错的纠错码即可。

  1. Discrete Mathematics + Information Theory

  2. https://en.wikipedia.org/wiki/BCH_code

外面套了一层POW防止欧皇，过了POW之后可以开始试验，不难发现love是或非，可能出现（15，7）纠两位错或（31，16）纠三位错两种情况。

对离散数学知识敏感的人可以知道或非构成完全集，这样可以实现任意编码，接下来就是选择纠错码了。

本题设计时是想让大家手写实现BCH码，BCH码所用的知识主要是多项式域和域的扩张，这些知识在信息安全数学基础上都学过，但BCH码手写起来比较麻烦，ptw同学使用了http://mint.sbg.ac.at/ 上的纠错码，实现起来比较简洁，大家可以参考。

#include <bits/stdc++.h>
#include <sys/prctl.h>
#include <fcntl.h>
#include "sha256.h"
#define BUFSIZE 0x400000
#define MAXN 1000
char buf[BUFSIZE];

#define out(fmt, s) {
strcpy(buf, s);
int len = strlen(s);
buf[len] = 'n', buf[len + 1] = 0;
write(1, buf, len + 1); fflush(stdout); }
#define RECV_AND_PRINT { fgets(buf, BUFSIZE, stdin); fprintf(stderr, "[%d]:", __LINE__); fputs(buf, stderr); fflush(stderr); }
int qwq = 0x10;
int quota = 0;
using u32 = unsigned int;

int lin16[16][31] = {
{1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0},
{0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0},
{0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0},
{0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0},
{0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0},
{0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1},
{0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1},
{0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1}
};

int lin7[7][15] = {
{0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1},
{0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0},
{0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0},
{0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0},
{1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0},
{1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1}
};

std::string Nor (const std::string &s1, const std::string &s2) {
return "( " + s1 + " love " + s2 + " )";
}

std::string Not (const std::string &s) {
return Nor(s, s);
}

std::string Or (const std::string &s1, const std::string &s2) {
return Not(Nor(s1, s2));
}

std::string And (const std::string &s1, const std::string &s2) {
return Nor(Not(s1), Not(s2));
}

std::string Xor (const std::string &s1, const std::string &s2) {
return Nor(Nor(s1, s2), Nor(Not(s1), Not(s2)));
}

std::string query16(const std::vector<int> &v, int l, int r) {
if (l == r) return "C" + std::to_string(v[l]);
int m = (l + r) >> 1;
return Xor(query16(v, l, m), query16(v, m + 1, r));
}

std::string query16(int x) {
std::vector<int> v;
for (int i = 0; i < 16; ++i) {
if (lin16[i][x]) v.emplace_back(i);
}
return query16(v, 0, int(v.size()) - 1);
}

u32 mul16(u32 x) {
u32 r = 0;
for (int i = 0; i < 16; ++i) {
for (int j = 0; j < 31; ++j) {
r ^= (((x >> i) & lin16[i][j]) << j);
}
}
return r;
}

u32 judge16(u32 x) {
u32 r = 0, ri = 233;
for (u32 i = 0; i < (1 << 16); ++i) {
int v = __builtin_popcount(x ^ mul16(i));
if (v < ri) r = i, ri = v;
}
return r;
}

std::string query7(const std::vector<int> &v, int l, int r) {
if (l == r) return "C" + std::to_string(v[l]);
int m = (l + r) >> 1;
return Xor(query7(v, l, m), query7(v, m + 1, r));
}

std::string query7(int x) {
std::vector<int> v;
for (int i = 0; i < 7; ++i) {
if (lin7[i][x]) v.emplace_back(i);
}
return query7(v, 0, int(v.size()) - 1);
}

u32 mul7(u32 x) {
u32 r = 0;
for (int i = 0; i < 7; ++i) {
for (int j = 0; j < 15; ++j) {
r ^= (((x >> i) & lin7[i][j]) << j);
}
}
return r;
}

u32 judge7(u32 x) {
u32 r = 0, ri = 233;
for (u32 i = 0; i < (1 << 7); ++i) {
int v = __builtin_popcount(x ^ mul7(i));
if (v < ri) r = i, ri = v;
}
return r;
}

int ask(const std::string &s) {
--quota;
// for (int i = 0; i < 0x10000000; ++i) qwq ^= qwq * 0x37;
out(" %s n", s.c_str());
// sleep(1);
// for (int i = 0; i < 0x1000000; ++i) qwq ^= qwq * 0x37;
fprintf(stderr, "red %dn", qwq);
RECV_AND_PRINT;
char res = buf[17];
if (res == 'u') exit(666);
if (buf[3] == '(') exit(1234);
RECV_AND_PRINT;
RECV_AND_PRINT;
// fprintf(stderr, "[I%d,%d]:%cn", __LINE__, i, res); fflush(stderr);
return (res == 'Y');
}

int main() {
int round = 0;
int fdDown[2]; // read write
int fdUp[2]; // read write
pipe(fdDown);
pipe(fdUp);
int t = fork();
if (!t) {
dup2(fdUp[1], 1);
dup2(fdDown[0], 0);
//  std::setvbuf(stdin, nullptr, _IONBF, 0);
//  std::setvbuf(stdout, nullptr, _IONBF, 0);
prctl(PR_SET_PDEATHSIG, SIGKILL);
execl("/usr/bin/nc", "/usr/bin/nc", "10.212.26.206", "23205", NULL);
}
dup2(fdUp[0], 0);
dup2(fdDown[1], 1);
// std::setvbuf(stdin, nullptr, _IONBF, 0);
// std::setvbuf(stdout, nullptr, _IONBF, 0);
char tail[256];
BYTE expected[256];
scanf("sha256(XXXX+%28s) == %s", tail, expected);
// fcntl(0, F_SETFL, O_NONBLOCK);
fprintf(stderr, "t:%s e:%sn", tail, expected);
for (int i = 0; i < 64; ++i) expected[i] = expected[i] - (isdigit(expected[i]) ? '0' : 'a' - 10);
char word[64] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
char bb[256];
BYTE hh[SHA256_BLOCK_SIZE];
strcpy(bb + 4, tail);
SHA256_CTX ctx;
for (int i1 = 0; i1 < 62; ++i1) {
bb[0] = word[i1];
fprintf(stderr, "%c", bb[0]);
for (int i2 = 0; i2 < 62; ++i2) {
bb[1] = word[i2];
for (int i3 = 0; i3 < 62; ++i3) {
bb[2] = word[i3];
for (int i4 = 0; i4 < 62; ++i4) {
bb[3] = word[i4];
sha256_init(&ctx);
sha256_update(&ctx, (BYTE *) bb, strlen(bb));
sha256_final(&ctx, hh);
int equ = 1;
for (int i = 0; i < SHA256_BLOCK_SIZE; ++i) {
equ = equ && (expected[i * 2] == (hh[i] >> 4) && expected[i * 2 + 1] == (hh[i] & 15));
}
if (equ) {
printf("%c%c%c%cn", bb[0], bb[1], bb[2], bb[3]);
fflush(stdout);
fprintf(stderr, "nfound hash: %c%c%c%cn", bb[0], bb[1], bb[2], bb[3]);
goto found_hash;
}
}
}
}
}
fputs("not found hash???", stderr);
return 0;
found_hash:

RECV_AND_PRINT;
RECV_AND_PRINT;
int ans[16] = {};
int chk[16] = {};
char tmp[233];
u32 res = 0;
for (int i = 0; i < 31; ++i) fprintf(stderr, "%sn", query16(i).c_str());
for (int i = 0; i < 15; ++i) fprintf(stderr, "%sn", query7(i).c_str());

sixteen:
fprintf(stderr, "------------ [Round %d] ------------n", ++round);
RECV_AND_PRINT;
RECV_AND_PRINT;

res = 0;
for (int i = 0; i < 31; ++i) {
res ^= ask(query16(i)) << i;
}
res = judge16(res);
for (int i = 0; i < 16; ++i) ans[i] = int((res >> i) & 1u);

RECV_AND_PRINT;
RECV_AND_PRINT;
RECV_AND_PRINT;
for (int i = 0; i < 16; ++i) {
int o = ans[i];
printf("%d%c", o, " n"[i == 15]);
fprintf(stderr, "%d%c", o, " n"[i == 15]);
}
fflush(stdout);
fflush(stderr);
RECV_AND_PRINT;
if (buf[3] == 'W' && buf[4] == 'r' && buf[5] == 'o') return -233;
RECV_AND_PRINT;
RECV_AND_PRINT;
sscanf(buf, "%s", tmp);
if (strcmp(tmp, "Sixteen") == 0) goto sixteen;
else if (strcmp(tmp, "Seven") == 0) goto seven;
else goto success;
seven:
fprintf(stderr, "------------ [Round %d] ------------n", ++round);
RECV_AND_PRINT;
RECV_AND_PRINT;

res = 0;
for (int i = 0; i < 15; ++i) {
res ^= ask(query7(i)) << i;
}
res = judge7(res);
for (int i = 0; i < 7; ++i) ans[i] = int((res >> i) & 1u);

RECV_AND_PRINT;
RECV_AND_PRINT;
RECV_AND_PRINT;
for (int i = 0; i < 7; ++i) {
int o = ans[i];
printf("%d%c", o, " n"[i == 6]);
fprintf(stderr, "%d%c", o, " n"[i == 6]);
}
fflush(stdout);
fflush(stderr);
RECV_AND_PRINT;
if (buf[3] == 'W' && buf[4] == 'r' && buf[5] == 'o') return -233;
RECV_AND_PRINT;
RECV_AND_PRINT;
sscanf(buf, "%s", tmp);
if (strcmp(tmp, "Sixteen") == 0) goto sixteen;
else if (strcmp(tmp, "Seven") == 0) goto seven;
success:
RECV_AND_PRINT;
RECV_AND_PRINT;
RECV_AND_PRINT;
RECV_AND_PRINT;
return 0;
}
// flag{2045_8r0ught_D0wn_39_h34ds_1n_th1s_cyb3r_g4m3}

文案 | 潘卓成

排版 | 张   涔

审核 | 高丰奕

免责声明:文章中涉及的程序(方法)可能带有攻击性，仅供安全研究与教学之用，读者将其信息做其他用途，由读者承担全部法律及连带责任，本站不承担任何法律及连带责任；如有问题可邮件联系(建议使用企业邮箱或有效邮箱,避免邮件被拦截，联系方式见首页)，望知悉。
  • 左青龙
  • 微信扫一扫
  • weinxin
  • 右白虎
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2024年8月15日16:27:37
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出)：
                   BUAACTF2023 Crypto WPhttps://cn-sec.com/archives/1998371.html
                  免责声明:文章中涉及的程序(方法)可能带有攻击性，仅供安全研究与教学之用，读者将其信息做其他用途，由读者承担全部法律及连带责任，本站不承担任何法律及连带责任；如有问题可邮件联系(建议使用企业邮箱或有效邮箱,避免邮件被拦截，联系方式见首页)，望知悉.

发表评论

匿名网友 填写信息