May 9, 2022

Official Writeups of Crypto Chals in Mini L CTF 2022

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

Double S

Description:

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

Attachment:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
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类,计算多项式

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

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

Unexpected Solution

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

Double SS

Description:

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

Attachment:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
...
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
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的倍数

接下来通过欧拉定理得到

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

如果说r不是q的倍数 了,但如果是,那么可能就找不到,并且不是n的倍数,那可能或许你就能够直接分解n(废话。

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

Copiano

Description:

Block of Piano?

Attachment:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
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模式的加密。每块加密过程如下

并且给出了 Misplaced &m&x ,因此我们可以分析得到
Misplaced & m\oplus x = m+x-2m&x
回代enc(m),我们发现
Misplaced & (m\oplus x)^3\equiv (m+x-2m&x)\mod N
其中x与 Misplaced &m&x 我们都已知,并且m大致是256bit,而N为2048位。因此想到的是使用coppersmith去解决这个问题。

Unexpected Solution

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

即可以拿到 ,直接异或回去就拿到了m。TnT……………

R1ngWin

Description:

ERROR ! ERROR ! ERROR !

Hint:

Do you know how Ding Key Exchange works?

Attachment:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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()

修改了一点点库函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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的商环上,该题

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

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

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

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

可以得知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

About this Post

This post is written by deebato, licensed under CC BY-NC 4.0.

#ctf#cryptography