Introduction to Hash Functions
A hash function H is a mathematical algorithm that accepts a variable-length block of data or message as input and produces a fixed-size output known as checksum, hash value, hash code, or message digest (h =H(M)).
- The primary objective of a hash function is to verify data integrity, as any alteration to even a single bit in the input message will, with high probability, produce a different hash code.
Applications of Hash Functions:
- The purpose of a hash function is to produce a "fingerprint" of a file, message, or a block of data.
- Hash functions are widely used across various domains due to their efficiency and versatility:
- Hash Tables: The most common use of hash functions in DSA is in hash tables, which provide an efficient way to store and retrieve data.
- Message Authentication: Message authentication is a mechanism or service used to verify the integrity of a message. When a hash function is used to provide message authentication, the hash value generated by the hash function is often referred to as message digest.
- Digital Signatures: In digital signatures, the hash value of the message is encrypted with the user's private key. Anyone who knows the sender's public key can verify the integrity of the message that is associated with the digital signature.
Hash Function Requirements:
To be useful for message authentication, a hash function H must have the following properties.
- Variable Input Size: A has function can be applied to a data block or message of any arbitrary size. i.e., H can be applied to a block of data of any size.
- Fixed Output Size: The output of a hash function should have a fixed size, regardless of the size of the input, i.e., the function H produces a fixed-length output regardless of how large or small the input message is.
- Efficiency: The hash function should be able to process the input quickly. H(x) is relatively easy and fast to compute for any given input x, making both software and hardware implementations practical.
- Pre-image Resistance: It should be computationally infeasible to reverse the hash function.
- For any given hash value h, it is computationally infeasible to find x (input message) such that H(x) = h.
- This property is also known as one-way property.
- Collision Resistance: It should be difficult to find two different inputs that produce the same hash value.
- For any given message x, it is computationally infeasible to find a different message y ≠ × such that H(y) = H(x).
- This property prevents an attacker from forging an alternative message that yields the same hash code as that of the original message.
- This property is sometimes referred to as weak collision resistance.
- Avalanche Effect: A small change in the input should produce a significantly different hash value.
- It is computationally infeasible to find any pair (x,y) such that H(x) = H(y).
- This property is sometimes referred to as strong collision resistance.
- The first three properties are requirements for the practical applications of a hash function to message authentication.
- A hash function that satisfies only the first five properties of hash functions is referred to as a weak hash function.
- If all the six properties of hash functions are inherited by a hash function, then it is referred to as a strong hash function.
- All hash functions operate using the following general principles:
- The input (message, file, etc.) is viewed as a sequence of n-bit blocks.
- The input is processed one block at a time in an iterative fashion to produce a set of n-bit hash values (say 128 bits in length).
- One of the simplest hash functions is the bit-by-bit exclusive-OR (XOR) or every block. This can be expressed as follows:
- This hash function produces a simple parity for each bit position and is known as a longitudinal redundancy check.
- It is reasonably effective for random data as a data integrity check.
- A simple approach to improve the simple hash function is to perform a one-bit circular shift, or rotation, on the hash value after each block is processed.
- The procedure can be summarised as follows:
- Initially set the n-bit hash value to zero.
- Process each successive n-bit block of data as follows:
- Rotate the current hash value to the left by one bit.
- XOR the block into the hash value.
Cryptographic Cash Function
- A cryptographic hash function is an hash function specifically designed for security applications and Internet protocols.
- These hash functions are designed for security rather than speed. They are used in applications where data protection is critical.
- All cryptographic hash functions involve the iterative use of a compression function.
- The compression function used in secure hash algorithms falls into one of two categories:
- a function specifically designed for the hash function
- an algorithm based on a symmetric block cipher. SHA and Whirlpool are examples of these two approaches, respectively.
- For a hash function to be cryptographically secure and effective in practice, it must satisfy the following two properties:
- The function is one-way, i.e, the function creates the checksum from the information, but the checksum can't be used for creating the information. This property is known as pre-image resistant.
- It should not be possible to find two pieces of information that provide the same checksum when run through the function. This property of the has function is known as collision resistance.
- Two secure hash functions that are commonly used are MD5, which produces a 128-bit checksum, and SHA, which produces a 160-bit checksum.
- Among these two, SHA, which was developed by the government of USA and is believed to be more secure than MD5
Message Authentication:
- Message authentication assures that the data received by the recipient are exactly the same as it was sent (with out insertion or deletion of some portion).
- In message authentication, the sender computes the hash value (called message digest) of the message by applying a hash function on it and transmits both the message digest and the message.
- The receiver performs the same hash calculation on the message and compares the calculated message digest with that of the message digest received from the sender.
- If there is a mismatch, the receiver knows that the message (or possibly the message digest) has been altered.
Digital Signatures
- Digital signature is an encrypted form of a message that can be utilised for enforcing integrity and authentication of the message during transmission from sender to the receiver.
- It can be used for ensuring the authentication of a message using cryptographic hash function.
- President Clinton signed a law to allow digital signatures to be used as a legal signature.
Use of Cryptography in Digital Signatures:
- Proper use of cryptography can provide confidentiality, authentication and integrity of information during transmission.
- Symmetric cryptography uses only one key for both encryption and decryption. Whereas, asymmetric cryptography (also called public key cryptography) uses a key pair - one key to encrypt the data and another key to decrypt the data
- In public key encryption , the private key is kept secret by the owner; the public key is published identifying who the owner is; one key can't be used for creating another.
Steps involved in using Digital Signatures:
- The information (message) to be secured is first put through a hash function. The hash function creates a checksum of the information.
- The checksum is then encrypted with the help of sender's private key. The encrypted checksum is known as the digital signature, because it needs the sender's public key for decrypting the checksum.
- The information (message) and the digital signature are sent to the receiver of the information. If confidentiality of the information is also desired, then the message as well as digital signature can be encrypted using a symmetric key cryptography.
- At the receiving side, the receiver gets the information and puts it through the same hash function to derive the checksum of the message being sent.
- The encrypted checksum (digital signature) came along the message is decrypted and the two checksums (original and calculated) are compared.
- If the received checksum and the calculated checksum do match with each other, it ensures that the information has not been modified during transmission, i.e., integrity of the message is secured.
The security and usefulness of a digital signature depends upon two critical elements:
- Protection of the sender's private key
- A secure hash function that creates a checksum of at least 128 bits.
Continue reading →