BCSE-309L: Cryptography

and Network Security

PREPARED BY
[Link] SHAMALA
SCOPE/VIT
Module 4: Message Digest and Hash
Functions
1. Cryptographic hash functions
2. Applications
3. Requirements
4. Security
5. MD5
6. SHA-512
7. Message Authentication Codes- HMAC
VIT/SCOPE/BCSE-309L/MODULE 4 2
What ciphers do?
Encryption
◦ Provide confidentiality
◦ Eve can’t see what Alice and Bob are saying
◦ Can Eve do anything?
C= Encrypt(M)

?
Alice Bob
Eve

VIT/SCOPE/BCSE-309L/MODULE 4 4
What ciphers can’t do?
• Suppose Eve can get between Alice and Bob
• What if Eve can manipulate the data?

Alice sent me M’
I’ll send Bob M
C= Encrypt(M)

Eve replaces M with M’

Alice Bob

VIT/SCOPE/BCSE-309L/MODULE 4 6
Hash Function
▪ Hashing function as
“chewing” or “digest”
function
◦ called the message digest
▪ A message digest is as a
``digital fingerprint'' of the
original document

A hash function H accepts a variable-length

block of data M as input and produces a fixed-
size hash value
h = H(M)
VIT/SCOPE/BCSE-309L/MODULE 4 8
Hash Function…
▪ The purpose of a hash function is to provide data integrity.
▪ The kind of hash function needed for security applications is
called a cryptographic hash function.
▪ 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)
◦ two data objects that map to the same hash result (the
collision-free property)

VIT/SCOPE/BCSE-309L/MODULE 4 9
 Hashing Vs Encryption
Hello, world. k NhbXBsZSBzZW50ZW5jZS
A sample sentence to E B0byBzaG93IEVuY3J5cHR
show encryption. pb24KsZSBzZ

Hello, world. k
NhbXBsZSBzZW50ZW5jZS
A sample sentence to D
B0byBzaG93IEVuY3J5cHR
show encryption. pb24KsZSBzZ

 Encryption is two way, and requires a key to encrypt/decrypt

This is a clear text that

can easily read without 52f21cf7c7034a20
using the key. The
h 17a21e17e061a863
sentence is longer than
the text above.

 Hashing is one- way. There is no ‘de-hashing’

VIT/SCOPE/BCSE-309L/MODULE 4 10
Applications of Cryptographic Hash
Functions
1. Message Authentication
2. Digital Signatures
3. Other Applications

VIT/SCOPE/BCSE-309L/MODULE 4 12
Message
Authentication
▪ Message
authentication
assures that data
received are exactly
as sent.
▪ When a hash function
is used to provide
message
authentication, the
hash function value is
often referred to as a
message digest.

VIT/SCOPE/BCSE-309L/MODULE 4 13
 Attack
Against
Hash
Function

VIT/SCOPE/BCSE-309L/MODULE 4 14
Message Authentication..
Hash code can be used to provide message authentication in
the following ways:
a) The message plus concatenated hash code is encrypted using
symmetric encryption.
b) Only the hash code is encrypted, using symmetric encryption.
c) Use hash function but no encryption for message
authentication.
d) Confidentiality can be added to the approach of (c) by
encrypting the entire message plus the hash code.

VIT/SCOPE/BCSE-309L/MODULE 4 15
 Use Hash Function for Message
Authentication
Symmetric Key
Unkeyed Hash

a) Message
encrypted
Message encrypted : Confidentiality and authentication

b) Message
unencrypted

Message unencrypted: Authentication

VIT/SCOPE/BCSE-309L/MODULE 4 16
 Use Hash Function for Message
Authentication
Symmetric Key
Keyed Hash

c) Message
unencrypted
Message unencrypted : Authentication (no encryption needed!)

d) Message
encrypted

Message encrypted: Authentication, confidentiality

VIT/SCOPE/BCSE-309L/MODULE 4 17
Message Authentication..
There has been growing interest in techniques that avoid
encryption due to several reasons:
◦ Encryption software is relatively slow.
◦ Encryption hardware costs are not negligible.
◦ Encryption hardware is optimized for large data sizes.
◦ Encryption algorithms may be covered by patents and licensing
costs.

VIT/SCOPE/BCSE-309L/MODULE 4 18
 Message Authentication Code (MAC)
▪ Also known as a keyed hash function
▪ Typically used between two parties that share a secret key to authenticate
information exchanged between those parties
A MAC function takes as input a secret key and a data block and produces a
hash value (MAC) which is associated with the protected message
• If the integrity of the message needs to be checked, the MAC function can
be applied to the message and the result compared with the associated
MAC value
• An attacker who alters the message will be unable to alter the associated
MAC value without knowledge of the secret key

© 2020 PEARSON EDUCATION, INC., HOBOKEN, NJ. ALL RIGHTS RESERVED.

Digital Signatures
▪ A digital signature is a mathematical scheme for verifying
the authenticity of digital messages or documents
▪ Ensures non-repudiation.
▪ The hash value of a message is encrypted with a user's
private key→ Signing
▪ Anyone who knows the user's public key can verify the
integrity of the message that is associated with the digital
signature→ Verification

VIT/SCOPE/BCSE-309L/MODULE 4 20
 Hash Function Usages

Authentication, digital signature

Authentication, digital signature, confidentiality

VIT/SCOPE/BCSE-309L/MODULE 4 21
Other Applications
▪ To create a one-way password file
◦ store hash of password not actual password
▪ For intrusion detection and virus detection
◦ keep & check the hash of files on a system
▪ To construct a pseudorandom function (PRF) or a pseudorandom number
generator (PRNG).
◦ Generate session keys, nonces
◦ Produce key from password
◦ Derive keys from the master key cooperatively
◦ Vernam Cipher/OTP

VIT/SCOPE/BCSE-309L/MODULE 4 23
Simple Hash Functions
▪ Bit-by-bit exclusive-OR (XOR) of every block.
◦ This can be expressed as Ci = bi1 ⊕ bi2 ⊕ … ⊕ bim
◦ Produces a simple parity for each bit position and is known as a
longitudinal redundancy check
◦ Reasonably effective for random data as a data integrity check
▪ Perform a one-bit circular shift, or rotation, on the hash
value after each block is processed
◦ Has the effect of randomizing the input more completely and
overcoming any regularities that appear in the input
VIT/SCOPE/BCSE-309L/MODULE 4 24
 Two Simple
Hash
Functions

VIT/SCOPE/BCSE-309L/MODULE 4 25
Requirements of Hash Functions
▪ 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 the function H, is
h.
▪ For any given hash value h, there will 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 undesirable.

VIT/SCOPE/BCSE-309L/MODULE 4 27
Requirements of Hash Functions…
▪ Arbitrary-length message to fixed-length digest
▪ Preimage resistant (One-way property)
▪ Given h(M), difficult to find M’ s.t. h(M’)=h(M)
▪ Second preimage resistant (Weak collision resistant)
▪ Given M, difficult to find M’ s.t. h(M’)=h(M), M’≠M
▪ Collision resistant (Strong collision resistance)
▪ Difficult to find any pair (M, M’) with M’≠ M s.t. h(M) = h(M’)
▪ If a hash function h does not meet these requirements…

VIT/SCOPE/BCSE-309L/MODULE 4 28
Properties: Fixed length
Hello, world 661dce0da2bcb2d8
h 2884e0162acf8194

Fixed length L
This is a clear text that
can easily read without
52f21cf7c7034a20
using the key. The h
17a21e17e061a863
sentence is longer than
the text above.

Arbitrary-length message to fixed-length digest

VIT/SCOPE/BCSE-309L/MODULE 4 29
 Preimage resistant
This measures how difficult to devise a message that hashes to the known digest
Roughly speaking, the hash function must be one-way.

Given only a message digest, can’t find any message (or preimage)
that generates that digest.

VIT/SCOPE/BCSE-309L/MODULE 4 30
 Second preimage resistant
 This measures how difficult to devise a message which hashes to the known
digest and its message

Given one message, can’t find another message that has the same message digest. An attack that
finds a second message with the same message digest is a second pre-image attack.
◦ It would be easy to forge new digital signatures from old signatures if the hash function used
weren’t second preimage resistant

VIT/SCOPE/BCSE-309L/MODULE 4 31
 Collision Resistant

◦ Can’t find any two different messages with the same message digest
◦ Collision resistance implies second preimage resistance
◦ Collisions, if we could find them, would give signatories a way to repudiate their
signatures
VIT/SCOPE/BCSE-309L/MODULE 4 32
 Requirements for a Cryptographic Hash Function H

• A hash function that satisfies the first five properties is referred to as a weak hash function.
• If the sixth property, collision resistant, is also satisfied, then it is referred to as a strong hash
function.
• A strong hash function protects against an attack in which one party generates a message for
another party to sign

VIT/SCOPE/BCSE-309L/MODULE 4 33
Attacks on Hash Functions
BRUTE-FORCE ATTACKS CRYPTANALYSIS
Does not depend on the specific An attack based on weaknesses in a
algorithm, only depends on bit length particular cryptographic algorithm
In the case of a hash function, attack Seek to exploit some property of the
depends only on the bit length of the algorithm to perform some attack
hash value other than an exhaustive search
Method is to pick values at random
and try each one until a collision
occurs

© 2020 PEARSON EDUCATION, INC., HOBOKEN, NJ. ALL RIGHTS RESERVED.

Attacks on Hash Functions
Brute-force attacks
▪ A preimage or second preimage attack
◦ Find y such that H(y)equals a given hash value
▪ Collision resistance
◦ Find two messages x & y with same hash so H(x) = H(y)
For a hash code of length m, the level of effort required is
proportional to the following

VIT/SCOPE/BCSE-309L/MODULE 4 37
 The effort required for collision resistant attack is
explained by birthday paradox

Yuval proposed the following strategy to exploit the

birthday paradox in a collision resistant attack:
• given user A prepared to sign a valid message x
m
• opponent generates 2 /2 variations x’ of x, all with
Birthday Paradox essentially the same meaning, and saves them
• opponent prepares a fraudulent message y for which A’s
signature is desired
m
• opponent generates 2 /2 variations y’ of y
How many people are
• two sets of messages are compared to find a pair with same
needed at a party such hash (probability > 0.5 by birthday paradox)
that there is a reasonable • have user sign the valid message, then substitute the
forgery which will have a valid signature
chance that at least two
people have the same Conclusion is that need to use larger MAC/hash
birthday?
Attacks on Hash Functions…
Cryptanalysis
▪ Cryptanalytic attacks exploit some property of algorithm so faster
than exhaustive search
▪ Hash functions use iterative structure
◦ Process message in blocks (including length)
▪ Attacks focus on collisions in function f

VIT/SCOPE/BCSE-309L/MODULE 4 41
MD5
▪ Designed by Ron Rivest in 1991.
▪ MD5 processes a variable-length message into a fixed-length output of
128 bits.
▪ The input message is broken up into chunks of 512-bit blocks
Step1 : The message is padded so that its length is divisible by 512.
o a single bit, 1 followed by as many zeros to bring the length 64 bits
fewer than a multiple of 512
o The remaining bits are filled with 64 bits representing the length of
the original message, modulo 264

VIT/SCOPE/BCSE-309L/MODULE 4 42
Padding Example
Given is the message “abc” consisting of three 8-bit ASCII
characters with a total length of l = 24 bits. Find the total number of
pad bits
k ≡ 512−64−l
k ≡ 448−l= 448−24= 424 mod 512.

VIT/SCOPE/BCSE-309L/MODULE 4 43
2. Initialize Buffers
▪ MD5 algorithm operates on a 128-bit state, divided into four 32-bit
words, denoted A, B, C, and D.
▪ These are initialized to certain fixed constants.
A = 01 23 45 67
B = 89 AB CD EF
C = FE DC BA 98
D = 76 54 32 10

VIT/SCOPE/BCSE-309L/MODULE 4 44
3. Processing of Message Block
▪ The algorithm uses each 512-bit message block to modify the
state.
▪ Divides the message block into 16, 32-bit words
M0, M1, M2,…M15
▪ The processing of a message block consists of 4 rounds
▪ Each round is composed of 16 similar operations based on a non-
linear function F, modular addition, and left rotation.
▪ An operation of MD5 is defined as
A = B ⊞ (( A ⊞ f(B, C, D) ⊞ Mi ⊞ Ki ) <<<s )

VIT/SCOPE/BCSE-309L/MODULE 4 45
Processing of Message Block…
// s specifies the per-round shift amounts
s[ 0..15] := { 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22 }
s[16..31] := { 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20 }
s[32..47] := { 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23 }
s[48..63] := { 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21 }
// Use binary integer part of the sines of integers (Radians) as
constants:
for i from 0 to 63 do K[i] := floor(232 × abs(sin(i + 1))) end for

VIT/SCOPE/BCSE-309L/MODULE 4 46
ONE MD5
Operation

VIT/SCOPE/BCSE-309L/MODULE 4 47
MD5…
▪ There are four possible functions; a different one is used in each
round:

⊕, ⋀, ‫ ¬ 𝑑𝑛𝑎 ڀ‬denote the XOR, AND, OR and NOT operations

respectively.

VIT/SCOPE/BCSE-309L/MODULE 4 48
Example
The quick brown fox jumps over the lazy dog
9e107d9d372bb6826bd81d3542a419d6
MD5("") = d41d8cd98f00b204e9800998ecf8427e

VIT/SCOPE/BCSE-309L/MODULE 4 49
VIT/SCOPE/BCSE-309L/MODULE 4 50
Secure Hash Algorithm
▪ SHA was originally designed by NIST & NSA in 1993
◦ Based on design of MD4 with key differences
▪ US standard for use with DSA signature scheme
◦ Revised in 1995 as SHA-1
◦ Standard is FIPS 180-1, also Internet RFC3174
▪ Produces 160-bit hash values
▪ In 2005, results on the security of SHA-1 raised concerns about its
use in future applications

VIT/SCOPE/BCSE-309L/MODULE 4 51
Revised SHA
▪ In 2002, NIST produced a revised version of the standard (
FIPS 180-2) that defined three new versions of SHA with hash
value lengths of 256, 384, and 512
◦ SHA-256, SHA-384, SHA-512
◦ Collectively known as SHA-2
▪ Designed for compatibility with increased security provided by
the AES cipher
▪ Structure & detail are similar to SHA-1
▪ Security levels are rather higher

VIT/SCOPE/BCSE-309L/MODULE 4 52
Revised SHA…
▪ A revised document was issued as FIP 180-3 in 2008,
which added a 224-bit version.
▪ SHA-2 is also specified in RFC 4634
▪ In 2015, NIST issued FIPS 180-4, which added two
additional algorithms: SHA-512/224 and SHA-512/256.

VIT/SCOPE/BCSE-309L/MODULE 4 53
SHA Versions

VIT/SCOPE/BCSE-309L/MODULE 4 54
General Structure of Secure Hash Code

VIT/SCOPE/BCSE-309L/MODULE 4 55
Secure Hash Code
▪ The hash algorithm involves repeated use of a compression function, f, that
takes two inputs and produces an n-bit output.
◦ an n-bit input from the previous step, called the chaining variable
◦ a b-bit block
▪ At the start of hashing, the chaining variable has an initial value that is
specified as part of the algorithm.
▪ The final value of the chaining variable is the hash value
▪ The hash function can be summarized as:
CV0 = IV = initial n-bit value
CVi = f(CVi-1, Yi-1) 1 ≤ i ≤ L
H(M) = CVL
where the input to the hash function is a message M consisting of the blocks Y0, Y1, … , YL-1

VIT/SCOPE/BCSE-309L/MODULE 4 56
Message Digest Generation using SHA-512

VIT/SCOPE/BCSE-309L/MODULE 4 58
SHA-512
The processing consists of the following steps:
1. Append padding bits
2. Append length.
3. Initialize hash buffer.
4. Process message in 1024-bit (128-byte) blocks
5. Output the final state value as the resulting hash

VIT/SCOPE/BCSE-309L/MODULE 4 59
 Padding and length field in SHA-512

What is the number of padding bits if the length of the original message is
2590 bits?
We can calculate the number of padding bits as follows:

The padding consists of one 1 followed by 353 0’s.

VIT/SCOPE/BCSE-309L/MODULE 4 60
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 the following 64-bit integers.

VIT/SCOPE/BCSE-309L/MODULE 4 61
4. SHA-512 Compression Function
▪ Heart of the algorithm
▪ Processes message in 1024-bit blocks
▪ Consists of 80 rounds
◦ Updating a 512-bit buffer
◦ using a 64-bit value Wt derived from the current message block
◦ A round constant Kt based on cube root of first 80 prime numbers
▪The output of the 80th round is added to input of first round
to produce the final hash value for this message block

VIT/SCOPE/BCSE-309L/MODULE 4 62
 SHA-512
Processing of a
Single 1024-Bit
Block
SHA-512…
We can summarize the behavior of SHA-512 as follows:

VIT/SCOPE/BCSE-309L/MODULE 4 64
SHA-512 Round Function
Each round is defined by the
following set of equations:

VIT/SCOPE/BCSE-309L/MODULE 4 65
The SHA-512 algorithm has the property that every bit of the hash
code is a function of every bit of the input.

VIT/SCOPE/BCSE-309L/MODULE 4 66
Creation of 80 - word Input Sequence for SHA-512
Processing of Single Block

VIT/SCOPE/BCSE-309L/MODULE 4 67
The padded message consists blocks M1, M2, … MN. Each message block Mi consists of 16 64-
bit words Mi,0, Mi,1 … Mi,15. All addition is performed modulo 264.

H0,0 = 6A09E667F3BCC908 H0,4 = 510E527FADE682D1

H0,1 = BB67AE8584CAA73B H0,5 = 9B05688C2B3E6C1F
H0,2 = 3C6EF372FE94F82B H0,6 = 1F83D9ABFB41BD6B
H0,3 = A54FF53A5F1D36F1 H0,7 = 5BE0CDI9137E2179

for i = 1 to N
1. Prepare the message schedule W:
for t = 0 to 15
Wt = Mi,t
for t = 16 to 79
Wt = s 1512 (Wt-2 ) + Wt-7 + s 0512 (Wt-15 ) + Wt-16
2. Initialize the working variables
a = Hi–1,0 e = Hi–1,4
b = Hi–1,1 f = Hi–1,5
c = Hi–1,2 g = Hi–1,6
d = Hi–1,3 h = Hi–1,7
3. Perform the main hash computation
for t = 0 to 79
T1 = h + Ch(e, f, g) + (å e) + W + K
512
1 t t

T2 = (å a) + Maj(a, b, c)
512
0
h = g
g = f
f = e
e = d + T1
d = c
c = b
b = a
a = T1 + T2
4. Compute the intermediate hash value
Hi,0 = a + Hi–1,0 Hi,4 = e + Hi–1,4
Hi,1 = b + Hi–1,1 Hi,5 = f + Hi–1,5
Hi,2 = c + Hi–1,2 Hi,6 = g + Hi–1,6
Hi,3 = d + Hi–1,3 Hi,7 = h + Hi–1,7
return {HN,0 || HN,1 || HN,2 || HN,3 || HN,4 || HN,5 || HN,6 || HN,7}

Figure 11.13 SHA-512 Logic

Example 1
▪ Consider one- block message consisting of three ASCII characters:
“abc,”
▪ The equivalent binary string is: 01100001 01100010 01100011
▪ After padding, the 1024-bit message block, in hexadecimal, is
6162638000000000 0000000000000000 0000000000000000 0000000000000000
0000000000000000 0000000000000000 0000000000000000 0000000000000000
0000000000000000 0000000000000000 0000000000000000 0000000000000000
0000000000000000 0000000000000000 0000000000000000 0000000000000018

VIT/SCOPE/BCSE-309L/MODULE 4 69
Example 1…
This block is assigned to the words W0, . . . , W15 of the message
schedule
W0 = 6162638000000000 W8 = 0000000000000000
W1 = 0000000000000000 W9 = 0000000000000000
W2 = 0000000000000000 W10 = 0000000000000000
W3 = 0000000000000000 W11 = 0000000000000000
W4 = 0000000000000000 W12 = 0000000000000000
W5 = 0000000000000000 W13 = 0000000000000000
W6 = 0000000000000000 W14 = 0000000000000000
W7 = 0000000000000000 W15 = 0000000000000018
VIT/SCOPE/BCSE-309L/MODULE 4 70
Example 1…
▪ The initial values of buffer variables a though h and their
values after each of the first two rounds are as follows:

VIT/SCOPE/BCSE-309L/MODULE 4 71
Example 1…
▪ The process continues through 80 rounds.
▪ The output of the final round is
73a54f399fa4b1b2 10d9c4c4295599f6
d67806db8b148677 654ef9abec389ca9
d08446aa79693ed7 9bb4d39778c07f9e
25c96a7768fb2aa3 ceb9fc3691ce8326

VIT/SCOPE/BCSE-309L/MODULE 4 72
Example 1…
The hash value is then calculated as
H1,0 = 6a09e667f3bcc908 + 73a54f399fa4b1b2 = ddaf35a193617aba
H1,1 = bb67ae8584caa73b + 10d9c4c4295599f6 = cc417349ae204131
H1,2 = 3c6ef372fe94f82b + d67806db8b148677 = 12e6fa4e89a97ea2
H1,3 = a54ff53a5f1d36f1 + 654ef9abec389ca9 = 0a9eeee64b55d39a
H1,4 = 510e527fade682d1 + d08446aa79693ed7 = 2192992a274fc1a8
H1,5 = 9b05688c2b3e6c1f + 9bb4d39778c07f9e = 36ba3c23a3feebbd
H1,6 = 1f83d9abfb41bd6b + 25c96a7768fb2aa3 = 454d4423643ce80e
H1,7 = 5be0cd19137e2179 + ceb9fc3691ce8326 = 2a9ac94fa54ca49f

VIT/SCOPE/BCSE-309L/MODULE 4 73
Example 1…
The resulting 512-bit message digest is:
ddaf35a193617aba cc417349ae204131
12e6fa4e89a97ea2 0a9eeee64b55d39a
2192992a274fc1a8 36ba3c23a3feebbd
454d4423643ce80e 2a9ac94fa54ca49f

VIT/SCOPE/BCSE-309L/MODULE 4 74
Example 2
▪ Suppose now that we change the input message by one bit, from “abc”
to “cbc.”
▪ Then, the 1024-bit message block is
6362638000000000 0000000000000000 0000000000000000 0000000000000000
0000000000000000 0000000000000000 0000000000000000 0000000000000000
0000000000000000 0000000000000000 0000000000000000 0000000000000000
0000000000000000 0000000000000000 0000000000000000 0000000000000018
▪ And the resulting 512-bit message digest is
531668966ee79b70 0b8e593261101354 4273f7ef7b31f279 2a7ef68d53f93264
319c165ad96d9187 55e6a204c2607e27 6e05cdf993a64c85 ef9e1e125c0f925f

VIT/SCOPE/BCSE-309L/MODULE 4 75
The need of new Hash standard
▪ MD5 should be considered cryptographically broken and
unsuitable for further use, US CERT 2010
▪ In 2004, a collision for the full SHA-0 algorithm was announced
▪ SHA-1 not yet fully “broken”
◦ but similar to the broken MD5 & SHA-0
◦ so considered insecure and be fade out
▪ SHA-2 (esp. SHA-512) seems secure
◦ shares same structure and mathematical operations as predecessors so have
concern

VIT/SCOPE/BCSE-309L/MODULE 4 76
SHA-3 Requirements
▪ NIST announced in 2007 a competition for the SHA-3 next
generation hash function
▪ Replace SHA-2 with SHA-3 in any use
◦ use same hash sizes
▪ Preserve the nature of SHA-2 (Must process small blocks (512 /
1024 bits)
▪ Evaluation criteria
◦ Security close to theoretical max for hash sizes
◦ Cost in time & memory
◦ Characteristics: such as flexibility & simplicity
▪ The winning design(Keccak) for SHA-3 was announced by NIST in
October 2012 and published as FIP 102 in August 2015.
VIT/SCOPE/BCSE-309L/MODULE 4 77
Review Questions
1) In SHA-512, show the value of the length field in
hexadecimal for the following message lengths:
◦ 1000 bits
◦ 10,000 bits
◦ 1000,000 bits
2) What is the padding for SHA-512 if the length of the
message is:
◦ 5120 bits
◦ 5121 bits
◦ 6143 bits
VIT/SCOPE/BCSE-309L/MODULE 4 78
Message Authentication
Code

VIT/SCOPE/BCSE-309L/CNS/MODULE 5 79
Network Attacks
Disclosure Sequence modification
◦ Release of message contents to any ◦ Any modification to a sequence of
person or process not possessing the messages between parties, including
appropriate cryptographic key insertion, deletion, and reordering
Traffic analysis Timing modification
◦ Discovery of the pattern of traffic ◦ Delay or replay of messages
between parties
Source repudiation
Masquerade ◦ Denial of transmission of message by
◦ Insertion of messages into the network source
from a fraudulent source
Destination repudiation
Content modification ◦ Denial of receipt of message by
◦ Changes to the contents of a message, destination
including insertion, deletion,
transposition, and modification

VIT/SCOPE/BCSE-309L/CNS/MODULE 5 80
Message Authentication
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.
More commonly, message authentication is achieved using
a message authentication code (MAC), also known as a
keyed hash function.

VIT/SCOPE/BCSE-309L/CNS/MODULE 5 81
Message Authentication Functions
Two levels of functionality: ◦ Hash function
◦ A function that maps a message of
Lower level any length into a fixed-length hash
• There must be some sort of function value which serves as the
that produces an authenticator authenticator
◦ Message encryption
◦ The ciphertext of the entire
message serves as its authenticator
◦ Message authentication code
(MAC)
◦ A function of the message and a
Higher-level
secret key that produces a fixed-
• Uses the lower-level function as a length value that serves as the
primitive in an authentication protocol
that enables a receiver to verify the
authenticator
authenticity of a message VIT/SCOPE/BCSE-309L/CNS/MODULE 5 82
Basic Uses of
Message
Encryption

83
 Message Authentication Code (MAC)
▪ Also known as a keyed hash function
▪ Typically used between two parties that share a secret key to
authenticate information exchanged between those parties
A MAC function takes as input a secret key and a data block and produces
a hash value (MAC) which is associated with the protected message
• If the integrity of the message needs to be checked, the MAC function can be
applied to the message and the result compared with the associated MAC value
• An attacker who alters the message will be unable to alter the associated MAC
value without knowledge of the secret key

© 2020 PEARSON EDUCATION, INC., HOBOKEN, NJ. ALL RIGHTS RESERVED.

Message Authentication Code
A small fixed-length value that serves as the authenticator
Generated from message + secret key
MAC = C(K,M)
Appended to message when sent
A MAC function is similar to encryption.
One difference is that the MAC algorithm need not be reversible, as
it must be for decryption.
It is a many-to-one function.

VIT/SCOPE/BCSE-309L/CNS/MODULE 5 85
Basic Uses of
MAC
• MAC provides
authentication
• Can also use encryption
for secrecy
• Use separate keys for
each
• Can compute MAC
either before or after
encryption

VIT/SCOPE/BCSE-309L/CNS/MODULE 5 86
Message Authentication Code…
Why use a MAC?
◦ sometimes only authentication is needed
◦ sometimes need authentication to persist longer than the
encryption
Note that a MAC is not a digital signature
◦ Does NOT provide non-repudiation

VIT/SCOPE/BCSE-309L/CNS/MODULE 5 87
MAC requirements
A MAC, also known as a cryptographic checksum, is generated by a
function MAC of the form T = MAC(K, M)
where M is a variable-length message
K is a secret key shared only by sender and receiver
MAC(K, M) is the fixed-length authenticator, sometimes called a tag
Assume that an opponent knows the MAC function but does not
know K.
Then the MAC function should satisfy the following requirements:
1. Knowing a message and MAC, is infeasible to find another message
with same MAC
2. MACs should be uniformly distributed
3. MAC should depend equally on all bits of the message

VIT/SCOPE/BCSE-309L/CNS/MODULE 5 88
Security of MACs
Brute-Force Attack requires known message-tag pairs
◦ A brute-force method of finding a collision is to pick a random bit string y
and check if H(y) = H(x)

Two lines of attack:

• Attack the key space
• If an attacker can determine the MAC key, then it is
possible to generate a valid MAC value for any input x
• Attack the MAC value
• The objective is to generate a valid tag for a given
message or to find a message that matches a given tag

VIT/SCOPE/BCSE-309L/CNS/MODULE 5 89
Security of MACs …
Cryptanalytic attacks seek to exploit some property of the algorithm
to perform some attack other than an exhaustive search
An ideal MAC algorithm will require a cryptanalytic effort greater
than or equal to the brute-force effort
There is much more variety in the structure of MACs than in hash
functions, so it is difficult to generalize about the cryptanalysis of
MACs

VIT/SCOPE/BCSE-309L/CNS/MODULE 5 90
MACs Based on Hash Functions: HMAC
Want a MAC based on a hash function
◦ Hash functions execute faster in software than symmetric block
ciphers
◦ Library code for cryptographic hash functions is widely available
Hash includes a key along with message
Original proposal:
KeyedHash = Hash(Key|Message)
◦ some weaknesses were found with this
◦ Eventually led to the development of HMAC

VIT/SCOPE/BCSE-309L/CNS/MODULE 5 91
HMAC Design Objectives
▪ RFC 2104 lists the following design objectives for HMAC:
1. Use the available hash functions without modifications
2. Allow for easy replacement of embedded hash function
3. Preserve original performance of hash function without
significant degradation
4. Use and handle keys in a simple way.
5. Have well understood cryptographic analysis of authentication
mechanism strength

VIT/SCOPE/BCSE-309L/CNS/MODULE 5 93
HMAC
HMAC has been chosen as the mandatory-to-implement
MAC for IP security
Has also been issued as a NIST standard (FIPS 198)
Uses hash function on the message
Overhead is just 3 more hash block calculations than the
message needs alone
Any hash function can be used
◦ Example: MD5, SHA-1, RIPEMD-160, Whirlpool

VIT/SCOPE/BCSE-309L/CNS/MODULE 5 94
HMAC …
H = embedded hash function (e.g., MD5, SHA-1, RIPEMD-160)
IV = initial value input to hash function
M = message input to HMAC (including the padding specified in the embedded
hash function)
Yi = i th block of M, 0 ≤ i ≤ (L - 1)
L = number of blocks in M
b = number of bits in a block
n = length of hash code produced by embedded hash function
K = secret key; recommended length is ≥ n; if key length is greater than b, the
key is input to the hash function to produce an n-bit key
K+ = K padded with zeros on the left so that the result is b bits in length

VIT/SCOPE/BCSE-309L/CNS/MODULE 5 95
HMAC …
ipad = 00110110 (36 in hexadecimal) repeated b/8 times
opad = 01011100 (5C in hexadecimal) repeated b/8 times
Then HMAC can be expressed as:
HMACK(M)= Hash[(K+ XOR opad)||
Hash[(K+ XOR ipad)|| M)]]
◦ where K+ is the key padded out to block size
ipad is a pad value of 36 hex repeated to fill block
opad is a pad value of 5C hex repeated to fill block
M is the message input to HMAC

VIT/SCOPE/BCSE-309L/CNS/MODULE 5 96
HMAC Algorithm
1. Append zeros to the left end of K to create a b-bit string K+ (e.g., if K is of
length 160 bits and b = 512, then K will be appended with 44 zeroes).
2. XOR (bitwise exclusive-OR) K + with ipad to produce the b-bit block Si
3. Append M to Si .
4. Apply H to the stream generated in step 3.
5. XOR K+ with opad to produce the b-bit block S0.
6. Append the hash result from step 4 to S0.
7. Apply H to the stream generated in step 6 and output the result.

VIT/SCOPE/BCSE-309L/CNS/MODULE 5 97
HMAC Structure

98
Efficient
Implementation
of HMAC

VIT/SCOPE/BCSE-309L/CNS/MODULE 5 99
Security of HMAC…
Proved security of HMAC relates to that of the underlying
hash algorithm
Attacking HMAC requires either:
◦ brute force attack on key used
◦ birthday attack (very unlikely)

Choose hash function used based on speed verses security

constraints

VIT/SCOPE/BCSE-309L/CNS/MODULE 5 101
Example

VIT/SCOPE/BCSE-309L/CNS/MODULE 5 102