11.2 Simple Hash Examples – Introduction to Cryptography with Coding Theory, 3rd Edition

11.2 Simple Hash Examples

There are many families of hash functions. The discrete log hash function that we described in the previous section is too slow to be of practical use. One reason is that it employs modular exponentiation, which makes its computational requirements about the same as RSA or ElGamal. Even though modular exponentiation is fast, it is not fast enough for the massive inputs that are used in some situations. The hash functions described in this section and the next are easily seen to involve only very basic operations on bits and therefore can be carried out much faster than procedures such as modular exponentiation.

We now describe the basic idea behind many cryptographic hash functions by giving a simple hash function that shares many of the basic properties of hash functions that are used in practice. This hash function is not an industrial-strength hash function and should never be used in any system.

Suppose we start with a message m of arbitrary length L. We may break m into n-bit blocks, where n is much smaller than L. We denote these n-bit blocks by mj, and thus represent m=[m1, m2, , ml]. Here l=L/n, and the last block ml is padded with zeros to ensure that it has n bits.

We write the jth block mj as a row vector

mj=[ mj1, mj2, mj3, , mjn ], 

where each mji is a bit.

Now, we may stack these row vectors to form an array. Our hash h(m) will have n bits, where we calculate the ith bit as the XOR along the ith column of the matrix, that is hi=m1im2imli. We may visualize this as

[ m11m12m1nm21m22m2nml1ml2mln ][c1c2cn]=h(m).

This hash function is able to take an arbitrary length message and output an n-bit message digest. It is not considered cryptographically secure, though, since it is easy to find two messages that hash to the same value (Exercise 9).

Practical cryptographic hash functions typically make use of several other bit-level operations in order to make it more difficult to find collisions. Section 11.4 contains many examples of such operations.

One operation that is often used is bit rotation. We define the right rotation operation

Ry(m)

as the result of shifting m to the right by y positions and wrapping the rightmost y bits around, placing them in leftmost y bit locations. Then Ry(m) gives a similar rotation of m by y places to the left.

We may modify our simple hash function above by requiring that block mj is left rotated by j1, to produce a new block mj=R(j1)(mj). We may now arrange the mj in columns and define a new, simple hash function by XORing these columns. Thus, we get

[ m11m12m1nm22m23m21m33m34m32mllml, l+1ml, l1 ][c1c2cn]=h(m).

This new hash function involving rotations mixes the bits in one position with those in another, but it is still easy to find collisions (Exercise 9). Building a cryptographic hash requires considerably more tricks than just rotating. In later sections, we describe hash functions that are used in practice. They use the techniques of the present section, coupled with many more ways of mixing the bits.