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
|
#!/usr/bin/python
# -*- coding: utf-8 -*-
from Crypto.Cipher import AES
from Crypto.Util.strxor import strxor
from Crypto.Random import get_random_bytes
from FLAG import flag
class MAC:
def __init__(self):
self.key = get_random_bytes(16)
self.iv = get_random_bytes(16)
def pad(self, msg):
pad_length = 16 - len(msg) % 16
return msg + chr(pad_length) * pad_length
def unpad(self, msg):
return msg[:-ord(msg[-1])]
def code(self, msg):
res = chr(0)*16
for i in range(len(msg)/16):
res = strxor(msg[i*16:(i+1)*16], res)
aes = AES.new(self.key, AES.MODE_CBC, self.iv)
return aes.encrypt(res).encode('hex')
def identity(self, msg, code):
if self.code(msg) == code:
msg = self.unpad(msg)
if msg == 'please send me your flag':
print 'remote: ok, here is your flag:%s' % flag
else:
print 'remote: I got it'
else:
print 'remote: hacker!'
if __name__ == '__main__':
mac = MAC()
message = 'see you at three o\'clock tomorrow'
print 'you seem to have intercepted something:{%s:%s}' %(mac.pad(message).encode('hex'), mac.code(mac.pad(message)))
print 'so send your message:'
msg = raw_input()
print 'and your code:'
code = raw_input()
mac.identity(msg.decode('hex'), code)
exit()
|
得到信息：
- AES_CBC模式加密
- 已知的1个明-密文对：
pad('see you at three o\'clock tomorrow') - 从服务器收到的密文
- 明文长度48=16*3，AES加密的是strxor后的明文
- 输入msg和code，其中msg要满足unpad(msg)后是
'please send me your flag'，而且用同样的key和IV加密这个msg后得到的内容是自己输入的code
由于密钥key和初始向量IV都是随机生成的，不可能爆破出来，所以key和IV是未知的。但想要用同样的key和IV重新AES加密自己输入的msg来使加密结果等于自己输入的code，这在未知key和IV的情况是是不可能的，除非只能构造跟
一样的明文和密文来验证。
注意到这边对长度超过16的明文加密前的操作：一个是pad，还有一个就是strxor。
message每次都是固定的，都是‘see you at three o’clock tomorrow’，pad后就是'see you at three o'clock tomorrow\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f'，然后再对这个pad后的结果进行strxor操作，也就是分成3组，每组对应位置的字符异或，然后得到一个16bytes长的res，每次pad后的结果也都是一样的，所以第一次加密的res也都是一样的，可以先算出来，是res = '$\x05ML\x1a\x0f\x19DN\x0f@\x16\x08\x0f\x18\x05'，所以每次AES都是对这个加密。
这里，我们可以构造一个msg，使得：
unpad(msg) = 'please send me your flag'strxor(pad(msg)) = res = '$\x05ML\x1a\x0f\x19DN\x0f@\x16\x08\x0f\x18\x05'
首先又注意到这边的pad,unpad函数的一个性质：
unpad时，是按照末尾字节的值来截断尾部的。
len('please send me your flag') = 24，所以截断后的长度必须为24，且msg[:24]='please send me your flag'。
再次，要使strxor(pad(msg)) = res = '$\x05ML\x1a\x0f\x19DN\x0f@\x16\x08\x0f\x18\x05'，仅仅长为24的'please send me your flag'是无法满足要求的，需要至少扩充到16×3=48位。 那么如果这里我们选择的msg长度为48的话，末尾字节的值必须是3×16-24=24=0x18`，所以msg[47]=’\x18’``。
现在，只需要填充剩余的msg[24:47]，使得strxor(pad(msg))后的结果是res就可以了。
下面是我的一个填充方法：
1
2
3
4
5
6
7
8
9
10
11
12
13
|
def fuck()
pad_message = 'see you at three o\'clock tomorrow' + 15 * chr(15)
res = chr(0) * 16
for i in range(len(pad_message) / 16):
res = strxor(pad_message[i*16:(i+1)*16], res)
# res = '$\x05ML\x1a\x0f\x19DN\x0f@\x16\x08\x0f\x18\x05'
msg = 'please send me your flagdeadbee' # 填充到16*2-1长，后面的用异或算出来就可以了。
msg += chr(ord(msg[15])^ord(res[15])^(16*3-24)) # 第16*2位不能填充，需要根据第16*1位和16*3位算出来
payload3 = ''
for i in range(15): #第三段的前15位
payload3 += chr(ord(msg[i]) ^ ord(msg[i + 16]) ^ ord(res[i]))
payload3 += chr(16*3 - 24) # 最后一位
return msg + payload3
|
然后就能构造出满足上面两个条件的msg，最后只要把这个msg和之前服务器发过来的密文发过去就可以了。
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
|
from pwn import *
from Crypto.Util.strxor import strxor
def fuck():
pad_message = 'see you at three o\'clock tomorrow' + 15 * chr(15)
res = chr(0) * 16
for i in range(len(pad_message) / 16):
res = strxor(pad_message[i*16:(i+1)*16], res)
# res = '$\x05ML\x1a\x0f\x19DN\x0f@\x16\x08\x0f\x18\x05'
msg = 'please send me your flagdeadbee'
msg += chr(ord(msg[15])^ord(res[15])^(16*3-24))
payload3 = ''
for i in range(15):
payload3 += chr(ord(msg[i]) ^ ord(msg[i + 16]) ^ ord(res[i]))
payload3 += chr(16*3 - 24)
return msg + payload3
# 'please send me your flagdeadbeed;\x1cZ\r\x0f\x06XPO\x04ER\x07\x0f]\x18'
r = remote('47.240.41.112', 12345)
context.log_level = 'debug'
code = r.recvline()[-34:-2]
r.recvuntil('message:\n')
r.sendline(fuck().encode('hex'))
r.recvuntil('code:\n')
r.sendline(code)
r.interactive()
# remote: ok, here is your flag:sctf{y0u_4r3_7h3_4p3x_ch4mp10n}
|
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
|
#!/usr/bin/python
# -*- coding: utf-8 -*-
from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from binascii import *
from FLAG import flag
from MESSAGE import message
class telecom:
def __init__(self, name):
self.name = name
self.key = get_random_bytes(16)
self.iv = get_random_bytes(16)
self.e = 3
p = getPrime(512)
q = getPrime(512)
self.fn = (p-1)*(q-1)
while True:
if GCD(self.e, self.fn) != 1:
p = getPrime(512)
q = getPrime(512)
self.fn = (p - 1) * (q - 1)
else:
break
self.d = inverse(self.e, self.fn)
self.n = p * q
def RSA_encrypt(self, plaintext):
assert bytes_to_long(plaintext).bit_length() < 512
a = getPrime(512)
b = getPrime(512)
m = bytes_to_long(plaintext)
c = pow(a * m + b, self.e, self.n)
message = 'admin:'+self.name+ ', your ciphertext is: c=' +hex(c)+ '\nwith some parameters:a=' +hex(a)+ ', b=' +hex(b)+'\n'
return message
def RSA_decrypt(self):
pass
def broadcast(self):
message = self.name+':'+'my pub-key is: '+'e='+str(self.e)+','+'n='+hex(self.n)+'\n'
return message
def pad(self, msg):
pad_length = 16 - len(msg) % 16
return msg + chr(pad_length) * pad_length
def unpad(self, msg):
return msg[:-ord(msg[-1])]
def AES_encrypt(self, message):
message = self.pad(message)
aes = AES.new(self.key, AES.MODE_OFB, self.iv)
return aes.encrypt(message)
def AES_decrypt(self, message):
aes = AES.new(self.key, AES.MODE_OFB, self.iv)
return self.unpad(aes.decrypt(message))
def proof_of_work():
p = getPrime(512)
q = getPrime(512)
n = p*q
e = 65537
fn = (p-1)*(q-1)
d = inverse(e, fn)
print "pubkey:{e, n}={65537, %s}\n" %hex(n)
print 'Give me something you want to encrypt:'
sys.stdout.flush()
m = int(raw_input())
c = pow(m, e, n)
if m == pow(c, d, n):
return False
return True
if __name__ == '__main__':
if not proof_of_work():
exit()
while True:
print 'You have the following options to do:\n[1]monitor\n[2]forge the message'
choice = raw_input()
if int(choice) == 1:
Alpha = telecom('Alpha')
Bravo = telecom('Bravo')
Charlie = telecom('Charlie')
print Alpha.broadcast()
print Bravo.broadcast()
print Charlie.broadcast()
print Alpha.RSA_encrypt(message)
print Bravo.RSA_encrypt(message)
print Charlie.RSA_encrypt(message)
print 'Alpha:David, make sure you\'ve read this:' + hexlify(Alpha.AES_encrypt(message))+'\n'
elif int(choice) == 2:
print 'you can send message to David now:'
input_cipher = raw_input()
if Alpha.AES_decrypt(unhexlify(input_cipher)) == message.replace('afternoon', 'morning'):
print 'you made it, this reward is prepared for you:' + flag
exit()
else:
print 'you failed'
exit()
else:
exit()
|
得到信息：
- 对同一个message线性pad后(a*m+b)，用不同的公钥加密3次，给出了每次加密完后c,a,b。
- 注意到e=3，低加密指数。
- 需要伪造对message
AES_OFB模式加密后的密文，使得解密后的明文中的afternoon被篡改为morning。
这个RSA很像之前强网杯的Challenge4，感觉可以用广播攻击。
但是这里的m是被pad过的，每次都不一样，所以Basic Broadcast Attack失效。
又看到pad是一个很类似强网杯Challenge5，但Related Message Attack显然不可能，因为并没有用同一个公钥对线性相关的m加密多次。
陷入困境，感觉这个可能要结合上述两个方法。搜寻一番后，发现果然有一个Broadcast Attack with Linear Padding。
结合wiki
，以及另外一篇给出了方法的文章
：
获得message，需要:
- 计算所有n的乘积(n1×n2×n3)
- 用CRT（中国剩余定理）计算每一个满足条件的T
- 建立在模N下的多项式环
- 计算每一个g=(a*x+b)^3-c，这里x就是我们想要的message
- 计算Ti*gi的和（多项式）并赋值给g
- 将多项式的最高次项系数化简为1
- 寻找g的根，多半就是message了
sage代码如下：
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
|
n=[82032188601940227752297417081294226543597575504416918007449661834299359067950465277706498580089107996755263427091915970632797292872337319081745842487600650365878082117843668748166556806508008992831799872668452888180728669229746719472110704095075270054792936797172777444638714087380138926023368608670981217091L, 144790109105696916737182878418639456117731330157011040204957460047368669964683349809310287923136309839414697358993776555550819796186587083349149593331591983649252876768081158685346872502328624435541992264407180812711658502822714431271074073131726414451778163016485973268562068628815869252990930579057754896173L, 75291463839461164667469229834843531305640509692662939401339536264435630748347655598022583030492163266505500249672170695051585801149706658572170917049940314913097219983077566373502443956836685905331660776209201294705162873672584599713463731511599324513575176660760395849807244914156996168333606402035878533381L]
c=[67497575318327879887596391364750753705169316916381036313287449919879742983169383559661964321852173414328395486815887056253402772840945029491705527313929081200464807407660414760161256035556293097461881324625478369607471130614351104463500599958969159169050874869751290896066581553838854811211907890750382746511L, 61417831208102453560914910052558296402381558961421547405790778254948342894828953024945127165546949565456233519419089997499796829911888055718138539158703076265672618023467204457469261580970191667410598385021272475612274977806376487258894705386083011345682311011008867926893257606509774484971214854873119396523L, 59139963329969277014867029295568306182785272886586884034466445222852652054855577647906813408336405743993989682438127549115465873135913639429070056018223773094951946677500375796734667908820959638217714514827653064127798201054131814345268242102046781245681177963062451193062599946629137832003277003715562783676L]
a=[10690284821425810281664680252419661592694244929597744471278947260947912212068164535406286136913239607137611205694268949515679703337156206775167860560960531L, 7084608813044653312908744751862853435370315673659572445175422987292025037024211691353987001505135183178528203370140920842675898979940113026011801133323387L, 7109556811500607022678698446990028501935112258837085372401389025171854709554488399418026529159439666193759252114352506000602595045828924640827082875525761L]
b=[8978952666402441172502571446625322184642731589908616056188753886315351207063560919714949439324395532521646399347732857483571187621924964620683026077931937L, 7161265246275328861792856065576124793212521627707981245532742473215873826957088742546550304939190194348241371526295386537134008106992791660625241828335409L, 10713585141780358045259127130466271189717723982908989041527459583656559664545085864785815191726519183276131221864053677348130406321637993310732667315632693L]
from functools import reduce
import gmpy2
def modinv(a, m):
return int(gmpy2.invert(gmpy2.mpz(a), gmpy2.mpz(m)))
def chinese_remainder(n, a):
sum = 0
prod = reduce(lambda a, b: a * b, n)
# 并行运算
for n_i, a_i in zip(n, a):
p = prod // n_i
sum += a_i * modinv(p, n_i) * p
return int(sum % prod)
T = []
T.append(chinese_remainder([n[0],n[1],n[2]],[1,0,0]))
T.append(chinese_remainder([n[1],n[0],n[2]],[1,0,0]))
T.append(chinese_remainder([n[2],n[1],n[0]],[1,0,0]))
N = n[0]*n[1]*n[2]
P.<x> = PolynomialRing(Zmod(N))
g=0
for i in range(3):
g+=((a[i]*x + b[i])^3 - c[i])*T[i]
g = g.monic()
print g.small_roots()
# [670865060925536167183341633904872636604138549784041874166444071991777516769578599095298315216573752629227374]
|
用long_to_bytes转出来得到message:I will send you the ticket tomorrow afternoon
这里AES用的是OFB模式，其实上就是一个stream cipher，只不过key用的是AES加密的结果。
也就是说:
ENC: AES_cipher = key_stream ^ pad(message)
DEC: AES_message = key_stream ^ cipher
现在有了message，只需要简单的xor一下就可以算出key_stream。
key_stream = AES_cipher ^ pad(message)
有了key_stream，基本上想干什么就能干什么了。
注意到题目里面只需要把解密后的message中的afternoon改成morning，那么只需要伪造出解密后想要的message = “I will send you the ticket tomorrow morning\x05\x05\x05\x05\x05”，再xor上key_stream，就得到了伪造的cipher，发过去解密，就能成功通过check，拿到flag了。
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
|
from pwn import *
from Crypto.Util.number import *
from Crypto.Util.strxor import strxor
from binascii import *
r = remote('47.240.41.112', 54321)
# context.log_level = 'debug'
r.recvuntil("encrypt:\n")
r.sendline("1"*1000)
r.recvuntil("[2]forge the message")
r.sendline("1")
# n, c, a, b = [],[],[],[]
# r.recvuntil("n=")
# n.append(int(r.recvline()[:-2],16))
# r.recvuntil("n=")
# n.append(int(r.recvline()[:-2],16))
# r.recvuntil("n=")
# n.append(int(r.recvline()[:-2],16))
# for i in range(3):
# r.recvuntil("c=")
# c.append(int(r.recvline()[:-2],16))
# r.recvuntil("a=")
# a.append(int(r.recvuntil(",")[:-2],16))
# r.recvuntil("b=")
# b.append(int(r.recvline()[:-2],16))
r.recvuntil("this:")
AES_cipher = r.recvline()[:-1]
# pad_message = "I will send you the ticket tomorrow afternoon\x03\x03\x03"
# forge_message = "I will send you the ticket tomorrow morning\x05\x05\x05\x05\x05"
cipher = unhexlify(AES_cipher)
k_stream = strxor(cipher, 'I will send you the ticket tomorrow afternoon\x03\x03\x03')
forge_cipher = strxor(k_stream, "I will send you the ticket tomorrow morning\x05\x05\x05\x05\x05")
payload = hexlify(forge_cipher)
r.recvuntil("[2]forge the message")
r.sendline("2")
r.recvuntil("now:")
r.sendline(payload)
r.interactive()
# you made it, this reward is prepared for you:sctf{7h15_ch4ll3n63_15_n07_h4rd_f0r_y0u_r16h7?}
|
注意一下proof_of_work这边的逻辑，是RSA解密失败了才会继续下去，不然会直接退出。
这里一开始没怎么注意到，就一直something wrong，看不到下面的广播信息。
那么，如何才能让RSA解密失败，多半应该只有让m大于n了。
[1] https://ctf-wiki.github.io/ctf-wiki/crypto/asymmetric/rsa/rsa_coppersmith_attack-zh/
[2] https://en.wikipedia.org/wiki/Coppersmith%27s_attack#Generalizations
[3] https://github.com/ashutosh1206/Crypton/tree/master/RSA-encryption/Attack-Hastad-Broadcast