Cryptography and Network Security (24BECSE406)

Module I
Hash Functions

Cryptographic Hash Functions: Secure hash algorithm (SHA-512), Message Authentication Codes
Digital signatures Key Management and Distribution: Distribution of Public Keys
Post-Quantum Cryptography: Concepts and Algorithms

Hash Functions
• A hash function H accepts a variable-length block of data M as input and produces a fixed-size
hash value h = H(M).
• A “good” hash function has the property that the results of applying the function to a large set
of inputs will produce outputs that are evenly distributed and apparently random. In general
terms, the principal object of a hash function is data integrity.
• A change to any bit or bits in M results, with high probability, in a change to the hash value.
Cryptographic Hash Functions
• The kind of hash function needed for security applications is referred to as a cryptographic
hash function.
• A cryptographic hash function is an algorithm for which it is computationally infeasible
(because no attack is significantly more efficient than brute force) to find either (a) a data object
that maps to a pre-specified hash result (the one-way property) or (b) two data objects that map
to the same hash result (the collision-free property). Because of these characteristics, hash
functions are often used to determine whether or not data has changed.

Fig 1: Cryptographic hash function h=H(M)

Sapthagiri NPS University 1

 • Fig 1 depicts the general operation of a cryptographic hash function. Typically, the input is
padded out to an integer multiple of some fixed length (e.g., 1024 bits), and the padding
includes the value of the length of the original message in bits.
• The length field is a security measure to increase the difficulty for an attacker to produce an
alternative message with the same hash value, as explained subsequently.
Applications of Cryptographic Hash Functions
i) 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 (i.e., there is no
modification, insertion, deletion, or replay).
• When a hash function is used to provide message authentication, the hash function value is
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.
ii) 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.
• Anyone who knows the user’s public key can verify the integrity of the message that is
associated with the digital signature. In this case, an attacker who wishes to alter the message
would need to know the user’s private key.
• Fig 2 shows how a hash code is used to provide a digital signature.
a. The hash code is encrypted, using public-key encryption with the sender’s private key.

Fig 2: Example of Digital Signature

Sapthagiri NPS University 2

 As with Figure 2 b, this provides authentication. It also provides a digital signature, because
only the sender could have produced the encrypted hash code. In fact, this is the essence of the
digital signature technique.
b. If confidentiality as well as a digital signature is desired, then the message plus the private-
key-encrypted hash code can be encrypted using a symmetric secret key. This is a common
technique
iii) To create a one-way password file
• Hash functions are commonly used to create a one-way password file. A hash of a password is
stored by an operating system rather than the password itself. Thus, the actual password is not
retrievable by a hacker who gains access to the password file. In simple terms, when a user
enters a password, the hash of that password is compared to the stored hash value for veri
fication. This approach to password protection is used by most operating systems.
iv) Intrusion detection and virus detection
• Hash functions can be used for intrusion detection and virus detection. Store H(F) for each file
on a system and secure the hash values (e.g., on a CD-R that is kept secure). One can later
determine if a file has been modified by recomputing H(F). An intruder would need to change
F without changing H(F).
v) Pseudorandom function (PRF) or a pseudorandom number generator (PRNG)
• Cryptographic hash function can be used to construct a pseudorandom function (PRF) or a
pseudorandom number generator (PRNG). A common application for a hash-based PRF is for
the generation of symmetric keys.

Secure Hash Function

• In recent years, the most widely used hash function has been the Secure Hash Algorithm
(SHA). Indeed, because virtually every other widely used hash function had been found to have
substantial cryptanalytic weaknesses, SHA was more or less the last remaining standardized
hash algorithm by 2005.
• SHA was developed by the National Institute of Standards and Technology (NIST).
SHA-512 Logic
• The algorithm takes as input a message with a maximum length of less than 2128 bits and
produces as output a 512-bit message digest. The input is processed in 1024-bit blocks.
• Fig 2 depicts the overall processing of a message to produce a digest.
• The processing consists of the following steps.
Step 1 Append padding bits.
• The message is padded so that its length is congruent to 896 modulo 1024 [length K 896(mod
1024)].
• Padding is always added, even if the message is already of the desired length. Thus, the number
of padding bits is in the range of 1 to 1024.
• The padding consists of a single 1 bit followed by the necessary number of 0 bits.

Sapthagiri NPS University 3

 Fig 2: Message Digest Generation using SHA-512
Step 2 Append length.
• A block of 128 bits is appended to the message. This block is treated as an unsigned 128-bit
integer (most significant byte first) and contains the length of the original message in bits
(before the padding).
• The outcome of the first two steps yields a message that is an integer multiple of 1024 bits in
length. In Fig 2, the expanded message is represented as the sequence of 1024-bit blocks M1,
M2, … MN, so that the total length of the expanded message is N * 1024 bits.
Step 3 Initialize hash buffer.
• A 512-bit buffer is used to hold intermediate and final results of the hash function. The buffer
can be represented as eight 64-bit registers (a, b, c, d, e, f, g, h). These registers are initialized
to a fixed 64-bit integers (hexadecimal values). Eg register a is initialized to
6A09E667F3BCC908.
• These values are stored in big-endian format, which is the most significant byte of a word in
the low-address (leftmost) byte position. These words were obtained by taking the first sixty-
four bits of the fractional parts of the square roots of the first eight prime numbers.
Step 4 Process message in 1024-bit (128-byte) blocks.
• The heart of the algorithm is a module that consists of 80 rounds which is represented as F. The
addition is done independently for each of the intermediate hash value in the buffer with each
of the corresponding words in Hi-1, using addition modulo 264 to obtain Hi.
Step 5 Output
• After all N 1024-bit blocks have been processed, the output from the Nth stage is the 512-bit
message digest.
• We can summarize the behavior of SHA-512 as follows:
H0=IV

Sapthagiri NPS University 4

 Hi =SUM64(Hi-1, abcdefghi)
MD=HN
Where,
IV =initial value of the abcdefgh buffer, defined in step 3
abcdefghi = the output of the last round of processing of the ith message block
N = the number of blocks in the message (including padding and length fields)
SUM64 = addition modulo 264 performed separately on each word of the pair of inputs
MD =final message digest value

Message Authentication Code

• Message authentication is a procedure to verify that received messages come from the alleged
source and have not been altered. Message authentication may also verify sequencing and
timeliness.
• A digital signature is an authentication technique that also includes measures to counter
repudiation by the source.
Message Authentication Function
• Any message authentication or digital signature mechanism has two levels of functionality. At
the lower level, there must be some sort of function that produces an authenticator: a value to
be used to authenticate a message. This lower-level function is then used as a primitive in a
higher-level authentication protocol that enables a receiver to verify the authenticity of a
message.
• Message Authentication techniques are of three types:
➢ Hash function: A function that maps a message of any length into a fixed-length hash
value, which serves as the authenticator
➢ Message encryption: The ciphertext of the entire message serves as its authenticator
➢ Message authentication code (MAC): A function of the message and a secret key that
produces a fixed-length value that serves as the authenticator
Message authentication code (MAC)
• Message authentication code (MAC) is an authentication technique.
• It 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 K. 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 performs 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 (Fig 3).

Sapthagiri NPS University 5

 Fig 3. Message Authentication
• If we assume that only the receiver and the sender know the identity of the secret key, and if
the received MAC matches the calculated MAC, then
1. The receiver is assured that the message has not been altered. If an attacker alters the message
but does not alter the MAC, then the receiver’s calculation of the MAC will differ from the
received MAC. Because the attacker is assumed not to know the secret key, the attacker cannot
alter the MAC to correspond to the alterations in the message.
2. The receiver is assured that the message is from the alleged sender. Because no one else
knows the secret key, no one else could prepare a message with a proper MAC
3. If the message includes a sequence number (such as is used with TCP), then the receiver can
be assured of the proper sequence because an attacker cannot successfully alter the sequence
number.
• One difference between MAC and encryption is that the MAC algorithm need not be reversible,
as it must be for decryption. In general, the MAC function is a many-to-one function.

Sapthagiri NPS University 6