Gian Klug

swiss hacking challenge 2024 - cry

Posted on May 1, 2024
Tags: SHC24 Writeup

Difficulty: medium

Category: crypto

Author: TheBadGod

Holy smokes Timothy! You locked the Code for the printer in the vault again. What did I tell you about using the vault without your supervisor? It’s your job to retreive the printer code again How am I supposed to print Barbaras time table?

Files

We are given cry.py

#!/usr/bin/env python3

from Crypto.Util.number import bytes_to_long, long_to_bytes
from Crypto.Util.Padding import pad, unpad
from Crypto.Cipher import AES
from secrets import randbelow
from string import printable
from os import getenv

def encrypt(data, keys):
    if isinstance(data, str):
        data = data.encode()

    data = pad(data, 16)

    data += b"<<valid_secret>>"
    print(f"About to encrypt '{data}'")
    for k in keys:
        data = AES.new(k, AES.MODE_ECB).encrypt(data)

    return data


def decrypt(data, keys):
    if isinstance(data, str):
        data = data.encode()

    for k in keys[::-1]:
        data = AES.new(k, AES.MODE_ECB).decrypt(data)

    if data[-16:] != b"<<valid_secret>>":
        return (f"Could not decrypt; invalid data: {data[:-16]}")

    return f"Decrypted data: {unpad(data[:-16], 16)}"

def add(vault, keys, key, data):
    vault[key] = encrypt(data, keys)

def get(vault, keys, key):
    return decrypt(vault.get(key, b""), keys)

def generate_keys():
    return [long_to_bytes(randbelow(2**9)).ljust(16) for _ in range(6)]

def main():
    vault = {}

    print("Welcome to the future of secret vaults")
    print("Here you can store all your secrets")

    admin_keys = generate_keys()
    user_keys = generate_keys()
    add(vault, admin_keys, "example", "nobody will be able to read this")
    add(vault, admin_keys, "FLAG", getenv("FLAG", "flag{fakeflagfakeflag}"))

    EVALUATION_PERIOD = 5

    while 1:
        print(f"Vault menu: {EVALUATION_PERIOD} TESTING QUERIES LEFT")
        print("  1) add value to vault")
        print("  2) get value from vault")
        print("  3) list available keys in the vault")
        option = int(input("option > "))

        match option:
            case 1:
                key = input("key  > ")
                text = input("text > ")
                assert all(i in printable for i in text)
                add(vault, user_keys, key, text)
                print(f"Successfully added the value ({vault[key]})")
            case 2:
                key = input("key > ")
                value = get(vault, user_keys, key)
                print(value)
            case 3:
                keys = [*vault]
                print(f"Available keys: {keys}")

        EVALUATION_PERIOD -= 1
        if EVALUATION_PERIOD <= 0:
            print("You used your entire allowance. Goodbye")
            exit(0)

if __name__ == "__main__":
    main()

The script allows the user to store and retrieve key/value pairs encrypted using 6 512-bit AES rounds. There is also a flag in the KV store but it is encrypted using a different set of keys.

If we try to get the flag, it gets wrongly decrypted using the user keys.

Exploitation

We’ll have to first brute-force the user keys to then undo the wrong decryption and then crack the admin keys.

Instead of having to brute-force the whole 512**6 possible keypairs, we can use a meet-in-the-middle attack to reduce the problem into having to brute-force two times 512**3 possible keys, which is significantly less compute-intensive. We do that by encrypting a known plaintext with all permutations of 3 possible keys and decrypting a known ciphertext the same way. Afterwards, we can take the intersection of these two halves and get all the keys.

User keys

I first got myself the ciphertext of the already existing nobody will be able to read this string and then wrote the following two very ugly scripts:

upper.py

#!/usr/bin/env python3

from Crypto.Util.number import long_to_bytes
from Crypto.Cipher import AES
from pwn import *

known_ciphertext = b"\xfd\xe6\x7fC\x0c\x86\xd3\xfc\xdc\xcbI\x04k5\xa3\xdat\xbd\x0c\xc5\xdd\xed\x8d6\xbf\xfb$\xda>\xd3h\x80\x84\xf7\xc3\xa9\xb6\x0b\xc3\xa5\x127j\xd0\xd8\x085hM\x07\xb1\xff\xb6\x80{c\x91geey\x11\xd25"[:16] # )]}

def decrypt(ct, key):
    return key.decrypt(ct)

key_obj = {}
def get_key(idx):
    global key_obj
    if str(idx) not in key_obj:
        key = AES.new(long_to_bytes(int(idx)).ljust(16), AES.MODE_ECB, use_aesni='True')
        key_obj[str(idx)] = key
    return key_obj[str(idx)]

with open('upper.dec', 'w') as f:
    for i in range(512):
        for j in range(512):
            for k in range(512):
                ct = known_ciphertext[:16]
                ct = decrypt(ct, get_key(i))
                ct = decrypt(ct, get_key(j))
                ct = decrypt(ct, get_key(k))
                cthex = ct.hex()
                f.write(f"{cthex};{k};{j};{i}\n")

lower.py


#!/usr/bin/env python3

from Crypto.Util.number import long_to_bytes
from Crypto.Cipher import AES
from pwn import *

known_plaintext =  b"nobody will be able to read this\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10<<valid_secret>>"[:16]

def encrypt(ct, key):
    return key.encrypt(ct)

key_obj = {}
def get_key(idx):
    global key_obj
    if str(idx) not in key_obj:
        key = AES.new(long_to_bytes(int(idx)).ljust(16), AES.MODE_ECB, use_aesni='True')
        key_obj[str(idx)] = key
    return key_obj[str(idx)]


with open('lower.enc', 'w') as f:
    for i in range(512):
        for j in range(512):
            for k in range(512):
                ct = known_plaintext[:16]
                ct = encrypt(ct, get_key(i))
                ct = encrypt(ct, get_key(j))
                ct = encrypt(ct, get_key(k))
                cthex = ct.hex()
                f.write(f"{cthex};{i};{j};{k}\n")
        print(i)

After that, I got two text files with a lot of possible keys and values. I wrote the following rust script to efficiently match both halves:

match.rs

use std::collections::HashSet;
use std::fs::File;
use std::io::{self, BufRead, BufReader};

fn main() -> io::Result<()> {
    let mut set = HashSet::new();
    {
        let file = File::open("lower.enc")?;
        let reader = BufReader::new(file);
        let mut line_counter: u64 = 0;

        for line in reader.lines() {
            let line = line?;
            let parts: Vec<&str> = line.split(';').collect();
            if let Some(&first_value) = parts.first() {
                set.insert(first_value.to_string());
            }

            line_counter += 1;
            if line_counter % 262144 == 0 { // 512^2
                println!("Loading lower.enc: Processed {} lines...", line_counter/512/512);
            }
        }
        println!("Completed loading lower.enc.");
    }

    let file = File::open("upper.dec")?;
    let reader = BufReader::new(file);
    let mut line_counter: u64 = 0;

    for line in reader.lines() {
        let line = line?;
        let parts: Vec<&str> = line.split(';').collect();
        if let Some(&first_value) = parts.first() {
            if set.contains(first_value) {
                println!("Match found: {}", line);
            }
        }

        line_counter += 1;
        if line_counter % 262144 == 0 {
            println!("Processing upper.dec: Processed {} lines...", line_counter/512/512);
        }
    }

    println!("Completed processing upper.dec.");
    Ok(())
}

After running it, I got the user keys: 425;342;43;260;30;272 in this case.

Getting the original known encrypted plaintext and encrypted flag

reencrypt.py

#!/usr/bin/env python3

from Crypto.Util.number import long_to_bytes
from Crypto.Cipher import AES
from pwn import *

dummy =            b"\xc4\x81\xea'\xa4[=\x05y\xc8\x95\xba\xf1Z\xb6a\xb6\xac\xceM\xe7|\x8d\x07$\xc2s\x90nm\xfb\xa6@\x96\xd4\x12\x18\xee\xd1i\x87\x14\xf6\xf3Z\x10\xa5\xcc" # ]
flag =             b"5tEH7a\xc4.\xb5\xc6\xa2\x90%\x0e\x17b\x03]\xca\xc1\x8f\x9f9\x8b\xf2t4\xefs~EX\x95K\x9a\x99\r>\x1c\x87U\xa5=\xd9Q!\xc16"

KEYS = [425, 342, 43, 260, 30, 272]

for key in KEYS:
    cipher = AES.new(long_to_bytes(key).ljust(16), AES.MODE_ECB)
    dummy = cipher.encrypt(dummy)
    flag = cipher.encrypt(flag)

print("original dummy:")
print(dummy)
print("original flag:")
print(flag)

original dummy:
b"@\x03\xf4\xf9\xfb\xb9{\xc0\x9c\xc8\x82\x10\x1b\xd2\xd6\xd5\x9e\x87\xa6\xd5OJ[\xddS\x86b\x0e\x9ag\x15'\xfb\xaf\xfd\x96\xde\xc3\xaa\x10V\xf2s\x01\x190\x8e\x8d"
original flag:
b'\x9c\x15D\xf5\x00\xfd\xa2H\xb2.\xfen\xaf\x9f\xea3\xb5\xf0\xe1\xe2\xa2{\x85o\x8bMM\x9a\x8b\x93\xe4A]\xb8\xd1\xf0\x0b\xdb\xad\xaa\xb6\x97>\x03\xc4\xd8\xdcT'

Cracking the admin keys

I repeated the same steps as for the user keys. Here, I only had to redo the part of the upper half again as I already calculated all the values for the plaintext encryptions of the same plaintext before. Again, I ran the matcher rust binary, this time with the new admin key part.

I got the following admin keys for my sample: 17;132;452;26;468;340

Afterwards, I just had to decrypt the flag:

flag.py

#!/usr/bin/env python3

from Crypto.Util.number import long_to_bytes
from Crypto.Cipher import AES
from concurrent.futures import ThreadPoolExecutor
import concurrent
from pwn import *
import threading

flag = b"\x9c\x15D\xf5\x00\xfd\xa2H\xb2.\xfen\xaf\x9f\xea3\xb5\xf0\xe1\xe2\xa2{\x85o\x8bMM\x9a\x8b\x93\xe4A]\xb8\xd1\xf0\x0b\xdb\xad\xaa\xb6\x97>\x03\xc4\xd8\xdcT"

KEYS = [17,132,452,26,468,340][::-1]

for key in KEYS:
    cipher = AES.new(long_to_bytes(key).ljust(16), AES.MODE_ECB)
    flag = cipher.decrypt(flag)

print(flag)

Flag

shc2024{every1_will_b3_able_t0_read_th1s}

Conclusion

Nice chalenge! Didn’t know about that attack before and I would’ve also assumed using multiple keys would increase the computational effort significantly.