5.7. The Fast Syndrome-Based (FSB) Hash Function

In the last session of thisweek, we will have a look at the FSB Hash Function whichis built using the one-way function we saw inthe previous session. What are the requirements fora cryptographic hash function? So, it is a function whichtakes an input of arbitrary size and outputs a fixed size. From a security point ofview, it should be hard to solve any of the three followingproblems: first, find an input with a given hash which iswhat we call preimage attacks; find an input with the samehash as a given input which is what we call secondpreimage attack; or find two inputs with the same hash whichis what we call collision attack. In addition, hash function havesome implementation constraints. It should be fast inboth software and hardware implementations, it shouldbe fast for both small inputs and large inputs and itshould have a compact description. Building a function ofarbitrary length is something which is not that obvious.Usually, you simply iterate a function with a fixed inputsize on blocks of the input. There are severalconstructions to achieve this, the oldest one is theMerkle-Damgård Construction. This function iterates acompression function f which takes at each round apart of the message m0, m1 or something like this andstarts with an IV or the chaining value which is the output ofthe previous compression function. It is easy to understand andit has a simple security proof. So, it is something that is usedpretty commonly in cryptography. Another constructionwhich is commonly used in cryptography is theDavies-Meyer Construction. For the compression function, thisconstruction uses a block cipher E. The message is used as thekey of the block cipher and the input is the chaining value. An interesting element ofthis construction is that it reuses the samehardware as the block cipher. So, if you have animplementation which already includes a block cipher, you don'tneed any more implementations. A much more recentconstruction is the Sponge construction. This construction uses a functionwith the same input and output size. The message is XORed to a partof an internal state fed to the function which issome kind of permutation, then, another part of themessage is exhorted and so on. This is the absorb phase. Once you have finishedabsorbing all the message in the padding, you have a squeezeout phase where you take out - bits of the message from the internalstate, iterating the function f again. The interesting aspect of thisconstruction is its versatility. It can be used as both thehash function where the input is larger than the outputor a pseudo-random generator where the input is smalland the output is large.