Cryptographic Hash Functions

and Digital Signatures.

Contd..
Prajwal Gautam
Message Authentication Code
• An alternative authentication technique involves the use of a
secret key to generate a small fixed-size block of data, known
as a cryptographic checksum or MAC, that is appended to the
message.
• This technique assumes that two communicating parties, say A
and B, share a common secret key .When A has a message to
send to B, it calculates the MAC as a function of the message
and the key:
 MAC = C(K,M)
Where,

M = input message,
C = MAC function,
K = shared secret key ,
MAC = message authentication code
• The message plus MAC are transmitted to the intended
recipient.
• The recipient per forms the same calculation on the received
message, using the same secret key, to generate a new MAC.
• The received MAC is compared to the calculated MAC (Figure
a).
• The process depicted in Figure a provides authentication but
not confidentiality, because the message as a whole is
transmitted in the clear. Confidentiality can be provided by
performing message encryption either after (Figure b) or before
(Figure c) the MAC algorithm.
• In both these cases, two separate keys are needed, each of
which is shared by the sender and the receiver
• In the first case, the MAC is calculated with the message as
input and is then concatenated to the message.
• The entire block is then encrypted. In the second case, the
message is encrypted first.
• Then the MAC is calculated using the resulting ciphertext and is
concatenated to the ciphertext to form the transmitted block.
• Typically, it is preferable to tie the authentication directly to the
plaintext, so the method of Figure b is used.
Cryptographic Hash Functions
• Hash function can be defined as a function that maps a
message of any length into a fixed length hash value, which
serves as the authenticator,
• Cryptographic hash functions are an important tool of
cryptography and play a fundamental role in efficient and secure
information processing.
• A hash function processes an arbitrary finite length of input
message to a fixed length output referred as hash value.
Properties of Hash Function
1. Preimage resistance : H is preimage resistance if for any
given hash value y of H, it is “computationally infeasible” to
find a message m such that H(m) = y. That is, it must be hard
to invert H from y to get a m corresponding to y. This property
is also called one-wayness. For an ideal H, it takes about 2^n
evaluations of H to find a preimage.
2. Second pre-image resistance : H is second preimage resistant
if for any given message m, it is “computationally infeasible” to
find another message m* such that m*=m and H(m) = H(m*).
3. Collision resistance : H is collision resistant if it is
“computationally infeasible” to find another message m* such
that m* != m and H(m) = H(m*). Due to birthday paradox, for
an ideal H , it takes about 2^n/2 evaluations of H to find a
collision.

Check this for more explanation:

Applications of Cryptographic Hash
Functions
• Message Authentication: Message authentication is a
mechanism or service used to verify the integrity of a message.
Message authentication assures that data received are exactly
as sent.
• Digital Signatures : Another important application, which is
similar to the message authentication application, is the digital
signature. 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.(later topic)
• Other Applications : Hash functions are commonly used to
create a one-way password file. Hash of a password is stored
by an operating system rather than the password itself.
• Hash functions can be used for intrusion detection and virus
detection.
• A hash function can be used to construct pseudorandom
function(PRF) or a pseudorandom number generator (PRNG).
• Common application of hash-based PRF us for generation of
symmetric keys.
Message Digests
A message digest is a cryptographic hash function containing a
string of digits created by one-way hashing formula.
Message digests are designed to protect the integrity of a piece
of data or media to detect changes and alternations to any part of
a message.
• Message Digest Version 4 (MD4): The MD4 function is a
cryptographic algorithm that takes a message of arbitrary length
as input and we need to find its message digest. It is assumed
that the bits of the message are m0, m1,…..,mb-1.
MD4 hashing steps:
Step 1: The message is padded so that its length is congruent to
448, modulo 512. A string ‘1’ bit is appended to the message and
then ‘0’ bits are appended so that the length in bits equals to 448
modulo 512.
Message 100000……
(Message length + padded bits) % 512 = 448
Step 2 : Append length :
A 64 bit representation of bits is appended to the result of the
previous step. The resulting message has a length that is an
exact multiple of 512 bits.

64 bits
(Message length + padded bits+64bit) % 512 = 0)
Step 3: Initialize MD buffer
A 4-word buffer (A,B,C,D) is used to compute the message
digest. Here each of A,B,C,D is a 32bit register. These are
initialized to the following values in hexadecimal, low-order byte
first:
A: 01 23 45 67
B: 89 ab cd ef
C: fe dc ba 98
D: 76 54 32 10
Step 4: Process message in 16–word blocks:
It contains three passes (rounds) with 16 steps or operation each.
We first define three auxiliary functions that each take as input
three 32-bit words and produce as output one 32-bit word.
Step 5: Output :
After all rounds have performed the buffer A,B,C,D contains the
MD4 output starting with lower bit A and ending with higher bit D.
Overview of MD4 Message Digest
Computation
• The message digest to be computed is a 128-bit quantity ( four
32bit words).
• The message is processed in 512-bit ( sixteen 32-bit words)
blocks.
• The message digest is initialized to a fixed value, and then each
stage of the message digest computation takes the current
value of the message digest and modifies it using next block of
message.
• The function that takes 512 bits of the message and digest it
with the previous 128-bit output known as the compression
function. The final result is the message digest for the entire
message.
MD4 Summary:
Message Digest Version 5 (MD5) :
The MD5-message digest algorithm is widely used cryptographic
hash function producing a 128-bit (16-byte) hash value. Typically
expressed in text format as a 32-digit hexadecimal number. MD5
were invented by Ron Rivest as an improvement version of MD4.
The major differences between MD4 and MD5 are:
• MD4 makes three passes over each 16-octet chunk of the
message. MD5 makes four passes over each 16-octet chunk.
• The functions are slightly different, as are the number of bits in
the shifts.
MD5 Hashing Steps
Step 1 to Step 3 : Identical to MD4 i.e.
Step 1: The message is padded so that its length is congruent to
448, modulo 512. A string ‘1’ bit is appended to the message and
then ‘0’ bits are appended so that the length in bits equals to 448
modulo 512.

(Message length + padded bits) % 512 = 448

Step 2 : Append length :
A 64 bit representation of bits is appended to the result of the
previous step. The resulting message has a length that is an
exact multiple of 512 bits.

(Message length + padded bits+64bit) % 512 = 0)

Step 3: Initialize MD buffer
A 4-word buffer (A,B,C,D) is used to compute the message
digest. Here each of A,B,C,D is a 32bit register. These are
initialized to the following values in hexadecimal, low-order byte
first:
A: 01 23 45 67
B: 89 ab cd ef
C: fe dc ba 98
D: 76 54 32 10
Step 4: It contains 4 passes, with 16 steps or operation each. We
first define four auxiliary functions that each take as input the
32-bit words and produce one 32-bit word.
Step 5: Output
After all have performed the buffer A, B, C, D contains the MD5
output starting with lower bit A and ending with higher bit D.
Assignment
• Read Md4 and Md5 algorithms.