Hash Functions (continued)

Evaluation of SHA-1 for Hash Tables

We evaluate SHA-1 for comparison purposes only. SHA-1 is a cryptographic hash and is not intended to be used for hash table lookups or similar purposes. SHA-1, like any cryptographic hash, should still meet all the uniform distribution and avalanche requirements of a hash intended for hash table lookup. If it didn't, it wouldn't meet the more stringent cryptographic requirements.

SHA stands for Secure Hash Algorithm. It was designed by the National Security Agency (of the US) and the original version was published in 1993 by the National Institute of Standards and Technology. SHA was updated two years later, and this revision was called SHA-1. The original SHA is now sometimes referred to as SHA-0.

Figure 1 shows the SHA-1 hash function modified for the purposes of this evaluation. This code depends on the SHA-1 implementation built into the .NET Framework. It takes takes the 160-bit result and splits it up into five 32-bit sub-sections, then xor's those subsections together to provide the final 32-bit result.

Uniform Distribution Test

The details of this test are described fully on a previous page. We examine the distribution of numbers derived from lower and upper bits of the hash output in sizes of 1 through 16 bits.

Figure 2 shows the results of this test for the SHA-1 function. This test indicates that the upper bits and lower bits of this hash produce uniformly distributed values for hash tables that are a power of two, up to at least 216, when the key octets are uniformly distributed, distributed similar to alphabetic text, or sparsely distributed.

The results show five values that fall within the 5% significance level for non-uniform output. This is a normal result for a completely uniformly distributed hash function. By definition, 5% of the values will be under 0.05. With 96 individual results, the expected number of values under 0.05 is 4.8.

While this test does not illustrate it, it can be surmised from the purpose of SHA-1 and from its proven history as a cryptographic primitive that the χ2 test would show uniform distribution for any classes of keys and any subset of its output bits. If it did not, this weakness would provide a way to identify collisions with less than brute-force effort.

Avalanche Test

The details of this test are described fully on a previous page. We examine the diffusion of input bits into different bit positions in the output.

Figure 3 shows the results of this test for the SHA-1 function. This test indicates that this hash has excellent avalanche behavior. It is unlikely that there are any specific classes of keys that will cause problems with this function, as key bits from every position appear to be dispersed well into all hash bit positions, even for very short hash keys.

Once again, this is the expected behavior for cryptographic hash function.

Conclusions

SHA-1 was never intended for hash table use. Although, since it provides uniformly distributed output bits, it could be used for hash table use, it is much slower than any of the other hash functions evaluated here and for that reason it is not recommended.

It's slow speed is due to the complexity of the algorithm. The increased complexity is required to ensure resistance to cryptanalytic or brute force attacks.

First page, Next page