UMass CTF 2021 - malware [crypto]

• Competition: UMass CTF 2021
• Challenge Name: malware
• Type: Crypto
• Points: 448 pts
• Description:

  We’ve identified some ransomeware on one of our employee’s systems, but it seems like it was made by a script kiddie. Think you can decrypt the files for us?

The challenge

malware.py is a Python “ransomware”. Code is super-short:

from Crypto.Cipher import AES
from Crypto.Util import Counter
import binascii
import os

key = os.urandom(16)
iv = int(binascii.hexlify(os.urandom(16)), 16)

for file_name in os.listdir():
    data = open(file_name, 'rb').read()

    cipher = AES.new(key, AES.MODE_CTR, counter = Counter.new(128, initial_value=iv))
    
    enc = open(file_name + '.enc', 'wb')
    enc.write(cipher.encrypt(data))

    iv += 1

So, the algorithm is:

1. key is 16 random bytes.
2. iv is 16 random bytes.
3. In each step, we use AES-CTR with the counter being 128 bits, with the initial value being the iv.
4. iv is simply increased in each step.

Luckily, one of the files that’s being encrypted is malware.py itself, so we have a plaintext-encrypted pair.

AES-CTR

The counter mode in block cipher cryptography generates a stream cipher out of a block cipher. The way it works is as follows:

       nonce+0      nonce+1   ....   nonce+n
         |            |                |
         V            V                V
       _____        _____            _____
      |     |      |     |          |     |
      | AES |      | AES |   ....   | AES |
      |_____|      |_____|          |_____|
         |            |                 |
 P0 --> XOR   P1 --> XOR        Pn --> XOR
         |            |                 |
   C0 <--+      C1 <--+           Cn <--+
         
         

So, nonce (which is practically a counter) is increased by one for each block. Note that blocks are not dependent on each other; this allows running the cipher in parallel. However, this also means the same input counter shouldn’t be used more than once - if it does, it harms the security of the cipher. This is exactly what happens in this challenge!

Solution

In our challenge, since iv is increased by one with each file, it means there are repetitions of the counter we could exploit.

Let us note that flag.txt.enc is 38 bytes long, so it has 3 blocks.

In python, os.listdir() is of arbitrary order. However, since we only know malware.py (as plaintext) and I assume the challenge is fully solvable, I assume flag.txt was encrypted after malware.py.

Let’s say flag.txt was encrypted k files after malware.py. Then, if the value of IV when encrypting malware was ctr then the IV value was ctr+k.

Now let’s denote the following:

1. Pm[n] is the plaintext block n of malware.py.
2. Cm[n] is the ciphertext block n from malware.py.enc.
3. Pf[n] is the plaintext block n of flag.txt.
4. Cf[n] is the ciphertext block n from flag.txt.enc.

Due to how AES-CTR works, we can conclude about flag.txt:

Cf[0] = Pf[0] ^ AES[ctr+k+0]
Cf[1] = Pf[1] ^ AES[ctr+k+1]
Cf[2] = Pf[2] ^ AES[ctr+k+2]

And conclude about malware.py:

Cm[k+0] = Pm[k+0] ^ AES[ctr+k+0]
Cm[k+1] = Pm[k+1] ^ AES[ctr+k+1]
Cm[k+2] = Pm[k+2] ^ AES[ctr+k+2]

Doing some algebra to isolate AES[ctr+k+0], AES[ctr+k+1] and AES[ctr+k+2] results in:

Pf[0] = Cf[0] ^ Pm[k+0] ^ Cm[k+0]
Pf[1] = Cf[1] ^ Pm[k+2] ^ Cm[k+1]
Pf[2] = Cf[2] ^ Pm[k+1] ^ Cm[k+2]

So, somewhere in malware.py and malware.py.enc we have blocks that XORed with the blocks of flag.txt.enc will get us the flag! Also, due to the low number of files, k can be either 1, 2 or 3 (since there are only 4 encrypted files).

So, the solution is simple:

def get_blocks(x):
    return [ x[i:i+16] for i in range(0, len(x), 16) ]

def xor_blocks(b1, b2):
    return [ b1[i] ^ b2[i] for i in range(len(b1)) ]

pm_blocks = get_blocks(open('malware.py', 'rb').read())
cm_blocks = get_blocks(open('malware.py.enc', 'rb').read())
cf_blocks = get_blocks(open('flag.txt.enc', 'rb').read())

for k in [1, 2, 3]:
    result = ''
    for index in range(3):
        xored_malware_block = xor_blocks(pm_blocks[index + k], cm_blocks[index + k])
        flag_plaintext_block = xor_blocks(cf_blocks[index], xored_malware_block)
        result += ''.join(map(chr, flag_plaintext_block))
    print('Result for k=%d is %s' % (k, result))

It worked for k=2 with the flag UMASS{m4lw4re_st1ll_n33ds_g00d_c4ypt0}.