Rating:
The challenge
==
`malware.py` is a Python "ransomware".
Code is super-short:
```python
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 repeations 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:
```python
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}`.
