2023安洵杯复现

Uncategorized
14k words

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就行。

使用该攻击的条件：

  1. 攻击者能够获得密文，以及密文对应的初始化向量iv
  2. 攻击者能够触发密文的解密过程，并且能够知道密文的解密结果是否正确

至于攻击的解析思路，可以看看这篇文章，大概的过程就是几步而已：

​ 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}'
Comments