writeup for 2020 红明谷杯

虎符前的一个比赛, 号都没注册, 借隔壁宿舍的号玩了一下. 密码一共就三题, 一题AES-OCB难爆(反正我是第一次知道OCB这个模式), 国内居然搜不到关于OCB的资料. 只找到一两个paper, 没这个耐心看. 剩下两题, 一题签到(估计是非预期才这么简单), 还有一道La爷爷那边有记录, 就直接做了.

0x00 babyForgery

problem

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
import os
import string
import random
import socketserver
import signal
from hashlib import sha256

from ocb.aes import AES # https://github.com/kravietz/pyOCB
from ocb import OCB

FLAG = #####REDACTED#####

BLOCKSIZE = 16
MENU = br"""
[1] Encrypt
[2] Decrypt
[3] Get Flag
[4] Exit
"""

class Task(socketserver.BaseRequestHandler):
def _recvall(self):
pass

def send(self, msg, newline=True):
pass

def recv(self, prompt=b'> '):
pass

def recvhex(self, prompt=b'> '):
pass

def proof_of_work(self):
pass

def timeout_handler(self, signum, frame):
pass

def encrypt(self, nonce, message, associate_data=b''):
assert nonce not in self.NONCEs
self.NONCEs.add(nonce)
self.ocb.setNonce(nonce)
tag, cipher = self.ocb.encrypt(bytearray(message), bytearray(associate_data))
return (bytes(cipher), bytes(tag))

def decrypt(self, nonce, cipher, tag, associate_data=b''):
self.ocb.setNonce(nonce)
authenticated, message = self.ocb.decrypt(
*map(bytearray, (associate_data, cipher, tag))
)
if not authenticated:
raise ValueError('REJECT')
return bytes(message)

def handle(self):
signal.signal(signal.SIGALRM, self.timeout_handler)
signal.alarm(60)
if not self.proof_of_work():
return

aes = AES(128)
self.ocb = OCB(aes)
KEY = os.urandom(BLOCKSIZE)
self.ocb.setKey(KEY)
self.NONCEs = set()

while True:
USERNAME = self.recv(prompt=b'Enter username > ')
if len(USERNAME) > BLOCKSIZE:
self.send(b"I can't remember long names")
continue
if USERNAME == b'Alice':
self.send(b'Name already used')
continue
break

signal.alarm(60)
while True:
self.send(MENU, newline=False)
try:
choice = int(self.recv(prompt=b'Enter option > '))

if choice == 1:
nonce = self.recvhex(prompt=b'Enter nonce > ')
message = self.recvhex(prompt=b'Enter message > ')
associate_data = b'from ' + USERNAME
ciphertext, tag = self.encrypt(nonce, message, associate_data)
self.send(str.encode(f"ciphertext: {ciphertext.hex()}"))
self.send(str.encode(f"tag: {tag.hex()}"))

elif choice == 2:
nonce = self.recvhex(prompt=b'Enter nonce > ')
ciphertext = self.recvhex(prompt=b'Enter ciphertext > ')
tag = self.recvhex(prompt=b'Enter tag > ')
associate_data = self.recvhex(prompt=b'Enter associate data > ')
message = self.decrypt(nonce, ciphertext, tag, associate_data)
self.send(str.encode(f"message: {message.hex()}"))

elif choice == 3:
nonce = self.recvhex(prompt=b'Enter nonce > ')
ciphertext = self.recvhex(prompt=b'Enter ciphertext > ')
tag = self.recvhex(prompt=b'Enter tag > ')
associate_data = b'from Alice'
message = self.decrypt(nonce, ciphertext, tag, associate_data)
if message == b'please_give_me_the_flag':
self.send(FLAG)

elif choice == 4:
break
else:
break

except:
self.send(b'Error!')
break
signal.alarm(0)

self.send(b'Bye!')
self.request.close()

class ForkedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
pass


if __name__ == "__main__":
HOST, PORT = '0.0.0.0', 10000
print(HOST, PORT)
server = ForkedServer((HOST, PORT), Task)
server.allow_reuse_address = True
server.serve_forever()

不重要的函数用pass省略了

analyses

全场只有一解的题, 真的不会, 等wp学习了

0x01 RSA attack

problem

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
from gmpy2 import *
from Crypto.Util.number import *
import sympy
import random
from secret import flag

p1 = getPrime(1024)
print(p1)
#p1=172071201093945294154292240631809733545154559633386758234063824053438835958515543354911249971174172649606257936857627547311760174511316984409767738981247877005802155796623587461774104951797122995266217334158736848307655543970322950339988489801672160058805422153816950022590644650247595501280192205506649936031

p2 = p1 - random(999,99999)
print(p2)
#p2=172071201093945294154292240631809733545154559633386758234063824053438835958515543354911249971174172649606257936857627547311760174511316984409767738981247877005802155796623587461774104951797122995266217334158736848307655543970322950339988489801672160058805422153816950022590644650247595501280192205506649902034

p_1=1
for i in range(1,p1+1):
p_1*=i
p3 = sympy.nextPrime(p_1 % p2 )

p4 = p3 >> 50 << 50
p = p4
while(isPrime(P)!=1):
P = p + random.randint(0,2**50)

Q = getPrime(1024)

e = 1+1+1
N = P * Q
print(N)
#N=28592245028568852124815768977111125874262599260058745599820769758676575163359612268623240652811172009403854869932602124987089815595007954065785558682294503755479266935877152343298248656222514238984548734114192436817346633473367019138600818158715715935132231386478333980631609437639665255977026081124468935510279104246449817606049991764744352123119281766258347177186790624246492739368005511017524914036614317783472537220720739454744527197507751921840839876863945184171493740832516867733853656800209669179467244407710022070593053034488226101034106881990117738617496520445046561073310892360430531295027470929927226907793

flag=bytes_to_long(flag)
c = pow(flag,e,N)
print(c)
#c=15839981826831548396886036749682663273035548220969819480071392201237477433920362840542848967952612687163860026284987497137578272157113399130705412843449686711908583139117413

analyse

我估计着这是非预期

看完一遍代码就知道是已知高位求了, 可惜这题目跟新生赛的题一个尿性, 没有对进行padding, 导致可以直接对开3次方……

非预期exp

1
2
3
4
from gmpy2 import iroot
from Crypto.Util.number import long_to_bytes
c = 15839981826831548396886036749682663273035548220969819480071392201237477433920362840542848967952612687163860026284987497137578272157113399130705412843449686711908583139117413
print(long_to_bytes(iroot(c,3)[0]))

预期解

威尔逊定理???? 题目是不是搞错了, p2<p1, 那么阶乘的时候肯定有p2在p_1里面…. 模p2直接是0了

????????????

0x02 ezCRT

problem

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
from Crypto.Util.number import *
import gmpy2
from random import shuffle

flag = b"flag is here"


def shuffle_flag(s):
str_list = list(s)
shuffle(str_list)
return ''.join(str_list)


nl = []
el = []
count = 0
while count != 5:
p = getPrime(512)
q = getPrime(512)
n = p * q
phi = (p - 1) * (q - 1)
d = gmpy2.next_prime(bytes_to_long(flag))
e = gmpy2.invert(d, phi)
nl.append(n)
el.append(int(e))
count += 1

print(nl)
print(el)

cl = []
flag = shuffle_flag(flag.decode()).encode()
for i in range(len(nl)):
cl.append(pow(bytes_to_long(flag), el[i], nl[i]))
print(cl)

analyses

Common Private Exponent -> https://www.ijcsi.org/papers/IJCSI-9-2-1-311-314.pdf

当私钥满足

其中为最大的, 就可以使用这个方法

我们可以记, 且 因为每次用的都是同一个私钥, 那么可以有:

可以构造格子

规约出来后, 取第一行第一个就是了.
计算出就是flag了

exp

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
#sagemath
from gmpy2 import *
from Crypto.Util.number import long_to_bytes as l2b
N = [...]
E = [...]
PK = []
for i,j in zip(N,E):
PK.append([i,j])

for i in range(len(PK)):
for j in range(i,len(PK)):
if PK[j][0] > PK[i][0]:
PK[j],PK[i] = PK[i] ,PK[j]
PK = PK[::-1]
M=iroot(int(PK[-1][0]),int(2))[0]
a=[0]*6
a[0]=[M,PK[0][1],PK[1][1],PK[2][1],PK[3][1],PK[4][1]]
a[1]=[0,-PK[0][0],0,0,0,0]
a[2]=[0,0,-PK[1][0],0,0,0]
a[3]=[0,0,0,-PK[2][0],0,0]
a[4]=[0,0,0,0,-PK[3][0],0]
a[5]=[0,0,0,0,0,-PK[4][0]]

Mat = matrix(ZZ,a)
Mat_LLL=Mat.BKZ()
d = int(abs(Mat_LLL[0][0])//M)
assert d * M == abs(Mat_LLL[0][0])
l2b(d)