一年一度的Mini L CTF!!! 出了好多锅TnT(委屈.jpg)

# Double S

# Description:

近来,L-team 成员内部流传着一个秘密,而你只能得到少部分成员加密后的密文,你能够拿到这个秘密吗。

# Attachment:

from Crypto.Util.number import *
from secret import flag
import random
import os
assert flag[:9] == b'miniLCTF{'
assert flag[-1:] == b'}'
flag = flag[9:-1]
flag = b'#' + flag + b'#' + os.urandom((64-len(flag)) % 64)
members = [
    ...
]
my_sec = [bytes_to_long(flag[i*4:i*4+4]) for i in range(16)]
n = 32
t = 32
class Sharing:
    def __init__(self,secret):
        self.A = secret
        self.init_func()
    def init_func(self):
        for i in range(n - 16):
            self.A.append(random.randrange(1,1<<32))
    
    def f(self,x):
        ret = 0
        tmp = 1
        for i in range(n):
            ret += self.A[i] * tmp
            tmp *= x
        return ret
def get_msg(name,SS):
    inp = bytes_to_long(name)
    cip = SS.f(inp)
    return name,cip
def main():
    SS = Sharing(my_sec)
    f = open("./outputs",'wb')
    for i in range(t):
        tmp_member = random.choice(members)
        members.remove(tmp_member)
        name , cipher = get_msg(tmp_member.encode(),SS)
        f.write(name + b" " + str(cipher).encode() + b"\n")
    f.close()
main()

# Expected Solution

题目给出 Sharing 类,计算多项式

f(x)=a0+a1x+a2x2+...+a31x31f(x)=a_0+a_1x+a_2x^2+...+a_{31}x^{31}

其中 a0,a1a_0,a_1 等部分系数是 flag 的内容。并且题目给出 t 条多项式 f (x) 和 x 的值,其中 t=n=32。于是可以构造矩阵

[1x0x02...x0311x1x12...x131...............1x31x312...x3131][a0a1...a31]=[c0c1...c31]\left[\begin{matrix}1&x_0&x_0^2&...&x_0^{31}\\ 1&x_1&x_1^2&...&x_1^{31}\\ ...&...&...&...&...\\ 1&x_{31}&x_{31}^2&...&x_{31}^{31}\\ \end{matrix}\right]\cdot \left[\begin{matrix}a_0\\ a_1\\ ...\\ a_{31}\\ \end{matrix}\right]= \left[\begin{matrix}c_0\\ c_1\\ ...\\ c_{31}\\ \end{matrix}\right]

代入发现左边这个矩阵满秩,即可通过解多项式获得系数的值。

# Unexpected Solution

由于多项式是在整数环下,并且可能某 member 的 id 太短辣,以至于可以转换成 id 的进制,就能直接得到系数 😦 。

# Double SS

# Description:

又有一个新的秘密被大家分享了,这次你还能够拿到这个秘密吗?

# Attachment:

from Crypto.Util.number import *
from secret import flag
import random
import os
assert flag[:9] == b'miniLCTF{'
assert flag[-1:] == b'}'
flag = flag[9:-1]
table = b"ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890abcdefghijklmnopqrstuvwxyz!_@#$%^&"
flag = b'#' + flag + b'#' 
for i in range((64-len(flag)) % 64):
    flag += bytes([random.choice(table)]) 
members = [
	...
]
my_sec = [bytes_to_long(flag[i*4:i*4+4]) for i in range(16)]
n = 32
t = 31
class Sharing:
    def __init__(self,secret):
        self.A = secret
        self.init_func()
    def init_func(self):
        for i in range(n - 16):
            self.A.append(random.randrange(1,1<<32))
    
    def f(self,x):
        ret = 0
        tmp = 1
        for i in range(n):
            ret += self.A[i] * tmp
            tmp *= x
        return ret
def get_msg(name,SS):
    inp = bytes_to_long(name)
    cip = SS.f(inp)
    return name,cip
def main():
    SS = Sharing(my_sec)
    f = open("./outputs",'wb')
    for i in range(t):
        tmp_member = random.choice(members)
        members.remove(tmp_member)
        name , cipher = get_msg(tmp_member.encode(),SS)
        f.write(name + b" " + str(cipher).encode() + b"\n")
    f.close()
main()

# Expected Solution

主函数部分与 DoubleS 类似,不过由于少给一条多项式,其中 t+1=n=32。有两种做法:

  1. 由于 4 个 byte 一块,第一块已知第一个字符为 # ,并且其中的字符是在 table 中的,同 DoubleS 构造爆破 # 后面的三个字符即可, 爆破时间是 O (70^3)。
  2. 第一块已知 第一个字符为 #,我们可以通过给他假设加入一条式子,我们让他成为满秩矩阵,解密即可得到近似解。

# Unexpected Solution

由于多项式是在整数环下,和 DoubleS 相同的非预期 TnT

# Double SS revenge

# Description:

由于上一道题和 Double S 相同的非预期,于是又调整了到了模多项式上。

# Attachment:

...
p = getPrime(256)
...
class Sharing:
    def __init__(self,secret):
        self.A = secret
        self.init_func()
    def init_func(self):
        for i in range(n - 16):
            self.A.append(random.randrange(1,1<<32))
    
    def f(self,x):
        ret = 0
        tmp = 1
        for i in range(n):
            ret += self.A[i] * tmp
            tmp *= x
        return ret % p
...

# Expected Solution

题目主要函数同上。只不过改成了 % p,并且给出了 p。

主要做法也与 Double SS 的预期解类似。

# factorchal

# Description:

这道题看起来好像很容易呢,你能在 5min 内挑战成功吗

# Attachment:

from Crypto.Util.number import*
from secret import flag
from hashlib import sha256
import socketserver
import signal
import string
import random
table = string.ascii_letters+string.digits
def get_key():
    tmp = random.randrange(1,1<<27)
    while 1:
        tmp += 2
        if isPrime(tmp):
            break
    d = tmp * p
    e = inverse(d,phi)
    return d,e
p = getPrime(512)
q = getPrime(512)
n = p * q
phi = (p-1) * (q-1)
d,e = get_key()
msg = getRandomRange(1,1<<400)
c = pow(msg,e,n)
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):
        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 sha.decode()
    def handle(self):
        Hash = self.proof_of_work()
        if not Hash:
            self.request.close()
        self.send(b"\nI'll send you my encrypt data.Can you decrypt it in 5mins???")
        self.send(b'e = ' + hex(e).encode())
        self.send(b'n = ' + hex(n).encode())
        self.send(b'c = ' + hex(c).encode())
        signal.alarm(300)
        self.send(b'plz response the msg:')
        sec_m = int(self.recv(),16)
        if sec_m == msg:
            self.send(b'\nYou win!Give you my flag!')
            self.send(flag)
        self.send(b"\nConnection has been closed  =.=  ")
        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', 10001
    print("HOST:POST " + HOST+":" + str(PORT))
    server = ForkedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    server.serve_forever()

# Expected Solution

主要漏洞点是题目中的 getkey 函数,其中 d=kp,并且 k 需要是一个 (1<<27) 内的素数。

我们选择的 r 是随意给出的一个数据,但不能是 n 的因子(那不就分解 n 了,想什么孽)或者 n 的倍数

c=memodn,(kp)e=kiϕ+1rkpe=rmodnrke1rmodnrkeprmodpc=m^{e}\mod n,(kp)e=k_i\phi+1\\ r^{kpe}=r\mod n\\ r^{ke\cdot 1}\equiv r \mod n\Rightarrow r^{ke\cdot p}\equiv r \mod p

接下来通过欧拉定理得到

rkermodprker0modpr^{ke}\equiv r \mod p\Rightarrow r^{ke}-r\equiv 0 \mod p

由于 k 是一个素数,此处 k 的爆破空间准确来讲范围应该是 2^26。

如果说 r 不是 q 的倍数 GCD(rker,n)=pGCD(r^{ke}-r,n)=p 了,但如果是,那么可能就找不到,并且不是 n 的倍数,那可能或许你就能够直接分解 n(废话。

ps: 此处如果直接用 python 自带的 pow 函数,可能速度不够,因为限制时间在 5min 内。因此调用 gmpy2 库中的 powmod 函数(gmpy2 yyds!)。同时爆破 k 过程中可以使用 s2 = 2^{2e},s1=s1 * s2% p 去优化速度。

# Copiano

# Description:

Block of Piano?

# Attachment:

from Crypto.Util.number import *
import os
from secret import flag
nbit = 2048
p, q = getPrime(nbit // 2), getPrime(nbit // 2)
N = p * q
e = 3
cipher_block_length = nbit // 8
plain_block_length = cipher_block_length // 8
def pad(msg):
    return msg + ((plain_block_length - len(msg) % plain_block_length) % plain_block_length) * b'\x00'
def block_enc(msg):
    m = bytes_to_long(msg)
    x = bytes_to_long(os.urandom(nbit // 8))
    c = long_to_bytes(pow(m ^ x, e, N)).rjust(cipher_block_length,b'\x00')
    t = m & x
    return c , (x,t)
def ecb_mode_enc(msg):
    plain_block = [msg[plain_block_length * i: plain_block_length * (i + 1)] for i in range(len(msg) // plain_block_length)]
    cipher_text = b''
    x_list = []
    t_list = []
    for msg_part in plain_block:
        cipher_part , (x_tmp,t_tmp) = block_enc(msg_part)
        cipher_text += cipher_part
        x_list.append(x_tmp)
        t_list.append(t_tmp)
    return cipher_text , x_list , t_list
cipher , x_list, t_list = ecb_mode_enc(pad(flag))
f = open("./output",'wb')
f.write(b"N =" + str(N).encode() + b'\n')
f.write(b"e =" + str(e).encode() + b'\n')
f.write(b"c =" + cipher + b'\n')
f.write(b"x_list =" +str(x_list).encode() + b'\n')
f.write(b"t_list =" +str(t_list).encode() + b'\n')
f.close()

# Expected Solution

题目中加密部分是讲明文分块进行 ECB 模式的加密。每块加密过程如下

enc(m)=(mx)emodNenc(m)=(m\oplus x)^e\mod N

并且给出了 m&xm\&x ,因此我们可以分析得到

mx=m+x2m&xm\oplus x = m+x-2m\&x

回代 enc (m),我们发现

(mx)3(m+x2m&x)modN(m\oplus x)^3\equiv (m+x-2m\&x)\mod N

其中 x 与 m&xm\&x 我们都已知,并且 m 大致是 256bit,而 N 为 2048 位。因此想到的是使用 coppersmith 去解决这个问题。

# Unexpected Solution

本题由于 e=3 很小,并且在调的过程中让 x 变小,但是没调回去,于是导致了低指数加密攻击......

即可以拿到 mxm\oplus x ,直接异或回去就拿到了 m。TnT...............

# R1ngWin

# Description:

ERROR ! ERROR ! ERROR !

# Hint:

Do you know how Ding Key Exchange works?

# Attachment:

from bfv.batch_encoder import BatchEncoder
from bfv.bfv_encryptor import BFVEncryptor
from bfv.bfv_key_generator import BFVKeyGenerator
from bfv.bfv_parameters import BFVParameters
from secret import flag
# source of py-fhe:https://github.com/sarojaerabelli/py-fhe/
def main():
    degree = 32 
    plain_modulus = 257
    ciph_modulus = 0x9000000000000
    params = BFVParameters(poly_degree=degree,
                            plain_modulus=plain_modulus,
                            ciph_modulus=ciph_modulus)
    key_generator = BFVKeyGenerator(params,e_times=3)
    f = open("./output",'w')
    public_key1 = key_generator.public_key
    f.write("public_key1 = (" + str(public_key1.p0) + "," + str(public_key1.p1) + ")\n")
    # encrypt part
    encoder = BatchEncoder(params)
    encryptor = BFVEncryptor(params, public_key1)
    message = list(flag)
    plain = encoder.encode(message)
    cipher = encryptor.encrypt(plain)
    f.write("cipher:" + str(cipher))
    f.close()
if __name__ == '__main__':
    main()

修改了一点点库函数

class BFVKeyGenerator:
    def __init__(self, params,e_times=1):
        self.generate_secret_key(params)
        self.generate_public_key(params,e_times)
        self.generate_relin_key(params)
    def generate_secret_key(self, params):
        self.secret_key = SecretKey(Polynomial(params.poly_degree,
                                               sample_triangle(params.poly_degree)))
    def generate_public_key(self, params,etimes):
        pk_coeff = Polynomial(params.poly_degree,
                              sample_uniform(0, params.ciph_modulus, params.poly_degree,odd=True))
        pk_error = Polynomial(params.poly_degree,
                              sample_triangle(params.poly_degree)).scalar_multiply(etimes,params.ciph_modulus)
        p0 = pk_error.add(pk_coeff.multiply(
            self.secret_key.s, params.ciph_modulus), params.ciph_modulus).scalar_multiply(
                -1, params.ciph_modulus)
        p1 = pk_coeff
        self.public_key = PublicKey(p0, p1)

# Expected Solution

该题是想让选手们了解一下 RLWE 这个东西,并且本题是通过使用了 py-fhe 库 [4] 进行的加密。

这里如果了解一点 RLWE 中的 BFV,我们可以知道它是在不可约多项式 f 的商环上,该题

f=x32+1f=x^{32}+1

同时 BFVKeyGenerator(params,e_times=3) 中可以得知公钥 p 和私钥 s 的关系如下

p=(p0=p1s+3e,p1)p=(p_0=p_1s+3e,p_1)

并且可以知道多项式私钥 s 的系数定义域是在 {1,0,1}\{-1,0,1\} 中,扰动向量是 3 的倍数。此处给出一个 Hint: Ding Key Exchange。

是由于 DKE 中有一个 "错误消除" 的方式,也是该题的出题思路 [1]。

DKE 中的错误消除方法是 Jintai Ding 在 2012 年发明的基于 LWE 和 RLWE 的类 DH 密钥交换算法 [2]。

kA=sApB=asAsB+2sAeB;kB=sBpA=asBsA+2sBeA;kAkB=a(sAsBsAsB)+2(sAeBsBeA)=2(sAeBsBeA)k_A=s_Ap_B=as_As_B+2s_Ae_B;k_B=s_Bp_A=as_Bs_A+2s_Be_A;\\ k_A-k_B=a(s_As_B-s_As_B)+2(s_Ae_B-s_Be_A)=2(s_Ae_B-s_Be_A)

可以得知 kA 以及 kB 奇偶性相同。于是 A 和 B 就可以将自己得到的 kA 或 kB 模 2 之后就能够得到相同的会话密钥了。

这道题是将其模 3 了我们就可以直接消除掉 e,但是好像与 DKE 的关系可能也不是很大(或许只是引起我这种想法的点吧。

不过 shallow 和 hashhash 都说该方法蛮像 Nguyen 早期攻击 GGH 的方法,如果有兴趣可以去看看他写的相关 paper [3]。

# Postscript:

可能因为第一次给一场比赛出这么多题,而且没有好好测题 (🔨🔨🔨),出了好一些非预期,背大锅,同时最近也没啥出题灵感 5555,出得不是很好,但是总归也希望这些题目能给大家带来一些学习以及上升的空间吧。

不过想到一年前也差不多这个时候的 Mini L CTF,肝了三天,能 ak 了 crypto (不过就 3 道的原因吧),算是我进入 L-Team 的入场券,同时也是我才一点点摸到 CTF 的门槛,真快啊,今年就到我们办了。不过过程中拿着 admin 账号看后台交 flag 记录,还挺有意思的捏:

比如说企鹅的题 who is the god of XDSEC ,Reply: miniLCTF{rx} ! 以及 zsky 学长的 You_are_too_younggthis_is_a_fake_flag!!! ,还有晚安题里的协会人们的黑照,以及彩蛋题之 hacked by shallow,甚至 Noah 的取证题里还有一个 dbt下崽器 (???)

出题人们属实太会整活辣。同时今年的学弟们也很给力捏 (ddw)!!!

也十分感谢 Merak,0Rays,Vidar 和 CNSS 等校外师傅愿意来赏脸参加 XD

# Reference:

[1] : 基于格 RLWE 问题的密钥交换协议和原理 - 知乎

[2] : A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem

[3] : Cryptanalysis of the Goldreich-Goldwasser-Halevi Cryptosystem from Crypto ’97

[4] : py-fhe