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

# DownUnderCTF 2022: File Magic

A short writeup about my favorite challenge from DUCTF. It took me approximatly
12h to solve. I found it was the most creative and challenging one that i
solved.

## 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 anything to make it past these checks 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 (`downunderctf2022`) and the provided IV
3. The IV must contain `DUCTF`

During the competition I discovered the information in the next three headings
in parallel but internally in-order.

## 1. AES CBC "flaw"

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

AES itself operates on 16-byte (for 128-bit AES) blocks, so bigger files are
split and then encrypted separately. To ensure that identical blocks don't
result in identical blocks in ciphertext, each block is first xor'd with
something that won't be identical. In the case of CBC, the last ciphertext block
or the initialisation vector (IV) is used. 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.

```
  ___ciphertext___|___ciphertext___|___ciphertext___|...
       v---,             v---,            v---,         
      ∀EZ   |           ∀EZ   |          ∀EZ   |         
       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 turns 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 in ciphertext after the first are now "uncontrollable" 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 you 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 Payload

The binary needs to be super small so creating it "manually" was required. I
followed 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, question marks `?` represent data that is implicitly
defined):

```
plaintext:  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
ciphertext: ff d8 ff fe {len} ?? ?? ?? ?? ?? ?? ?? ?? ?? ??
```

This scenario is a little more complicated because in some places we define
ciphertext and plaintext and in some we define ciphertext and IV. This is not a
problem 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
- _end of the jpeg comment_
- Rest of the JPEG image

All this information should be enough to solve this challenge!

I here 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;
// write the JPEG headers to start a comment
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, stripping the first segment
buf.put(&imgbuf.into_inner()[2..]);

// 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();
```

I am also still looking for team mates for upcoming CTF events and would be
happy to hack together with you! Just [contact](https://metamuffin.org/contact) me.