Fast syndrome-based hash function (FSB) | |
Designers: | Daniel Augot, Matthieu Finiasz, Nicolas Sendrier |
Publish Date: | 2003 |
Derived From: | McEliece cryptosystem and Niederreiter cryptosystem |
Derived To: | Improved fast syndrome-based hash function |
Related To: | Syndrome-based hash function |
Digest Size: | Scalable |
In cryptography, the fast syndrome-based hash functions (FSB) are a family of cryptographic hash functions introduced in 2003 by Daniel Augot, Matthieu Finiasz, and Nicolas Sendrier.Unlike most other cryptographic hash functions in use today, FSB can to a certain extent be proven to be secure. More exactly, it can be proven that breaking FSB is at least as difficult as solving a certain NP-complete problem known as regular syndrome decoding so FSB is provably secure. Though it is not known whether NP-complete problems are solvable in polynomial time, it is often assumed that they are not.
Several versions of FSB have been proposed, the latest of which was submitted to the SHA-3 cryptography competition but was rejected in the first round. Though all versions of FSB claim provable security, some preliminary versions were eventually broken. The design of the latest version of FSB has however taken this attack into account and remains secure to all currently known attacks.
As usual, provable security comes at a cost. FSB is slower than traditional hash functions and uses quite a lot of memory, which makes it impractical on memory constrained environments. Furthermore, the compression function used in FSB needs a large output size to guarantee security. This last problem has been solved in recent versions by simply compressing the output by another compression function called Whirlpool. However, though the authors argue that adding this last compression does not reduce security, it makes a formal security proof impossible.
We start with a compression function
\phi
{n,r,w}
n>w
wlog(n/w)>r
s=wlog(n/w)
r
n,r,w,s
log(n/w)
log
w ⋅ log(n/w)>r
\phi
r x n
H
n
wlog(n/w)
n | |
(F | |
2) |
n
r
For security purposes as well as to get a faster hash speed we want to use only “regular words of weight
w
w
n
n
w
w
n
[(i-1)(n/w),i(n/w))
0<i<w+1
There are exactly
(n/w)w
w
n
log((n/w)w)=wlog(n/w)=s
s
w
n
s
n
w
H
r
This version is usually called syndrome-based compression. It is very slow and in practice done in a different and faster way resulting in fast syndrome-based compression. We split
H
Hi
r x n/w
wlog(n/w)
w
n/w
n
w
n/w
s
s
w
s1,...,sw
n/w
Hi
r
r
We can now use the Merkle–Damgård construction to generalize the compression function to accept inputs of arbitrary lengths.
Situation and initialization: Hash a message
s=010011
4 x 12
H=\left(\begin{array}{llllcllllcllll} 1&0&1&1&~&0&1&0&0&~&1&0&1&1\\ 0&1&0&0&~&0&1&1&1&~&0&1&0&0\\ 0&1&1&1&~&0&1&0&0&~&1&0&1&0\\ 1&1&0&0&~&1&0&1&1&~&0&0&0&1\end{array}\right)
w=3
H1
H2
H3
Algorithm:
s
w=3
log2(12/3)=2
s1=01
s2=00
s3=11
si
s1=1
s2=0
s3=3
H1
H2
r=0111 ⊕ 0001 ⊕ 1001=1111
The Merkle–Damgård construction is proven to base its security only on the security of the used compression function. So we only need to show that the compression function
\phi
A cryptographic hash function needs to be secure in three different aspects:
Note that if an adversary can find a second pre-image, then it can certainly find a collision. This means that if we can prove our system to be collision resistant, it will certainly be second-pre-image resistant.
Usually in cryptography hard means something like “almost certainly beyond the reach of any adversary who must be prevented from breaking the system”. We will however need a more exact meaning of the word hard. We will take hard to mean “The runtime of any algorithm that finds a collision or pre-image will depend exponentially on size of the hash value”. This means that by relatively small additions to the hash size, we can quickly reach high security.
As said before, the security of FSB depends on a problem called regular syndrome decoding (RSD). Syndrome decoding is originally a problem from coding theory but its NP-completeness makes it a nice application for cryptography. Regular syndrome decoding is a special case of syndrome decoding and is defined as follows:
Definition of RSD: given
w
Hi
r x (n/w)
S
r
w
Hi
S
This problem has been proven to be NP-complete by a reduction from 3-dimensional matching. Again, though it is not known whether there exist polynomial time algorithms for solving NP-complete problems, none are known and finding one would be a huge discovery. It is easy to see that finding a pre-image of a given hash
S
We still need to prove collision resistance. For this we need another NP-complete variation of RSD: 2-regular null syndrome decoding.
Definition of 2-RNSD: Given
w
Hi
r x (n/w)
S
r
w'
Hi
(0<w'<2w)
2-RNSD has also been proven to be NP-complete by a reduction from 3-dimensional matching.
Just like RSD is in essence equivalent to finding a regular word
w
Hw=S
w'
Hw'=0
n
w
n
[(i-1)w,iw)
Suppose that we have found a collision, so we have Hash(m1) = Hash(m2) with
m1 ≠ m2
w1
w2
Hw1=Hw2
H(w1+w2)=Hw1+Hw2=2Hw1=0
(w1+w2)
The latest versions of FSB use the compression function Whirlpool to further compress the hash output. Though this cannot be proven, the authors argue that this last compression does not reduce security. Note that even if one were able to find collisions in Whirlpool, one would still need to find the collisions pre-images in the original FSB compression function to find a collision in FSB.
Solving RSD, we are in the opposite situation as when hashing. Using the same values as in the previous example, we are given
H
w=3
r=1111
r
s1=1
s2=0
s3=3
In 2-RNSD we want to find in each sub-block not one column, but two or zero such that they would sum up to 0000 (and not to
r
H1
H2
H3
H3
The provable security of FSB means that finding collisions is NP-complete. But the proof is a reduction to a problem with asymptotically hard worst-case complexity. This offers only limited security assurance as there still can be an algorithm that easily solves the problem for a subset of the problem space. For example, there exists a linearization method that can be used to produce collisions of in a matter of seconds on a desktop PC for early variants of FSB with claimed 2^128 security. It is shown that the hash function offers minimal pre-image or collision resistance when the message space is chosen in a specific way.
The following table shows the complexity of the best known attacks against FSB.
Output size (bits) | Complexity of collision search | Complexity of inversion | |
---|---|---|---|
160 | 2100.3 | 2163.6 | |
224 | 2135.3 | 2229.0 | |
256 | 2190.0 | 2261.0 | |
384 | 2215.5 | 2391.5 | |
512 | 2285.6 | 2527.4 |
FSB is a speed-up version of syndrome-based hash function (SB). In the case of SB the compression function is very similar to the encoding function of Niederreiter's version of McEliece cryptosystem. Instead of using the parity check matrix of a permuted Goppa code, SB uses a random matrix
H
H
In 2007, IFSB was published. In 2010, S-FSB was published, which is 30% faster than the original.[1]
In 2011, D. J. Bernstein and Tanja Lange published RFSB, which is 10x faster than the original FSB-256. RFSB was shown to run very fast on the Spartan 6 FPGA, reaching throughputs of around 5 Gbit/s.>