path: root/content/articles/2022-09-25-ductf-file-magic.md

# DownUnderCTF 2022: File Magic

A short writeup about my favorite challenge from DUCTF.

## Task

The challenge consists of a python script and an ip-port-pair which appears to
be running that script. Also the path of the flag is given: `./flag.txt`

```py
#!/usr/bin/env python3

from Crypto.Cipher import AES
from PIL import Image
from tempfile import NamedTemporaryFile
from io import BytesIO
import subprocess, os

KEY = b'downunderctf2022'

iv = bytes.fromhex(input('iv (hex): '))
assert len(iv) == 16 and b'DUCTF' in iv, 'Invalid IV'

data = bytes.fromhex(input('file (hex): '))
assert len(data) % 16 == 0, 'Misaligned file length'
assert len(data) < 1337, 'Oversized file length'

data_buf = BytesIO(data)
img = Image.open(data_buf, formats=['jpeg'])
assert img.width == 13 and img.height == 37, 'Invalid image size'
assert img.getpixel((7, 7)) == (7, 7, 7), 'Invalid image contents'

aes = AES.new(KEY, iv=iv, mode=AES.MODE_CBC)
dec = aes.decrypt(data)
assert dec.startswith(b'\x7fELF'), 'Not an ELF'

f = NamedTemporaryFile(delete=False)
f.write(dec)
f.close()

os.chmod(f.name, 0o777)
pipes = subprocess.Popen([f.name], stdout=subprocess.PIPE)
stdout, _ = pipes.communicate()
print(stdout.decode())

os.remove(f.name)
```

So for a anything to make it past these check and be executed it must:

1. be a valid 13x37 JPEG image with the pixel at 7,7 set to #070707
2. be a valid ELF binary that reads `./flag.txt` after decrypting with AES CBC,
   fixed key and the provided IV
3. The IV must contain `DUCTF`

## 1. AES CBC

We need to generate a file that is a sort-of polyglot with JPEG and ELF,
converted with AES CBC.

AES itself operates on 16-byte (for 128-bit AES) blocks, so bigger files are
split and then encrypted seperately. To ensure that identical blocks dont result
in identical blocks in ciphertext, (when using CBC) each block is first xor'd
with something that wont be identical, in this case, the last ciphertext block
or the initialisation vector (IV). Here is a diagram for encryption

```
  ___plaintext____|___plaintext____|___plaintext____|...
       v                 v                v              
IV--->XOR   ,---------->XOR   ,--------->XOR   ,---- ...
       v    |            v    |           v    |         
      AES   |           AES   |          AES   |         
       v---'             v---'            v---'          
  ___ciphertext___|___ciphertext___|___ciphertext___|...
```

For decryption we can just flip the diagram and replace AES with reverse AES
(`AES'`).

```
  ___ciphertext___|___ciphertext___|___ciphertext___|...
       v---,             v---,            v---,         
      AES   |           AES   |          AES   |         
       v    |            v    |           v    |         
IV--->XOR   '---------->XOR   '--------->XOR   '---- ...
       v                 v                v              
  ___plaintext____|___plaintext____|___plaintext____|...
```

This does make sense, however i noticed that all but the first block do not
depend on IV. This turn out useful since we can turn any block into any other
block by applying a chosen value with XOR. So we can control the ciphertext with
the IV directly as follows:

- $m$: first plaintext block
- $c$: first ciphertext block

$$ c = AES(m \oplus IV) \\

AES^{-1}(c) = m \oplus IV \\

AES^{-1}(c) \oplus m = IV \\ $$

All blocks after the first are now "uncontrollable" as ciphertext because IV and
plaintext are set.

## 2. JPEG

JPEG consists of a list of _segments_. Each starts with a marker byte (`ff`)
followed by a identifier and the length of the segment (if non-zero).

| Identifier | Name                                           |
| ---------- | ---------------------------------------------- |
| `d8`       | Start of Image                                 |
| `fe`       | Comment                                        |
| `d9`       | End of Image                                   |
| ...        | _a bunch more that we dont need to know about_ |

The comment segment is perfect for embedding our ELF binary into JPEG. We can
first generate a JPEG image, then insert a _comment_ somewhere containing any
data we want.

## 3. ELF

The binary needs to be super small so creating it "manually" was required. I
followed a the guide
[Creating a minimal ELF-64 file by tchajed](https://github.com/tchajed/minimal-elf/)
and recreated it for my needs. Like in the guide i also wrote the assembly with
a rust EDSL.

```rs
let mut str_end = a.create_label();
let mut filename = a.create_label();
a.jmp(str_end)?; // jump over the string
a.set_label(&mut filename)?;
a.db(b"flag.txt\0")?;
a.set_label(&mut str_end)?;

// open("flag.txt", O_RDONLY)
a.mov(eax, 2)?;
a.lea(rdi, ptr(filename))?;
a.mov(rsi, 0u64)?;
a.syscall()?; // fd -> rax

// sendfile(1, rax, 0, 0xff)
a.mov(rsi, rax)?;
a.mov(eax, 40)?;
a.mov(rdi, 1u64)?;
a.mov(rdx, 0u64)?;
a.mov(r10, 0xffu64)?;
a.syscall()?;
```

I was able to produce a 207 byte long executable.

## 4. _magic!_

Here is how we align the files now (single quotes `'` indicate ASCII
representation for clarity):

```
ciphertext: 7f 'E 'L 'F 02 01 01 00 00 00 00 00 00 00 00 00 
iv:         ?? ?? ?? ?? ?? ?? 'D 'U 'C 'T 'F 00 00 00 00 00
plaintext:  ff d8 ff fe {len} ?? ?? ?? ?? ?? ?? ?? ?? ?? ??
```

This scenario is a little more complicated because in places we define cipertext
and plaintext and in some we define ciphertext and IV. This is not a problem
though, because XOR operates on every byte individually.

All-in-all the file looks like this now:

- First block
  - overlapping headers (6 bytes)
  - `DUCTF` string (5 bytes)
  - padding (5 bytes)
- Rest of the ELF binary
- Rest of the JPEG image

All this information should be enough to solve this challenge.

I also attach the implementation that i created _during_ the CTF here. I kept it
as messy as it was, just removed not-so-interesting code and added comments.

```rs
let mut i = image::RgbImage::new(13, 37);
// jpeg is lossy so filling guarantees the pixel actually has the *exact* color
i.pixels_mut().for_each(|p| *p = Rgb([7, 7, 7]));

let mut imgbuf = Cursor::new(vec![]);
image::codecs::jpeg::JpegEncoder::new(&mut imgbuf)
    .encode_image(&i)
    .unwrap();

let key = Aes128::new(&GenericArray::from(*b"downunderctf2022"));
let mut payload = create_elf_payload();
let mut buf = BytesMut::new();

// pad payload so AES works
while payload.len() % 16 != 0 {
    payload.put_u8(0);
}
assert!(payload.len() % 16 == 0);

let prefix_len = 6;
buf.put_u16(0xffd8);
buf.put_u16(0xfffe);
buf.put_u16(payload.len() as u16 + 2 /*seg len*/ - prefix_len as u16);

// find a good IV
let iv = {
    let mut fblock_target = vec![0u8; 16];
    fblock_target[0..prefix_len].copy_from_slice(&buf[0..prefix_len]);
    key.decrypt_block(GenericArray::from_mut_slice(&mut fblock_target));
    let mut iv = xor_slice(&fblock_target, &payload[0..16]);
    iv[prefix_len..prefix_len + 5].copy_from_slice(b"DUCTF");
    iv
};

// fill the first block up with zeroes
for _ in prefix_len..16 {
    buf.put_u8(0);
}

// encrypt starting with the 2nd block
buf.put(&payload[16..]);
let block_range = |n: usize| (n) * 16..(n + 1) * 16;
for i in 1..buf.len() / 16 {
    let tb = Vec::from(&buf[block_range(i - 1)]);
    xor_assign(&mut buf[block_range(i)], &tb);
    key.encrypt_block(GenericArray::from_mut_slice(&mut buf[block_range(1)]));
}

// append the rest of the image
buf.put(&imgbuf.into_inner()[2..]); // skip "header" (first segment)

// pad the final buffer again because the image might not be aligned
while buf.len() % 16 != 0 {
    buf.put_u8(0);
}
assert!(buf.len() < 1337);

File::create("image").unwrap().write_all(&buf).unwrap();
File::create("iv").unwrap().write_all(&iv).unwrap();
```