HASH FUNCTIONSHash tables. Data normalization. Specialized uses.

CONTENTS

1. Definition
2. Overview
3. Hash functions choice

DEFINITION

A hash function is any function that can be used to map data of arbitrary size to fixed-size values.

The values returned by a hash function are called hash values, hash codes, digests, or simply hashes.

The values are usually used to index a fixed-size table called a hash table.

Use of a hash function to index a hash table is called hashing or scatter storage addressing.

Hash functions and their associated hash tables are used in data storage and retrieval applications to access data in a small and nearly constant time per retrieval. They require an amount of storage space only fractionally greater than the total space required for the data or records themselves.

Hashing is a computationally and storage space-efficient form of data access that avoids the non-constant access time of ordered and unordered lists and structured trees, and the often exponential storage requirements of direct access of state spaces of large or variable-length keys.

OVERVIEW

A hash function takes an input as a key, which is associated with a datum or record and used to identify it to the data storage and retrieval application.

The keys may be fixed length, like an integer, or variable length, like a name. In some cases, the key is the datum itself. The output is a hash code used to index a hash table holding the data or records, or pointers to them.

A hash function may be considered to perform three functions:

• Convert variable - length keys into fixed length (usually machine word length or less) values, by folding them by words or other units using a parity-preserving operator like ADD or XOR.


• Scramble the bits of the key - so that the resulting values are uniformly distributed over the keyspace.


• Map the key - map the key values into ones less than or equal to the size of the table.

A good hash function satisfies two basic properties: it should be very fast to compute; it should minimize duplication of output values (collisions).

Hash functions rely on generating favourable probability distributions for their effectiveness, reducing access time to nearly constant. High table loading factors, pathological key sets and poorly designed hash functions can result in access times approaching linear in the number of items in the table.

Hash functions can be designed to give the best worst-case performance, good performance under high table loading factors, and in special cases, perfect (collisionless) mapping of keys into hash codes. Implementation is based on parity-preserving bit operations (XOR and ADD), multiply, or divide.

A necessary adjunct to the hash function is a collision-resolution method that employs an auxiliary data structure like linked lists, or systematic probing of the table to find an empty slot.

HASH FUNCTIONS CHOICE

The choice of hash functions is a base component in configuring the used crypto primitives.

In BS Project hash tables are used to implement associative arrays and dynamic sets.

Hash functions selection is done by selecting the algorithm from the list of standard algorithms in the Hash functions mode combo box located in the Encrypted settings panel.

Standard Hash Functions (FDM-SPE edition)

1. MD2 - MD2 Message-Digest Algorithm (RFC 1321);
2. MD4 - MD4 Message-Digest Algorithm (RFC 1321);
3. MD5 - MD5 Message-Digest Algorithm (RFC 1321);
4. RipeMD128 - RIPE Message Digest (RFC 2857);
5. RipeMD160 - RIPE Message Digest (RFC 2857);
6. RipeMD256 - RIPE Message Digest (RFC 2857);
7. RipeMD320 - RIPE Message Digest (RFC 2857);
8. SHA0 - SHA hash algorithm (RFC 6194);
9. SHA1 - SHA hash algorithm (RFC 6194);
10. SHA224 - SHA hash algorithm (RFC 6194);
11. SHA256 - SHA hash algorithm (RFC 6194);
12. SHA384 - SHA hash algorithm (RFC 6194);
13. SHA512 - SHA hash algorithm (RFC 6194);
14. Haval128 - HAVAL cryptographic hash function (RFC 6039);
15. Haval160 - HAVAL cryptographic hash function (RFC 6039);
16. Haval192 - HAVAL cryptographic hash function (RFC 6039);
17. Haval224 - HAVAL cryptographic hash function (RFC 6039);
18. Haval256 - HAVAL cryptographic hash function (RFC 6039);
19. Tiger - Tiger cryptographic hash function (RFC 6920);
20. Panama - Panama cryptographic hash function (RFC 3409);
21. Whirlpool0 - WHIRLPOOL cryptographic hash function (RFC 6931);
22. Whirlpool1 - WHIRLPOOL cryptographic hash function (RFC 6931);
23. WhirlpoolT - WHIRLPOOL cryptographic hash function (RFC 6931);
24. Square - Square cryptographic hash function (RFC 6234);
25. Snefru128 - Snefru cryptographic hash function (RFC 4949);
26. Snefru256 - Snefru cryptographic hash function (RFC 4949);
27. Sapphire - Sapphire cryptographic hash function (RFC 6920).

Note: The number of hash functions used is different for the standard and advanced versions of the crypto primitives configuration module. Only hash functions that have proven their reliability and crypto resistance are used in BS applications.

  Contents        < Previous    Next >