1618 words
8 minutes
2023安洵杯复现
1，010101
题目是直接给了n、p（改了两次其中的一个比特）以及c。
而这道题的话，关键点也雀食是与改动有关的那两行语句：
p1[random.choice([i for i, c in enumerate(p1) if c == '1'])] = '0'
p2[random.choice([i for i, c in enumerate(p1) if c == '0'])] = '1'
也就是说，它再怎么改，都是~~根据p1去改的~~。
因此，我们直接去爆破就行，总次数不多。当时是第二组数据就出了。
（小插曲1：写wp的时候，再去连靶机，发现再获得的四组数据里，只有第四组能搞出flag，笑死。。。。估计是出题人的靶机设置有点问题）
（小插曲2：突然想起赛后有一个师傅聊了聊，发现他的数据有点特别，就去试着复现了他的看看，然后就发现一个很好笑的事——题目的p1，其实是原来的p的p1（（（；所以收回前边说的那个靶机问题，这是出题人的问题了。。。因此本题直接看 “p1的0的位置集合” 和 “p2的1的位置集合”，然后利用起来爆破就行）
代码如下：
点击展开代码
from sage.all import *
from Crypto.Util.number import *
from gmpy2 import *
from tqdm import *
"""
交互获得相关参数
from pwn import *
from pwnlib.util.iters import mbruteforce
from hashlib import *
import string
import itertools
table = string.ascii_letters + string.digits
io = remote(host='124.71.177.14', port=10001)
def pow1():
io.recvuntil(b'XXXX + ')
suffix = io.recv(16).decode("utf8")
io.recvuntil(b':')
cipher = io.recvline().strip().decode("utf8")
proof = mbruteforce(lambda x: sha256((x + suffix).encode()).hexdigest() == cipher, table, length=4, method='fixed')
io.sendlineafter(b'XXXX:\n', proof.encode())
return cipher
pow1()
print(1)
io.interactive()
"""
n = 763193405859690434424481155507657771400826255867665737934357110780028016399375699067669771100844089299525037795826692232756621795204270639250685811398697226059594390335751746071876587852806722699629792482195908827920721473907818113175678419998267847039151142048648044018762382782634242284167755254609666022356987874558455736699630118805669828499964784340000508472743903490397987514422207924986817834175365781478312351604529308544983301347088594597844365005353740724528268576738795778909592672357443982963063851256542668179216283941721673425914187428366380678662882632846665049862077241991275142962711366964589708141339179378796336237387859539565138456377246401011248551512679838524964484514504812381929475728577083557712619124229344086855389263726124840268897281990478139634223644107711525881925475388275491248861054787394547382612382552410377300829601468225660574915221922607609008808059124858453917095601772327165255261943980110304985533615717875025520915137964648897372262468869559821846148185711456914282444970904107072721050111548066604126941275812404567073864186301715209938973231621975742952950315513777244937854549507756955915402450041010672684146442270202439060262868442297862994429597174597253429274166878783027619060805563
p0 = "11110001111100000001011000000001010100110011011010010101111011001111101110001011110001010010110011011001000101000010100100010111001010000001100011100111010110001100110011100000000110101110010110100001110110010000001101110110010100000011111110010011100001010001101100111101101101001011111101101110101001111110011111100011000001011110011010110101111010010011110101110110001110001011000010000000011101011100110001000010000010101010000101101000011100000010100100111011010111001001000011010101101110110101110001110101101001100011000101110001100100110100110001111011101001001010010000110001001001100010110100110110010100111000011011001010001000010111010111111100011000001111101110000100101101111101100001111001110001001110101000010100010110110110101000101111110100110011011111100111100101010101110001010101001100111101111000101100110010111100110111110010001010110101100100111101001001101010010011011000011101110100110111010000001010100001101111011111111101111110001011100101000011010010101001000000000100100011000100011000000110010110101000000000011011101000001010000011100100001011000110010101100011011110001100111000011000001100110101100011001000010101001100011001111111000110111101101000100101100000111110001100011010010011111110000110011100011100000001001100101010100110111000000001010101000110101100111110101011011011110010110001100100000101010101111110010010001001001011011101000110001010110001001011100110111101010111110111101001001101111100011111110011000011111100100001100000010011011110110010111011001111000000110111111011010100111111111000010100001001101101101110010000010100111011000000000111001001110001111011110101101000101110110001111101001111111000001100010011101110010000111011100101111110010010011000101000000000011111011100110101101000010110011111100110011000010000000011111011100001010001101111010000001100101000001110101010000011111000110100011000101100100110101010110010001000100010111001100011011101101010000010101010110010111011000000111000011110011001100100111011011011011101010010100110100111011000101101000011010100010110110111"
c = 453215674474214965202132063035092026492874728601914890993418038624836803388055351737632719208382143093524483365159680508786211319504345529565843680750345848452636169422993361213711605785862332086238014315373962416927928746217310465085984289505263081233684332466649254490055520612973456717192249499729080368013841118291994859737790191617612746373067506355642484877287906595793821414990939609411491480602290773741365104729857143028660902021746767108395064307781249987622017310075078290452933285640491598279580872500313941044020700140832316639023277896435658695043626745904830432738945408900080039583637107582442037290455805799776583931244707009506013575707145162760701043823093488738770256839644241757798728575423382744043714006681673118211918527778745099706228797487193141139433458609598204192409077816308952318137632227988238139768935139738116379983145790893067776701126672207290844651507202484962256937819826845969632355646240575460888273942799378127551717504116946370481415804929730921408214594333793027774593200261033813331073390763343688402160013614954010828922477543156939329791285376878433085894485678038988207919445082344788365656770403908597410733004665871525236638994317111029861183719400591447145554229760970885645449829906
def attack(n, p0, c):
p1 = p0[:1024]
p2 = p0[1024:]
# p1的0的位置集合
pp1 = [i for i, c in enumerate(p1) if c == '0']
# p2的1的位置集合
pp2 = [i for i, c in enumerate(p2) if c == '1']
# print(pp1)
for i in tqdm(pp1):
p1 = list(p0[:1024])
p1[i] = '1'
for j in pp2:
p2 = list(p0[1024:])
p2[j] = '0'
ppp = ''.join(p1) + ''.join(p2)
ppp2 = int(ppp, 2)
if n % ppp2 == 0:
p = ppp2
print(i, j)
# print(p)
q = n // p
d = invert(65537, (p-1)*(q-1))
m = long_to_bytes(int(pow(c, d, n)))
if b'D0g3' in m:
print(m)
return
attack(n, p0, c)
# b'D0g3{sYuWzkFk12A1gcWxG9pymFcjJL7CqN4Cq8PAIACObJ}'
2，POA（padding oracle attack）
现在才反应过来题目名字就是个提示（虽然当时就有看到个检查填充的函数）。
题目是给了两选项：拿密文和测密文，其中：
第一个选项返回的是：iv+cipher
第二个选项返回的是：True或False，本选项的结果由下图函数产生：
def asserts(pt: bytes):
num = pt[-1]
if len(pt) == 16:
result = pt[::-1]
count = 0
for i in result:
if i == num:
count += 1
else:
break
if count == num:
return True
else:
return False
else:
return False
就跟我开头所说，你要是仔细看这个函数，就会发现：这个函数就是拿来测填充的。那就好说了——用padding oracle attack就行。
使用该攻击的条件：
- 攻击者能够获得密文，以及密文对应的初始化向量iv
- 攻击者能够触发密文的解密过程，并且能够知道密文的解密结果是否正确
至于攻击的解析思路，可以看看这篇文章，大概的过程就是几步而已：
1，伪造的iv设为全零。
2，然后从最后一位（即位置为index=15） i 开始，先异或我们此时用来爆破的填充长度make_pad_len，然后再进行爆破；重复此操作，直至靶机返回true。
3，而后保存我们爆破出的明文的那一位：m[index] = i ^ iv[index] ^ make_pad_len。
4，若没爆破完，就回到1，且填充数+1、index-1；重复此操作，直至爆破完成16次。
代码如下：
点击展开代码
<details>
from pwn import *
from hashlib import sha256
import string
from pwnlib.util.iters import mbruteforce
import binascii
r = remote("124.71.177.14",10010)
table = string.ascii_letters+string.digits
def pow():
r.recvuntil("XXXX + ")
suffix = r.recv(16).decode("utf8")
r.recvuntil(":")
cipher = r.recvline().strip().decode("utf8")
proof = mbruteforce(lambda x: sha256((x + suffix).encode()).hexdigest() ==
cipher, table, length=4, method='fixed')
r.sendline(proof)
pow()
r.sendline('1')
r.recvuntil('This is your flag: ')
c=r.recvuntil('\n',drop=True)
print('c=',c)
iv = c[:32]
cipher = c[32:]
enc=binascii.unhexlify(cipher)
iv=binascii.unhexlify(iv)
print('enc=',enc)
print('iv=',iv)
pt = bytearray(b'\x00'*16)
for make_pad_len in range(1, 17):
xored_iv = bytearray(16)
for i in range(16):
xored_iv[i] = iv[i] ^ pt[i]
index = 16-make_pad_len
for i in range(0x100):
_iv = bytearray(16)
for j in range(index, 16):
_iv[j] = xored_iv[j] ^ make_pad_len
_iv[index] = i
_iv = bytes(_iv.rjust(16, b'\x00'))+enc
ivv=_iv.hex()
r.sendline('2')
r.recvuntil('Please enter ciphertext:\n')
# print('tt=',len(tt))
print('ivv=',ivv)
r.send(str(ivv))
res=r.recvuntil('\n')
if b'True' in res:
v = i ^ iv[index] ^ make_pad_len
pt[index] = v
print(chr(v), pt.hex(), bytes(pt))
break
r.interactive()
# D0g3{0P@d4Ttk}
</details>
3，Rabin
这道题的的话，当时确实没啥思路。。。后面回看代码才发现：其实也不难。。。
r的话，其实就是个爆破，所以直接套题目代码去爆破就行（（（
至于p和q，因为题目给了，那就好说了——直接解方程即可：
然后，因为题目有段代码透露了点e2的信息：
phi = (p - 1) * (q - 1) * (q - 1)
while True:
try:
d = gmpy2.invert(e2, phi)
break
except Exception as e:
p, q, r = get_pqr()
所以直接 “爆破+解密” 就可以得到e2为5。
而e1与e2又有一定的关系：
def relation(x, e1, e2):
a, b = 0, 0
for i in range(x - (2**2 - 1)):
a += pow(e1, i)
for j in range(3):
b += pow(e2, j)
if a == b:
return True
return False
所以利用该函数就可以得到e1为2。
既然e1都为2了，那就直接rabin解一下就行。
代码如下：
点击展开代码
from Crypto.Util.number import *
from gmpy2 import *
def relation(x, e1, e2):
a, b = 0, 0
for i in range(x - (2**2 - 1)):
a += pow(e1, i)
for j in range(3):
b += pow(e2, j)
if a == b:
return True
return False
def test(m):
for i in m:
if i<30 or i>128:
return 0
return 1
n = 215542486690138348212640234404049799919635427821313456969621251060999619198049047177072651018596544086402247352197285854843845944372301101422143366852931792615984769993889362115389973674629219193681750795772428481025752569774971440700306858894319538900851053583957864898029826758456758476619888366993364509220001242453888211103365435807215558774330391648097111192320095659694195319870239601662744928595090571700281957206646074244053933917448825828116228773874450831077283631747199997562891127685983157490466956878844826999250949967889884408411238677552341586945776575736364562048823343133984988014074417893788969853348022438640049948495874102924583288041703323158838354435889321339895166262946251136237334452847197215642687015027283700043029064025676789331785263748936936589277948304052970796224998343174149147147825538493796451624708076418345938026992306198704695731510527238272653831179535713229090956546499980190091985344767690497086521576965126306339387466154573101734114253603740422219025538947147
inv_p = 42303340248191508590637063222127304189798558157588443790287020455054903668959919705907012217039621753010835237163373479926246138771911376613172517329936815122771296881304423494164177980298297954870868896488874496302031411866199638897092450925107731959148013972036564031411733025530903966971361620019879441046
inv_q = 108281530158680481529257160988048244220104324778044618902789696175636926788933408251321927395373813259289932361561809821270122662464083251300770924671777879317998407078089890974336206377978989769254394653288774903527875925382673950895972748704361661483325711235831620837397565541852531379417737459613251603132
c1 = 108779499726987796123243044076927163372148428373461727512406355353001951926931692618756259644794020686134975137514649542293974888228505908650388231782834884889723132173393439504573328481904226908768531266644629177330947241267372808001017789568046851963706688585356535966622598605399411494376992220751655374379502245525194656904741190167987429851704732889719842799707693647229656598746833338923701821809460839980885526831731338712888358954087777377698981893809810277775759239689246402013995206167771472996547655199525717172826108066304315439485445663389860828504014310408858433597931429608052636372582717944547720680325304095168810680856572073015571059680292969533066493748374990887314398112719714964568021697235443087376351857322723837829356316573940640433284422025509637252953021214327321232010337237713622408281268819287255779593631400029813269930844032583038407102487949065898966857593360369639959701137856395127704766275352298948537110088435577393229082505547497763697565339314660467499866565031139
c2 = 126641678662088475795900594462021578825062586198260258622573933730221154275309051701082155647754451393014032648118633542338782140403874773833233531216363837556899359597741429158316220508205037252766440479487529046233686611855023423107357769808929455387748622947096135131398989874517655524504781737277223632420397457489532106189728169251506627440185522826947905049599375924438912782354192221925523039088875395041400506882168579881109045385821051413535300269787170960178023703096353399505016725131062676509272552078174872100391136685131297626390995552588221455466611104671072271048534660511476503188073143996265892268160337366573222682684602686314572680231993635877342912886474951926603753688656938734758744660925084067855333567866876361512644097122561247251853307606349211983366293576843962416452456715205411381656686711203249989197381031076946584031629173011913620122138318508139720341907325246545820237070145852366433998496874296201142881051058294343520072773633985324325758872790159135652433052540302
m = b""
f2 = 0
flag = 0
for x in range(2, 100):
r = 2
while True:
r = r * x
if r.nbits() > 1024 and isPrime(int(r - 1)):
r = r - 1
break
if n % r == 0:
n1 = n // r
p, q = var('p q')
eq1 = inv_p*p + inv_q*q == n1 + 1
eq2 = p * q == n1
s = solve([eq1, eq2], [p, q])[0]
p = int(str(s[0]).split()[-1])
q = int(str(s[1]).split()[-1])
phi = (p-1)*(q-1)
# print(phi)
if f2 == 0:
for j in range(3, 100):
if gcd(phi, j) != 1:
continue
e2 = j
print("e2 = ", e2)
d = invert(e2, phi)
m2 = long_to_bytes(int(pow(c2, d, n1)))
if b'}' in m2[:21] and test(m2[21:]) == 1:
m2 = m2[:21]
f2 = 1
# print(m2)
break
ff = 0
for k in range(2, 10):
if relation(x, k, e2):
e1 = k
print("e1 = ", e1)
ff = 1
break
if ff:
mp = int(pow(c1, (p + 1) // 4, p))
mq = int(pow(c1, (q + 1) // 4, q))
mm = []
a = (inv_p * p * mq + inv_q * q * mp) % n1
mm += [int(a), n1 - int(a)]
c = (inv_p * p * mq - inv_q * q * mp) % n1
mm += [int(c), n1- int(c)]
for m in mm:
m1 = long_to_bytes(m)
if b'D0g3' in m1:
m1 = m1[-21:]
print(m1 + m2)
flag = 1
break
if flag:
break
# b'D0g3{82309bce-9db6-5340-a9e4-a67a9ba15345}'