Hash function, message digest, digital signature, etc
Learning Objectives
- Summarize the applications of cryptographic hash functions
- Explain why a hash function used for message authentication needs to be secured
- Understand the differences among preimage resistant, second preimage resistant, and collision resistant properties
- Present an overview of the basic structure of cryptographic hash functions
- Describe how cipher block chaining can be used to construct a hash function
- Understand the operation of SHA-512
- Understand the birthday paradox and present an overview of the birthday attack
Hash Function
A hash function H accepts a variable-length block of data M as input and produces a fixed-size hash value h = H(M). In general terms, the principal object of a hash function is data integrity.
A cryptographic hash function is an algorithm for which it is computationally infeasible to find either a data object that maps to a pre-specified hash result(the one-way property) or two data objects that map to the same hash result(the collision-free property).
Applications of Cryptographic hash functions
Message Authentication
Message authentication is mechanism or service used to verify the integrity of a message. When a hash function is used to provide message authentication, the hash function value if often referred to as a message digest.
The essence of the use of a hash function for message integrity is as follows. The sender computes a hash value as a function of the bits in the message and transmits both the hash value and the message. The receiver performs the same hash calculation on the message bits and compares this value with the incoming hash value. If there is a mismatch, the receiver knows that the message(or possibly the hash value) has been altered.
More commonly, message authentication is achieved using a message authentication code(MAC), also known as a keyed hash function. Typically, MACs are used between two parties that share a secret key to authenticate information exchanged between those parties.
Digital Signatures
The operation of the digital signature is similar to that of the MAC. In the case of the digital signature, the hash value of a message is encrypted with a user’s private key. Anyone who knows the user’s public key can verity the integrity of the message that is associated with the digital signature.
Other Applications
Hash functions are commonly used to create a one-way password file. They can be used for intrusion detection and virus detection.
Security requirements for Cryptographic Hash Functions
Before proceeding, we need to define two terms. For a hash value h = H(x), we say that x is the preimage of h. That is, x is a data block whose hash value, using function H, is h. Because H is many-to-one mapping, for any given hash value h, there will general be multiple preimages. A collision occurs if we have x !=y and H(x) = H(y). Because we are using hash functions for data integrity, collisions are clearly undesirable.
Requirements for a Cryptographic Hash Function H
Hash function resistance properties required for various data integrity applications
Brute-Force Attacks
As with encryption algorithms, there are two categories of attacks on hash functions: brute-force attacks and cryptanalysis.
Preimage and Second Preimage attacks
For a preimage or sencond preimage attack, an adversary wishes to find a value y such that H(y) is equal to a given hash value h. For an m-bit hash value, the level of effort is proportional to 2^m.
Collision Resistant Attacks
For a collision resistant attack, an adversary wishes to find two messages or data blocks, x and y, that yield the same hash function: H(x) = H(y). This effort required is explained by a mathematical result referred to as birthday paradox
Crytanalysis
As with encryption algorithms, crytanalysis attacks on hash functions seek to exploit some property of the algorithm to perform some attack other than an exhaustive search.
In recent years, there has been considerable effort, and some successes, in developing cryptanalysis attacks on hash functions. To understand these, we need to look at the overall structure of a typical secure hash function.
The hash function algorithm involves repeated use of a compression function, f, that takes two inputs( an n-bit input from the previous step, called the chaining variable, and a b-bit block) and produces an n-bit output.
Cryptanalysis of hash functions focuses on the internal structure of f and is based on attempts to find efficient techniques for producing collisions for a single execution of f. One that is done, the attack must take into account the fixed value of IV.
Secure Hash Algorithm(SHA)
…to be continued :)
References