Record some of my challenge-solving ideas for Securinets CTF 2022,if there are any discrepancies ,plz correct me ~.

# Sherry

task.py:

#!/usr/bin/env sage
from sage.all import *
from Crypto.Util.number import *
import random, sys, json
FLAG = "Securinets{REDACTED}"
def getRandomElement(F, deg):
        return F.random_element(degree=deg)
def polyToList(p):
        return p.list()
def listToPoly(F, l):
        return sum(F(c*x**i) for i, c in enumerate(l))
def polySum(p1, p2):
        if p1.parent() == p2.parent():
                return p1 + p2
        else:
                return p1 + p1.parent()(p2)
def getShare(g, secret):
        y = g**secret
        print(polyToList(y))
        e = getRandomElement(PolynomialRing(GF(getPrime(256)), "x"), 10)
        print(e)
        s = polySum(y, e)
        share = polyToList(s)
        return share
if __name__ == '__main__':
        print(f"Welcome to Black Organization.\nTo join us, you have to guess our secret.\n")
        p = getStrongPrime(512)
        P = PolynomialRing(GF(p), "x")
        x = P.gen()
        N = getRandomElement(P, 10)
        Q = P.quotient_ring(N**2)
        x = Q.gen()
        G = Q(getRandomElement(P, 10))
        secret = random.randint(1, p-1)
        print(secret)
        pub = G**secret
        params = {"N": polyToList(N), "pub": polyToList(pub), "G": polyToList(G), "p":p}
        print(f"{params}\n")
        for _ in range(5):
                try:
                        g = eval(input("Your guess g : "))
                        s = eval(input("Your guess s : "))
                        g = listToPoly(Q, g)
                        s = int(s, 16) % p
                        if g**s == pub:
                                if s != secret:
                                        print(f"Don't cheat! :)")
                                        continue
                                print(f'From now, your name will be Sherry! Here is your flag : {FLAG}')
                                sys.exit()
                        else:
                                share = {'share': getShare(g, secret)}
                                print(f'{share}\n')
                except Exception as e:
                        print(e)
                        sys.exit()

根据 题意 分析,我们可以得到以下关系。

pub=GsecretmodN2y1=gsecretmodN2,y1+e1=share1pub = G^{secret}\mod N^2\\ y_1 = g^{secret}\mod N^2,y_1+e_1=share_1

其中 g 是我们发送给服务器方的一个参数,G,N,share 以及他们是在 GF (p) 下的,并且 p 是 512 位,而 y1 以及 e1 我们不知道,而其中 e1 是 256 位的一个 11 个系数 度为 10 的多项式。

这道题是需要我们找到 secret,并且满足

gs=Gsecret,s==secretg^s=G^{secret},s==secret

我们如果给出 g,s 不符合 g^s == pub ,则服务器返回一个 share 就是上述的 share。

到这里我们或许会尝试 g = pub ,s = 1,但是很不幸,"Don't cheat! 😃"。

接下去我们可以发现如果给出 g=a(a 是一个常数),大致是可以通过 HNP 的手段将 a ^ secret % p 恢复出来,可是这里就出现问题了,我恢复出来了 a ^ secret % p,但是 p 是一个 strongPrime, 那么我们没有办法求得他的阶,很遗憾,Failed。

再想想,如果 secret 是一个奇数,我给出 g=N+1,他返回的是

(N+1)secret+emodN2=secretN+1+emodN2(N+1)^{secret}+e\mod N^2 = secret\cdot N + 1 +e \mod N^2

但是 N 的度和 e 的度是 10,怎么样才能把它们区分开来,第一个想到的是将值 % N,但是发现得到的值可能会比较大,但是这里我们可以发现

(share1)secretNkp=e(share-1)-secret\cdot N - kp=e

这样我们接下去对他进行 LLL 一下,构造格子

[share0share1...shareiN0N1...Nipp....p]\left[\begin{matrix}share_0&share_1&...&share_i\\ N_0&N_1&...&N_i\\ p\\&p\\&&....\\&&&p \end{matrix}\right]

LLL 之后拿到只要 e 的大小接近 256bit,那么就是对应得到的 secret 了。

接着回代即可。

# AES2

task.py:

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import os, sys, hashlib, random
FLAG = b"Securinets{REDACTED}"
key, iv1, iv2 = [os.urandom(16) for _ in range(3)]
def xor(a, b):
	return bytes(i ^ j for i, j in zip(a, b))
def get_token(msg, iv1, iv2):
	if len(msg) % 16 != 0:
		msg = pad(msg, 16)
	aes = AES.new(key, AES.MODE_ECB)
	blocks = [msg[i:i+16] for i in range(0, len(msg), 16)]
	enc = b""
	tmp1 = iv1
	tmp2 = iv2
	for block in blocks:
		tmp = aes.encrypt(xor(block, tmp1))
		_tmp = aes.encrypt(xor(tmp, tmp2))
		enc += _tmp
		tmp1 = _tmp
		tmp2 = tmp
	return enc
def proof(msg):
	res = b"\x00"*16
	for i in range(0, len(msg), 16):
		res = xor(res, msg[i:i+16])
	return hashlib.sha256(res).digest()
if __name__ == "__main__":
	alice_username = os.urandom(32)
	alice_token = get_token(alice_username, iv1, iv2)
	print(f"Alice's creds : {alice_username.hex()} -> {alice_token.hex()}\n")
	while True:
		try:
			username = bytes.fromhex(input("Username : "))
			token = get_token(username, iv1, iv2)
			print(f"Your creds : {username.hex()} -> {token.hex()}")
			if proof(token) == proof(alice_token):
				if token == alice_token:
					print(f"You are not Alice!")
					sys.exit()
				else:
					print(f"Hey Alice! Here is your flag {FLAG}")
					sys.exit()	
			else:
				print("Try again!\n")
		except Exception as e:
			print(e)
			print("Invalid input.\n")

aes_1

分析题目中需要得到 proof (Aliceusername) == proof (myusername),而这里他 proof 部分使用的是 xor,其中我们可以想到如果是有长度限制的话很容易想到去交换 enc1 和 enc2 的位置去得到,但是目前我认为并没有办法做下去。

但是该题没有长度限制,我们想它既然是 xor,的那么我只需要让后面加 2 块 (maybe more?) 去使得他能够得到的 enc3^enc4=0 即可。

在这里我们可以发现 BLOCK 和 ENC 是可控的,即可以做到 CPA。

在第二块以后的 IV1 部分我们也是可以控制其第一次 AES 之前的值,但是 AES 之后我们就不可知,只有 ENC2 之后是可知的。

2 次 AES 之间存在一个 XOR IV2,我们可以发现他与这块使用的 IV2 无关,只与上一块前半部分 AES 有关,那么可以控制后面只需要使得 ENC3 和 ENC4 相等即可,往回推,如果可以使得 BLOCK2 和 BLOCK3 第一次 AES 后相同即可,而这里我们发现他 AES 之前使用的异或值我们都是可知的,那么 ENC1 ^ BLOCK2=ENC2 ^ BLOCK3 即可做到在 ENC3 和 ENC4 部分对于前一次 AES 用于异或的值相同。那么接下来只需要第一次 AES 前输入的值相同即可得到 ENC3==ENC4,与第二块和第二块相同分析,使得 ENC3 ^ BLOCK4 = ENC2 ^ BLOCK3 = ENC1 ^ BLOCK2

:=> BLOCK3 = ENC1 ^ BLOCK2 ^ ENC2 ; BLOCK4 = ENC1 ^ BLOCK2 ^ ENC3 ;

这样就可以做到成功伪造。

# Well

只要跟着题目的流程走即可得到同构下的 key 是相同的。

请我喝[茶]~( ̄▽ ̄)~*

De3B4to 微信支付

微信支付

De3B4to 支付宝

支付宝