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.
Description of the hash function
We start with a compression function with parameters such that and . This function will only work on messages with length ; will be the size of the output. Furthermore, we want and to be natural numbers, where denotes the binary logarithm. The reason for is that we want to be a compression function, so the input must be larger than the output. We will later use the Merkle–Damgård construction to extend the domain to inputs of arbitrary lengths.
The basis of this function consists of a (randomly chosen) binary matrix which acts on a message of bits by matrix multiplication. Here we encode the -bit message as a vector in , the -dimensional vector space over the field of two elements, so the output will be a message of bits.
For security purposes as well as to get a faster hash speed we want to use only “regular words of weight ” as input for our matrix.
Definitions
A message is called a word of weight and length if it consists of bits and exactly of those bits are ones. A word of weight and length is called regular if in every interval it contains exactly one nonzero entry for all . More intuitively, this means that if we chop up the message in w equal parts, then each part contains exactly one nonzero entry.
The compression function
There are exactly different regular words of weight and length , so we need exactly bits of data to encode these regular words. We fix a bijection from the set of bit strings of length to the set of regular words of weight and length and then the FSB compression function is defined as follows :
input: a message of size
convert to regular word of length and weight
multiply by the matrix
output: hash of size
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 into sub-matrices of size and we fix a bijection from the bit strings of length to the set of sequences of numbers between 1 and . This is equivalent to a bijection to the set of regular words of length and weight , since we can see such a word as a sequence of numbers between 1 and . The compression function looks as follows:
Input: message of size
Convert to a sequence of numbers between 1 and
Add the corresponding columns of the matrices to obtain a binary string a length Output: hash of size
We can now use the Merkle–Damgård construction to generalize the compression function to accept inputs of arbitrary lengths.
Example of the compression
Situation and initialization: Hash a message using matrix H
that is separated into sub-blocks , , .
Algorithm: We split the input into parts of length and we get , , . We convert each into an integer and get , , . From the first sub-matrix , we pick the column 2, from the second sub-matrix the column 1 and from the third sub-matrix the column 4. We add the chosen columns and obtain the result .