类型:Crypto
翻译自:https://github.com/p4-team/ctf/tree/master/2018-06-23-google-ctf/crypto_dogestore
考察知识点：CTR mode，birthday attack
这道题目给了我们服务器的代码，加密过的flag和一个服务。尽管服务器是用rust写的，但逻辑比较简单，还是很容易看懂的。服务器的操作如下：
- 从用户处读取输入
- 使用AES-CTR 解密用户的输入
- 将解密结果反序列化，具体操作是将相邻两个字节变为一组，如[1,2,3,4,5,6]变为[(1,2),(3,4),(5,6)]
- 将反序列化的结果做解码，具体是对于每一组(Char,d) 转化为Char*(d+1),如('A',3)变为'AAAA'，再把每组的结果拼接起来
- 计算结果的sha3_256
- 将hash值返回给用户
在这个过程中，有问题的点在于：
iv = get_iv();
openssl::symm::decrypt(
openssl::symm::Cipher::aes_256_ctr(),
&key,
Some(&iv),
data
)
对CTR（Counter）模式有所了解的话都知道，在AES CTR模式中，使用的是一个计数器而不是IV；而且计数器不应当以可预测的方式出现，更不能是常量。这是因为AES-CTR模式是一种流式加密，他会根据输入的Counter和key通过AES加密 生成一个密钥流。给定相同的key和counter，每一次都会生成相同的密钥流。然后密钥流或和输入进行异或得到输出。
因此实际上这道题的加密过程可以认为是我们输入的数据和一个常量密钥流做异或加密。也就是说只要我们能够泄露服务器上的密钥流，就可以解密flag。
这里的第二个漏洞在于我们可以利用birthday attack的原理，通过构造相同的哈希来泄露密钥流。假设我们只考虑前四个字节，后面全设为0。假设前四个字节为AxBy，A,B为字符，x,y为数字。我们把最终计算出的哈希值记下。
然后我们字节翻转x,y得到新的v,z,使x+y==v+z 。如果初始时我们就足够幸运，使得让A==B,那么我们就能够得到一次冲突。
换言之，当冲突发生时，我们可以知道A和B是相同的字母，也就有
payload[0]^KEY[0] == payload[2]^KEY[2]
由于payload是我们可控的，那么就得到了key的信息
KEY[0]^KEY[2] == payload[0]^payload[2]
以此类推，可以通过寻找冲突得到 KEY[2]^KEY[4]等等得值，然后再通过爆破KEY[0]来恢复所有偶数位的key
具体的冲突搜索算符如下：
def find(key_byte_number, get_result_fun=get_result):
payload = [0] * 110
attempts = 0
while True:
attempts += 1
if attempts % 5 == key_byte_number % 5:
print(key_byte_number, attempts)
payload[key_byte_number] = 0
payload[key_byte_number + 1] = random.randint(0, 255)
payload[key_byte_number + 2] = random.randint(0, 255)
payload[key_byte_number + 3] = random.randint(0, 255)
res = get_result_fun(payload)
for i in range(4):
pay2 = payload[:]
pay2[key_byte_number + 1] ^= 1 << i
pay2[key_byte_number + 3] ^= 1 << i
r2 = get_result_fun(pay2)
if res == r2:
print("KEY[%d] ^ KEY[%d] = %d" % (key_byte_number, key_byte_number + 2, payload[key_byte_number + 2]))
print(res, r2, payload, pay2)
return payload[key_byte_number + 2]
我们可以离线的验证这个算法是否真的有效：
def sanity_test():
secret = "alamakotaa"
def decrypt(data):
return xor_string(secret, data)
def deserialize(decrypted):
return chunk(decrypted, 2)
def decode(secret):
return "".join([a * (ord(b) + 1) for a, b in secret])
def mimick_server(data):
import sha3
decrypted = decrypt(data)
secret = deserialize(decrypted)
expanded = decode(secret)
return sha3.sha3_256(expanded).digest()
def fake_get_result(data):
payload_bytes = "".join(map(chr, data))
return base64.b64encode(mimick_server(payload_bytes))
flag = xor_string("CTF{XXXXX}", secret)
found = []
for i in range(0, len(secret) - 2, 2):
found.append(find(i, fake_get_result))
print(found)
在验证过程中，我们把题目中的AES_CTR算法 等价为了一个简单的XOR加密。我们找到的冲突，计算出的结果为[0,0,14,14] ，这与 'a'^'a'==0 ,'a'^'o'==14的事实相符。
然后我们把实验中的服务器代码替换为真实的与服务器交互的代码，就可以恢复奇数位key的关系：
from crypto_commons.netcat.netcat_commons import nc, send
def get_result(payload):
url = "dogestore.ctfcompetition.com"
port = 1337
while True:
try:
s = nc(url, port)
payload_bytes = "".join(map(chr, payload))
send(s, payload_bytes)
result = s.recv(9999)
return result
except:
pass
得到的结果是 [191, 119, 132, 188, 171, 242, 33, 15, 50, 0, 32, 130, 110, 51, 57, 36, 108, 223, 132, 48, 58, 47, 190, 144, 54, 115, 250, 91, 13, 16, 25, 193, 178, 26, 115, 140, 231, 65, 99, 180, 221, 121, 92, 206, 16, 64, 152, 181, 231, 228, 136, 149, 177, 237, 0]
接下来我们需要推测key的第一个字节的值。可以采用穷举法来爆破，然后用推测的key来解密密文，只有解密的结果大部分都是可见字符的时候，才是可能的key。通过这种方式可以很快的判断key[0]的每一个可能值是否合理。
def brute_first():
found = [191, 119, 132, 188, 171, 242, 33, 15, 50, 0, 32, 130, 110, 51, 57, 36, 108, 223, 132, 48, 58, 47, 190, 144, 54, 115, 250, 91, 13, 16, 25, 193, 178,26,115, 140, 231, 65, 99, 180, 221, 121, 92, 206, 16, 64, 152, 181, 231, 228, 136, 149, 177, 237, 0]
with codecs.open("encrypted_secret") as flag_file:
flag = flag_file.read()
for first in range(256):
real_even_keystream = [chr(first)]
for c in found:
real_even_keystream.append(chr(ord(real_even_keystream[-1]) ^ c))
with_zeros = reduce(lambda x, y: x + y, map(list, zip(real_even_keystream, ['0'] * len(found))))
xored = xor_string(flag, "".join(with_zeros))
even_chars = "".join([xored[i] for i in range(0, len(xored), 2)])
print(first, even_chars)
brute_first()
最后得到了一个很合理的解密结果：
(174, 'HFHFHDHDHDSAaACTF{SADASDSDCTF{L_E_R_OY_JENKINS}ASDCTF{\n')
现在已经恢复出了key的所有奇数位，下一步需要恢复偶数位。想法也很简单：
- 提前计算字符串A，AA，AAA...直到可能的最长字符串（长度为55*256）的sha3_256，并保存下来，得到一张彩虹表。
- 我们希望所有的字母位都相同，由于我们已经知道了所有的奇数位key，我们可以构造payload[i]='A' ^KEY[i] 来做到这一点
- 我们任意填写计数位，然后进行哈希，根据哈希结果可以知道A的总数，即异或之后，计数位的和。
- 然后我们翻转第一个计数位的最低一个比特（异或 1），计算新的哈希，根据哈希知道新的串中计数位的和。如果这个和比原来小，说明我们使该比特从1变为了0，否则就是比特从0变为了1，这样我们就知道了和key异或之后该比特的真实值。然后可以用相同的方法求该计数位的次低比特位，以此类推。
- 求完一个计数位之后可以接着求下一个计数位。
- 得到所有异或之后的计数位之后，和异或前的计数位做异或，就可以得到所有偶数位的KEY。
def recover_counters(keybytes, get_result_fun=get_result):
hashes = []
with codecs.open("hashes", 'r') as hashes_file:
for line in hashes_file:
hashes.append(line[:-1])
# prepare payload with 'A' on even positions
payload = [0] * (len(keybytes) * 2)
for i in range(0, len(keybytes) * 2, 2):
payload[i] = ord(xor_string(keybytes[i / 2], 'A'))
counter_bytes = []
for counter in range(1, len(keybytes) * 2, 2):
print('recovering counter', counter)
reference_hash = get_result_fun(payload)
reference_number_of_A = hashes.index(reference_hash)
bits = []
for bit in range(8):
new_payload = payload[:]
new_payload[counter] ^= 1 << bit
new_hash = get_result_fun(new_payload)
new_A_number = hashes.index(new_hash)
if new_A_number > reference_number_of_A: # we set a bit to 1 so it was 0
bits.append('0')
else:
bits.append('1')
original_counter = int("".join(bits[::-1]), 2)
print('original counter', original_counter)
counter_bytes.append(original_counter)
return map(chr, counter_bytes)
原有的验证代码可以扩展位：
def sanity_test():
secret = "alamakotaa"
def decrypt(data):
return xor_string(secret, data)
def deserialize(decrypted):
return chunk(decrypted, 2)
def decode(secret):
return "".join([a * (ord(b) + 1) for a, b in secret])
def mimick_server(data):
import sha3
decrypted = decrypt(data)
secret = deserialize(decrypted)
expanded = decode(secret)
return sha3.sha3_256(expanded).digest()
def fake_get_result(data):
payload_bytes = "".join(map(chr, data))
return mimick_server(payload_bytes).encode("base64")
flag = xor_string("CTF{XXXXX}", secret)
found = []
for i in range(0, len(secret) - 2, 2):
found.append(find(i, fake_get_result))
print(found)
real_found = [chr(ord(flag[0]) ^ ord('C'))]
for c in found:
real_found.append(chr(ord(real_found[-1]) ^ c))
print(real_found)
counters = recover_counters(real_found, fake_get_result)
print(counters)
print(reduce(lambda x, y: x + y, map(lambda x: x[0] + x[1], zip(real_found, counters))))
最后把代买改写为同真实服务器交互的版本
def recover_from_letters():
found = [191, 119, 132, 188, 171, 242, 33, 15, 50, 0, 32, 130, 110, 51, 57, 36, 108, 223, 132, 48, 58, 47, 190, 144, 54, 115, 250, 91, 13, 16, 25, 193, 178,
26, 115, 140, 231, 65, 99, 180, 221, 121, 92, 206, 16, 64, 152, 181, 231, 228, 136, 149, 177, 237, 0]
with codecs.open("encrypted_secret") as flag_file:
flag = flag_file.read()
real_found = [chr(174)]
for c in found:
real_found.append(chr(ord(real_found[-1]) ^ c))
print(real_found)
counters = recover_counters(real_found)
print(counters)
keystream = reduce(lambda x, y: x + y, map(lambda x: x[0] + x[1], zip(real_found, counters)))
print(keystream)
print(decode(deserialize(xor_string(flag, keystream))))
recover_from_letters()
得到完整的密钥流之后，就可以通过decode deserialize得到flag
