前置知识
第一原像攻击
对于哈希函数\(H(x)\),给定一个哈希值\(h\),攻击者要找到一个消息\(M\)使得:
\[
H(M)=h
\]
第二原像攻击
对于哈希函数\(H(x)\),给定一指定消息\(M\)以及其哈希值\(H(M)\),攻击者要找到另外一条消息\(M’\neq M\)使得:
\[
H(M’)=H(M)
\]
FNV系列哈希算法
FNV(Fowler-Noll-Vo)系列算法依照实现可以分为FNV-0、FNV-1以及FNV-1a三类,而每一类的FNV算法都会根据位宽\(n\)的不同选取不同的参数,对于固定位宽\(n\),三种算法细节如下:
FNV-0
对于输入消息\(B=(b_1,b_2,\ldots,b_{m})\),其中\(b_1,b_2,\ldots,b_{m}\in\{0,1,\ldots,255\}\)是组成消息\(B\)的字节,然后根据位宽选取FNV质数\(p_n\),令初始状态为\(h_0=0\),有递推式:
\[
h_{i}=p_nh_{i-1}\oplus b_{i}\mod{M}
\]
其中\(M=2^n,i=1,2,\ldots,m\),通过上式得到的\(h_m\)即为使用位宽为\(n\)的FNV-0算法计算出的消息\(B\)的哈希值.
FNV-1
对于输入消息\(B=(b_1,b_2,\ldots,b_{m})\),其中\(b_1,b_2,\ldots,b_{m}\in\{0,1,\ldots,255\}\)是组成消息\(B\)的字节,然后根据位宽选取FNV质数\(p_n\),令初始状态为\(h_0=\text{offset_basis}_n\)(其中\(\text{offset_basis}n\)为根据位宽\(n\)选取的常数),有递推式:
\[
h{i}=p_nh_{i-1}\oplus b_{i}\mod{M}
\]
其中\(M=2^n,i=1,2,\ldots,m\),通过上式得到的\(h_m\)即为使用位宽为\(n\)的FNV-1算法计算出的消息\(B\)的哈希值.
实际上,FNV-0与FNV-1的原理完全一致,只是初始状态不同
FNV-1a
对于输入消息\(B=(b_1,b_2,\ldots,b_{m})\),其中\(b_1,b_2,\ldots,b_{m}\in\{0,1,\ldots,255\}\)是组成消息\(B\)的字节,然后根据位宽选取FNV质数\(p_n\),令初始状态为\(h_0=\text{offset_basis}_n\)(其中\(\text{offset_basis}n\)为根据位宽\(n\)选取的常数),有递推式:
\[
h{i}=p_n(h_{i-1}\oplus b_{i})\mod{M}
\]
其中\(M=2^n,i=1,2,\ldots,m\),通过上式得到的\(h_m\)即为使用位宽为\(n\)的FNV-1a算法计算出的消息\(B\)的哈希值.
FNV系列算法的参数选择
针对FNV系列算法所使用的FNV质数\(p_n\),RFC 9923标准给出了\(p_n\)的选取规则:\(p_n\)是满足以下格式的最小质数:
\[
p_n=256^{\text{int}((5+n)/12)}+2^8+b
\]
其中:
- \(b\in{0,1,\ldots,2^8}\),且\(b\)的二进制表示中\(1\)的个数只有\(4\)或\(5\)个(即\(b\)的汉明重量为\(4\)或\(5\))
- \(p_n\)满足\((p_n\mod{(2^{40}-2^{24}-1)})>(2^{24}+2^8+2^7)\)
故针对上述规则我们可以得到对\(n=32,64,128,256,512,1024\)时\(p_n\)的具体取值:
| \(n\) | \(p_n\) |
|---|---|
| \(32\) | \(256^3+2^8+147\) |
| \(64\) | \(256^5+2^8+179\) |
| \(128\) | \(256^{11}+2^8+59\) |
| \(256\) | \(256^{21}+2^8+99\) |
| \(512\) | \(256^{43}+2^8+87\) |
| \(1024\) | \(256^{85}+2^8+141\) |
而对于FNV-1以及FNV-1a需要用到的\(\text{offset_basis}_n\),它是由字符串chongo <Landon Curt Noll> /\../\经位宽为\(n\)的FNV-0算法计算出来的哈希值.
实现
使用Python实现上述FNV系列算法的代码如下:
from Crypto.Util.number import *
class FNV_0:
def __init__(self, n):
self.n = n
if n not in [32, 64, 128, 256, 512, 1024]:
ValueError(f"n must be one of 32, 64, 128, 256, 512, or 1024.")
self.M = 2**n
if n == 32:
self.p = 256**3 + 2**8 + 147
elif n == 64:
self.p = 256**5 + 2**8 + 179
elif n == 128:
self.p = 256**11 + 2**8 + 59
elif n == 256:
self.p = 256**21 + 2**8 + 99
elif n == 512:
self.p = 256**43 + 2**8 + 87
elif n == 1024:
self.p = 256**85 + 2**8 + 141
assert isPrime(self.p)
def checksum(self, msg: bytes):
H = 0
M = 2**self.n - 1
for b in msg:
H = ((self.p * H) ^ b) & M
return H
class FNV_1:
def __init__(self, n):
self.n = n
if n not in [32, 64, 128, 256, 512, 1024]:
ValueError(f"n must be one of 32, 64, 128, 256, 512, or 1024.")
self.M = 2**n
if n == 32:
self.p = 256**3 + 2**8 + 147
elif n == 64:
self.p = 256**5 + 2**8 + 179
elif n == 128:
self.p = 256**11 + 2**8 + 59
elif n == 256:
self.p = 256**21 + 2**8 + 99
elif n == 512:
self.p = 256**43 + 2**8 + 87
elif n == 1024:
self.p = 256**85 + 2**8 + 141
assert isPrime(self.p)
fnv0 = FNV_0(self.n)
self.offset_basis = fnv0.checksum(b'chongo <Landon Curt Noll> /\\../\\')
def checksum(self, msg: bytes):
H = self.offset_basis
M = 2**self.n - 1
for b in msg:
H = ((self.p * H) ^ b) & M
return H
class FNV_1a:
def __init__(self, n):
self.n = n
if n not in [32, 64, 128, 256, 512, 1024]:
ValueError(f"n must be one of 32, 64, 128, 256, 512, or 1024.")
self.M = 2**n
if n == 32:
self.p = 256**3 + 2**8 + 147
elif n == 64:
self.p = 256**5 + 2**8 + 179
elif n == 128:
self.p = 256**11 + 2**8 + 59
elif n == 256:
self.p = 256**21 + 2**8 + 99
elif n == 512:
self.p = 256**43 + 2**8 + 87
elif n == 1024:
self.p = 256**85 + 2**8 + 141
assert isPrime(self.p)
fnv0 = FNV_0(self.n)
self.offset_basis = fnv0.checksum(b'chongo <Landon Curt Noll> /\\../\\')
def checksum(self, msg: bytes):
H = self.offset_basis
M = 2**self.n - 1
for b in msg:
H = (self.p * (H ^ b)) & M
return H针对FNV系列哈希算法的第一原像攻击
FNV-0
首先我们讨论最简单的FNV-0算法,对于一串长度为\(m\)的消息:
\[
B=(b_1,b_2,\ldots,b_{m})
\]
其中\(b_1,b_2,\ldots,b_{m}\in\{0,1,\ldots,255\}\),使用位宽为\(n\)的FNV-0计算消息\(B\)的哈希值有:
\[
\begin{aligned}
&h_0=0\\
&h_1=p_nh_0\oplus b_1\mod{M}\\
&h_2=p_nh_1\oplus b_2\mod{M}\\
&\cdots\\
&h_m=p_nh_{m-1}\oplus b_m\mod{M}\\
\end{aligned}
\]
其中\(M=2^n\),而在模\(M\)下,一个数异或一个8位的小数仅会修改原来的数的低8位,这可以近似地看作在原来的数的基础上加上或者减去一个至多8位的整数,也就是说对于\(i=1,2,\ldots,m\),总存在一个数\(\varepsilon_i\in[-255,255]\)使得:
\[
h_i=p_nh_{i-1}\oplus b_i\mod{M}\Leftrightarrow h_i=p_nh_{i-1}\oplus \varepsilon_i\mod{M}
\]
那么我们可以将计算消息\(B\)的哈希值的流程改写如下:
\[
\begin{aligned}
&h_0=0\\
&h_1=p_nh_0+\varepsilon_1\mod{M}\\
&h_2=p_nh_1+\varepsilon_2\mod{M}\\
&\cdots\\
&h_m=p_nh_{m-1}+\varepsilon_m\mod{M}\\
\end{aligned}
\]
其中\(\varepsilon_i\in[-255,255]\),可得:
\[
h_n=p_n^mh_{0}+p_n^{m-1}\varepsilon_{1}+p_n^{m-2}\varepsilon_{2}+\cdots+p_n\varepsilon_{m-1}+\varepsilon_m\mod{M}
\]
即:
\[
p_n^{m-1}\varepsilon_{1}+p_n^{m-2}\varepsilon_{2}+\cdots+p_n\varepsilon_{m-1}+\varepsilon_m-h_m+kM=0
\]
其中\(\varepsilon_1,\varepsilon_2,\ldots,\varepsilon_m\in[-255,255]\)未知,\(k\)为未知整数,那么可以将上式改写为:
\[
(\varepsilon_1,\varepsilon_2,\ldots,\varepsilon_{m-1},\varepsilon_m,1,k)\left(\begin{matrix}
p_n^{m-1}\\
p_n^{m-2}\\
\vdots\\
p_n\\
1\\
-h_m\\
M
\end{matrix}\right)=0
\]
那么我们可以尝试构造格基:
\[
\pmb{B}_\mathcal{L}=\left(\begin{matrix}
1&&&&&&p_n^{m-1}\\
&1&&&&&p_n^{m-2}\\
&&\ddots&&&&\vdots\\
&&&1&&&p_n\\
&&&&1&&1\\
&&&&&1&-h_m\\
&&&&&&M
\end{matrix}\right)
\]
此时必然有:
\[
(\varepsilon_1,\varepsilon_2,\ldots,\varepsilon_{m-1},\varepsilon_m,1,k)\pmb{B}_\mathcal{L}=(\varepsilon_1,\varepsilon_2,\ldots,\varepsilon_{m-1},\varepsilon_m,1,0)
\]
令目标向量\(\vec{v}=(\varepsilon_1,\varepsilon_2,\ldots,\varepsilon_{m-1},\varepsilon_m,1,0)\),有:
\[
\det{\pmb{B}_{\mathcal{L}}}=M=2^n
\]
而:
\[
||\vec{v}||=\sqrt{\varepsilon_1^2+\varepsilon_2^2+\cdots+\varepsilon_m^2+1}\le\sqrt{256^2m}=256\sqrt{m}
\]
根据高斯启发式,若我们想通过规约算法从格中规约出目标向量,则需要:
\[
||\vec{v}||\le256\sqrt{m}\le\sqrt{\frac{m+2}{2\pi e}}(\det\pmb{B}_\mathcal{L})^{1/(m+2)}
\]
很显然该格基与目标向量并不符合上式,那么我们需要对格基进行配平:
\[
\pmb{B}’_\mathcal{L}=\left(\begin{matrix}
256&&&&&&p_n^{m-1}\cdot M\\
&256&&&&&p_n^{m-2}\cdot M\\
&&\ddots&&&&\vdots\\
&&&256&&&p_n\cdot M\\
&&&&256&&1\\
&&&&&256&-h_m\cdot M\\
&&&&&&M\cdot M
\end{matrix}\right)
\]
这样就有:
\[
(\varepsilon_1,\varepsilon_2,\ldots,\varepsilon_{m-1},\varepsilon_m,1,k)\pmb{B}’_\mathcal{L}=(256\varepsilon_1,256\varepsilon_2,\ldots,256\varepsilon_{m-1},256\varepsilon_m,256,0)
\]
令目标向量\(\vec{v}=(256\varepsilon_1,256\varepsilon_2,\ldots,256\varepsilon_{m-1},256\varepsilon_m,256,0)\),此时有:
\[
\det{\pmb{B}’_{\mathcal{L}}}=256^{m+1}M^2
\]
而:
\[
||\vec{v}||=256\sqrt{\varepsilon_1^2+\varepsilon_2^2+\cdots+\varepsilon_m^2+1}\le256^2\sqrt{m}
\]
当\(m\)(即想要得到的消息长度)足够大的时候,对于FNV系列算法最小的模数\(M=2^{32}\),都有:
\[
||\vec{v}||\le\sqrt{\frac{m+2}{2\pi e}}(\det\pmb{B}_\mathcal{L}’)^{1/(m+2)}
\]
此时我们就可以通过规约算法求解出目标向量:
\[
\vec{v}=(256\varepsilon_1,256\varepsilon_2,\ldots,256\varepsilon_{m-1},256\varepsilon_m,256,0)
\]
由此我们可以从中提取出\(\varepsilon_1,\varepsilon_2,\ldots,\varepsilon_m\),那么我们就可以根据这\(m\)个数倒推回消息\(B=(b_1,b_2,\ldots,b_{m})\),已知对于\(i=1,2,\ldots,m\),有:
\[
h_i=p_nh_{i-1}\oplus b_i\mod{M}=p_nh_{i-1}+\varepsilon_i\mod{M}\
\]
那么我们可以得到:
\[
p_nh_{i-1}=h_i-\varepsilon_i\mod{M}
\]
由此有:
\[
\begin{cases}
h_{i-1}\equiv p_n^{-1}(h_i-\varepsilon_i)\pmod{M}\\
b_i=h_{i}\oplus p_nh_{i-1}
\end{cases}
\]
根据上述关系我们就可以倒推出消息\(B\),从而达成针对FNV-0算法的第一原像攻击,举个例子,已知一条长度未知的消息使用位长为128位的FNV-0算法计算得到的哈希值为:
978a496d524f0ee5b806e89cf4c1ab48我们可以通过上述方法计算出一条长为64字节的消息使得其通过位长为128位的FNV-0算法计算得到的哈希值为上述值,求解代码如下:
from FNV import *
from sage.all import *
from Crypto.Util.number import *
from os import urandom
fnv0 = FNV_0(128)
p = 256**11 + 2**8 + 59
M = 2**128
H = 0x978a496d524f0ee5b806e89cf4c1ab48 # Target hash value
m = 64
L = matrix(ZZ, m+2, m+2)
for i in range(m):
L[i, i] = 256
L[i, -1] = p**(m - i - 1) * M
L[-2, -2] = 256
L[-2, -1] = -H * M
L[-1, -1] = M * M
res = L.BKZ()
for l in res:
if l[-1] == 0 and l[-2] == 256:
tmpH = H
out = []
for eps in l[:-2][::-1]:
ph = tmpH - eps // 256
b = tmpH ^ ph
tmpH = inverse(p, M) * ph % M
out.append(b)
if all(x >= 0 and x < 256 for x in out):
msg1 = bytes(out[::-1])
H1 = fnv0.checksum(msg1)
if H == H1:
print(msg1.hex())可以得到其中一条128位FNV-0哈希值为978a496d524f0ee5b806e89cf4c1ab48的消息为:
0107010e001e06013d1f010701000301031e001f0105000002031f0300020007010100030300061e0201010f02ff070001020001010001020100001e02020d00经测试,选取的\(m\)越大,该攻击成功率越高.
FNV-1
针对FNV-1算法的第一原像攻击也可以用针对FNV-0算法的思路进行分析,对于一串长度为\(m\)的消息:
\[
B=(b_1,b_2,\ldots,b_{m})
\]
其中\(b_1,b_2,\ldots,b_{m}\in\{0,1,\ldots,255\}\),使用位宽为\(n\)的FNV-0计算消息\(B\)的哈希值有:
\[
\begin{aligned}
&h_0=\text{offset_basis}_n\\
&h_1=p_nh_0\oplus b_1\mod{M}\\
&h_2=p_nh_1\oplus b_2\mod{M}\\
&\cdots\\
&h_m=p_nh_{m-1}\oplus b_m\mod{M}\\
\end{aligned}
\]
其中\(M=2^n\),而在模\(M\)下,一个数异或一个8位的小数仅会修改原来的数的低8位,这可以近似地看作在原来的数的基础上加上或者减去一个至多8位的整数,也就是说对于\(i=1,2,\ldots,m\),总存在一个数\(\varepsilon_i\in[-255,255]\)使得:
\[
h_i=p_nh_{i-1}\oplus b_i\mod{M}\Leftrightarrow h_i=p_nh_{i-1}\oplus \varepsilon_i\mod{M}
\]
那么我们可以将计算消息\(B\)的哈希值的流程改写如下:
\[
\begin{aligned}
&h_0=\text{offset_basis}_n\\
&h_1=p_nh_0+\varepsilon_1\mod{M}\\
&h_2=p_nh_1+\varepsilon_2\mod{M}\\
&\cdots\\
&h_m=p_nh_{m-1}+\varepsilon_m\mod{M}\\
\end{aligned}
\]
其中\(\varepsilon_i\in[-255,255]\),可得:
\[
h_n=p_n^mh_{0}+p_n^{m-1}\varepsilon_{1}+p_n^{m-2}\varepsilon_{2}+\cdots+p_n\varepsilon_{m-1}+\varepsilon_m\mod{M}
\]
即:
\[
p_n^m\cdot\text{offset_basis}_n+p_n^{m-1}\varepsilon_{1}+p_n^{m-2}\varepsilon_{2}+\cdots+p_n\varepsilon_{m-1}+\varepsilon_m-h_m+kM=0
\]
其中\(\varepsilon_1,\varepsilon_2,\ldots,\varepsilon_m\in[-255,255]\)未知,\(k\)为未知整数,那么此时我们可以用类似于针对FNV-0进行攻击的方法构造格:
\[
\pmb{B}_\mathcal{L}=\left(\begin{matrix}
256&&&&&&p_n^{m-1}\cdot M\\
&256&&&&&p_n^{m-2}\cdot M\\
&&\ddots&&&&\vdots\\
&&&256&&&p_n\cdot M\\
&&&&256&&1\\
&&&&&256&(p_n^m\cdot\text{offset_basis}n-h_m)\cdot M\\
&&&&&&M\cdot M
\end{matrix}\right)
\]
这样就有:
\[
(\varepsilon_1,\varepsilon_2,\ldots,\varepsilon{m-1},\varepsilon_m,1,k)\pmb{B}_\mathcal{L}=(256\varepsilon_1,256\varepsilon_2,\ldots,256\varepsilon_{m-1},256\varepsilon_m,256,0)
\]
我们同样可以通过规约算法求解出目标向量\((256\varepsilon_1,256\varepsilon_2,\ldots,256\varepsilon_{m-1},256\varepsilon_m,256,0)\),从而用相同的方法倒推出目标消息,以达成针对FNV-1算法的第一原像攻击,举个例子,同样已知一条长度未知的消息使用位长为128位的FNV-1算法计算得到的哈希值为:
978a496d524f0ee5b806e89cf4c1ab48我们可以通过上述方法计算出一条长为30字节的消息使得其通过位长为128位的FNV-1算法计算得到的哈希值为上述值,求解代码如下:
from FNV import *
from sage.all import *
from Crypto.Util.number import *
fnv1 = FNV_1(128)
fnv0 = FNV_0(128)
p = 256**11 + 2**8 + 59
M = 2**128
H = 0x978a496d524f0ee5b806e89cf4c1ab48 # Target hash value
offset_basis = fnv0.checksum(b'chongo <Landon Curt Noll> /\\../\\')
m = 30
L = matrix(ZZ, m+2, m+2)
for i in range(m):
L[i, i] = 256
L[i, -1] = p**(m - i - 1) * M
L[-2, -2] = 256
L[-2, -1] = (p**m * offset_basis - H) * M
L[-1, -1] = M * M
res = L.BKZ()
for l in res:
if l[-1] == 0 and l[-2] == 256:
tmpH = H
out = []
for eps in l[:-2][::-1]:
ph = tmpH - eps // 256
b = tmpH ^ ph
tmpH = inverse(p, M) * ph % M
out.append(b)
if all(x >= 0 and x < 256 for x in out):
msg1 = bytes(out[::-1])
H1 = fnv1.checksum(msg1)
if H == H1:
print(msg1.hex())可以得到其中一条128位FNV-1哈希值为978a496d524f0ee5b806e89cf4c1ab48的消息为:
f51e1f0305060102010c3204060316010d0f0708031e0b00083f1538fd0d同样的,选取的\(m\)越大,该攻击成功率越高.
FNV-1a
对于一串长度为\(m\)的消息:
\[
B=(b_1,b_2,\ldots,b_{m})
\]
其中\(b_1,b_2,\ldots,b_{m}\in\{0,1,\ldots,255\}\),使用位宽为\(n\)的FNV-1a计算消息\(B\)的哈希值有:
\[
\begin{aligned}
&h_0=\text{offset_basis}_n\\
&h_1=p_n(h_0\oplus b_1)\mod{M}\\
&h_2=p_n(h_1\oplus b_2)\mod{M}\\
&\cdots\\
&h_m=p_n(h_{m-1}\oplus b_m)\mod{M}\\
\end{aligned}
\]
其中\(M=2^n\),因为\(p_n\)是质数,那么我们可以知道\(p_n\)在模\(M\)下的逆元一定存在,所以我们可以将上述递推改写为:
\[
\begin{aligned}
&h_0=\text{offset_basis}_n\\
&h_0=p_n^{-1}h_1\oplus b_1\mod{M}\\
&h_1=p_n^{-1}h_2\oplus b_2\mod{M}\\
&\cdots\\
&h_{m-1}=p_n^{-1}h_m\oplus b_m\mod{M}\\
\end{aligned}
\]
如果我们将\(h_0\)看作哈希结果,\(h_m\)看作初始值,我们其实可以将上式看作参数选择和计算顺序略有不同的FNV-1算法,记\(q_n=p_n^{-1}\mod{M}\),有:
\[
\begin{aligned}
&h_m=h_m\\
&h_{m-1}=q_nh_m\oplus b_m\mod{M}\\
&h_{m-2}=q_nh_{m-1}\oplus b_{m-1}\mod{M}\\
&\cdots\\
&h_1=q_nh_2\oplus b_2\mod{M}\\
&h_0=q_nh_1\oplus b_1\mod{M}=\text{offset_basis}_n\\
\end{aligned}
\]
上式同样可以等价于:
\[
\begin{aligned}
&h_m=h_m\\
&h_{m-1}=q_nh_m+\varepsilon_{m}\mod{M}\\
&h_{m-2}=q_nh_{m-1}+\varepsilon_{m-1}\mod{M}\\
&\cdots\\
&h_1=q_nh_2+\varepsilon_2\mod{M}\\
&h_0=q_nh_1+\varepsilon_1\mod{M}=\text{offset_basis}_n\\
\end{aligned}
\]
其中\(\varepsilon_1,\varepsilon_2,\ldots,\varepsilon_m\in[-255,255]\),可以得到:
\[
h_0=q_{n}^mh_m+q_{n}^{m-1}\varepsilon_{m}+q_{n}^{m-2}\varepsilon_{m-1}+\cdots+q_{n}\varepsilon_2+\varepsilon_1\mod{M}
\]
即:
\[
q_{n}^mh_m+q_{n}^{m-1}\varepsilon_{m}+q_{n}^{m-2}\varepsilon_{m-1}+\cdots+q_{n}\varepsilon_2+\varepsilon_1-\text{offset_basis}_n+kM=0
\]
其中\(\varepsilon_1,\varepsilon_2,\ldots,\varepsilon_m\in[-255,255]\)未知,\(k\)为未知整数,那么此时我们可以用类似于针对FNV-0进行攻击的方法构造格:
\[
\pmb{B}_\mathcal{L}=\left(\begin{matrix}
256&&&&&&q_n^{m-1}\cdot M\\
&256&&&&&q_n^{m-2}\cdot M\\
&&\ddots&&&&\vdots\\
&&&256&&&q_n\cdot M\\
&&&&256&&1\\
&&&&&256&(q_n^mh_m-\text{offset_basis}_n)\cdot M\\
&&&&&&M\cdot M
\end{matrix}\right)
\]
这样就有:
\[
(\varepsilon_m,\varepsilon_{m-1},\ldots,\varepsilon_{2},\varepsilon_1,1,k)\pmb{B}_\mathcal{L}=(256\varepsilon_m,256\varepsilon_{m-1},\ldots,256\varepsilon_{2},256\varepsilon_1,256,0)
\]
我们可以通过规约算法求解出目标向量\((256\varepsilon_m,256\varepsilon_{m-1},\ldots,256\varepsilon_{2},256\varepsilon_1,256,0)\),从而可以通过类似于针对FNV-1的攻击的方式倒推出消息\(B\),以达成针对FNV-1a算法的第一原像攻击,举个例子,已知一条长度未知的消息使用位长为128位的FNV-1a算法计算得到的哈希值为:
2e73628c09188b7e262ccb8b670772f2我们可以通过上述方法计算出一条长为30字节的消息使得其通过位长为128位的FNV-1算法计算得到的哈希值为上述值,求解代码如下:
from FNV import *
from sage.all import *
from Crypto.Util.number import *
fnv1a = FNV_1a(128)
fnv0 = FNV_0(128)
p = 256**11 + 2**8 + 59
M = 2**128
q = inverse(p, M)
H = 0x2e73628c09188b7e262ccb8b670772f2 # Target hash value
offset_basis = fnv0.checksum(b'chongo <Landon Curt Noll> /\\../\\')
m = 30
L = matrix(ZZ, m+2, m+2)
for i in range(m):
L[i, i] = 256
L[i, -1] = q**(m - i - 1) * M
L[-2, -2] = 256
L[-2, -1] = (q**m * H - offset_basis) * M
L[-1, -1] = M * M
res = L.BKZ()
for l in res:
if l[-1] == 0 and l[-2] == 256:
tmpH = offset_basis
out = []
for eps in l[:-2][::-1]:
qh = tmpH - eps // 256
b = tmpH ^ qh
tmpH = inverse(q, M) * qh % M
out.append(b)
if all(x >= 0 and x < 256 for x in out):
msg1 = bytes(out)
H1 = fnv1a.checksum(msg1)
if H == H1:
print(msg1.hex())可以得到其中一条128位FNV-1a哈希值为2e73628c09188b7e262ccb8b670772f2的消息为:
0703033401061e0103fe0009011b060a04010a0413000f06021f14050104同样的,选取的\(m\)越大,该攻击成功率越高.