Meet me in the middle

2022-03-23

OFPPT-CTF的一道题，AES的中间相遇攻击，实际上也是任何对称密码加密两次的攻击方法。攻击思路就是把给的密文解密一次，已知的明文（或者遍历明文的所有组合）加密一次，来对照两者的结果，若相等则可以确定加解密的密钥。

Q：

from random import randint
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import json

flag = b'OFPPT-CTF{Not_the_real_flag}'

def gen_key(option=0):
    alphabet = b'0123456789abcdef'
    const = b'0fpptCTF5!@#'
    key = b''
    for i in range(16-len(const)):
        key += bytes([alphabet[randint(0,15)]])

    if option:
        return key + const
    else:
        return const + key

def encrypt(data, key1, key2):
    cipher = AES.new(key1, mode=AES.MODE_ECB)
    ct = cipher.encrypt(pad(data, 16))
    cipher = AES.new(key2, mode=AES.MODE_ECB)
    ct = cipher.encrypt(ct)
    return ct.hex()


def challenge():
    k1 = gen_key()
    k2 = gen_key(1)

    
    ct = encrypt(flag, k1, k2)
    
    
    print('Super strong encryption service approved by 2022 stansdards.\n'+\
                    'Message to decrypt:\n' +ct + '\nEncrypt your text:\n> ')
    try:
            
        dt = json.loads(input().strip())
        pt = bytes.fromhex(dt['pt'])
        res = encrypt(pt, k1, k2)
        print(res + '\n')
        exit(1)
    except Exception as e:
        print(e)
        print('Invalid payload.\n')
        exit(1)
    
if __name__ == "__main__":
    challenge()

DATA:

Super strong encryption service approved by 2022 stansdards.
Message to decrypt:
187f25ea856f518bcd8e7e7c17e7e6016bc77459513740e6792c84d07b465ea9cee6609881421eb4ae1606792a2d8859
Encrypt your text:
>
{"pt":"4f465050542d435446"}
f71f3b195e2336a6d30077b8184304c6

这道题给了一对明文——密文对，那么可以通过遍历密钥空间来分别对明文加密一次，密文解密一次。只要取两者交集就能得到密钥。

hash的exp：

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad

pt='4f465050542d435446'
pt = bytes.fromhex(pt)
c='f71f3b195e2336a6d30077b8184304c6'
c=bytes.fromhex(c)
alphabet = b'0123456789abcdef'
const = b'0fpptCTF5!@#'
dict={}

def check(a):
    if a in dict.keys():
        print(dict[a])
        return 1
    else:
        return 0

for i1 in range(16):
    for i2 in range(16):
        for i3 in range(16):
            for i4 in range(16):
                key1=const+bytes([alphabet[i1]])+bytes([alphabet[i2]])+bytes([alphabet[i3]])+bytes([alphabet[i4]])
                cipher = AES.new(key1, mode=AES.MODE_ECB)
                ct = cipher.encrypt(pad(pt, 16))
                index1=str(i1)+' '+str(i2)+' '+str(i3)+' '+str(i4)
                dict[ct]=index1

for i1 in range(16):
    for i2 in range(16):
        for i3 in range(16):
            for i4 in range(16):
                key2=bytes([alphabet[i1]])+bytes([alphabet[i2]])+bytes([alphabet[i3]])+bytes([alphabet[i4]])+const
                cipher = AES.new(key2, mode=AES.MODE_ECB)
                ct = cipher.decrypt(c)
                index2=str(i1)+' '+str(i2)+' '+str(i3)+' '+str(i4)
                if check(ct):
                    print(index2)


c='187f25ea856f518bcd8e7e7c17e7e6016bc77459513740e6792c84d07b465ea9cee6609881421eb4ae1606792a2d8859'
c=bytes.fromhex(c)
index1=[2,15,7,4]
index2=[14,10,1,4]
key1=const
key2=b''
for i in range(4):
    key1+=bytes([alphabet[index1[i]]])
    key2+=bytes([alphabet[index2[i]]])
key2+=const
cipher1 = AES.new(key1, mode=AES.MODE_ECB)
cipher2 = AES.new(key2, mode=AES.MODE_ECB)
m=cipher2.decrypt(c)
print(cipher1.decrypt(m))

#b'OFPPT-CTF{M33t_1n_Th3_Middle_4tt4ck_4_RS4}\x06\x06\x06\x06\x06\x06'

第二种思路应该算是非预期，加密选择的是ECB模式，每块之间无混淆，并且已知flag格式为：OFPPT-CTF{，那么可以考虑爆破后续的6字节，再将这16字节进行遍历密钥的加密；同时对密文进行遍历密钥的解密，对照前16字节，若两者前16字节相等则两者取得密钥就是先后加密两次的密钥。但是时间复杂度较高，不是好的方法。


from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from binascii import b2a_hex, a2b_hex
import string

# def decrypt(key,c):
#     cipher = AES.new(key, mode=AES.MODE_ECB)
#     ct = cipher.decrypt(c)
#     return ct
#
# c = '187f25ea856f518bcd8e7e7c17e7e6016bc77459513740e6792c84d07b465ea9cee6609881421eb4ae1606792a2d8859'
# const = '0fpptCTF5!@#'
# alphabet = '0123456789abcdef'
# f = open("msg.txt","w")
# for i in range(16):
#     for j in range(16):
#         for m in range(16):
#             for n in range(16):
#                 key2 = bytes( alphabet[i] + alphabet[j] + alphabet[m] + alphabet[n] + const,encoding="utf-8")
#                 flag = decrypt(key2,a2b_hex(c))
#                 f.write(str(flag))
#                 f.write("\n")
#   不同密钥解密出的所有可能结果存在msg.txt中

def encrypt(key,m):
    cipher = AES.new(key, mode=AES.MODE_ECB)
    ct = cipher.encrypt(m)
    return ct


known = 'OFPPT-CTF{'

const = '0fpptCTF5!@#'
table = '0123456789abcdef'
ff = open("c1.txt","w")
for i1 in range(16):
    for i2 in range(16):
        for i3 in range(16):
            for i4 in range(16):
                for i5 in range(16):
                    for i6 in range(16):
                        mm = bytes(known+table[i1]+table[i2]+table[i3]+table[i4]+table[i5]+table[i6],encoding='utf-8')
                        for i in range(16):
                            for j in range(16):
                                for m in range(16):
                                    for n in range(16):
                                        key1 = bytes(const + table[i] + table[j] + table[m] + table[n],
                                                     encoding="utf-8")
                                        c1 = encrypt(key1,mm)
                                        ff.write(str(c1))
                                        # 爆破未知6字节，遍历密钥空间，获得所有可能的加密结果；最后只需要对照msg.txt和c1.txt，找到前十六个字节相同的那两组。