2021第五届强网杯网络安全挑战赛决赛-crypto writeup
2021第五届强网杯网络安全挑战赛决赛-crypto writeup
不垫底就算成功蛮恶心的，差点因为服务器太慢出不来
from sage.stats.distributions.discrete_gaussian_integer import DiscreteGaussianDistributionIntegerSampler
from random import randint, getrandbits
from secret import flag
import sys
import signalq = 2 ^ 54
t = 83
T = 3
d = 1024
delta = int(q / t)
sigma = 2
P. = PolynomialRing(ZZ)
f = x ^ d + 1
R. = P.quotient(f)
D = DiscreteGaussianDistributionIntegerSampler(sigma=sigma)def sample1():
return R([D() for _ in range(d)])def sample2():
return R([randint(0, q - 1) for _ in range(d)])def sample3(x):
return [randint(0, T - 1) for _ in range(x)]def Roundq(a):
A = a.list()
for i in range(len(A)):
A[i] = A[i] % q
if A[i] > (q / 2):
A[i] = A[i] - q
return R(A)def Roundt(a):
A = a.list()
for i in range(len(A)):
A[i] = A[i] % t
if A[i] > (t / 2):
A[i] = A[i] - t
return R(A)def keygen():
s = sample1()
a = Roundq(sample2())
e = Roundq(sample1())
pk = [Roundq(-(a * s + e)), a]
return s, pkdef encrypt(m):
u = sample1()
e1 = sample1()
e2 = sample1()
return (Roundq(pk[0] * u + e1 + delta * m), Roundq(pk[1] * u + e2))def baseT(n, b=T):
v = []
while True:
x = n // b
y = n % b
v.append(y)
if x == 0:
break
n = x
v.reverse()
return vdef mutual(k, c, s):
tmp = t * Roundq(c[0] + c[1] * s)
TMP = tmp.list()
for i in range(len(TMP)):
TMP[i] = round(TMP[i] / q)
tmp2 = Roundt(R(TMP))
if tmp2[min(k, d)] == 0:
print(True)
else:
print(False)signal.alarm(1024)
sk, pk = keygen()
print(f"public key:{
pk[0].list()}, {
pk[1].list()}")namelist = ["admin", "Adam", "Bruce", "Chris", "David"]
users = dict()
for i in namelist:
users[i] = getrandbits(32)menu = '''
1.Add friends
2.find friends
3.Send Message
4.Regist'''friends = set()
while 1:
print(f"Current number of users: {
len(users)}")
print(menu)
op = int(input(">").strip())
if op == 1:
name = input("name:").strip()
id_num = int(input("id:").strip())
if name in users.keys():
if id_num == users[name]:
friends.add(name)
else:
print("failed")
else:
print("failed")
elif op == 2:
op2 = input("recv ct?(Y/N)").strip()
if op2.upper() == "Y":
for name in users.keys():
id_num = users[name]
x = baseT(id_num)
y = x + sample3(d - len(x))
ct = encrypt(R(y))
print(ct[0].list(), ct[1].list())
op3 = input("continue?(Y/N)")
if op3.upper() == "N":
break
elif op3.upper() != "Y":
sys.exit(1)
elif op2.upper() != "N":
sys.exit(1)for i in range(len(users)):
c1 = input("c1:").strip().split(" ")
c2 = input("c2:").strip().split(" ")
cc1 = list(map(int, c1))
cc2 = list(map(int, c2))
mutual(i, [R(cc1), R(cc2)], sk)elif op == 3:
name = input("name:").strip()
message = input("message:").strip()
if name not in friends:
print("failed")
else:
if name == "admin":
if message == "give me the flag":
print(flag)
else:
print(f"send '{
message}' to {
name}")
elif op == 4:
name = input("name:").strip()
if name not in users.keys():
users[name] = getrandbits(32)
print("succeeded")
else:
print("failed")
else:
sys.exit(1) 分析
需要我们泄露admin的id来添加一个friend来get massage
【2021第五届强网杯网络安全挑战赛决赛-crypto writeup】这个题是一个经典的 CCA attack on FPSI
针对全同态的一个攻击，但和常规情况不同的是在生成密钥时并未像标准加密系统中为了方便硬件运算使用0 1序列生成的多项式
而是使用 [-7,-6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6,7] 得序列随机生成的私钥
from sage.stats.distributions.discrete_gaussian_integer import DiscreteGaussianDistributionIntegerSampler
D = DiscreteGaussianDistributionIntegerSampler(sigma=sigma)def sample_2():
return R([randint(0,1) for _ in range(d)])
def sample1():
return R([D() for _ in range(d)])def keygen():
s = sample1()
a = Roundq(sample2())
e = Roundq(sample1())
pk = [Roundq(-(a * s + e)), a]
return s, pk原版payload只需要给 t i = m t_i=m ti?=m
可以恢复出密钥
payload:
M=delta//4+50
Recoverd_key=[]
for i in range(d):
Recoverd_key.append(recover_key(i))def recover_key(i):
t1=[0 for _ in range(d)]
t1[i]=M
t2=M
cc0=pk[0]+R(t1)
cc1=pk[1]+R(t2)
ans = decrypt([cc0,cc1]).list()
return ans[i]
但题目情况密钥并不为0 1 序列而且Oracle attack只能判断为该位上数字是否为0
在改变t1[i]=M M的个数后发现以下性质：
| 私钥\ 返回的数据 | M | 2M | 7M | 5M |
|---|---|---|---|---|
| 7 | 2 | 2 | 3 | 0 |
| 6 | 2 | 2 | 3 | 0 |
| 5 | 2 | 2 | 3 | 0 |
| 4 | 1 | 2 | 3 | 0 |
| 3 | 1 | 1 | 3 | -1 |
| 2 | 1 | 1 | 2 | -1 |
| 1 | 1 | 1 | 2 | -1 |
| 0 | 0 | 1 | 2 | -1 |
| -1 | 0 | 0 | 2 | -2 |
| -2 | 0 | 0 | 1 | -2 |
| -3 | -1 | 0 | 1 | -2 |
| -4 | -1 | -1 | 1 | -2 |
| -5 | -1 | -1 | 1 | -3 |
| -6 | -1 | -1 | 0 | -3 |
| -7 | -1 | -1 | 0 | -3 |
exp
from pwn import *
# from icecream import *
from tqdm import tqdmfrom time import *
p1 = time()# -----------------------------------
# get pk
# io = remote('0.0.0.0',10001)
io = remote('172.20.5.23',8001)q = 2 ^ 54
t = 83
T = 3
d = 1024
delta = int(q / t)
sigma = 2
P. = PolynomialRing(ZZ)
f = x ^ d + 1
R. = P.quotient(f)def Roundt(a):
A = a.list()
for i in range(len(A)):
A[i] = A[i] % t
if A[i] > (t / 2):
A[i] = A[i] - t
return R(A)def Roundq(a):
A = a.list()
for i in range(len(A)):
A[i] = A[i] % q
if A[i] > (q / 2):
A[i] = A[i] - q
return R(A)
def mutual2(k, c, s):
tmp = t * Roundq(c[0] + c[1] * s)
TMP = tmp.list()
for i in range(len(TMP)):
TMP[i] = round(TMP[i] / q)
tmp2 = Roundt(R(TMP))
return tmp2io.recvuntil('public key:[')
pk1 = io.recvuntil(']')[:-1]
io.recvuntil('[')
pk2 = io.recvuntil(']')[:-1]
# print(pk1)
# print(pk2[:100])
pk2 = [int(i) for i in pk2.split(b',')]
# print(pk2[:10])
pk1 = [int(i) for i in pk1.split(b',')]
pk=[R(pk1),R(pk2)]
for i in range(1024-5):
print(io.recvuntil('>'))
io.sendline('4')
io.sendline(str(i))M=delta//4+50
padding = [8,7, 6, 5, 4, 3, 2, 1,0, -1, -2, -3, -4, -5,-4]
sks=[-7,-6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6,7]
rk=[100 for i in range(1024)]for x in range(len(sks)):
print(io.recvuntil('>'))
io.sendline('2')
print(io.recvuntil('recv ct?(Y/N)'))
io.sendline('Y')
sleep(1)
print(io.recvuntil('['))
adminC1 = io.recvuntil(']')[:-1]
print((io.recvuntil('[')))
adminC2 = io.recvuntil(']')[:-1]
adminC1 = [int(i) for i in adminC1.split(b',')]
# print(pk2[:10])
adminC2 = [int(i) for i in adminC2.split(b',')] print(io.recvuntil('continue?(Y/N)'))
io.sendline('N')
pad = padding[x]
print(f'第{
x}个了')
for k in tqdm(range(1024)):
t1=[0 for _ in range(d)]
t1[k]=pad*M
t2=M
# ================================
cc0=(pk[0]+R(t1)).list()
payload_c1 = ''
for i in cc0:
payload_c1 += str(i)
payload_c1+=' '
payload_c2 = ''
cc1=(pk[1]+R(t2)).list()
for i in cc1:
payload_c2 += str(i)
payload_c2+=' 'io.recvuntil('c1:')
io.sendline(payload_c1)
# sleep(1)
io.recvuntil('c2:')
io.sendline(payload_c2)
# =====================================fb = io.recvline()
if(b'True' in fb and rk[k]==100):
rk[k] = sks[x]
# input()
for i in range(len(rk)):
if(rk[i]==100):
rk[i]=7sk = R(rk)
adminCT=[R(adminC1),R(adminC2)]
# cc0=R(ct[0].list())
# cc1=R(ct[1].list())ans = mutual2(0,adminCT,sk)x = ans.list()[:25]
admin_id =0
use=[]
ids=[]
for i in x:
admin_id *= T
admin_id += i
use.append(i)
ids.append(admin_id)print(rk)
print(ids)
# io.interactive()
sleep(1)
for id in ids:
print(io.recvuntil('>'))
io.sendline('1')
print(io.recvuntil('name:'))
io.sendline('admin')
print(io.recvuntil('id:'))
io.sendline(str(id))
print(io.recvline())
print(io.recvuntil('>'))
io.sendline('3')
io.sendlineafter('name:','admin')
io.sendlineafter('message:','give me the flag')
sleep(1)
print(io.recv(2048))
p2 = time()
print(p2-p1)
FLAG
b'name:'
b'id:'
b'failed\n'
b'Current number of users: 1024\n\n1.Add friends\n2.find friends\n3.Send Message\n4.Regist\n>'
b'name:'
b'id:'
b'failed\n'
b'Current number of users: 1024\n\n1.Add friends\n2.find friends\n3.Send Message\n4.Regist\n>'
b'flag{CCA_attack_BFV_123698745}\n'
[*] Closed connection to 172.20.5.23 port 8001
/mnt/c/U/1/De/qwb决赛/bfv
服务器OI速度及其慢 等了半天才打通
推荐阅读
- 2021-02-17|2021-02-17 小儿按摩膻中穴-舒缓咳嗽
- 2021-02-10（找不回的“年味”……）
- 2021-05-05五一的五天假期结束了
- 2021/1/15|2021/1/15 数幸福
- 20210307《挑战赛怂人胆》【能量将帅挑战赛（01）】
- 2020年，告别焦虑的自己，2021年，期待满意的自己。
- 今天开心的三件事（第454天，20210125，星期一，阴）
- 《我怎样教语文》读书打卡（十九）20210317
- 华杉版资治通鉴【1154】别人家的孩子，是中国人民永远的噩梦。2021-04-03
- 2021年第四周复盘|2021年第四周复盘 | 寻找初心，再次出发