Solution

The challenge itself has a really small source code:

#!/usr/bin/env python3

import json
import random

from Crypto.Cipher import AES
from Crypto.Util.number import getPrime
from Crypto.Util.Padding import pad

FLAG = "dach2026{xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx}"

pbits = 137
p = getPrime(pbits)
key_bits = 16

# Generate hash of the key
factors = [random.SystemRandom().randint(0, p-1) for _ in range(key_bits)]
preimage = [random.SystemRandom().randint(0, 0xff) for _ in range(key_bits)]
hash = sum([factors[i] * preimage[i] % p for i in range(key_bits)]) % p

# Encrypt flag
key = bytes(preimage)
cipher = AES.new(key, AES.MODE_ECB)
enc = cipher.encrypt(pad(FLAG.encode(), 16)).hex()

data = {
    "p": p,
    "factors": factors,
    "hash": hash,
    "enc_flag": enc
}

with open("data.json", "w") as f:
    json.dump(data, f, indent=4)

After a lot of “wtf”, I found out, that we’re dealing with a knapsack -> hidden subset sum problem here.

We only know the factors output, not the preimage values, where each value is an element of range(0xff).

Simplified, this looks like this, but with longer primes:

123456 = sum(
    [
        [ 148 * randint(0, 0xff) % 123 ],
        [ 250 * randint(0, 0xff) % 123 ],
        [ 947 * randint(0, 0xff) % 123 ],
        [ 147 * randint(0, 0xff) % 123 ],
        [ 573 * randint(0, 0xff) % 123 ],
    ] % 123
)

Now, without understanding what a lattice even is, we can steal these Team EU bootcamp slides from 2024, to learn about practical lattice reduction.

We use fpylll, as this seems to be the simplest library to work with.

We need to arrange all of our values onto the matrix like this and add the main diagonal:

W (the Weight) was just randomly chosen. It is required, to make balance things and my script didn’t work without it. From the slides:

How to determine weights: Wing it and hope for the best :)

After calling LLL.reduction, the matrix looks quite a bit different:

We now need to find the closest vector (or something like that, I’m still just following simillar writeups and the slides) to the result of the hash.

Thankfully, that is just one call of CVP.closest_vector with another row of the matrix:

After that, all that is left to do is to reconstruct the key and AES decrypt the flag.

Full script:

#!/usr/bin/env python3

import json
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from fpylll import LLL, IntegerMatrix, CVP

# stolen from generate.py
pbits = 137
n = 16

# load data
data = json.load(open("./data.json", "r"))
p = data["p"]
factors = data["factors"]
h = data["hash"]
ct = bytes.fromhex(data["enc_flag"])

# good guess
W = 120

M = IntegerMatrix(n+1, n+1)
M[0,0] = W * p
for i in range(1,n+1):
    M[i,i ] = 1 # diagonal
    M[i, 0] = W * factors[i-1]

LLL.reduction(M)

target = [W * h] + [W] * (n)
key = bytearray(CVP.closest_vector(M, target)[1:])
cipher = AES.new(key, AES.MODE_ECB)
flag = unpad(cipher.decrypt(ct), 16).decode()
print(flag)

Flag:

dach2026{r3duc3_m3_b4by_0n3_m0r3_t1m3_5a3d66ae5ef12bb5}

Solution#

Solution