# X-MAS CTF 2019 - Hashed Presents v1

This week I decide to continue studying on a lattice based CTF problem.

## Problem

class secureHash(object):
    def __init__(self):
        self.bits = 128
        self.mod = 2**128
        self.mask = 2**128 - 1
        self.step = 23643483844282862943960719738L
        self.hash = 9144491976215488621715609182563L

    def update(self, inp):
        for ch in inp:
            self.hash = ((self.hash + ord(ch)) * self.step) & self.mask

    def hexdigest(self):
        x = self.hash
        out = ''
        for i in range(self.bits/8):
            out=hex(x & 0xff)[2:].replace('L','').zfill(2)+out
            x >>= 8
        return out

We need to make 10 collisions against above hash function.

## Analysis
The hash function computes
\begin{align} Hs^{n}+a_{n}s^{n}+...+a_{2}s^{2}+a_{1}s^{1} \equiv h\pmod {2^{128}} \end{align}
where $a_{n}$ is each char, $H$ is hash value, $s$ is step value.

## Vulnerability
My exploit senario is to create $x_{k}x_{k-1}x_{k-2}...x_{1}$ that
satisfy $\sum x_{i}s_{i} \equiv 0 \pmod {2^{128}}$, so that
\begin{align} Hs^{n}+(a_{n}+x_{n})s^{n}+...+(a_{2}+x_{2})s^{2}+(a_{1}+x_{1})s^{1} \equiv h\pmod {2^{128}} \end{align}

This way we can create collision with two different hash value.

In order to this, we contruct base and apply LLL to find smallest set of $x$. Once you reduced the basis, add that value of retrieved char will make same hash value.

## Exploit Code

p = 23643483844282862943960719738
mask = pow(2,128)
def collision(N):
    B = 100000
    rows = []
    for i in range(N):
        row = [1 if j==i else 0 for j in range(N)] + [B*Integer(pow(p, N+1-i, mod))]
        rows.append(row)

    Mat = Matrix(rows)
    print(type(Mat))
    reduced = Mat.LLL()[0]
    poly, vals = reduced[:N], reduced[N:]
    
    assert all(abs(x) <= 70 for x in poly)
    assert all(x == 0 for x in vals)
    print(poly)
    
for x in range(22, 35):    
    collision(x)