Imam Mohammad Ibn Saud Islamic University

Applied College
Computer Sciences Program

CYB - 104
Lecture 2 : Hash Functions and
Message authentication code
 • Cryptographic Hash Functions
• Security considerations
• Attacks on Hash Functions
• Brute-Force Attacks
Outline •
•
Cryptanalysis Attacks
Type of Hash Functions :
• Secure Hash Functions (SHA)
• The SHA-2 hash function
• The SHA-3 hash function
• Hashing passwords
• Applications of Cryptographic Hash Functions
• A man-in-the-middle (MITM) attack
• Message Authentication
• Message Authentication code
Data Integrity and Source
Authentication
• Encryption does not protect data from modification by
another party.
• Need a way to ensure that data arrives at destination in
its original form as sent by the sender and it is coming
from an authenticated source.

3
• We are concerned with the types of
functions that may be used to produce an
authenticator. These may be grouped into
three classes.
o Hash function: A function that maps a
message of any length into a fixed-length hash
value, which serves as the authenticator
o Message encryption: The cipher text of the
entire message serves as its authenticator (We
learned in the first lecture )
o Message authentication code (MAC):
A function of the message and a secret key
that produces a fixed-length value that serves
as the authenticator
 Hash Functions
o A hash function H accepts a variable-length block of data M as input and produces a
fixed-size hash value h = H(M).
o 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 random. In general
terms, the principal object of a hash function is data integrity. A change to any bit or bits
in M results in a high
probability of a change to the hash value.
o The kind of hash function needed for security applications is called a cryptographic hash
function.
o The output of a hash function is often called a digest or a hash.
o The input of this function can be of any size. It can even be empty.
o The output is always of the same length and is deterministic; it always produces the
same result if given the same input.
o Hash functions are one-way, meaning that one shouldn’t be able to find the input from
just the output.
• The above figure 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.
 Security considerations
Three security properties of a hash function:
1- Pre-image resistance:
 Security considerations
2- Second pre-image resistance
 Security considerations
3- Collision resistance
 Attacks on Hash Functions
1-Brute-Force attacks:
▪A brute-force attack does not depend on the specific algorithm but depends only on bit
length.
▪In the case of a hash function, a brute-force attack depends only on the bit length of the
hash value.
▪A cryptanalysis, in contrast, is an attack based on weaknesses in a particular
cryptographic algorithm.

•Preimageand second preimage attacks

▪For a preimage or second preimage attack, an adversary wishes to find a value such that H(y) is
equal to a given hash value.
▪The brute-force method is to pick values of yat random and try each value until a collision occurs.

• Collision-resistant attacks
▪For a collision-resistant attack, an adversary wishes to find two message data blocks, x and y, that
yield the same hash function: H(x) = H(y).
 Attacks on Hash Functions

2- Birthday Attacks
might think a 64-bit hash is secure
but by Birthday Paradox is not
birthday attack works thus:
•given user prepared to sign a valid message x
•have a user sign the valid message, then substitute the forgery which will have a valid signature
conclusion is that need to use a larger MAC/hash
3- Cryptanalysis Attacks
As with encryption algorithms, cryptanalytic attacks on hash functions seek to exploit
some property of the algorithm to perform some attack other than an exhaustive search.
 Type of Hash Functions
Secure Hash Functions (SHA)
• Secure Hash Algorithms, also known as SHA, are a family of
cryptographic functions designed to keep data secured.
It works by transforming the data using a hash function:
• an algorithm that consists of bitwise operations, modular
additions, and compression functions.
• The hash function then produces a fixed-size string that
looks nothing like the original.
• These algorithms are designed to be one-way functions,
meaning that once they’re transformed into their
respective hash values, it’s virtually impossible to
transform them back into the original data.
Type Secure Hash Functions (SHA):
SHA-1, SHA-2, and SHA-3, each of which was successively
designed with increasingly stronger encryption in response to
hacker attacks.
• It all starts with a special function called a compression function. A compression function takes
two inputs of some size and produces one output of the size of one of the inputs. Put simply, it takes
some data and returns less data.
The SHA-2 hash function
• While there are different ways of building a compression function, SHA-2 uses the
Davies–Meyer method, which relies on a block cipher (a cipher that can encrypt a fixed-size
block of data)

SHA-2 is an algorithm that hashes a message by iteratively calling such a compression

function. It works by going through the following two steps.
The SHA-2 hash function
1- it applies padding to the input we want to hash, then cuts the input into
blocks that can fit into the compression function.

Padding means appending specific bytes to the input to make its length a multiple of some block size. Cutting the padded
input into chunks of the same block size allows us to fit these in the first argument of the compression function. For example,
SHA-256 has a block size of 512 bits.
2- it iteratively applies the compression function to the message blocks, using the previous output of the compression
function as the second argument to the compression function. The final output is the digest
The SHA-3 hash function

• SHA-3 is a cryptographic algorithm built on top of a permutation.

• Each element can only have one arrow starting from and terminating to it.
• Any permutation is also reversible, meaning that from the output we can find the input.
 Hashing passwords
• Password hashing is defined as putting a password through a hashing
algorithm to turn plaintext into an unintelligible series of numbers and
letters.
• Hash your passwords and only store the digests.
When someone logs in to your website, the flow will be similar to the
following:
1. You receive the user’s password.
2. You hash the password they give you and get rid of the password.
3. You compare the digest with what you had stored previously; if it
matches, the user is logged in.
• “Hello”, for example, will always equal to the same combination of letters
and numbers, and therefore can be guessed through brute force. One way
of protecting against this is by adding password salt or using salted
passwords.
• Salting is the act of adding a series of random characters to a password
before going through the hashing function.
 Applications of Cryptographic Hash Functions

The most versatile cryptographic algorithm is the cryptographic hash function. It is used in a wide variety of security
applications and Internet protocols. The following are various applications where it is employed.
1. 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, o r
replay).
When a hash function is used to provide message authentication, the hash function value is often referred to as a message
digest.
2. 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
We will learn about it later
3. Other Applications:
Hash functions are commonly used to create a one-way password file.
Hash functions can be used for intrusion detection and virus detection.
A cryptographic hash function can be used to construct a pseudorandom function (PRF) or a pseudorandom number
generator (PRNG).
 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.
o The sender computes a hash value as a function of the bits in the message and transmits
both the hash value and the message.
o The receiver performs the same hash calculation on the message bits and compares this
value with the incoming hash value.
o If there is a mismatch, the receiver knows that the message (or possibly the hash value) has
been altered (Figure a).
o The hash value must be transmitted securely. That is, the hash value must be protected so
that if an adversary alters or replaces the message, it is not feasible for an adversary to also
alter the hash value to fool the receiver. This type of attack is shown in the next Figure . .
• A man-in-the-middle (MITM) attack is
a cyberattack where the attacker secretly relays and
possibly alters the communications between two
parties who believe that they are directly
communicating with each other, as the attacker has
inserted themselves between the two parties.
• The following are a variety of ways in which a hash code can be used to provide message
authentication.
a. The message plus concatenated hash code is encrypted using symmetric encryption. Because
only A and B share the secret key, the message must have come from A and has not been altered.
The hash code provides the structure or redundancy required to achieve authentication. Because
encryption is applied to the entire message plus hash code, confidentiality is also provided.
b. Only the hash code is encrypted, using symmetric encryption. This reduces the processing burden
for those applications that do not require confidentiality.

c. It is possible to use a hash function but no encryption for message authentication. The technique
assumes that the two communicating parties share a common secret value S. A computes the hash
value over the concatenation of M and S and appends the resulting hash value to M. Because B
possesses S, it can re-compute the hash value to verify. Because the secret value itself is not sent,
an opponent cannot modify an intercepted message and cannot generate a false message.
d. Confidentiality can be added to the approach of method (c) by encrypting the entire message
plus the hash code.
 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 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.
Reference:

• Introduction to Modern Cryptography , 2021 , By JonathanKatz, Yehuda Lindell

• An Introduction Cryptography ,2020 , By Nigel Smart.
• Real world Cryptography,2021, by David Wong.
• The Mathematics of Encryption,2021, By Margaret Cozzens, Steven J. Miller