Introduction to Hash Functions
A hash function H is a mathematical algorithm that accepts a variable-length block or message of data as input and produces a fixed-size output known as a 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:
- A hash function maps a variable-length message into a fixed-length hash value, or message digest.
- 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.
- Data Integrity: Hash functions are used to ensure the integrity of data by generating checksum.
- Cryptography: In cryptographic applications, hash functions are used to create secure hash algorithms like SHA-256.
Properties of Hash Functions:
A good hash function should satisfy certain properties to ensure efficient and reliable data storage, retrieval, and security.
- Deterministic: A hash function must consistently produce the same output for the same input.
- Variable Input Size: A has function can be applied to a data block or message of any arbitrary 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 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 an input y such that H(y) = h. This property ensures that the original message or a shared secret cannot be recovered simply by observing the hash value.
- 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 a known message.
- Avalanche Effect: A small change in the input should produce a significantly different hash value.
- Pseudorandomness: The output of H meets standard tests for pseudorandomness, producing hash values that appear evenly distributed and random.
Here is a video lecture on Hash Functions.
Simple Hash Functions
- A hash function accepts a variable-length block of data as input and processes it to produce a fixed-length output known as a hash value, hash code, or message digest.
- Hashing enables efficient storage and fast retrieval of data.
- Applying modulo division on an integer is an example of a simple hash function. Here is an exmple:
H(x) = x % 10
- The operation of module division by 10 converts any large number into a value between 0 and 9, making it suitable for indexing in a hash table.
- Here is another example. When we apply the modulo division by 100 on an integer, we get a has value that falls between 0 and 99
h(k) = k mod 100
- For a hash table of size 100, valid indices range from 0 to 99 that can be generated by the hash function mentioned above
Modular Additional Hash
- A modular addition hash is one of the simplest conceptual forms of an iterated hash function. It processes input data by breaking it into fixed-size blocks and summing them sequentially modulo a chosen number N.
Cryptographic Cash Function
- A cryptographic hash function is an algorithm specifically designed for security applications.
- 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:
- (i) a function specifically designed for the hash function
- (ii) 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. In other words, the function creates a checksum from the information, but it can't be the other way around, the checksum can't be used for creating the information. This property is known as Pre-image Resistance.
- It should not be possible to produce 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.
- The most two common secure hash functions 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.
Digital Signatures
- Digital signatures are a form of encryption that can be utilised for enforcing integrity and authentication of messages during transmission from send to the receiver.
- It is a method of electronic authentication of a message using cryptographic hash functions.
- President Clinton signed a law to allow digital signatures to be used as a legal signature.
- Given below are the steps involved in applying digital signatures for message authentication:
- The information to be secured is first put through a message digest or hash function. The hash function creates a check sum of the information.
- The checksum is then encrypted by the user's private key.
- The information and the encrypted checksum are sent to the receiver of the information.
- 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 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 changed during transmission (integrity is secured).
The security and usefulness of a digital signature depends upton two critical elements:
- Protection of the user's private key
- A secure hash function that creates a checksum of atleast 128 bits.
Need for Public Key Encryption in Authentication:
- Public key encryption uses a key pair - one key to encrypt the data and another key to decrypt the data
- Proper use of public key encryption can provide confidentiality, authentication and integrity of information.
- 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 key.
- If authentication is desired, the owner of the key pair encrypts information with the private key and the encrypted message to the recipient.
- Only the correct public key can decrypt the information, and successful decryption provides the assurance that only the owner the key pair could have sent the information.i.e., the received message has been authenticated.
