lattice-crypto-attacks

$27

Problem Type

Lattice Technique

Key Parameter

RSA small roots

Coppersmith (LLL on polynomial lattice)

Root bound X < N^(1/e)

RSA small d

Boneh-Durfee (multivariate Coppersmith)

d < N^0.292

DSA/ECDSA nonce bias

Hidden Number Problem → CVP

Bias bits known

Knapsack cipher

Low-density lattice attack

Density < 0.9408

LCG truncated output

CVP on recurrence lattice

Unknown bits per output

Subset sum

LLL reduction on knapsack lattice

Element size vs count

NTRU key recovery

Lattice reduction on NTRU lattice

Dimension and key size

1. LATTICE FUNDAMENTALS

1.1 Definitions

A lattice L is the set of all integer linear combinations of basis vectors:

L = { a₁·b₁ + a₂·b₂ + ... + aₙ·bₙ | aᵢ ∈ ℤ }

where b₁, ..., bₙ are linearly independent vectors in ℝᵐ.

Key problems:

• SVP (Shortest Vector Problem): Find the shortest non-zero vector in L

• CVP (Closest Vector Problem): Given target t, find v ∈ L closest to t

• SVP is NP-hard in general, but LLL finds an approximately short vector in polynomial time

1.2 Lattice Quality Metrics

Determinant: det(L) = |det(B)| where B is the basis matrix

Gaussian heuristic: shortest vector ≈ √(n/(2πe)) · det(L)^(1/n)

2. LLL ALGORITHM

2.1 What LLL Does

Takes a lattice basis B and produces a reduced basis B' where:

• Vectors are nearly orthogonal

• First vector is approximately short (within 2^((n-1)/2) factor of SVP)

• Runs in polynomial time: O(n^5 · d · log³ B) where d = dimension, B = max entry size

2.2 SageMath Usage

# SageMath

M = matrix(ZZ, [

    [1, 0, 0, large_value_1],

    [0, 1, 0, large_value_2],

    [0, 0, 1, large_value_3],

    [0, 0, 0, modulus],

])

L = M.LLL()

# Short vectors in L reveal the solution

short_vector = L[0]  # first row is typically shortest

2.3 Python (fpylll)

from fpylll import IntegerMatrix, LLL

n = 4

A = IntegerMatrix(n, n)

# Fill matrix A...

A[0] = (1, 0, 0, large_value_1)

A[1] = (0, 1, 0, large_value_2)

A[2] = (0, 0, 1, large_value_3)

A[3] = (0, 0, 0, modulus)

LLL.reduction(A)

print(A[0])  # shortest vector

3. BKZ (BLOCK KORKINE-ZOLOTAREV)

3.1 Comparison with LLL

Property

LLL

BKZ-β

Quality

2^((n-1)/2) approximation

2^(n/(β-1)) approximation

Speed

Polynomial

Exponential in β

Block size

Fixed (2)

Configurable β

Best for

Quick reduction

High-quality reduction

3.2 Usage

# SageMath

M = matrix(ZZ, [...])

L = M.BKZ(block_size=20)  # β = 20

# fpylll

from fpylll import BKZ

BKZ.reduction(A, BKZ.Param(block_size=20))

Rule of thumb: start with LLL, increase to BKZ if needed. BKZ block size 20-40 is usually sufficient for CTF.

4. COPPERSMITH'S METHOD

4.1 Univariate Case

Given f(x) ≡ 0 (mod N) with small root |x₀| < X, find x₀.

Bound: X < N^(1/d) where d = degree of f.

# SageMath — built-in small_roots

N = ...

R.<x> = PolynomialRing(Zmod(N))

f = x^3 + a*x^2 + b*x + c  # known polynomial

roots = f.small_roots(X=2^100, beta=1.0, epsilon=1/30)

Parameters:

• X: upper bound on the root

• beta: N = p^beta (beta=1.0 for modular root of N itself; beta=0.5 for root mod unknown factor p ≈ √N)

• epsilon: smaller = better results but slower (try 1/30 to 1/100)

4.2 Stereotyped Message Attack (RSA)

# SageMath

n, e, c = ...  # RSA parameters

known_msb = ...  # known upper portion of message

R.<x> = PolynomialRing(Zmod(n))

f = (known_msb + x)^e - c

# x represents the unknown lower bits

X = 2^(unknown_bit_count)

roots = f.small_roots(X=X, beta=1.0)

if roots:

    m = known_msb + int(roots[0])

4.3 Partial Key Exposure (Factor p)

Known MSBs of p: p = p_known + x where x is small.

# SageMath

n = ...

p_known = ...  # known upper bits of p

R.<x> = PolynomialRing(Zmod(n))

f = p_known + x

roots = f.small_roots(X=2^unknown_bits, beta=0.5)

# beta=0.5 because p ≈ √n

if roots:

    p = p_known + int(roots[0])

    q = n // p

4.4 Multivariate Coppersmith (Howgrave-Graham)

For f(x, y) ≡ 0 (mod N):

• No polynomial-time algorithm guaranteed

• Heuristic methods work in practice

• Used in Boneh-Durfee for RSA small d

# SageMath — Boneh-Durfee

# e*d ≡ 1 (mod phi) where phi = (p-1)(q-1)

# Rewrite: e*d = 1 + k*((n+1) - (p+q))

# Let x = k, y = (p+q), both small relative to n

R.<x, y> = PolynomialRing(ZZ)

A = (n + 1) // 2

f = 1 + x * (A + y)  # mod e

# Build shift polynomials and construct lattice

# Apply LLL to find small (x₀, y₀)

5. HIDDEN NUMBER PROBLEM (HNP) — DSA/ECDSA NONCE RECOVERY

5.1 Problem Statement

Given: signatures (rᵢ, sᵢ) where nonces kᵢ have known bias (leaked MSBs or LSBs).

DSA equation: s = k⁻¹(H(m) + xr) mod q

Rearranged: k = s⁻¹(H(m) + xr) mod q

If partial bits of k are known: reduces to CVP on a lattice.

5.2 Attack Setup

# SageMath

def ecdsa_nonce_attack(signatures, q, known_bits, bit_position='msb'):

    """

    signatures: list of (r, s, hash, known_nonce_bits)

    q: curve order

    known_bits: number of known bits per nonce

    """

    n = len(signatures)

    # Build lattice

    B = 2^(q.nbits() - known_bits)  # bound on unknown part

    M = matrix(QQ, n + 2, n + 2)

    for i in range(n):

        r_i, s_i, h_i, a_i = signatures[i]

        t_i = Integer(inverse_mod(s_i, q) * r_i % q)

        u_i = Integer(inverse_mod(s_i, q) * h_i % q)

        M[i, i] = q

        M[n, i] = t_i

        M[n+1, i] = u_i - a_i  # a_i = known nonce bits

    M[n, n] = B / q

    M[n+1, n+1] = B

    # LLL reduction

    L = M.LLL()

    # Find row containing the private key x

    for row in L:

        x_candidate = Integer(row[n] * q / B) % q

        # Verify x_candidate against one signature

        if verify_private_key(x_candidate, signatures[0], q):

            return x_candidate

    return None

5.3 Practical Nonce Bias Sources

Source

Leaked Bits

Required Signatures

MSB bias (always 0)

1 bit

~100 signatures

k generated with wrong length

Variable

~50 signatures

Timing side channel

1-4 bits

20-100 signatures

Insecure PRNG

Many

Few

Reused nonce (k₁ = k₂)

All

2 signatures

For reused nonce (simplest case):

def ecdsa_reused_nonce(r, s1, s2, h1, h2, q):

    """Recover private key when nonce k is reused."""

    # s1 - s2 = k⁻¹(h1 - h2) mod q  (since r is same)

    k = ((h1 - h2) * inverse_mod(s1 - s2, q)) % q

    x = ((s1 * k - h1) * inverse_mod(r, q)) % q

    return x, k

6. KNAPSACK / SUBSET SUM ATTACKS

6.1 Low-Density Attack

Knapsack: given weights a₁,...,aₙ and target S, find x₁,...,xₙ ∈ {0,1} such that Σxᵢaᵢ = S.

Density d = n / max(log₂ aᵢ). If d < 0.9408, lattice attack works.

# SageMath

def knapsack_lattice(weights, target):

    """Solve subset sum via LLL lattice attack."""

    n = len(weights)

    # Build lattice (Lagarias-Odlyzko style)

    N = ceil(sqrt(n) / 2)  # scaling factor

    M = matrix(ZZ, n + 1, n + 1)

    for i in range(n):

        M[i, i] = 1

        M[i, n] = N * weights[i]

    M[n, n] = N * target

    # Alternative: CJLOSS embedding

    M2 = matrix(ZZ, n + 1, n + 2)

    for i in range(n):

        M2[i, i] = 1

        M2[i, n + 1] = N * weights[i]

    M2[n, n] = 1

    M2[n, n + 1] = N * (-target)

    L = M2.LLL()

    # Look for short vector with entries in {0, 1, -1}

    for row in L:

        if all(v in (0, 1) for v in row[:n]):

            solution = list(row[:n])

            if sum(solution[i] * weights[i] for i in range(n)) == target:

                return solution

    return None

7. NTRU CRYPTANALYSIS

7.1 NTRU Lattice

# SageMath

def ntru_lattice_attack(h, q, N):

    """

    Construct NTRU lattice for key recovery.

    h = public key polynomial (mod q)

    q = modulus

    N = dimension

    """

    # NTRU lattice:

    # | qI  0 |

    # | H   I |

    # where H is the circulant matrix of h

    H = matrix(ZZ, N, N)

    for i in range(N):

        for j in range(N):

            H[i, j] = h[(j - i) % N]

    M = block_matrix([

        [q * identity_matrix(N), zero_matrix(N)],

        [H, identity_matrix(N)]

    ])

    L = M.LLL()

    # Short vector in reduced basis = (f, g) private key

    for row in L:

        f = vector(row[:N])

        g = vector(row[N:])

        if f.norm() < q and g.norm() < q:

            return f, g

    return None

8. CONSTRUCTING ATTACK LATTICES — METHODOLOGY

8.1 General Recipe

1. Express the cryptographic problem as:

   "Find small x such that f(x) ≡ 0 (mod N)"

   or "Find x close to target t in some lattice L"

2. Choose lattice type:

   ├─ Polynomial lattice → Coppersmith-style

   ├─ Modular lattice → HNP-style CVP

   └─ Knapsack lattice → subset sum / CJLOSS

3. Determine dimensions:

   └─ More dimensions = better approximation but slower

4. Set scaling factors:

   └─ Balance the rows so short vector has roughly equal entries

   └─ Common: multiply by N/X where X is the root bound

5. Apply reduction:

   ├─ LLL first (fast, usually sufficient)

   └─ BKZ if LLL fails (increase block size: 20, 30, 40)

6. Extract solution:

   └─ Check reduced basis rows for valid solutions

8.2 Embedding Technique (CVP → SVP)

Transform CVP into SVP by embedding the target into the lattice:

# SageMath

def cvp_to_svp(basis_matrix, target, scale=1):

    """Convert CVP to SVP via Kannan's embedding."""

    n = basis_matrix.nrows()

    m = basis_matrix.ncols()

    # Augment matrix

    M = matrix(ZZ, n + 1, m + 1)

    for i in range(n):

        for j in range(m):

            M[i, j] = basis_matrix[i, j]

        M[i, m] = 0

    for j in range(m):

        M[n, j] = target[j]

    M[n, m] = scale  # scaling factor (try 1, then adjust)

    L = M.LLL()

    # Look for row with last entry = ±scale

    for row in L:

        if abs(row[m]) == scale:

            return vector(target) - vector(row[:m]) * (row[m] // abs(row[m]))

    return None

8.3 Dimension Selection Guide

Problem

Typical Dimension

Notes

Coppersmith univariate (degree d)

d × m where m ≈ 1/ε

Larger m = smaller root bound

HNP with n signatures

n + 2

n ≥ known_bits_ratio × q_bits

Knapsack with n weights

n + 1 or n + 2

Depends on density

LCG with n outputs

n + 1

More outputs = easier

Boneh-Durfee

(m+1)(m+2)/2

m = parameter depth

9. DECISION TREE

Lattice approach needed — which construction?

│

├─ RSA-related?

│  ├─ Small unknown part of message → Coppersmith univariate

│  │  └─ Check: unknown_bits < n_bits / e

│  ├─ Partial factor knowledge → Coppersmith mod p

│  │  └─ Use beta=0.5, X=2^unknown_bits

│  ├─ Small private exponent d → Boneh-Durfee

│  │  └─ Check: d < N^0.292

│  └─ Multiple related equations → multivariate Coppersmith

│

├─ DSA/ECDSA-related?

│  ├─ Reused nonce → direct algebraic recovery (no lattice needed)

│  ├─ Partial nonce leakage → HNP → CVP lattice

│  │  └─ Need enough signatures: n ≥ q_bits / leaked_bits

│  └─ Nonce bias → statistical HNP → larger lattice

│

├─ Knapsack / subset sum?

│  ├─ Low density (d < 0.9408) → CJLOSS lattice attack

│  ├─ High density → lattice attack unlikely to work

│  └─ Super-increasing → greedy algorithm (no lattice needed)

│

├─ LCG / PRNG?

│  ├─ Full outputs known → algebraic recovery (no lattice)

│  ├─ Truncated outputs → CVP on recurrence lattice

│  └─ Unknown modulus → use GCD of output differences

│

├─ NTRU?

│  └─ Build circulant lattice → LLL/BKZ for short key vector

│

└─ Custom problem?

   ├─ Express as "find small root of polynomial mod N" → Coppersmith

   ├─ Express as "find lattice point close to target" → CVP

   ├─ Express as "find short vector in lattice" → SVP / LLL

   └─ If none fit → probably not a lattice problem

10. COMMON PITFALLS

Pitfall

Symptom

Fix

Root bound too large

small_roots() returns empty

Reduce X, increase epsilon, verify bound satisfies Coppersmith criterion

Wrong scaling

LLL finds irrelevant short vector

Scale columns so target vector has balanced entries

Insufficient dimension

Solution not in reduced basis

Increase m parameter (more shift polynomials)

Wrong beta

Coppersmith doesn't find factor

beta=0.5 for half-size factor, beta=1.0 for full modulus

Too few signatures (HNP)

Lattice attack fails

Collect more signatures with nonce bias

BKZ block size too small

Solution not short enough

Increase block size (try 25, 30, 40)

Integer overflow

SageMath crashes

Use ZZ ring explicitly, avoid mixing QQ and ZZ