hack.lu 2016: Cryptolock (Crypto, 200 pts)

Description:
Oh no! Cthulhu's laptop was hit by ransomware and an important document was encrypted! But you have obtained the encryption script and it seems like the encryption is vulnerable...
Even tough you don't know the encryption password, can you still help recover the important ODT file?
Download

Flag:
flag{v3ry_b4d_crypt0_l0ck3r}

Upon downloading the file and opening the source code, the first thing I noticed is the weird way they handled their key.

assert len(user_input) == 8  
i = len(user_input) // 4  
keys = [ # Four times 256 is 1024 Bit strength!! Unbreakable!!  
    hashlib.sha256(user_input[0:i]).digest(),
    hashlib.sha256(user_input[i:2*i]).digest(),
    hashlib.sha256(user_input[2*i:3*i]).digest(),
    hashlib.sha256(user_input[3*i:4*i]).digest(),
]

Then for actually using these keys they encrypt four times:

def enc(self, plaintext): # Because one encryption is not secure enough  
    one        = self.ciphers[0].encrypt(plaintext)
    two        = self.ciphers[1].encrypt(one)
    three      = self.ciphers[2].encrypt(two)
    ciphertext = self.ciphers[3].encrypt(three)
    return ciphertext

Looking at the encrypt function in AESCipher.py, you will notice that regardless of the block size, they pad the plaintext:

def encrypt(self, raw):  
    raw = self._pad(AESCipher.str_to_bytes(raw))
    iv = Random.new().read(AES.block_size)
    cipher = AES.new(self.key, AES.MODE_CBC, iv)
    return iv + cipher.encrypt(raw)

This means that a valid decryption will also have a valid padding at the end. Thus I wrote a function that checks if the padding is valid or not:

def checkPadding(raw):  
    pad_value = raw[-1]

    if(pad_value == chr(0) or pad_value == chr(1)):
        return False

    if(raw[len(raw)-ord(pad_value):len(raw)] == pad_value*ord(pad_value)):
        return True
    else:
        return False

I had the function return False if the padding was 0x01 since there is a 1/256 chance of that just happening. From here, I just ran through every two byte combination of SHA256 hashes for the key and was able get a decryption with valid padding when the last key was chr(52) + chr(68) (and only those keys). The loop I ran to check for valid padding can be seen here:

for i in range(256):  
    print i

    temp = CT

    for j in range(256):
        key = hashlib.sha256(chr(i) + chr(j)).digest()

        cipher = AESCipher(key)

        decrypted = cipher.decrypt(temp)

        if checkPadding(decrypted):
            print i
            print j
            valid.append(str(i) + " " + str(j) + " " + decrypted[len(decrypted)-16:len(decrypted)].encode("hex"))

print valid  

I simply repeated this for each of the four keys and their corresponding cipher texts. Each loop took about 3 minutes to check every key combination. The entire script can be viewed here.

Looking back, I could have speed up this process by only checking bytes of printable characters since the key was received from a user input. But, the whole process only took about 15 minutes so I don't think the optimization is too big of a factor here. Here is the contents of the OST file that resulted from a successful full decryption:

So I looked for some Cthulhu flag designs. Which one should we choose?
Source:

https://static.wixstatic.com/media/b78968_1f60a5a8f99a43de98bc75a9bd203926.jpg_srz_900_601_85_22_0.50_1.20_0.00_jpg_srz

Or perhaps rather something like this?

Source:
https://images4.alphacoders.com/218/218446.png

flag{v3ry_b4d_crypt0_l0ck3r}