Writeup for 红明谷's crypto
不知道是为啥，只有一个难题，虽然巨难无比，但收获不小
RSAattack
$e=3$ $c$ 远小于 $n$ ，直接开方就完了
ezCRT
和VNCTF的factor是一个题，换一下数据直接出
babyFogery
题目解析
加密模式为AES.OCB，服务器提供加密和解密功能，getflag的要求如下：
- associate_data为
from Alice
- 明文为
please_give_me_the_flag
分析
阅读整体代码，掌握AES.OCB模式的特点与加解密过程如下：
（本文只说明对该题有意义的函数与特点，如果想仔细了解请阅读github上的源代码）
后文中 $E(),D()$ 表示AES.OCB内部的 $aes.encrypt(),aes.decrypt()$
认证
AES.OCB在解密时会对 $tag$ 与 $cipher$ 进行认证，如果发现与加密时的不同，则不会返回解密后的 明文，所以这一点要求我们在伪造 $cipher$ 和同时要对 $tag$ 进行伪造，使得其通过认证检测，我们才能得到明文，才能保证连接不被中断
pmac
是一种加密（或处理）associate_data的函数，其输出结果只与内部 $aes$ 和 $header$ 参数有关
encrypt
AES.OCB加密函数，对于除去最后一块的前面所有明文块，其满足
$$
c_i=2^i\cdot E(nonce) \bigoplus E(2^i\cdot E(nonce) \bigoplus m_i)
$$
而对与最后一块，其满足
$$
c_n=m_n \bigoplus E(2^n\cdot E(nonce)\bigoplus len(0^n))
$$
而加密时的 $tag$ 与其他参数，满足
$$
checksum=\bigoplus^n_{i=1}m_i
$$
$$
tag=E(3\cdot 2^n\cdot E(nonce)\bigoplus checksum)
$$
另外，如果 $header>0$ ，则新的 $tag=tag\bigoplus header$ ，此外，一个 $nonce$ 只能够被使用一次
decrypt
AES.OCB解密函数，对于除去最后一块的前面所有明文块，其满足
$$
m_i=D(c_i\bigoplus 2^i\cdot E(nonce)) \bigoplus 2^i\cdot E(nonce)
$$
而对与最后一块，其满足
$$
m_n=c_n \bigoplus E(2^n\cdot E(nonce)\bigoplus len(0^n))
$$
解密时的 $checktag$ 与其他参数，满足
$$
checksum=\bigoplus^n_{i=1}m_i
$$
$$
checktag=E(3\cdot 2^n\cdot E(nonce)\bigoplus checksum)
$$
同样的，如果 $header>0$ ，则新的 $checktag=checktag\bigoplus header$
如果 $cipher$ 或 $tag$ 被检测出被修改过，则直接返回 $(False,[])$ ，否则返回 $(True,[message])$
解决问题
很显然，我们本地无法加密的原因是因为AES.OCB模式内部的 $aes$ 我们无法使用，另外在线的加密函数我们无法使得associate_data为from Alice，所以只要我们能够求出 $msg$ 所对应的 $E(msg)$ ，这个问题就会迎刃而解（任意加密攻击）
这里我们这样构造
$$
m_1=len(0^n)=15\times b’\x00’+b’\x80’~~~~~
m_2=0=16\times b’\x00’
$$
那么 $m_1$ 会被当作非最后一块加密
$$
c_1=2\cdot E(nonce)\bigoplus E(2\cdot E(nonce)\bigoplus m_1)
$$
$$
c_2=m_2\bigoplus E(4\cdot E(nonce)\bigoplus len(0^n))\
=E(4\cdot E(nonce)\bigoplus len(0^n))
$$
随后调用解密函数时只提交 $c1$ ，此时会被当作最后一块解密，那么我们会发现
$$
m_1=c_1\bigoplus E(2\cdot E(nonce)\bigoplus m_1) \
=\underbrace{2\cdot E(nonce)\bigoplus E(2\cdot E(nonce)\bigoplus len(0^n))}_{c_1}\bigoplus E(2\cdot E(nonce)\bigoplus m_1)
$$
而我们构造的 $m_1=len(0^n)$ ，那么显然 $m_1=2\cdot E(nonce)$ ，此时，我们就能够轻松算出 $E(nonce)$ ！
但因为AES.OCB的认证特殊性，我们需要使得伪造 $tag$ 来通过认证检测，这里我们选择令 $header$ 为空，那么此时的
$$
checktag=E(6\cdot E(nonce)\bigoplus 2\cdot E(nonce))\
=E(4\cdot E(nonce))
$$
如何能得到这个玩意呢？
当我们再次稍微变化一下 $c_1=c_1\bigoplus m1$ 后，我们发现此时
$$
checktag=E(m_1\bigoplus 6\cdot E(nonce)\bigoplus 2\cdot E(nonce))\
=E(m_1\bigoplus 4\cdot E(nonce))=c_2
$$
也就是说，我们给在线 $decrypt$ 函数提供的数据分别为： $nonce$ 为加密时的 $nonce$ ， $tag$ 为 $c_2$ ， $c = c_1$ ， $header$ 为空，这样就能够成功通过客户端的认证检查，并且得到 $2\cdot E(nonce)$ ，对 $times2$ 函数写个逆即可求得 $E(nonce)$
此时，我们即可对于任意的 $nonce$ ，都能得到其对应的 $E(nonce)$ ，但是对于任意的明文 $m$ ，并不能自如的完成任意加密，那么我们现在相当于已经有了 $nonce$ 与其对应的 $E(nonce)$ ，如何来完成任意加密的效果呢？
这里我们为了便于解释，我们记 $L=E(nonce)$ 、$L’=E(2\cdot L\bigoplus m_1)$ ，那么可以轻松算得 $L’=c_1\bigoplus 2\cdot L$ ，我们再次使用客户端的 $encrypt$ 函数，但这次我们的 $nonce=2\cdot L\bigoplus m_1$ ，$m=message\bigoplus2\cdot L’$ ，那么 $c=2\cdot L’\bigoplus E(message\bigoplus2\cdot L’\bigoplus2\cdot L’)$ ，我们就能轻松算出 $E(message)=c\bigoplus 2\cdot L’$
我们将前面所有的过程看作一个函数，即使用一个 $nonce$ 名额，来得到我想要的 $aes.encrypt(message)$ ，那么此时所有的加密过程都可以在本地完成，直接在本地计算题目所需要的 $cipher$ 与 $tag$ ，直接打给服务器即可
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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
| from Crypto.Util.number import *
from gmpy2 import *
from pwn import *
import os
def times2(input_data,blocksize = 16):
assert len(input_data) == blocksize
output = bytearray(blocksize)
carry = input_data[0] >> 7
for i in range(len(input_data) - 1):
output[i] = ((input_data[i] << 1) | (input_data[i + 1] >> 7)) % 256
output[-1] = ((input_data[-1] << 1) ^ (carry * 0x87)) % 256
assert len(output) == blocksize
return output
def times3(input_data):
assert len(input_data) == 16
output = times2(input_data)
output = xor_block(output, input_data)
assert len(output) == 16
return output
def back_times2(output_data,blocksize = 16):
assert len(output_data) == blocksize
input_data = bytearray(blocksize)
carry = output_data[-1] & 1
for i in range(len(output_data) - 1,0,-1):
input_data[i] = (output_data[i] >> 1) | ((output_data[i-1] % 2) << 7)
input_data[0] = (carry << 7) | (output_data[0] >> 1)
if(carry):
input_data[-1] = ((output_data[-1] ^ (carry * 0x87)) >> 1) | ((output_data[-2] % 2) << 7)
assert len(input_data) == blocksize
return input_data
def xor_block(input1, input2):
assert len(input1) == len(input2)
output = bytearray()
for i in range(len(input1)):
output.append(input1[i] ^ input2[i])
return output
def hex_to_bytes(input):
return bytearray(long_to_bytes(int(input,16)))
context(log_level='debug')
r=remote("127.0.0.1","10000")
r.recvuntil("Enter username > ")
r.sendline("aaa")
def Arbitrary_encrypt(msg):
num = bytearray(os.urandom(16))
r.recvuntil("Enter option > ")
r.sendline("1")
r.recvuntil("Enter nonce > ")
r.sendline(num.hex())
r.recvuntil("Enter message > ")
m = bytearray(b"\x00"*15 + b"\x80" + b"\x00"*16)
r.sendline(m.hex())
r.recvuntil("ciphertext: ")
cipher = r.recvline(False)
r.recvuntil("tag: ")
tag = r.recvline(False)
r.recvuntil("Enter option > ")
r.sendline("2")
r.recvuntil("Enter nonce > ")
r.sendline(num.hex())
r.recvuntil("Enter ciphertext > ")
m0 = bytearray(b"\x00"*15 + b"\x80")
m1 = bytearray(b"\x00"*16)
c0 = hex_to_bytes(cipher[:32])
r.sendline(xor_block(c0,m0).hex())
r.recvuntil("Enter tag > ")
c1 = cipher[32:]
r.sendline(c1)
r.recvuntil("Enter associate data > ")
r.sendline("")
r.recvuntil("message: ")
enc = xor_block(bytearray(hex_to_bytes(r.recvline(False))),m0)
L = back_times2(enc)
LL = enc
LLL = xor_block(LL,c0)
msg = bytearray(msg)
r.recvuntil("Enter option > ")
r.sendline("1")
r.recvuntil("Enter nonce > ")
r.sendline(xor_block(LL,m0).hex())
r.recvuntil("Enter message > ")
r.sendline(xor_block(msg,times2(LLL)).hex()+m1.hex())
r.recvuntil("ciphertext: ")
enc = bytearray(hex_to_bytes(r.recvline(False))[:16])
r.recvline()
return xor_block(enc,times2(LLL))
def my_pmac(header, blocksize = 16):
assert len(header)
m = int(max(1, math.ceil(len(header) / float(blocksize))))
offset = Arbitrary_encrypt(bytearray([0] * blocksize))
offset = times3(offset)
offset = times3(offset)
checksum = bytearray(blocksize)
for i in range(m - 1):
offset = times2(offset)
H_i = header[(i * blocksize):(i * blocksize) + blocksize]
assert len(H_i) == blocksize
xoffset = xor_block(H_i, offset)
encrypted = Arbitrary_encrypt(xoffset)
checksum = xor_block(checksum, encrypted)
offset = times2(offset)
H_m = header[((m - 1) * blocksize):]
assert len(H_m) <= blocksize
if len(H_m) == blocksize:
offset = times3(offset)
checksum = xor_block(checksum, H_m)
else:
H_m.append(int('10000000', 2))
while len(H_m) < blocksize:
H_m.append(0)
assert len(H_m) == blocksize
checksum = xor_block(checksum, H_m)
offset = times3(offset)
offset = times3(offset)
final_xor = xor_block(offset, checksum)
auth = Arbitrary_encrypt(final_xor)
return auth
def my_ocb_encrypt(plaintext, header, nonce, blocksize = 16):
assert nonce
m = int(max(1, math.ceil(len(plaintext) / float(blocksize))))
offset = Arbitrary_encrypt(nonce)
checksum = bytearray(blocksize)
ciphertext = bytearray()
for i in range(m - 1):
offset = times2(offset)
M_i = plaintext[(i * blocksize):(i * blocksize) + blocksize]
assert len(M_i) == blocksize
checksum = xor_block(checksum, M_i)
xoffset = Arbitrary_encrypt(xor_block(M_i, offset))
ciphertext += xor_block(offset, xoffset)
assert len(ciphertext) % blocksize == 0
M_m = plaintext[((m - 1) * blocksize):]
offset = times2(offset)
bitlength = len(M_m) * 8
assert bitlength <= blocksize * 8
tmp = bytearray(blocksize)
tmp[-1] = bitlength
pad = Arbitrary_encrypt(xor_block(tmp, offset))
tmp = bytearray()
C_m = xor_block(M_m, pad[:len(M_m)])
ciphertext += C_m
tmp = M_m + pad[len(M_m):]
assert len(tmp) == blocksize
checksum = xor_block(tmp, checksum)
offset = times3(offset)
tag = Arbitrary_encrypt(xor_block(checksum, offset))
if len(header) > 0:
tag = xor_block(tag, my_pmac(header))
return (tag, ciphertext)
finalnonce = bytearray(hex_to_bytes('11'*16))
finaltag,finalcipher = (my_ocb_encrypt(bytearray(b'please_give_me_the_flag'),bytearray(b'from Alice'),finalnonce))
finaltag = finaltag.hex()
finalnonce = finalnonce.hex()
finalcipher = finalcipher.hex()
r.recvuntil("Enter option > ")
r.sendline("3")
r.recvuntil("Enter nonce > ")
r.sendline(finalnonce)
r.recvuntil("Enter ciphertext > ")
r.sendline(finalcipher)
r.recvuntil("Enter tag > ")
r.sendline(finaltag)
flag = r.recvline()
if(b'flag' in flag):
print(flag)
|
wechat
