# Fowler–Noll–Vo hash function¶

## 2018 网鼎杯 hashcoll¶

h0 = 45740974929179720441799381904411404011270459520712533273451053262137196814399

# 2**168 + 355
g = 374144419156711147060143317175368453031918731002211L

def shitty_hash(msg):
h = h0
msg = map(ord, msg)
for i in msg:
h = (h + i) * g
# This line is just to screw you up :))
h = h & 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff

return h - 0xe6168647f636


$hash(m)=h_0g^n+x_1g^n+x_2g_{n-1}+...+x_ng \bmod 2^{256}$

$h_0g^n+x_1g^n+x_2g_{n-1}+...+x_ng \equiv h_0g^n+y_1g^n+y_2g_{n-1}+...+y_ng\bmod 2^{256}$

$(x_1-y_1)g^{n-1}+(x_2-y_2)g^{n-2}+...+(x_n-y_n)g^0 \equiv 0 \bmod 2^{256}$

$z_1g^{n-1}+z_2g^{n-2}+...+z_ng^0-k*2^{256}=0$

A = \left[ \begin{matrix} 1 & 0 & 0 & \cdots & 0 & Kg^{n-1} \\ 0 & 1 & 0 & \cdots & 0 & Kg^{n-2} \\ 0 & 0 & 1 & \cdots & 0 & Kg^{n-3} \\\vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 &0 & \cdots & 1 & K*mod \\ \end{matrix} \right]

from sage.all import *

mod = 2**256
h0 = 45740974929179720441799381904411404011270459520712533273451053262137196814399

g = 2**168 + 355

def shitty_hash(msg):
h = h0
msg = map(ord, msg)
for i in msg:
h = (h + i) * g
# This line is just to screw you up :))
h = h & 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff

return h - 0xe6168647f636

K = 2**200
N = 50
base_str = 'a' * N
base = map(ord, base_str)
m = Matrix(ZZ, N + 1, N + 2)
for i in xrange(N + 1):
ge = ZZ(pow(g, N - i, mod))
m[i, i] = 1
m[i, N + 1] = ZZ(ge * K)
m[i, N + 1] = ZZ(K * mod)

ml = m.LLL()
ttt = ml.rows()[0]
print "result:", ttt
if ttt[-1] != 0:
print "Zero not reached, increase K"
exit()
else:
msg = []
for i in xrange(N):
msg.append(base[i] + ttt[i])
if not (0 <= msg[i] <= 255):
print "Need more bytes!"
quit()
print msg
other = ''.join(map(chr, msg))

print shitty_hash(base_str)
print shitty_hash(other)


➜  hashcoll sage exp.sage
result: (15, -14, 17, 14, 6, 0, 12, 21, 8, 29, 6, -4, -9, 10, -2, -12, -6, 0, -12, 13, -28, -28, -24, -3, 6, -5, -16, 15, 17, -14, 3, -2, -16, -25, 3, -21, -27, -9, 16, 5, -1, 0, -3, -4, -4, -19, 6, 8, 0, 0, 0, 0)
[112, 83, 114, 111, 103, 97, 109, 118, 105, 126, 103, 93, 88, 107, 95, 85, 91, 97, 85, 110, 69, 69, 73, 94, 103, 92, 81, 112, 114, 83, 100, 95, 81, 72, 100, 76, 70, 88, 113, 102, 96, 97, 94, 93, 93, 78, 103, 105, 97, 97]
106025341237231370726407656306665079105509255639964756437758376184556498283725
106025341237231370726407656306665079105509255639964756437758376184556498283725