ezzzecc
解题过程
看到其他数都给了,唯独p是通过加密的。
通过一次base62,4次base64即可解密得到一串不知名字符串
在通过与给定格式的p值相对比得到-11
写脚本跑出来原来的p值
data="""e2p.*'*-)+-,+*'&.&)&+'+&+-,',..,.(*,++-%()-&',,*--&%+,..(*.)%,)-+*,%%)+(*.,+',%(r"""
for i in range(len(data)):
print(chr(ord(data[i])+11),end="")
通过发现,其实k值也没有给出,需要自己写脚本爆破
M = 95258468765219141626168727997935766803481277588106799359407486570046359762703
a = 87425770561190618633288232353256495656281438408946725202136726983601884085917
b = 107879772066707091306779801409109036008421651378615140327877558014536331974777
def add(A,B):
if A==(0,0): return B
if B==(0,0): return A
x1,y1 = A
x2,y2 = B
if A!=B:
p = (y2-y1)*pow(x2-x1,M-2,M)
else:
p = (3*x1*x1+a)*pow(2*y1,M-2,M)
x3 = p*p-x1-x2
y3 = p*(x1-x3)-y1
return (x3%M,y3%M)
base = (34031022567935512558184471533035716554557378321289293120392294258731566673565, 74331715224220154299708533566163247663094029276428146274456519014761122295496)
pub = (49293150360761418309411209621405185437426003792008480206387047056777011104939, 43598371886286324285673726736628847559547403221353820773139325027318579443479)
X = (0,0)
for i in range(M):
if X==pub:
secret = i
print("secret:" + str(secret))
break
X = add(X, base)
print(i)
from libnum import s2n,n2s
from Crypto.Util.number import *
p = 95258468765219141626168727997935766803481277588106799359407486570046359762703
a = 87425770561190618633288232353256495656281438408946725202136726983601884085917
b = 107879772066707091306779801409109036008421651378615140327877558014536331974777
k = 166909
E=EllipticCurve(GF(p),[a,b])
c1 = E(3315847183153421424358678117707706758962521458183324187760613108746362414091 , 61422809633368910312843316855658127170184420570309973276760547643460231548014)
c2 = E(12838481482175070256758359669437500951915904121998959094172291545942862161864 , 60841550842604234546787351747017749679783606696419878692095419214989669624971)
cipher_left = 75142205156781095042041227504637709079517729950375899059488581605798510465939
cipher_right = 61560856815190247060747741878070276409743228362585436028144398174723191051815
m=c1-k*c2
print(n2s(int(cipher_left/m[0]))+n2s(int((cipher_right/m[1]))))
happy2024
解题过程
题目是RSA+AES的组合,其中RSA加密了AES的key,而AES的iv由矩阵乘法混淆了,实际上是一个hssp。
首先求解一下rsa。这里的hint比特关系非常明显,可以猜测是用格来打。梳理一下hint的组成:
根据该条件可以构造一个格,目的是得到每一维度量级在1024比特左右的三维向量。格子构造如下:
规约后理论上能得到的短向量是,但是实际测试发现无论怎么调系数都无法得到正确结果。于是用高斯启发式Gaussian Heuristic计算一下发现是卡了界的。于是考虑爆破几个比特,那么需要修改一下格的结构。这里有个小技巧是可以爆破p^2和 q^2,如果是直接爆破p q的话等式展开会麻烦不少。爆破和 的5个比特分别为i和j,设,那么新的格子如下:
拿到CBC_key之后再求一下iv即可。
对于hssp问题,论文A Polynomial-Time Algorithm for Solving the Hidden Subset Sum Problem给出了攻击方法:
实现一下算法求解即可:
from Crypto.Util.number import *
n = 60
m = 330
p = ...
w = ...
MM = ...
e = 0x10001
MM = matrix(GF(2), MM)
def allpmones(v):
return len([vj for vj in v if vj in [-1, 0, 1]]) == len(v)
# We generate the lattice of vectors orthogonal to b modulo x0
def orthoLattice(b, x0):
m = b.length()
M = Matrix(ZZ, m, m)
for i in range(1, m):
M[i, i] = 1
M[1:m, 0] = -b[1:m] * inverse_mod(b[0], x0)
M[0, 0] = x0
for i in range(1, m):
M[i, 0] = mod(M[i, 0], x0)
return M
def allones(v):
if len([vj for vj in v if vj in [0, 1]]) == len(v):
return v
if len([vj for vj in v if vj in [0, -1]]) == len(v):
return -v
return None
def recoverBinary(M5):
lv = [allones(vi) for vi in M5 if allones(vi)]
n = M5.nrows()
for v in lv:
for i in range(n):
nv = allones(M5[i] - v)
if nv and nv not in lv:
lv.append(nv)
nv = allones(M5[i] + v)
if nv and nv not in lv:
lv.append(nv)
return Matrix(lv)
def kernelLLL(M):
n = M.nrows()
m = M.ncols()
if m < 2 * n:
return M.right_kernel().matrix()
K = 2 ^ (m // 2) * M.height()
MB = Matrix(ZZ, m + n, m)
MB[:n] = K * M
MB[n:] = identity_matrix(m)
MB2 = MB.T.LLL().T
assert MB2[:n, : m - n] == 0
Ke = MB2[n:, : m - n].T
return Ke
def attack(m, n, p, h):
# This is the Nguyen-Stern attack, based on BKZ in the second step
print("n =", n, "m =", m)
iota = 0.035
nx0 = int(2 * iota * n ^ 2 + n * log(n, 2))
print("nx0 =", nx0)
x0 = p
b = vector(h)
# only information we get
M = orthoLattice(b, x0)
t = cputime()
M2 = M.LLL()
print("LLL step1: %.1f" % cputime(t))
# assert sum([vi == 0 and 1 or 0 for vi in M2 * X]) == m - n
MOrtho = M2[: m - n]
print(" log(Height, 2) = ", int(log(MOrtho.height(), 2)))
t2 = cputime()
ke = kernelLLL(MOrtho)
print(" Kernel: %.1f" % cputime(t2))
print(" Total step1: %.1f" % cputime(t))
if n > 170:
return
beta = 2
tbk = cputime()
while beta < n:
if beta == 2:
M5 = ke.LLL()
else:
M5 = M5.BKZ(block_size=beta)
# we break when we only get vectors with {-1,0,1} components
if len([True for v in M5 if allpmones(v)]) == n:
break
if beta == 2:
beta = 10
else:
beta += 10
print("BKZ beta=%d: %.1f" % (beta, cputime(tbk)))
t2 = cputime()
MB = recoverBinary(M5)
print(" Recovery: %.1f" % cputime(t2))
print(" Number of recovered vector = ", MB.nrows())
print(" Number of recovered vector.T = ", MB.ncols())
return MB
res = attack(m, n, p, w)
最后解aes。
Signature
解题过程
proof过程根据逻辑编写python代码爆破
from pwn import *
from Crypto.Util.number import *
import gmpy2
r = remote('',1337)
context.log_level = 'debug'
def proof():
r.recvuntil(b'Your gift --> ')
gift = r.recvline()[:-1].decode()
password = 'happy_the_year_of_loong'
l = 19
table = [i for i in range(len(password)) if password[i] in string.ascii_lowercase]
# print(table)
for i in range(2 ** l):
pad = bin(i)[2:].zfill(l)
tmp_list = list(password)
for j in range(len(table)):
if pad[j] == '0':
tmp_list[table[j]] = tmp_list[table[j]].upper()
payload = ''.join(tmp_list)
if hashlib.sha256(payload.encode()).hexdigest()[:6] == gift:
r.recvuntil(b'>')
r.sendline(payload.encode())
return
proof()
成功爆破得解进入下一环节。
之后是DSA签名,主要洞在签名部分的系数k上
k = int(hashlib.md5(os.urandom(20)).hexdigest(),16)
这样生成的系数k为128位,偏小,可以通过格基规约的方法得解。通过8次交互获取数据构造格。
首先先理清楚签名关系。x是私钥大小为160位,构造等式为。
令,构造格子如下
可以得到系数k,之后再计算x。得到的未必就是x的精确值,这里用系数代回式子得到x,完整exp如下
from pwn import *
from Crypto.Util.number import *
import gmpy2
r = remote('116.205.134.67',1337)
context.log_level = 'debug'
def proof():
r.recvuntil(b'Your gift --> ')
gift = r.recvline()[:-1].decode()
password = 'happy_the_year_of_loong'
l = 19
table = [i for i in range(len(password)) if password[i] in string.ascii_lowercase]
for i in range(2 ** l):
pad = bin(i)[2:].zfill(l)
tmp_list = list(password)
for j in range(len(table)):
if pad[j] == '0':
tmp_list[table[j]] = tmp_list[table[j]].upper()
payload = ''.join(tmp_list)
if hashlib.sha256(payload.encode()).hexdigest()[:6] == gift:
r.recvuntil(b'>')
r.sendline(payload.encode())
return
proof()
r.recvuntil(b'>')
r.sendline(b'3')
r.recvuntil(b'Oh,your key is (')
p,q,g = list(map(int,r.recvline()[:-2].decode().split(',')))
ms = [str(i).encode() for i in range(8)]
rs = []
ss = []
hs = []
for m in ms:
H = int(hashlib.sha256(m).hexdigest(), 16)
r.recvuntil(b'>')
r.sendline(b'1')
r.recvuntil(b'Username:')
r.sendline(m)
r.recvuntil(b'This is your signature -- > ')
R,S = list(map(int,r.recvline()[:-1].decode().split(',')))
rs.append(R)
ss.append(S)
hs.append(H)
def getk0(q,rs,ss,hs):
A = []
B = []
n = len(rs)
for i in range(n):
a = rs[i] * inverse_mod(ss[i], q) % q
b = hs[i] * inverse_mod(ss[i], q) % q
A.append(a)
B.append(b)
mat = [[0 for _ in range(n + 2)] for _ in range(n + 2)]
for i in range(n):
mat[i][i] = q
mat[-2][i] = A[i]
mat[-1][i] = B[i]
mat[-2][-2] = 1 / (2 ** 32)
mat[-1][-1] = 2 ** 128
mat = matrix(QQ, mat)
print(mat.LLL())
return abs(int(mat.LLL()[1][0]))
k0 = getk0(q,rs,ss,hs)
print(f'k0 --> {k0}')
r0 = rs[0]
s0 = ss[0]
H0 = hs[0]
pri = int((s0 * k0 - H0) * gmpy2.invert(r0,q) % q)
k = int(hashlib.md5(os.urandom(20)).hexdigest(),16)
m = b'admin'
H = int(hashlib.sha256(m).hexdigest(),16)
rr = pow(g,k,p) % q
s = pow(k,-1,q) * (H + pri * rr) % q
r.sendline(b'2')
r.recvuntil(b'r:')
r.sendline(str(rr).encode())
r.recvuntil(b's:')
r.sendline(str(s).encode())
r.interactive()
class
解题过程
下载附件得到一个class文件,打开可以发现是一个python文件,里面有很多的类。搜索一下OS 命令,可以发现存在一个 cat /flag
该函数肯定和flag有关,每个类和函数均为_符号+八个字节,尝试将执行os.system('cat /flag')
的整个利用链的所有类和函数全部统计出来
写一个python脚本进行污点分析:
import ast
import astor
with open("class", "r") as file:
source_code = file.read()
syntax_tree = ast.parse(source_code)
class_dict = {}
for node in syntax_tree.body:
if isinstance(node, ast.ClassDef):
class_name = node.name
class_dict[class_name] = {}
for inner_node in node.body:
if isinstance(inner_node, ast.FunctionDef):
func_name = inner_node.name
class_dict[class_name][func_name] = []
for code in inner_node.body:
class_dict[class_name][func_name].append(astor.to_source(code).strip())
class_keys = []
for func_dict in class_dict.items():
if 'os.system' in str(func_dict):
sub = func_dict[1][list(func_dict[1].items())[0][0]][0].split('n')[0].split(' ')
if sub[2] == '>':
if int(sub[1]) < int(sub[3][:-1]):
continue
elif sub[2] == '<':
if int(sub[1]) > int(sub[3][:-1]):
continue
class_keys.append(func_dict[0])
for key in class_keys:
class_key = key
func_key = list(class_dict[class_key])[0]
list_class = [class_key]
flag = 1
flags = 0
while flag != 0 and flags == 0:
flag = 1
flags = 0
for func_dict in class_dict.items():
for code in func_dict[1].items():
if class_key in code[1][0] and func_key in code[1][0]:
sub = code[1][0].split('n')[0].split(' ')
if sub[2] == '>':
if int(sub[1]) < int(sub[3][:-1]):
flag = -1
elif sub[2] == '<':
if int(sub[1]) > int(sub[3][:-1]):
flag = -1
flags = 2
func_key = code[0]
class_key = func_dict[0]
list_class.append(class_key)
else:
if flag == -1:
flags = 1
if flags == 2:
flags = 0
continue
if flag == 1 and flags == 0:
break
if flag != -1:
for cla in list_class:
print(cla[1:].replace('O', '0'), end='')
跑一遍即可得到一整个利用链的命名顺序,注意将’O’字符转化为’0’字符
做一个hex解密,可以得到是7z压缩包
解压压缩包即可得到flag:
SavethePrincess
解题过程
通过格式化字符串漏洞泄漏libc_base,canary,pie_base,stack地址,
因为禁用了exevce函数,进而通过构造orw获取flag。
from pwn import *
from struct import *
from ctypes import *
#import ctf_pb2
c = cdll.LoadLibrary('./libc.so.6')
# srop : frame = SigreturnFrame()
# fmt : fmtstr_payload(offset=7,writes={0x4031E0:0x0401445,0x403410:0x401445},numbwritten=((14*2)+1),write_size='short')
s = lambda a :pw.send(a)
sl = lambda a :pw.sendline(a)
sa = lambda a,b :pw.sendafter(a,b)
sla = lambda a,b :pw.sendlineafter(a,b)
r = lambda a=6666 :pw.recv(a)
rl = lambda :pw.recvline()
ru = lambda a,b=True :pw.recvuntil(a,b)
g64 = lambda :u64(pw.recvuntil(b'x7f')[-6:].ljust(8,b'x00'))
g32 = lambda :u32(pw.recvuntil(b'xf7').ljust(4,b'x00'))
gl = lambda a :u64(pw.recvuntil(a,drop=True).ljust(8,b'x00'))
gc = lambda a :u64(pw.recv(7).rjust(8,b'x00'))
pwpw = lambda :pw.interactive()
lss = lambda s :log.success(' 33[1;31;40m%s --> 0x%x