Reduced Collisions — Lattice-Based Hash Collision

Initial Analysis

We are provided with a service and its source code (server.py). The challenge implements a lattice-based hash function.

Key Parameters:

• q = 67 (The modulus)
• n = 8 (Number of rows in matrix A)
• m = 20 (Number of columns in matrix A and length of vector y)
• d = 2 (The bound for the collision vector)

A secret 8×20 matrix A is generated randomly. The server generates a random vector y of length 20 (elements in [-2, 0]), calculates h = A·y mod q and provides both y and h. We must provide y' ≠ y such that A·y' = A·y mod q with every element in [-2, 2].

Strategy

Step 1: Recovering Matrix A

Since matrix A is constant for the duration of the connection, we treat the hash function as a system of linear equations. The relationship is H = Y·Aᵀ mod q. By collecting 20 independent samples of (y, h), we construct a 20×20 matrix Y and a 20×8 matrix H, then solve: Aᵀ = Y⁻¹·H mod q.

Step 2: Finding a Collision (The Lattice Problem)

A collision y' satisfies A·(y' − y) = 0 mod q. Let z = y' − y. We need a non-zero vector z such that A·z = 0 mod q and y' = y + z satisfies |y'_i| ≤ 2. This is a classic Short Integer Solution (SIS) problem.

Lattice Construction

We construct a lattice basis B for { z ∈ Z^m : A·z ≡ 0 (mod q) }. We apply the LLL (Lenstra–Lenstra–Lovász) algorithm to reduce the lattice basis. Because q = 67 is small, LLL quickly finds very short vectors z, often with entries in {−1, 0, 1}.

Solve Script

# Recover A using Matrix Inversion
Y_mat = Matrix(Y_samples)
H_mat = Matrix(H_samples)
A = (Y_mat.inv_mod(q) * H_mat).transpose() % q

# Construct lattice basis and reduce with LLL
M = LLL.reduction(IntegerMatrix.from_matrix(B))

# Find collision
for z in M:
    yp = [y[i] + z[i] for i in range(20)]
    if all(abs(x) <= 2 for x in yp):
        # Send yp to server

Flag