枫霜月雨のblog

Maple-rain

0%

MTCTF密码部分wp

发表于 更新于
本文字数： 14k 阅读时长 ≈ 13 分钟

美团CTF密码部分wp

比赛的时候做出了easy_RSA，然后random的RSA部分做了一半，可惜不懂pwn模块，没写出nc爆破的脚本。RSAsig在第二天复现即将做出来的时候，平台靶机关了，难受。

easy_RSA

经典套娃题

第一层

题目：

1
2
3
4
n=0x9371c61a2b760109781f229d43c6f05b58de65aa2a674ff92334cb5219132448d72c1293c145eb6f35e58791669f2d8d3b6ce506f4b3543beb947cf119f463a00bd33a33c4d566c4fd3f4c73c697fa5f3bf65976284b9cc96ec817241385d480003cdda9649fa0995b013e66f583c9a9710f7e18396fbf461cb31720f94a0f79L
e=0x3
encrypt(m)=0x5f4e03f28702208b215f39f1c8598b77074bfa238dfb9ce424af7cc8a61f7ea48ffbbd5a5e1a10f686c3f240e85d011f6c8b968d1d607b2e1d5a78ad6947b7d3ec8f33ad32489befab601fe745164e4ff4aed7630da89af7f902f6a1bf7266c9c95b29f2c69c33b93a709f282d43b10c61b1a1fe76f5fee970780d7512389fd1L
encrypt(m+1)=0x5f4e03f28702208b215f39f1c8598b77074bfa238dfb9ce424af7cc8a61f7ea48ffc5c26b0c12bcff9f697f274f59f0e55a147768332fc1f1bac5bbc8f9bb508104f232bdd20091d26adc52e36feda4a156eae7dce4650f83fabc828fdcfb01d25efb98db8b94811ca855a6aa77caff991e7b986db844ff7a140218449aaa7e8L

解答：

原题，一个字不改的，直接上exp了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import *
def getM2(a,b,c1,c2,n,e):
    a3 = pow(a,e,n)
    b3 = pow(b,e,n)
    first = c1-a3*c2+2*b3
    first = first % n
    second = e*b*(a3*c2-b3)
    second = second % n
    third = second*inverse(first,n)
    third = third % n
    fourth = (third+b)*inverse(a,n)
    return fourth % n
e=0x3
a=1
b=-1
c1=0x5f4e03f28702208b215f39f1c8598b77074bfa238dfb9ce424af7cc8a61f7ea48ffbbd5a5e1a10f686c3f240e85d011f6c8b968d1d607b2e1d5a78ad6947b7d3ec8f33ad32489befab601fe745164e4ff4aed7630da89af7f902f6a1bf7266c9c95b29f2c69c33b93a709f282d43b10c61b1a1fe76f5fee970780d7512389fd1
c2=0x5f4e03f28702208b215f39f1c8598b77074bfa238dfb9ce424af7cc8a61f7ea48ffc5c26b0c12bcff9f697f274f59f0e55a147768332fc1f1bac5bbc8f9bb508104f232bdd20091d26adc52e36feda4a156eae7dce4650f83fabc828fdcfb01d25efb98db8b94811ca855a6aa77caff991e7b986db844ff7a140218449aaa7e8
padding2=1
n=0x9371c61a2b760109781f229d43c6f05b58de65aa2a674ff92334cb5219132448d72c1293c145eb6f35e58791669f2d8d3b6ce506f4b3543beb947cf119f463a00bd33a33c4d566c4fd3f4c73c697fa5f3bf65976284b9cc96ec817241385d480003cdda9649fa0995b013e66f583c9a9710f7e18396fbf461cb31720f94a0f79
m = getM2(a,b,c1,c2,n,e)-padding2
print(long_to_bytes(m))

解出来

1
the key is :everything_is_easy_in_this_question

即为压缩包密码，然后进入第二层

参考链接：

原理参考：浅析RSA Padding Attack

脚本参考：深入浅出RSA在CTF中的攻击套路

第二层

题目给了提示，one_time_cipher，一次一密。额，又是原题，但不完全是。需要修改一下。

题目:

1
2
3
4
5
6
7
8
9
10
11
12
280316470206017f5f163a3460100b111b2c254e103715600f13,
091b0f471d05153811122c70340c0111053a394e0b39500f0a18,
4638080a1e49243e55531a3e23161d411a362e4044111f374409,
0e0d15470206017f59122935601405421d3a244e10371560140f,
031a08080e1a540d62327f242517101d4e2b2807177f13280511,
0a090f001e491d2c111d3024601405431a36231b083e022c1d,
16000406080c543854077f24280144451c2a254e093a0333051a,
02050701120a01334553393f32441d5e1b716027107f19334417,
131f15470800192f5d167f352e0716481e2b29010a7139600c12,
1609411e141c543c501d7f232f0812544e2b2807177f00320b1f,
0a090c470a1c1d3c5a1f2670210a0011093a344e103715600712,
141e04040f49153142043a22601711520d3a331d0826

解答：

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
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
#!/usr/bin/python
## OTP - Recovering the private key from a set of messages that were encrypted w/ the same private key (Many time pad attack) - crypto100-many_time_secret @ alexctf 2017
# @author intrd - http://dann.com.br/ 
# Original code by jwomers: https://github.com/Jwomers/many-time-pad-attack/blob/master/attack.py)

import string
import collections
import sets, sys

# 11 unknown ciphertexts (in hex format), all encrpyted with the same key

c1 = "280316470206017f5f163a3460100b111b2c254e103715600f13"
c2 = "091b0f471d05153811122c70340c0111053a394e0b39500f0a18"
c3 = "4638080a1e49243e55531a3e23161d411a362e4044111f374409"
c4 = "0e0d15470206017f59122935601405421d3a244e10371560140f"
c5 = "031a08080e1a540d62327f242517101d4e2b2807177f13280511"
c6 = "0a090f001e491d2c111d3024601405431a36231b083e022c1d"
c7 = "16000406080c543854077f24280144451c2a254e093a0333051a"
c8 = "02050701120a01334553393f32441d5e1b716027107f19334417"
c9 = "131f15470800192f5d167f352e0716481e2b29010a7139600c12"
c10 = "1609411e141c543c501d7f232f0812544e2b2807177f00320b1f"
c11 = "0a090c470a1c1d3c5a1f2670210a0011093a344e103715600712"
ciphers = [c1, c2, c3, c4, c5, c6, c7, c8, c9, c10, c11]
# The target ciphertext we want to crack
target_cipher = "141e04040f49153142043a22601711520d3a331d0826"

# XORs two string
def strxor(a, b):     # xor two strings (trims the longer input)
    return "".join([chr(ord(x) ^ ord(y)) for (x, y) in zip(a, b)])

# To store the final key
final_key = [None]*150
# To store the positions we know are broken
known_key_positions = set()

# For each ciphertext
for current_index, ciphertext in enumerate(ciphers):
	counter = collections.Counter()
	# for each other ciphertext
	for index, ciphertext2 in enumerate(ciphers):
		if current_index != index: # don't xor a ciphertext with itself
			for indexOfChar, char in enumerate(strxor(ciphertext.decode('hex'), ciphertext2.decode('hex'))): # Xor the two ciphertexts
				# If a character in the xored result is a alphanumeric character, it means there was probably a space character in one of the plaintexts (we don't know which one)
				if char in string.printable and char.isalpha(): counter[indexOfChar] += 1 # Increment the counter at this index
	knownSpaceIndexes = []

	# Loop through all positions where a space character was possible in the current_index cipher
	for ind, val in counter.items():
		# If a space was found at least 7 times at this index out of the 9 possible XORS, then the space character was likely from the current_index cipher!
		if val >= 7: knownSpaceIndexes.append(ind)
	#print knownSpaceIndexes # Shows all the positions where we now know the key!

	# Now Xor the current_index with spaces, and at the knownSpaceIndexes positions we get the key back!
	xor_with_spaces = strxor(ciphertext.decode('hex'),' '*150)
	for index in knownSpaceIndexes:
		# Store the key's value at the correct position
		final_key[index] = xor_with_spaces[index].encode('hex')
		# Record that we known the key at this position
		known_key_positions.add(index)

# Construct a hex key from the currently known key, adding in '00' hex chars where we do not know (to make a complete hex string)
final_key_hex = ''.join([val if val is not None else '00' for val in final_key])
# Xor the currently known key with the target cipher
output = strxor(target_cipher.decode('hex'),final_key_hex.decode('hex'))

print "Fix this sentence:"
print ''.join([char if index in known_key_positions else '*' for index, char in enumerate(output)])+"\n"

# WAIT.. MANUAL STEP HERE 
# This output are printing a * if that character is not known yet
# fix the missing characters like this: "Let*M**k*ow if *o{*a" = "cure, Let Me know if you a"
# if is too hard, change the target_cipher to another one and try again
# and we have our key to fix the entire text!

#sys.exit(0) #comment and continue if u got a good key
list1=' abcdefghijklmnopqrstuvwxyz'

for i in range(26):
	for j in range(26):
		for k in range(26):

			target_plaintext = "r{0}e{1}{2} answer successly".format(list1[i],list1[j],list1[k])
# print "Fixed:"
# print target_plaintext+"\n"

			key = strxor(target_cipher.decode('hex'),target_plaintext)

#print "Decrypted msg:"
#for cipher in ciphers:
#	print strxor(cipher.decode('hex'),key)
			if 'flag{' in key:
				print target_plaintext
				print "\nPrivate key recovered: "+key+"\n"
				for cipher in ciphers:
					print strxor(cipher.decode('hex'),key)

# print "Fixed:"
# print target_plaintext+"\n"

# key = strxor(target_cipher.decode('hex'),target_plaintext)

# print "Decrypted msg:"
# for cipher in ciphers:
# 	print strxor(cipher.decode('hex'),key)

# print "\nPrivate key recovered: "+key+"\n"

得到的密文为r*e** answer succks*ly

爆破恢复+猜测后，得到实际密文:rrect answer successly

明文段落：

1
2
3
4
5
6
7
8
9
10
11
12
Now you need to use th
own flag as the key of
 Time Pad Encryptin. N
hat you have passed th
evious RSA test, this 
lenge is not particula
please get the true me
difficult for you. It 
ust simple encryption.
pe you can solve this 
lem quickly and get th
rrect answer successly

得到flag：flag{it_1s_P@dd1n_@nd_好恶心啊，缺了几个字符。

仔细看明文出来的，缺了字母，恶心坏了。

缺了4个字节，最后一个字节肯定是}，复原第八行明文后异或爆破前三位，得到flag

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import random
 
def xor_bytes(key_stream, message):
    length = min(len(key_stream), len(message))
    return bytes([key_stream[i]^ message[i] for i in range(length)])
 
message = b"difficult for you. It is j"
for i in range(128):
    for j in range(128):
        for k in range(128):
            key_stream = b'flag{it_1s_P@dd1n_@nd_'+f'{chr(i)}'.encode()+f'{chr(j)}'.encode()+f'{chr(k)}'.encode()+b'}'
            cipher = xor_bytes(key_stream, message)
            if cipher.hex() == "02050701120a01334553393f32441d5e1b716027107f19334417":
                print(key_stream)
                print(cipher.hex())
                print(xor_bytes(key_stream, cipher))

参考链接：

alexctf2k17-crypto100（类似例题有杭电2019week1）

Wankko ReeのBlog

RSAsig

题目：

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
#encoding:utf-8
import signal
from Crypto.PublicKey import RSA
from Crypto.Util.number import *
import Crypto.Util.number
from secret import flag
from base64 import *
from Crypto import Random
from proof_of_work import proof_of_work
banner = '''
 ____                             ____  _                   _
/ ___|  ___  ___ _   _ _ __ ___  / ___|(_) __ _ _ __   __ _| |_ _   _ _ __ ___
\___ \ / _ \/ __| | | | '__/ _ \ \___ \| |/ _` | '_ \ / _` | __| | | | '__/ _ \
 ___) |  __/ (__| |_| | | |  __/  ___) | | (_| | | | | (_| | |_| |_| | | |  __/
|____/ \___|\___|\__,_|_|  \___| |____/|_|\__, |_| |_|\__,_|\__|\__,_|_|  \___|
                                          |___/

'''

def dosend(m):
    sys.stdout.flush()
    print(m)
    sys.stdout.flush()

def dorecv():
    sys.stdout.flush()
    return sys.stdin.readline().strip()

def gen():
    random_generator = Random.new().read
    rsa = RSA.generate(1024, random_generator)
    private_pem = rsa
    return private_pem

def main():
    rsakey = gen()
    a = RSA._RSAobj(None, rsakey)
    modBits = Crypto.Util.number.size(rsakey.n)
    k = ceil_div(modBits,8)

    while (True):
        dosend("Welcome to this secure cryptosystem:")
        dosend("1.Get flag.\n2.Have my signature.\n3.Exit.\n4.Get my key.")
        dosend("What is your choice?")

        try:
            option = int(dorecv().strip())
            if option == 1:
                cipher = rsakey.encrypt(flag, k)
                dosend(b64encode(cipher[0]))
            elif option == 2:
                dosend("What message to sign?")
                m = int(dorecv().strip())
                sign = a.sign(m, k)
                dosend(str(sign[0][0]))
            elif option == 3:
                dosend("Bye~")
                exit()
            elif option == 4:
                dosend(str(rsakey.n))
                dosend(str(rsakey.e))
            else:
                dosend("Invalid choice!")
        except:
            exit()
#if  proof_of_work():
#    exit()
#signal.alarm(20)
main()

解答:

第一关为sha224爆破。基操，直接贴exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
import hashlib
str1 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890'
for i in range(len(str1)):
	for j in range(len(str1)):
		for k in range(len(str1)):	
			message = '{0}{1}{2}Vw3UrFafQ94N5k4QB'.format(str1[i],str1[j],str1[k])
			#print(message)
			m = hashlib.sha224()
			m.update(message.encode('utf-8'))
			c = m.hexdigest()
			if c == '6da53efa50c3ef1481cc0f403212262dd1bcead74d9f0b34f306318c':
				print (message)
				print(c)

爆破前3位字符，然后进下一关。

疑似非预期了，昨天早上复现到一半，机器被关了，连不上了。根据VN的wp和大佬的指点，可以想象到解法步骤：

点1拿到base64，将base64转为十进制数，拿到2里签名。签名出来直接转byte就是flag。

人麻了，人麻了。人麻了？人麻了！

random（第一关RSA部分）

第一关都没过，还没做到LCG。

第一关：

题目：

1
2
3
4
5
6
7
rsa_sign:pow(m,d,p)
e*d+n:3563329754048976946603729466426236052000141166700839903323255268203185709020494450173369806214666850943076188175778667508946270492708397447950521732324059148390232744011000065982865974194986726739638097566303135573072114448615095262066554751858952042395375417151593676621825939069783767865138657768553767717034970
e*d-n:3563121718917234588723786463275555826875232380691165919033718924958406353810813480184744219046717838078497090403751007254545187720107602959381881715875898243474504999760208133192572812110967142474619366650504948619637909653723376917174456091396220576841259798792078769198369072982063716206690589554604992470787752
tmp = e*d
please sign the message with p:you_can_get_more_message
please enter sign:

解答：

先简单的二元一次方程解出n和e*d的值。

1
2
len(bin(tmp))-2=1039
len(bin(n))-2=1024

可以发现，两者差了15位。

写一个脚本爆破phi的值。

1
2
3
4
5
6
phi=[]  #11个
for i in range(2**15,2**16):
	if ((tmp-1) // i) * i != tmp-1:
		continue
	else:
		phi.append((tmp-1) // i)

可以得到有11个可能的phi值。

随后用z3爆破，得到p和q

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from z3 import *
x=Int('x')
y=Int('y')
s = Solver()

for i in range(11):
	s.add(x*y==n)
	s.add(x+y==n-phi[i]+1)
	s.add(x>0)
	s.add(y>0)


	if s.check()!=sat:
		continue
	else:
		print(phi[i])
		print('x=',s.model()[x])
		print('y=',s.model()[y])
		continue
1
2
3
4
p = 10980405508174271259925333166343579553719061316941945190323939083665489902286168861229664589365210026388298173482496757264697996404794685064674668272479771
q = 9473016801951797771267846445459738473973421588058140695253031511700407533935872397264731631901174665159278878658035094231228063878480145556088206641042779
phi=104017565871178939971501575340112562454393004836992144768171622389677604840484994312793583974506432289548886013830127200541386300397244284320008224080452437410449815269897363953401430206474104816882552899007591140131802079961736224008071736969511510673117632180401571196581547933965545949203486211512709601060
#k=34256

然后的操作比较复杂，先素数分解tmp，得到因子

image-20210526080806673

279位显然是可以忽略的，然后用以下代码判断e的因子。

1
2
3
4
5
e=[3,47,97,157,1601,21851,56277292709098311733]
for i in range(7):
	if tmp // e[i] == inverse(e[i],phi):
		print('e=',e[i])
#因子为：56277292709098311733

判断完因子后，使其互乘得到所有可能的e。代码来源于Wankko Ree大佬，用的算法类似于DFS。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
a=[3,47,97,157,1601,21851]
b = set()

def go(p, t):
    b.add(t)
    if p == len(a):
        return
    go(p+1, t*a[p])
    go(p+1, t)

go(0, 1)
c = list(b)
for i in range(len(b)):
	c[i]*=56277292709098311733
print(c)

解出来后，需要爆破所有可能的e，总数量为

应该是很好理解的，然后pq的值不确定，同样需要爆破。由于需要用到pwn的remote模块，而我完全不会。同时靶机也在第二天关闭，未能完整复现。根据已有WP，e的值应该是5627729270909831173 * 3 * 21851，然后根据题目要求sign：pow(m,d,p)签名。

后半部分LCG未能复现。

参考链接：

WP参考VN战队wp，中间的递归求e来自于Wankko Ree大佬。

-------------本文结束感谢您的阅读-------------