Practical lattice reductions

for CTF challenges

Robin Jadoul
2024/02/23
Bootcamp ICC Team Europe, Athens, Greece
 Outline

Outline

1. Lattices?
2. Why lattices?
3. How lattices?
4. Lattice tips and tricks
5. Common lattice problems
6. Building with lattices
7. Get your hands dirty

Practical lattice reductions for CTF challenges Athens, 2024/02/23 2

Lattices?
 Lattices

• “A lattice ℒ of dimension 𝑛 is a discrete additive subgroup of ℝ𝑛 .”

• It’s a group ⇒ addition, scalar mult
• Discrete ⇒ we can map it to ℚ𝑛 or ℤ𝑛
• A group is a ℤ-module, so think vector spaces
• Pick a basis 𝑩 = (𝒃1 , …, 𝒃𝑛 ) ∈ ℝ𝑛
∘ We usually write 𝒃𝑖 as rows of 𝑩
• ℒ = {∑ 𝑎𝑖 ⋅ 𝒃𝑖 | 𝒂 ∈ ℤ𝑛 }
• Many choices of 𝑩

Practical lattice reductions for CTF challenges Athens, 2024/02/23 4

 Lattices

https://www.redwoodstore.com/spectre-
fan-lattice
https://en.wikipedia.org/wiki/Lattice_%28 https://en.wikipedia.org/wiki/File:
group%29 Diamond_lattice.stl

Practical lattice reductions for CTF challenges Athens, 2024/02/23 5

 Lattices

https://en.wikipedia.org/wiki/Lattice_reduction

Practical lattice reductions for CTF challenges Athens, 2024/02/23 6

 Lattice properties

• “Fundamental parallelepiped” 𝒫(𝑩): a single “enclosed region”

∘ 𝒫(𝑩) = {∑ 𝑎𝑖 ⋅ 𝒃𝑖 | 𝒂 ∈ [0, 1)}
∘ ℝ𝑛 is tiled by 𝒫(𝑩)
• det(ℒ) = vol(𝒫(𝑩))) = |det(𝑩)|
∘ Invariant, independent of 𝑩
∘ Base change: invertible and unimodular
• Successive minima: 𝜆𝑖 (ℒ)
∘ 𝜆1 (ℒ) length of shortest vector
√ 1
∘ 𝜆1 (ℒ) ≤ 𝑛|det(ℒ)| 𝑛
1 √ 1
∘ GM(𝜆1 , …, 𝜆𝑛 ) = (∏ 𝜆𝑖 ) 𝑛 ≤ 𝑛|det(ℒ)| 𝑛
• Distance 𝜇(𝒕, ℒ) = min‖𝒕 − 𝒗‖
𝒗∈ℒ

Practical lattice reductions for CTF challenges Athens, 2024/02/23 7

 Lattice properties

https://simons.berkeley.edu/sites/default/files/docs/14953/intro.pdf
https://simons.berkeley.edu/sites/default/files/docs/14953/intro.pdf

Practical lattice reductions for CTF challenges Athens, 2024/02/23 8

 Sage

from sage.modules.free_module_integer import IntegerLattice

B = Matrix(QQ, [[1, 0], [0, 2]])/2
L = IntegerLattice(B.denominator() * B, lll_reduce=False)
# Warning, may be slow :)
L.shortest_vector() # (1, 0)
L.closest_vector((123/42, 345/12)) # (3, 28)

L.volume() # 2

Practical lattice reductions for CTF challenges Athens, 2024/02/23 9

Why lattices?
 Why lattices? Part 1: construction

• Many things in lattices are hard

• SVP: “shortest vector problem”
• CVP: “closest vector problem”
• SIS: “short integer solutions”
• ⇒ build trapdoors, e.g. LWE
• Hopefully post-quantum too
• See later

Practical lattice reductions for CTF challenges Athens, 2024/02/23 11

 Why lattices? Part 2: destruction

• Many things are “small”

• Many things are discrete
• e.g. some instances of integer programming
• RSA: 𝑝𝑞 − 𝜑(𝑝𝑞) = 𝑝 + 𝑞 − 1 is “small” wrt. 𝑝𝑞
• Breaking lattice schemes
• Generally: linear structure
• Think about linear systems with small solutions

Practical lattice reductions for CTF challenges Athens, 2024/02/23 12

 Why lattices? Part 2: destruction

• Known to break many crypto “weaknesses”

• Some bias in your RNG? Lattices will break it.
• Chose your RSA private key wrong? Lattices will break it.
• Lost some precision in your floating points calculations? Lattices
might help.
• Some think they even might break factoring :)

Practical lattice reductions for CTF challenges Athens, 2024/02/23 13

How lattices?
 Improving a basis

• Starting point: some basis 𝑩

• Goal: good basis 𝑩′
• But what is good?
• And how do we find it?

Practical lattice reductions for CTF challenges Athens, 2024/02/23 15

 Good lattices

• Goal: find a better basis

• Good basis?
∘ Shorter basis vectors
∘ Close to orthogonal
∘ Find some short vectors
• Great basis?
∘ Read off 𝜆1 (ℒ)
∘ Read off all 𝜆𝑖 (ℒ)?

Practical lattice reductions for CTF challenges Athens, 2024/02/23 16

 Intuition from linear algebra

• We know det(ℒ) is constant

• Want: shorter 𝒃𝑖
• So we need wider angles between all 𝒃𝑖 to have more area
• Hence, more orthogonal

• Gram-Schmidt orthogonalization
• But breaks the lattice
• Use it as a guideline

Practical lattice reductions for CTF challenges Athens, 2024/02/23 17

 Lattice reduction algorithms

• LLL (Lenstra–Lenstra–Lovász)
∘ Polynomial time 𝒪(𝑛6 log3 ‖𝑩‖∞ )
𝑛−1
′
∘ ‖𝒃1 ‖ ≤ 2 2 𝜆1 (ℒ)
• HKZ (Hermite–Korkine–Zolotarev)
∘ Exponential time
∘ ‖𝒃1′ ‖ = 𝜆1 (ℒ)
• BKZ (Block (H)KZ)
∘ Parametrized by block size 𝛽
∘ Larger 𝛽: slower
∘ Smaller 𝛽: worse basis
• Sieving and other costly approaches

Practical lattice reductions for CTF challenges Athens, 2024/02/23 18

 Basis reduction in 2D

• In two dimensions, exact is easy

• Provides some basic intuition for LLL
• Looks like GCD
def gauss_reduction(v1, v2):
while True:
if v2.norm() < v1.norm():
v1, v2 = v2, v1 # swap step
m = round( (v1 * v2) / (v1 * v1) )
if m == 0:
return (v1, v2)
v2 = v2 - m*v1 # reduction step

Practical lattice reductions for CTF challenges Athens, 2024/02/23 19

 A brief look at LLL

def LLL(B, delta):

Q = gram_schmidt(B)

def mu(i,j):
v = B[i]
u = Q[j]
return (v*u) / (u*u)

n, k = B.nrows(), 1
while k < n:

# length reduction step

for j in reversed(range(k)):
if abs(mu(k,j)) > .5:
B[k] = B[k] - round(mu(k,j))*B[j]
Q = gram_schmidt(B)

# swap step
if Q[k]*Q[k] >= (delta - mu(k,k-1)**2)*(Q[k-1]*Q[k-1]):
k = k + 1
else:
B[k], B[k-1] = B[k-1], B[k]
Q = gram_schmidt(B)
k = max(k-1, 1)

return B

Practical lattice reductions for CTF challenges Athens, 2024/02/23 20

Lattice tips and tricks
 Weights

𝒛 = 𝑎1 𝒗1 + … + 𝑎𝑚 𝒗𝑚
• 𝑚>𝑛
• All 𝑎𝑖 small
• Linear system with a small solution
∘ But underdetermined
∘ So not just linear algebra
• (approximate) SVP would find a short solution

Practical lattice reductions for CTF challenges Athens, 2024/02/23 22

 Weights

𝒛 0 0 … 0
⎛
⎜ ⎞
⎜ −𝒗1 1 0 … 0⎟ ⎟
⎜
⎜ ⎟
⎜ −𝒗2 0 1 … 0⎟ ⎟
⎜
⎜ ⎟
⎟
⎜ ⋮ ⋮ ⋮ ⋱ ⋮ ⎟
−𝒗 0 0 … 1
⎝ 𝑚 ⎠
• But, what if we have some remaining short 𝒓 = 𝒛 − ∑ 𝑎𝑖 𝒗𝑖 ?
• To LLL, short is short
• Assign higher weights 𝑊 to first columns
∘ ⇒ 𝑊 𝒓 not so short anymore
∘ Could even vary 𝑊𝑖 for element of 𝒛
• Note: short vectors can also be the negation of what you search

Practical lattice reductions for CTF challenges Athens, 2024/02/23 23

 Weights

𝑊𝒛 0 0 … 0
⎛
⎜ ⎞
⎜ −𝑊 𝒗1 1 0 … 0⎟
⎟
⎜
⎜ ⎟
⎜ −𝑊 𝒗2 0 1 … 0⎟
⎟
⎜
⎜ ⎟
⎜ ⋮ ⋮ ⋮ ⋱ ⋮⎟
⎟
−𝑊 𝒗𝑚 0 0 … 1
⎝ ⎠

z = vector(ZZ, [...])
v = Matrix(ZZ, m, n, [[...], ...])
L = Matrix.block([[Matrix(z), 0], [v, 1]])
W = Matrix.diagonal([w1, w2, ..., wn, 1, 1, ..., 1])
L = (L * W).LLL() / W

Practical lattice reductions for CTF challenges Athens, 2024/02/23 24

 How to determine weights

1. Wing it and hope for the best :)

• Works fairly often
• Can finetune with synthetic data
• Wiggling weights can even help finding different solutions
2. Investigate expected weights
• Mostly when different columns have different expected weights in
the target vector
• Observe: outliers in ‖𝒗‖ = √𝑣12 + … + 𝑣𝑛2 weigh more
• So the goal is: make all 𝑣𝑖 roughly equal
∘ Investigate expected result in target vector
∘ Modify weights per column so target vector is all 1 (or arbitrary
constant like 2128 )

Practical lattice reductions for CTF challenges Athens, 2024/02/23 25

 CVP

• Sometimes, switch view to CVP

• Rather than solving a linear system, you’re close to some lattice point
• e.g. integer multiple + random noise (see LWE later)
• So looking for a lattice vector close to our target
∘ Either close vector is final goal
∘ Or just solve with linear algebra after
• If you have a range of values, put the target in the center

Practical lattice reductions for CTF challenges Athens, 2024/02/23 26

 How to CVP

Kannan embedding
𝑩 0
( )
𝒕 𝑞
• Embed CVP into an SVP instance
• Likely close to what you started with
• Short vector: (𝒕 − 𝑩𝒄, 𝑞)
• 𝑞 ~ a weight, matters for results

Practical lattice reductions for CTF challenges Athens, 2024/02/23 27

 How to CVP

Babai’s closest plane

• Uses a reduced basis for the original lattice
• Greedy algorithm
• Iteratively project each coordinate onto the closest hyperplane
• In sage, over ℚ: GS step is generally slow
∘ Exact numbers that grow fast-ish
def Babai_CVP(mat, target):
M = IntegerLattice(mat, lll_reduce=True).reduced_basis
G = M.gram_schmidt()[0]
diff = target
for i in reversed(range(G.nrows())):
diff -= M[i] * ((diff * G[i]) / (G[i] * G[i])).round()
return target - diff

Practical lattice reductions for CTF challenges Athens, 2024/02/23 28

 Try different reductions

• When LLL is fast enough, but gives no results

• Consider trying BKZ instead
• Experiment with block size 𝛽, synthetic data is good
• (𝛽 = 𝑛) ≡ HKZ
• For more speed (especially coppersmith): consider flatter

Practical lattice reductions for CTF challenges Athens, 2024/02/23 29

 Magic tricks for fast exploration

• Got a linear system and some bounds?

• Why not try asking nicely
• rkm0959 made a tool/library: rkm0959/Inequality_Solving_with_CVP
• Could even make a wrapper for convenience
• Good for first exploration, not always foolproof

Practical lattice reductions for CTF challenges Athens, 2024/02/23 30

 Enumeration

• Your target is not always the shortest

• Or even in the basis for that matter
• It’s still short though
∘ It’s a small linear combination of basis vectors
∘ Try bruteforce
∘ Or random combinations
• fp(y)lll also has structured enumeration
• Optionally with extra pruning
• badly documented
∘ https://fpylll.readthedocs.io/en/latest/modules.html

Practical lattice reductions for CTF challenges Athens, 2024/02/23 31

 fpylll enumeration

from fpylll import IntegerMatrix

from fpylll.fplll.gso import MatGSO
from fpylll.fplll.enumeration import (Enumeration,
EvaluatorStrategy)
A = IntegerMatrix.from_matrix(M.LLL())
count = 2000
G = MatGSO(A)
G.update_gso()
enum = Enumeration(G, nr_solutions=count,
strategy=EvaluatorStrategy.BEST_N_SOLUTIONS)
n = M.nrows()
for vec, length in enum.enumerate(0, n, max_dist, 0, t):
...

Practical lattice reductions for CTF challenges Athens, 2024/02/23 32

 Polynomials

• Polynomials form a vector space

∘ If degree is bounded/fixed
∘ Over ℝ or otherwise
• So we can take a discrete additive subgroup of them
• Look, ma, it’s a lattice!
• Basis for coppersmith’s method and ring-LWE (see later)

Practical lattice reductions for CTF challenges Athens, 2024/02/23 33

 Codes

• Hmm, I have a lattice over 𝔽2

• While that may be true, “small” mostly breaks down
• Have a look at coding theory instead
• Techniques like ISD can be very powerful here
• Can also apply over
∘ 𝔽3 or other small fields
∘ Fields of small characteristic (𝔽2𝑘 etc)

Practical lattice reductions for CTF challenges Athens, 2024/02/23 34

Common lattice problems
 Making things modular

• Instead of working over ℤ, we now want ℤ/𝑞ℤ

• Keep thinking about linear systems
• ∑ 𝑎𝑖 𝑥𝑖 ≡ 𝑦 (mod 𝑞)
• ∑ 𝑎𝑖 𝑥𝑖 = 𝑦 + 𝑘𝑞
• Repeat a few times
• Stack 𝑞 ⋅ 𝐼𝑚 under your matrix

Practical lattice reductions for CTF challenges Athens, 2024/02/23 36

 Knapsack and Subset Sum

• Given:
∘ A set 𝑆 = {𝑠1 , …, 𝑠𝑛 }
∘ A value 𝑣 = ∑ 𝑏𝑖 𝑠𝑖 , with 𝑏𝑖 ∈ {0, 1}
• Find appropriate 𝑏𝑖
• Often called a knapsack problem
• More accurately it’s a subset sum problem
∘ there are no values attached
• Known public key cryptosystem
∘ Merkle-Damgård
∘ Broken by lattices (low density)

Practical lattice reductions for CTF challenges Athens, 2024/02/23 37

 Knapsack and Subset Sum

𝑣 0 0 … 0
⎛
⎜ ⎞
⎜ −𝑠1 1 0 … 0⎟ ⎟
⎜
⎜ ⎟
⎜ −𝑠2 0 1 … 0⎟ ⎟
⎜
⎜ ⎟
⎟
⎜ ⋮ ⋮ ⋮ ⋱ ⋮ ⎟
−𝑠 0 0 … 1
⎝ 𝑛 ⎠
• Short vector (0, 𝑏1 , 𝑏2 , …, 𝑏𝑛 )
• Rephrase as CVP
∘ Leave out first row
∘ Target: (𝑣, 0, 0, …, 0)
• Optimize CVP:
∘ Want 𝑏𝑖 ∈ {0, 1}, so centered around 12
∘ Can do the same trick in the original lattice

Practical lattice reductions for CTF challenges Athens, 2024/02/23 38

 Knapsack and Subset Sum

Think about it:

• What about a more general version
∘ 𝑏𝑖 ∈ 𝒳
∘ Knapsack: optimize for some value 𝑡𝑖
∘ Dealing with negative numbers
∘ Parallel instances
∘ Modular
∘ …
• Hidden Subset Sum problem

• Don’t forget to look at the negatives in your reduced basis!

Practical lattice reductions for CTF challenges Athens, 2024/02/23 39

 Approximate GCD

• Given: samples 𝑥𝑖 = 𝑞𝑖 𝑝 + 𝑟𝑖 , with small 𝑟𝑖

• Target: Find 𝑝, the gcd of the samples, up to errors 𝑟𝑖
• Partial AGCD: 𝑟0 = 0
∘ i.e. 𝑥0 = 𝑞0 𝑝
∘ e.g. RSA with extra information

Practical lattice reductions for CTF challenges Athens, 2024/02/23 40

 AGCD: SDA

• 𝑥𝑥𝑖 ≈ 𝑞𝑞𝑖
0 0
• Find candidate 𝑞0
• Recover 𝑝 from 𝑥0 , 𝑞 + 0
• Short vector: (𝑊 𝑞0 , 𝑞0 𝑟1 − 𝑞1 𝑟0 , …)

⎛ 𝑊 𝑥1 𝑥2 … 𝑥𝑛 ⎞
⎜
⎜ 0 𝑥0 0 … 0⎟⎟
⎜
⎜ ⎟
⎟
⎜
⎜ 0 0 𝑥0 … 0⎟⎟
⎜
⎜ ⎟
⎜ ⋮ ⋮ ⋮ ⋱ ⋮ ⎟
⎟
0 0 0 … 𝑥0
⎝ ⎠

Practical lattice reductions for CTF challenges Athens, 2024/02/23 41

 AGCD: Orthogonal lattice

• Orthogonal lattice
∘ ℒ⟂ = {𝒗 | ∀𝑏 ∈ ℒ, ⟨𝒗, 𝒃⟩ = 0}
⟂
∘ Observe: ℒ ⊆ (ℒ⟂ )
∘ Useful for some problems, including hidden subset sum
• General idea: find short vector orthogonal to some target
∘ Often just to one vector or a lattice with 2 basis vectors
∘ Then derive some useful quantity
• ℒ(𝒒, 𝒓)⟂ ⊆ ℒ(𝒙)⟂ , and short
• reduce ℒ(𝒙)⟂ to find a sub-basis spanning ℒ(𝒒, 𝒓)
• recover 𝒒, 𝒓

Practical lattice reductions for CTF challenges Athens, 2024/02/23 42

 Hidden Number Problem

𝛼𝑖 𝑥 + 𝜌𝑖 𝑘𝑖 ≡ 𝛽𝑖 (mod 𝑁 )
• 𝑘𝑖 bounded
• See (EC)DSA biased nonce attacks
∘ 𝛼𝑖 = −𝑟𝑖 , 𝜌𝑖 = 𝑠𝑖 , 𝛽𝑖 = 𝐻 − 2𝑡 MSBnonce , 𝑘𝑖 = LSBnonce
• Key realization: 𝑘𝑖 ≡ 𝛽𝑖 −𝛼 𝜌𝑖
𝑖𝑥
is bounded/small
∘ Try to build the lattice ;)
∘ Or read biased nonce papers
• Generalization: EHNP
∘ Support multiple “holes”
∘ Formulation gets complex
∘ “Just” implementing the paper is feasible

Practical lattice reductions for CTF challenges Athens, 2024/02/23 43

 Coppersmith’s Method

• Shift in focus
∘ No longer linear systems… one polynomial
• 𝑓(𝑥) ≡ 0 (mod 𝑁 ), monic, 𝑥 < 𝑋 bounded
∘ Or even mod 𝑑 ≈ 𝑁 𝛽 with 𝑑 | 𝑁
• Sage has f.small_roots(), with some parameters
∘ or use implementation from kiona/defund/…
∘ flatter usually works very well for these
𝛽2
• 𝑋 < 𝑁 deg(𝑓) −𝜀
∘ 𝜀 is a useful parameter for sage
∘ Smaller 𝜀 is slower, maybe brute some bits
• Multivariate (heuristic) generalizations

Practical lattice reductions for CTF challenges Athens, 2024/02/23 44

 Coppersmith intuition

• Generate polynomials sharing roots (mod 𝑁 )

∘ 𝑥𝑘 𝑓(𝑥)
∘ 𝑁 𝑘 𝑓(𝑥)
∘ 𝑓 𝑘 (𝑥)
∘ ⇒ 𝑥𝑖 𝑁 𝑗 𝑓 𝑘 (𝑥)
• Find small 𝑓 ′ over ℤ
∘ Lattice reduction
∘ Factor over ℤ
∘ Check results (mod 𝑁 )
• Multivariate
∘ Extract roots from multiple polynomials
∘ Gröbner basis, resultants, …

Practical lattice reductions for CTF challenges Athens, 2024/02/23 45

 Coppersmith attacks

• RSA: stereotyped message

∘ 𝑓(𝑥) = (𝐾 + 𝑥)𝑒 − 𝑐 ≡ 0 (mod 𝑁 ), 𝑥 small
• RSA: partially known factor
1
∘ 𝑓(𝑥) = (𝑝high + 𝑥) ≡ 0 (mod 𝑝), 𝑥 < 𝑁 4 , 𝑝 | 𝑁
• Boneh-Durfee
∘ 𝑓(𝑥, 𝑦) = 𝑥((𝑁 + 1) − 𝑦) ≡ 0 (mod 𝑒)
∘ 𝑦 = −(𝑝 + 𝑞), 𝑥 modular “wraps”
• AGCD
∘ Multivariate

Practical lattice reductions for CTF challenges Athens, 2024/02/23 46

Building with lattices
 Learning With Errors

𝒔 ← 𝜒𝑛k
𝒂𝒊 ← ℤ𝑛𝑞
𝑒𝑖 ← 𝜒e
𝑏𝑖 = ⟨𝒔, 𝒂𝑖 ⟩ + 𝑒𝑖

𝒃 = 𝑨𝑠 + 𝒆

Practical lattice reductions for CTF challenges Athens, 2024/02/23 48

 LWE

• Distinguishing
• Key recovery
• Embedding messages
∘ 𝑏 = ⟨𝒔, 𝒂⟩ + 𝑒 + 𝑝𝑞 ⋅ 𝑚
∘ 𝑏 = ⟨𝒔, 𝒂⟩ + 𝑝 ⋅ 𝑒 + 𝑚

Practical lattice reductions for CTF challenges Athens, 2024/02/23 49

 Ring-LWE

𝑅 = ℤ[𝑋]/𝑓(𝑋), 𝑓 monic irreducible, deg(𝑓) = 𝑁

𝑅𝑞 = 𝑅/𝑞𝑅
𝑠(𝑋) ← 𝜒𝑁
k ∈ 𝑅𝑞

𝑒(𝑋) ← 𝜒𝑁
e ∈ 𝑅𝑞

𝑏𝑖 (𝑋) = 𝑎𝑖 (𝑋) ⋅ 𝑠(𝑋) + 𝑒𝑖 (𝑋)

Practical lattice reductions for CTF challenges Athens, 2024/02/23 50

 Ring-LWE

𝑏𝑖 (𝑋) = 𝑎𝑖 (𝑋) ⋅ 𝑠(𝑋) + 𝑒𝑖 (𝑋)

𝑎 (𝑋 −1 𝑎) … (𝑋 −𝑁+1 𝑎)1 ⎞
⎛
⎜
𝑖,1 1
⎟
⎜
⎜ 𝑎 (𝑋 −1 𝑎) … (𝑋 −𝑁+1 𝑎)2 ⎟
⎟
𝒃𝒊 = ⎜
⎜
𝑖,2 2 ⎟
⎟ ⋅ 𝒔 + 𝒆𝒊
⎜
⎜ ⋮ ⋮ ⋱ ⋮ ⎟
⎟
⎜ ⎟
𝑎𝑖,𝑁 (𝑋 −1 𝑎)𝑁 … (𝑋 −𝑁+1 𝑎)𝑁
⎝ ⎠

Practical lattice reductions for CTF challenges Athens, 2024/02/23 51

 NTRU

𝑅 = ℤ[𝑋]/(𝑋 𝑁 ± 1)
𝑅𝑞 = 𝑅/𝑞𝑅
𝑓 ← 𝜒𝑁 ∈ 𝑅𝑞 , ∃𝑓 −1
𝑔 ← 𝜒𝑁 ∈ 𝑅𝑞
𝑔
ℎ=
𝑓

Practical lattice reductions for CTF challenges Athens, 2024/02/23 52

 NTRU

• Distinguishing
• Recover 𝑓
• Embedding messages
∘ 𝑓 = 𝑝 ⋅ 𝑓′ + 1
∘ 𝑐 = 𝑓𝑔 + 𝑝𝑞 ⋅ 𝑚
∘ 𝑐 ⋅ 𝑓 ≡ 𝑔 + 𝑝𝑞 ⋅ 𝑚 ⋅ 𝑝 ⋅ 𝑓 ′ + 𝑝𝑞 ⋅ 𝑚
• Alternative:
∘ ℎ = 𝑝 ⋅ 𝑓𝑔 , 𝑐 = 𝑟 ⋅ ℎ + 𝑚
• Parameters matter: NTRU fatigue/overstretched NTRU

Practical lattice reductions for CTF challenges Athens, 2024/02/23 53

 NTRU lattice

1 ℎ
( )
0 𝑞
• Matrix form for ℎ (and 0, 1, 𝑞)
∘ (anti-)circulant matrix
• short vector: (𝑓, 𝑔) = 𝑓 ⋅ (1, ℎ) + 𝑘 ⋅ (0, 𝑞)

Practical lattice reductions for CTF challenges Athens, 2024/02/23 54

 Estimating difficulty

• https://github.com/malb/lattice-estimator
∘ Viability
∘ Ideas for attacks to look at
∘ Making sure your own lattices are safe?
• https://github.com/WvanWoerden/NTRUFatigue
∘ Specifically for NTRU
∘ Fatigue/overstretched regime

Practical lattice reductions for CTF challenges Athens, 2024/02/23 55

 Breaking things

Linear algebra
• Basis is linear algebra + noise
• Sometimes the noise is not there
• Or not enough
• So just throw matrices at it

Lattice reduction
• AKA primal attack
• The straightforward thing

Practical lattice reductions for CTF challenges Athens, 2024/02/23 56

 Breaking things

Weak structure
• RLWE/NTRU/… in a weird ring
∘ Composite modulus
∘ Reducible polynomial
∘ …
• Chinese remainder theorem
∘ AKA working mod a factor
• Depends on end goal

Practical lattice reductions for CTF challenges Athens, 2024/02/23 57

 Breaking things

Linearization
• Arora-Ge attack
• Consider 𝑒 ∈ {−1, 0, 1}
• Write 𝑣 = ⟨𝒔, 𝒂⟩ − 𝑏
• 𝑣 ⋅ (𝑣 − 1) ⋅ (𝑣 + 1) ≡ 0
• Max degree: 3
• Enough samples → each monomial becomes 1 linear variable
• Linear algebra

Practical lattice reductions for CTF challenges Athens, 2024/02/23 58

 Some resources
• https://eprint.iacr.org/2023/032.pdf
• https://eprint.iacr.org/2020/1506.pdf
• https://kel.bz/post/lll/
• https://github.com/rkm0959/Inequality_Solving_with_CVP
• https://github.com/jvdsn/crypto-attacks
• https://github.com/kionactf/coppersmith
• https://gist.github.com/RobinJadoul/796857fa33b118c17a4e54ff1b7ccfbe
• https://doi.org/10.1007/3-540-44670-2_12
Get your hands dirty
 mapsack

ImaginaryCTF (round 25)

A multiplicative knapsack, kinda.
Author Robin_Jadoul
Flag format ictf{...}

Practical lattice reductions for CTF challenges Athens, 2024/02/23 61

 tan

ImaginaryCTF 2023
tan(x) is a broken hash function in terms of collision resistance and second
preimage resistance. But you surely can’t find the preimage of tan(flag),
right?
Author maple3142
Flag format ictf{...}

Practical lattice reductions for CTF challenges Athens, 2024/02/23 62

 flagtor

ImaginaryCTF 2023
I threw in a bit of source-given rev, because why not.
> I hate crypto and rev because both are math
Sorry to people who feel like this and even say so in the ictf discord ;)
Author Robin_Jadoul
Flag format ictf{...}

Practical lattice reductions for CTF challenges Athens, 2024/02/23 63

 Tough decisions

ECSC 2023
Champagne for my real friends, real pain for my sham friends.
Author Robin_Jadoul
Flag format ECSC{...}

Practical lattice reductions for CTF challenges Athens, 2024/02/23 64

 Unbalanced

ICC 2022
I want to keep my private key small, but I’ve heard this is dangerous. I
think I’ve found a way around this though!
Author jack
Flag format ICC{...}

Practical lattice reductions for CTF challenges Athens, 2024/02/23 65

 LeaK

pbctf 2020
I know there’s a famous attack on biased nonces. Then, how about this?
Author rbtree
Flag format pbctf{...}
Extra note (try the harder approach, just for fun)

Practical lattice reductions for CTF challenges Athens, 2024/02/23 66

 Seed Me

pbctf 2021
I came up with this fun game that only lucky people can win. Do you feel
lucky?
Author UnblvR
Flag format pbctf{...}

Practical lattice reductions for CTF challenges Athens, 2024/02/23 67

 not new PRNG

SECCON finals 2022

Recently, I learned that this random number generator is called “MRG”.
Author Xornet
Flag format SECCON{...}

Practical lattice reductions for CTF challenges Athens, 2024/02/23 68

 onelinecrypto

SEETF 2023
How to bypass this line?
assert __import__('re').fullmatch(r'SEE{\w{23}}', flag:=in-
put()) and not int.from_bytes(flag.encode(), 'big') % 13**37

Author Neobeo
Flag format SEE{...}

Practical lattice reductions for CTF challenges Athens, 2024/02/23 69

 RNG+++

TSJ CTF 2022

I encrypted the flag and messages by xoring them with a random number
generator again. But it should be harder to break this time.
Author maple3142
Flag format TSJ{...}

Practical lattice reductions for CTF challenges Athens, 2024/02/23 70

 Random Shuffling Algorithm

HITCON CTF 2023

I think you already know what is this challenge about after seeing the chal-
lenge name :)
Author maple3142
Flag format hitcon{...}

Practical lattice reductions for CTF challenges Athens, 2024/02/23 71

 Reality (remake)

<Mostly new>
Based upon the challenge reality from google ctf 2019
Author Robin_Jadoul
Flag format flag{...}

Practical lattice reductions for CTF challenges Athens, 2024/02/23 72