Backpack Cryptography

Platform: cryptohack | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-06-23 | Status: Solved Techniques: cjloss_centered_lattice, lll_reduction, merkle_hellman_attack

Summary

Task: Merkle-Hellman knapsack encryption with 272-bit message (34 bytes). Public key a[] and ciphertext ct given. Solution: CJLOSS centered lattice construction with N=n+1=273 scaling, LLL reduction finds the binary message vector.

Backpack Cryptography — CryptoHack (Post-Quantum / Lattices)

Description

Lightweight cryptography is all the rage! Here's my attempt at a lightweight knapsack cipher.

Given a Merkle-Hellman knapsack cryptosystem: a superincreasing private key b[] is transformed via modular multiplication a_i = r * b_i mod q to produce the public key a[]. The flag (34 bytes = 272 bits) is encrypted as a subset sum: ct = sum(x_i * a_i) where x_i are the message bits.

Analysis

The Merkle-Hellman knapsack is known to be insecure due to lattice attacks. The key parameter is the density: ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

d = n / log2(max(a_i)) ≈ 272 / 377 ≈ 0.72

Since d < 0.9408 (the CJLOSS threshold), the system is vulnerable to lattice-based subset-sum attacks.

What failed:

• Standard lattice (identity matrix + public key column) with LLL/BKZ: the solution vector x (with entries in {0,1}, norm ~√136) is NOT the shortest vector in the lattice. LLL finds shorter vectors with entries in {-2,...,2}.
• BKZ with block sizes up to 70: still finds non-binary vectors.
• Shamir attack via 2D lattice, continued fractions, random permutation LLL — all failed. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

The fundamental issue: the solution vector norm (~11.7) is larger than the shortest lattice vectors (~5-6).

Solution

The correct approach is the CJLOSS centered lattice (Coster, Joux, LaMacchia, Odlyzko, Schnorr, Stern 1992). Instead of searching for x ∈ {0,1}^n, we center the problem: let y_i = 2*x_i - 1 ∈ {-1,1}. The target becomes:

sum(a_i * (y_i + 1) / 2) = ct
=> sum(a_i * y_i) = 2*ct - sum(a_i)

The CJLOSS lattice is an (n+1) × (n+1) matrix with N = n+1 = 273:

• Rows 0..n-1: diagonal entry 2, last column N * a_i
• Row n: all 1s in first n columns, last column N * ct ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

The target vector has entries y_i ∈ {-1, 1} in the first n positions and 0 in the last column. LLL finds this vector because in the centered representation, the target has a distinctive structure.

 python read-only • copy allowed Copy
#!/usr/bin/env python3
from fpylll import IntegerMatrix, LLL
from Crypto.Util.number import long_to_bytes

# Load public key and ciphertext from output file
# public_key = [...]  (272 integers)
# ct = 45690752833299626276860565848930183308016946786375859806294346622745082512511847698896914843023558560509878243217521
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

n = len(public_key)  # 272
N = n + 1  # 273 (scaling factor)

# Build CJLOSS centered lattice
M = IntegerMatrix(n + 1, n + 1)

for i in range(n):
    M[i, i] = 2
    M[i, n] = N * public_key[i]

for j in range(n):
    M[n, j] = 1
M[n, n] = N * ct

# LLL reduction
LLL.reduction(M)

# Find the solution row: entries in {-1, 1} for first n columns, 0 for last
for i in range(n + 1):
    row = [M[i, j] for j in range(n + 1)]
    if row[-1] == 0 and all(abs(v) == 1 for v in row[:-1]):
        # Convert from {-1, 1} to {0, 1}: x_i = (y_i + 1) / 2
        # May need to negate the row
        bits = row[:-1]
        if bits[0] == -1:  # Try negation
            bits = [-b for b in bits]
        x = [(b + 1) // 2 for b in bits]
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

        # Reconstruct message from bits (LSB first per the encrypt function)
        msg = 0
        for j, bit in enumerate(x):
            msg |= bit << j
        flag = long_to_bytes(msg)
        if b'crypto{' in flag:
            print(f"Flag: {flag.decode()}")
            break

The solution is found at row 257 (negated) of the LLL-reduced basis. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍