Fast syndrome-based hash

• A message is called a word of weight ${\displaystyle w}$ and length ${\displaystyle n}$ if it consists of ${\displaystyle n}$ bits and exactly ${\displaystyle w}$ of those bits are ones.
• A word of weight ${\displaystyle w}$ and length ${\displaystyle n}$ is called regular if in every interval ${\displaystyle [(i-1)(n/w),i(n/w))}$ it contains exactly one nonzero entry for all ${\displaystyle 0<i<w+1}$. More intuitively, this means that if we chop up the message in w equal parts, then each part contains exactly one nonzero entry.

There are exactly ${\displaystyle (n/w)^{w}}$ different regular words of weight ${\displaystyle w}$ and length ${\displaystyle n}$, so we need exactly ${\displaystyle \log((n/w)^{w})=w\log(n/w)=s}$ bits of data to encode these regular words. We fix a bijection from the set of bit strings of length ${\displaystyle s}$ to the set of regular words of weight ${\displaystyle w}$ and length ${\displaystyle n}$ and then the FSB compression function is defined as follows :

1. input: a message of size ${\displaystyle s}$
2. convert to regular word of length ${\displaystyle n}$ and weight ${\displaystyle w}$
3. multiply by the matrix ${\displaystyle H}$
4. output: hash of size ${\displaystyle 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 ${\displaystyle H}$ into sub-matrices ${\displaystyle H_{i}}$ of size ${\displaystyle r\times n/w}$ and we fix a bijection from the bit strings of length ${\displaystyle w\log(n/w)}$ to the set of sequences of ${\displaystyle w}$ numbers between 1 and ${\displaystyle n/w}$. This is equivalent to a bijection to the set of regular words of length ${\displaystyle n}$ and weight ${\displaystyle w}$, since we can see such a word as a sequence of numbers between 1 and ${\displaystyle n/w}$. The compression function looks as follows:

1. Input: message of size ${\displaystyle s}$
2. Convert ${\displaystyle s}$ to a sequence of ${\displaystyle w}$ numbers ${\displaystyle s_{1},\dots ,s_{w}}$ between 1 and ${\displaystyle n/w}$
3. Add the corresponding columns of the matrices ${\displaystyle H_{i}}$ to obtain a binary string a length ${\displaystyle r}$
4. Output: hash of size ${\displaystyle 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 ${\displaystyle s=010011}$ using ${\displaystyle 4\times 12}$ matrix H
${\displaystyle 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)}$
that is separated into ${\displaystyle w=3}$ sub-blocks ${\displaystyle H_{1}}$, ${\displaystyle H_{2}}$, ${\displaystyle H_{3}}$.

Algorithm:

1. We split the input ${\displaystyle s}$ into ${\displaystyle w=3}$ parts of length ${\displaystyle \log _{2}(12/3)=2}$ and we get ${\displaystyle s_{1}=01}$, ${\displaystyle s_{2}=00}$, ${\displaystyle s_{3}=11}$.
2. We convert each ${\displaystyle s_{i}}$ into an integer and get ${\displaystyle s_{1}=1}$, ${\displaystyle s_{2}=0}$, ${\displaystyle s_{3}=3}$.
3. From the first sub-matrix ${\displaystyle H_{1}}$, we pick the column 2, from the second sub-matrix ${\displaystyle H_{2}}$ the column 1 and from the third sub-matrix the column 4.
4. We add the chosen columns and obtain the result ${\displaystyle r=0111\oplus 0001\oplus 1001=1111}$.

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 ${\displaystyle w}$ matrices ${\displaystyle H_{i}}$ of dimension ${\displaystyle r\times (n/w)}$ and a bit string ${\displaystyle S}$ of length ${\displaystyle r}$ such that there exists a set of ${\displaystyle w}$ columns, one in each ${\displaystyle H_{i}}$, summing to ${\displaystyle S}$. Find such a set of columns.

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 ${\displaystyle S}$ is exactly equivalent to this problem, so the problem of finding pre-images in FSB must also be NP-complete.

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 ${\displaystyle w}$ matrices ${\displaystyle H_{i}}$ of dimension ${\displaystyle r\times (n/w)}$ and a bit string ${\displaystyle S}$ of length ${\displaystyle r}$ such that there exists a set of ${\displaystyle w'}$ columns, two or zero in each ${\displaystyle H_{i}}$, summing to zero. ${\displaystyle (0<w'<2w)}$. Find such a set of columns.

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 ${\displaystyle w}$ such that ${\displaystyle Hw=S}$, 2-RNSD is equivalent to finding a 2-regular word ${\displaystyle w'}$ such that ${\displaystyle Hw'=0}$. A 2-regular word of length ${\displaystyle n}$ and weight ${\displaystyle w}$ is a bit string of length ${\displaystyle n}$ such that in every interval ${\displaystyle [(i-1)w,iw)}$ exactly two or zero entries are equal to 1. Note that a 2-regular word is just a sum of two regular words.

Suppose that we have found a collision, so we have Hash(m₁) = Hash(m₂) with ${\displaystyle m_{1}\neq m_{2}}$. Then we can find two regular words ${\displaystyle w_{1}}$ and ${\displaystyle w_{2}}$ such that ${\displaystyle Hw_{1}=Hw_{2}}$ . We then have ${\displaystyle H(w_{1}+w_{2})=Hw_{1}+Hw_{2}=2Hw_{1}=0}$; ${\displaystyle (w_{1}+w_{2})}$ is a sum of two different regular words and so must be a 2-regular word of which the hash is zero, so we have solved an instance of 2-RNSD. We conclude that finding collisions in FSB is at least as difficult as solving 2-RNSD and so must be NP-complete.

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 ${\displaystyle H}$ separated into ${\displaystyle w=3}$ sub-blocks and a string ${\displaystyle r=1111}$. We are asked to find in each sub-block exactly one column such that they would all sum to ${\displaystyle r}$. The expected answer is thus ${\displaystyle s_{1}=1}$, ${\displaystyle s_{2}=0}$, ${\displaystyle s_{3}=3}$. This is known to be hard to compute for large matrices.

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 ${\displaystyle r}$). In the example, we might use column (counting from 0) 2 and 3 from ${\displaystyle H_{1}}$, no column from ${\displaystyle H_{2}}$ column 0 and 2 from ${\displaystyle H_{3}}$. More solutions are possible, for example might use no columns from ${\displaystyle H_{3}}$.

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.