Canal-U

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

In the last session of this week, we will have a look at the FSB Hash Function which is built using the one-way function we saw in the previous session. What are the requirements for a cryptographic hash function? So, it is a function which takes an input of arbitrary size and outputs a fixed size. From a security point of view, it should be hard to solve any of the three following problems: first, find an input with a given hash which is what we call preimage attacks; find an input with the same hash as a given input which is what we call second preimage attack; or find two inputs with the same hash which is what we call collision attack. In addition, hash function have some implementation constraints. It should be fast in both software and hardware implementations, it should be fast for both small inputs and large inputs and it should have a compact description. Building a function of arbitrary length is something which is not that obvious. Usually, you simply iterate a function with a fixed input size on blocks of the input. There are several constructions to achieve this, the oldest one is the Merkle-Damgård Construction. This function iterates a compression function f which takes at each round a part of the message m0, m1 or something like this and starts with an IV or the chaining value which is the output of the previous compression function. It is easy to understand and it has a simple security proof. So, it is something that is used pretty commonly in cryptography. Another construction which is commonly used in cryptography is the Davies-Meyer Construction. For the compression function, this construction uses a block cipher E. The message is used as the key of the block cipher and the input is the chaining value. An interesting element of this construction is that it reuses the same hardware as the block cipher. So, if you have an implementation which already includes a block cipher, you don't need any more implementations. A much more recent construction is the Sponge construction. This construction uses a function with the same input and output size. The message is XORed to a part of an internal state fed to the function which is some kind of permutation, then, another part of the message is exhorted and so on. This is the absorb phase. Once you have finished absorbing all the message in the padding, you have a squeeze out phase where you take out - bits of the message from the internal state, iterating the function f again. The interesting aspect of this construction is its versatility. It can be used as both the hash function where the input is larger than the output or a pseudo-random generator where the input is small and the output is large.