Hat Trick - Alpacahack Round 3
Table of Contents
Challenge overview
Here’s a brief overview of the challenge code:
class RollingHash:
def __init__(self, p=None, base=None) -> None:
self.p = getPrime(64) if p is None else p
self.base = (getRandomInteger(64) if base is None else base) % self.p
def hash(self, s: str):
res = 0
for i, c in enumerate(s):
res += ord(c) * (self.base ** i)
res %= self.p
return res
def check_str(s: str, max_len: int):
assert len(s) <= max_len, "too long!"
for i, c in enumerate(s):
assert c in string.ascii_lowercase, f"found invalid char {c} at {i}"
MAX_LEN = 54
rhs = [RollingHash() for _ in range(3)]
print("params:",json.dumps([{ "base": rh.base, "p": rh.p } for rh in rhs]))
for _ in range(3):
target_hash = [random.randrange(0, rh.p) for rh in rhs]
print('target:', target_hash)
s = input("> ")
check_str(s, MAX_LEN)
actual_hash = [rh.hash(s) for rh in rhs]
if target_hash != actual_hash:
print("Oops! You missed the target hash. Better luck next time!")
exit(1)
print("Congratulations! Here is your flag:", flag)
So, we have 3 rounds to pass, in each one the server gives 3 different base and p values.
Basically, we need to find a string $s$ of length $\leq 54$ that solves this system of equations:
Where each element of $s_i$ is a lowercase letter, meaning $s_i \in [97, 122]$, where 97 represents a and 122 represents z in the ASCII table.
One equation only
Let’s create the solution step by step.
Assume we only need to solve one equation, without any constraint on $s_i$.
Then we have a single equation $\pmod{p}$:
$$ s_0 + s_1 \cdot \text{base} + s_2 \cdot \text{base}^2 + s_3 \cdot \text{base}^3 + \text{...} + s_{53} \cdot \text{base}^{53} \equiv \text{target} \pmod{p}$$Then we can just select every $s_{i>0}$ randomly and then choose $s_0$ ad-hoc to solve the equation:
$$ s_0 + \text{some\_random\_stuff} \equiv \text{target} \pmod{p}$$(I’m pretty sure that if you are reading this writeup you are able to solve this by yourself 🫠)
At this point, we are either extremely lucky or, realistically, we have perfectly chosen $s_{i>0}$ with a very bad $s_0$.
Finding small solution
- Let’s try to find solutions that are $ \in [-10,10]$.
- For simplicity, assume $\text{target} = 0$.
- Also, to avoid handling the modulus, we can just add another variable $k$.
With those assumptions, this is the equation that we are trying to solve:
$$ \begin{pmatrix} s_0 & s_1 & \text{...} & s_{53} & k \end{pmatrix} \cdot \begin{pmatrix} \text{base}^0 \\ \text{base}^1 \\ \text{...} \\ \text{base}^{53} \\ -p \end{pmatrix} $$Where this is a linear combination of $\text{base}^i$ with integer coefficients ($s_i$). This is exactly a lattice! And $\text{LLL}$ finds a small vector in the lattice!
So, to find a solution, we can just run the $\text{LLL}$ algorithm on the column-matrix $\text{base}^i$.
sage: base = 100
sage: p = 101
sage: eqs = Matrix([base^i % p for i in range(5)]).T
sage: M = eqs.stack(vector([p]))
sage: M
[ 1]
[14]
[95]
[17]
[36]
[101]
sage: M.LLL()
[0]
[0]
[0]
[0]
[0]
[1]
We see that there is a non-trivial integral linear combination of these vectors that gets to 0. But we also want to extract the coefficients for it!
To do this, we can construct the lattice:
that is
$$ \begin{pmatrix} 1 & 1 & 0 & 0 & 0 & 0 \\ 14 & 0 & 1 & 0 & 0 & 0 \\ 95 & 0 & 0 & 1 & 0 & 0 \\ 17 & 0 & 0 & 0 & 1 & 0 \\ 36 & 0 & 0 & 0 & 0 & 1 \\ 101 & 0 & 0 & 0 & 0 & 0 \\ \end{pmatrix} $$sage: M = block_matrix([
....: [eqs,1],
....: [p,0]])
sage: M
[ 1| 1 0 0 0 0]
[ 14| 0 1 0 0 0]
[ 95| 0 0 1 0 0]
[ 17| 0 0 0 1 0]
[ 36| 0 0 0 0 1]
[---+-------------------]
[101| 0 0 0 0 0]
sage: M.LLL()
[ 1 1 0 0 0 0]
[ 1 0 1 -1 1 -1]
[ 2 -1 -1 0 1 0]
[ 1 -1 0 0 -2 1]
[-1 1 -1 -2 0 0]
[ 1 -1 1 0 1 2]
For each row now we have:
- row[0] is the result of the equation
- row[1:] are the coefficients
In this case, we haven’t found a solution, but we could combine the first and the second row to get the solution vector:
$$ \begin{pmatrix} 0 & 1 & -1 & 1 & -1 & 1 \end{pmatrix} $$Why didn’t $\text{LLL}$ directly give us a solution? Because it searches for the shortest vector in the lattice, and right now we’ve added the identity matrix on the right, which has non-null entries!
We can add a big weight $W$ on the ’equation column’ (the first one) so that $\text{LLL}$ will try to minimize it before the others (as in the first one we will have 10-digit numbers while in the other columns we will have only 1s).
sage: M.rescale_col(0,W)
sage: M
[ 1000| 1 0 0 0 0]
[ 14000| 0 1 0 0 0]
[ 95000| 0 0 1 0 0]
[ 17000| 0 0 0 1 0]
[ 36000| 0 0 0 0 1]
[------+----------------------------------]
[101000| 0 0 0 0 0]
sage: M.LLL()
[ 0 -1 1 -1 1 -1]
[ 0 -2 0 0 -2 1]
[ 0 0 -2 1 2 0]
[ 0 -1 0 -1 -2 -2]
[ 0 2 -1 -2 0 0]
[1000 1 0 0 0 0]
This is what we like to see. We can take the first 4 rows of $\text{M.LLL()}$, and any linear combination of them will result in a 0.
sage: vector(M.LLL()[0][1:]) * vector([base^i % p for i in range(5)])
-101
sage: vector(M.LLL()[0][1:]) * vector([base^i % p for i in range(5)]) % p
0
Solving for target
We can’t just directly integrate the target into our equations matrix naively:
sage: target = 28 # random
sage: eqs = eqs.stack(vector([-target]))
[ 1]
[14]
[95]
[17]
[36]
[-28]
sage: M = block_matrix([
....: [eqs,1],
....: [p,0]])
sage: M
[ 1| 1 0 0 0 0 0]
[ 14| 0 1 0 0 0 0]
[ 95| 0 0 1 0 0 0]
[ 17| 0 0 0 1 0 0]
[ 36| 0 0 0 0 1 0]
[-28| 0 0 0 0 0 1]
[---+-----------------------]
[101| 0 0 0 0 0 0]
sage: M.rescale_col(0,W)
sage: M.LLL()
[ 0 0 -1 -1 0 1 1]
[ 0 -1 1 -1 1 -1 0]
[ 0 0 -2 0 0 0 -1]
[ 0 0 -1 1 -1 -1 1]
[ 0 0 0 1 2 0 1]
[ 0 -2 0 1 0 1 1]
[1000 1 0 0 0 0 0]
As in this case, $\text{LLL}$ could use the target $n$-times without any problem. In this small example, we got lucky and found a solution that has a coefficient for the target of $1$ (in the last column), but this isn’t always the case.
Again, we can put a weight on the coefficient of the target to tell $\text{LLL}$ to use that as little as possible.
sage: M.rescale_col(6,W)
sage: M
[ 1000| 1 0 0 0 0 0]
[ 14000| 0 1 0 0 0 0]
[ 95000| 0 0 1 0 0 0]
[ 17000| 0 0 0 1 0 0]
[ 36000| 0 0 0 0 1 0]
[-28000| 0 0 0 0 0 1000]
[------+-----------------------------------------]
[101000| 0 0 0 0 0 0]
sage: M.LLL()
[ 0 -1 1 -1 1 -1 0]
[ 0 -2 0 0 -2 1 0]
[ 0 0 -2 1 2 0 0]
[ 0 -1 0 -1 -2 -2 0]
[ 0 2 -1 -2 0 0 0]
[1000 1 0 0 0 0 0]
[ 0 0 0 1 2 0 1000]
Dividing by the weight, now we get
[ 0 -1 1 -1 1 -1 0]
[ 0 -2 0 0 -2 1 0]
[ 0 0 -2 1 2 0 0]
[ 0 -1 0 -1 -2 -2 0]
[ 0 2 -1 -2 0 0 0]
[ 1 1 0 0 0 0 0]
[ 0 0 0 1 2 0 1]
Where $M[-1]$ uses the target only once (and is a valid solution), $M[-2]$ can be discarded (as it doesn’t solve the equation), and so we have all the possible solutions defined by:
$$ M[-1] + a_0 \cdot M[0] + a_1 \cdot M[1]+ a_2 \cdot M[2]+ a_3 \cdot M[3]+ a_4 \cdot M[4] $$Closest Vector Problem
At this point, we are basically done. Now, instead of having a short vector, we want a vector that is as close as possible to:
$$ \begin{pmatrix} 0 & 110 & 110 & 110 & 110 & 110 & 1 \end{pmatrix} $$Where the first 0 is the result of the equation, the 110 is the average value of ASCII lowercase letters, and the last 1 is the coefficient of the target.
Sage CVP
To do this, we could take some implementation of CVP online (like Babai) or use Sage’s implementation.
sage: L = IntegerLattice(M, lll_reduce=False)
sage: L
Free module of degree 7 and rank 7 over Integer Ring
User basis matrix:
[ 0 -1 1 -1 1 -1 0]
[ 0 -2 0 0 -2 1 0]
[ 0 0 -2 1 2 0 0]
[ 0 -1 0 -1 -2 -2 0]
[ 0 2 -1 -2 0 0 0]
[ 1 1 0 0 0 0 0]
[ 0 0 0 1 2 0 1]
sage: target_v = vector([0,110,110,110,110,110,1])
sage: L.approximate_closest_vector(target_v)
(0, 110, 109, 109, 109, 110, 1)
(now the closest vector is a solution to the equation bounded as ASCII lowercase letters)
Three equations
By now, you should have an intuition on how to solve the complete case.
Our eqs matrix will have 3 columns instead of 1, with 3 different moduli variables.
The problem is now:
$$ \begin{pmatrix} s_0 & s_1 & \text{...} & s_{53} & t_0 & t_1 & t_2 & k_0 & k_1 & k_2 \end{pmatrix} \cdot \begin{pmatrix} \text{base}_0^0 & \text{base}_1^0 & \text{base}_2^0 \\ \text{base}_0^1 & \text{base}_1^1 & \text{base}_2^1 \\ \text{...} & \text{...} & \text{...} \\ \text{base}_0^{53} & \text{base}_1^{53} & \text{base}_2^{53} \\ -target_0 & 0 & 0 \\ 0 & -target_1 & 0 \\ 0 & 0 & -target_2 \\ p_0 & 0 & 0 \\ 0 & p_1 & 0 \\ 0 & 0 & p_2 \end{pmatrix} $$Where $s_i$ must be as close as possible to $110$, $t_i$ must be $1$, and $k_i$ can be an arbitrary integer.
LLL
Like above, assuming eqs is the 3-column matrix on the right, we can reduce this lattice:
We discard the last 3 columns (as they are the coefficients of the moduli) and from here, apply CVP to:
$$ \begin{pmatrix} 0 & 0 & 0 & \underbrace{110 \quad 110 \quad \dots \quad 110}_{\text{54 times}} \end{pmatrix} $$Complete code
import colored_traceback
colored_traceback.add_hook = lambda: None
import string
from pwn import remote, process
import json
# r = remote('34.170.146.252',47001)
r = process(['python3', 'server.py'])
r.recvuntil(b'params: ')
params = json.loads(r.recvline())
def solve_equations(params, target):
for LEN in range(48,55):
print(LEN)
P = PolynomialRing(ZZ, ','.join([f'x{i}' for i in range(LEN)]))
xs = P.gens()
eqs = []
for param,tt in zip(params,target):
base = param['base']
p = param['p']
eq = sum([x * (pow(base,i,p)) for i, x in enumerate(xs)]) - tt
eqs.append(eq)
M,mons = Sequence(eqs).coefficient_matrix(sparse=False)
M = block_matrix([
[M.T, 1],
])
# add below p0,0; p1,0; p2,0
M = M.stack(vector([params[0]['p']] + [0] * (LEN + 3)))
M = M.stack(vector([0]*1 + [params[1]['p']] + [0] * (LEN + 2)))
M = M.stack(vector([0]*2 + [params[2]['p']] + [0] * (LEN + 1)))
ww = [1] * 3+ [128] * LEN + [1]
ws = diagonal_matrix([max(ww) // w for w in ww])
M = M * ws
M = M.LLL()
M = M / ws
M = M.change_ring(ZZ)
# now solve CVP to vector [0,0,0,1] + [61]*LEN
target_v = vector([0,0,0] + [109]*LEN + [1])
def Babai_closest_vector(M, target):
# Babai's Nearest Plane algorithm
G = M.gram_schmidt()[0]
small = target
for _ in range(1):
for i in reversed(range(M.nrows())):
c = ((small * G[i]) / (G[i] * G[i])).round()
small -= M[i] * c
return target - small
closestvector = Babai_closest_vector(M, target_v)
print(closestvector)
# this should solve all equations
for i,eq in enumerate(eqs):
print(eq(*closestvector[3:-1]) % params[i]['p'])
if all([0<x<128 for x in closestvector[3:-1]]):
s = ''.join([chr(int(x)) for x in closestvector[3:-1]])
else:
s = 'failed\x01'
print(s,LEN)
# if all ascii lowercase
if all([c in string.ascii_lowercase for c in s]):
return s
for _ in range(3):
r.recvuntil(b'target: ')
target = json.loads(r.recvline())
s = solve_equations(params, target)
r.sendline(s)
r.interactive()
# Alpaca{i_st1ll_h4v3_n0_id3a_why_r0ll1ng_h4sh_is_c4ll3d_th4t}