针对FNV系列哈希算法的第一原像攻击

前置知识

第一原像攻击

对于哈希函数\(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\)越大,该攻击成功率越高.

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇