# Fowler–Noll–Vo hash function

具体请参见 <https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo\\_hash\\_function。>

## 2018 网鼎杯 hashcoll

其实这道题是从 NSU Crypto 抄过来的，<https://nsucrypto.nsu.ru/archive/2017/problems\\_solution，具体的> wp 之前 hellman 也写了，<https://gist.github.com/hellman/9bf8376cd04e7a8dd2ec7be1947261e9。>

简单看一下题目

```python
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}$

假设两个消息的 hash 值相同那么

$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}$

即我们只需要找到一个 n 维向量 $z\_i=x\_i-y\_i$，满足上述等式即可，我们可以进一步将其化为

$z\_1g^{n-1}+z\_2g^{n-2}+...+z\_ng^0-k\*2^{256}=0$

即找到一组向量满足上述这个式子。这可以认为是 LLL Paper 中第二个例子的简单情况（参见格问题部分）。

那么我们可以快速构造矩阵，如下

$$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]$$

之后我们使用LLL 算法即可获得两个一样的哈希值

```python
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)
```

注意不能直接仅仅使用 pow(g, N - i, mod)，不然生成的数会在 mod 对应的域中，这真是个大坑。

如下

```shell
➜  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
```

即成功。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://ctfwiki.stinger.team/crypto/hash/fnv.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.