Crypto-Brutal Mogging

"I've been securitymaxxing lately so I increased the key size on my new encryption system. Only securitychads like me can crack it now. Good luck. ;)"

Full implementation

Challenge

I'll try to make it as simple as possible, without going too much in depth.

The code that is relevant to us are the decrypt and encrypt function, which perform operations using 4 bytes at a time, split in two operations using 2 bytes of the key at a time.

def encrypt(data, key):
    data = pad(data)
    return encrypt_data(encrypt_data(data, key[0:2]), key[2:4])

def decrypt(data, key):
    plain = decrypt_data(decrypt_data(data, key[2:4]), key[0:2])
    return unpad(plain)

Exploit

Encrypt() basically encrypts the data twice , first to a state we'll call the Middlestate using the first two bytes of the key and encrypts the Middlestate to get the Ciphertext using the last two bytes of the key. Decrypt() is similar, Ciphertext to Middlestate and Middlestate to Message

We could directly bruteforce 4 bytes of the key to directly obtain the Message from the Ciphertext, however this is not feasible on most computers. However, if we could somehow find the Middlestate, then we would only have to bruteforce 2 bytes, which can be finished in less than 10 seconds.

The exploit lies in figuring out that between the Message and Ciphertext, there exists only one middle state. If we make a list of the possible middle states from the Message (by encrypting once) and another list for the Ciphertext (by decrypting once), then the common element will be the Middlestate.

After finding the Middlestate, we can obtain the complete key by combining the partial key used to find the Middlestate from the Message and the partial key used to find the Middlestate from the Ciphertext.

Implementation

The challenge uses a server which encrypts the flag and gives us three inputs which the server encrypts and gives us the encrypted outputs. However, given the Message starts with "UMAS" and the encryption is done in blocks of 4 bytes, we won't need to use the inputs provided using this method.

First, let's connect to the server and get the encrypted flag.

from pwn import *
r = remote("brutalmogging.ctf.umasscybersec.org","1337")
print(r.recvuntil("s:"))
t1=r.recvline().strip().decode()
r.close()
#t1 = 7213d06923a531a4db074b823ba8de37512553077ac5d9742fc13543ec4fc68aba0a8ab27dbacc29d82f731d946773d8

Since the message starts with the flag format, therefore the first 4 bytes of the message is "UMAS". Also the encryption is done 4 bytes at a time, therefore the ciphertext is the first 4 bytes of the output for the message "UMAS", which is the first 8 hexadecimal digits.

Given the Message and the Ciphertext, we can now find the Middlestate and ultimately the key.

Code to generate partial keys

from Crypto.Util.number import *
a1 =[] 
for i in range(256):
    a1.append(long_to_bytes(i))
partial_keys=[]
for i in a1:
    for j in a1:
        partial_keys.append(i+j)

We decrypt once to find out all the possible combinations of the middlestate from the ciphertext by trying all combinations of partial keys . Here, decrypt is the main function that calls decrypt_data twice where as decrypt_data only decrypts once.

h1=[]
for i in partial_keys:
    h1.append(decrypt_data(long_to_bytes(int(t1[:8],16)),i))

We do a similar operation for the message by encrypting once

h2=[]
for i in partial_keys:
    h2.append(encrypt_data(b'UMAS',i))

We now find the common element between the two lists. This element will be the Middlestate.

g1=list(set(h1).intersection(h2))[0]
#g1 = b'1\xb5\x14?'

We figure out which partial key was used for the encryption/decryption to the Middlestate and combine them to find out the full key

key = partial_keys[h2.index(g1)] + partial_keys[h1.index(g1)]
#key = b'\xcf\xbfJ9'

Finally, we decrypt the flag using the key we just got

print(decrypt(long_to_bytes(int(t1,16)),key))
#b'UMASS{1_h4ve_b33n_m3w1ng_f0r_my_l1f3_733061741}'