Cryptography & Network Security

Module IV – Study Notes

Cryptographic Hash Functions, MACs, Digital Signatures & Key Management

Dr. Naga Jyothi Pothabathula | GITAM University, Visakhapatnam

1. Introduction to Cryptographic Hash Functions

1.1 What is a 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)
• A change to any bit or bits in M results, with high probability, in a change to the hash code.
• The kind of hash function needed for security applications is a cryptographic hash function.

1.2 Properties of Cryptographic Hash Functions

• One-Way Property: It is computationally infeasible to find a data object that maps to a pre-specified hash
result.
• Collision-Free Property: It is computationally infeasible to find two data objects that map to the same
hash result.

1.3 General Operation

• The input is padded out to an integer multiple of some fixed length (e.g., 1024 bits).
• The padding includes the value of the length of the original message in bits.
• The length field is a security measure to increase difficulty for an attacker to produce an alternative
message with the same hash value.

2. Applications of Cryptographic Hash Functions

2.1 Message Authentication

Message authentication is concerned with:
• Protecting the integrity of a message
• Validating identity of originator
• Non-repudiation of origin (dispute resolution)

Three alternative functions used for message authentication:

 • Message Encryption
• Message Authentication Code (MAC)
• Hash Function

2.2 Hash Code Usage – Four Schemes

• Scheme (a): Message + concatenated hash code encrypted with symmetric key. Provides both
authentication AND confidentiality.
• Scheme (b): Only the hash code is encrypted using symmetric encryption. Provides authentication only
(no confidentiality). Faster due to smaller data encrypted.
• Scheme (c): Source A computes hash over concatenation of M and shared secret S: H(M||S). Provides
authentication only — no encryption used.
• Scheme (d): Extends Scheme (c) by encrypting entire message + hash code. Provides both confidentiality
and authenticity.

2.3 Digital Signatures

• In 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 message integrity.
• An attacker who wishes to alter the message would need to know the user's private key.

2.4 Other Applications

• One-way password files
• Intrusion detection and virus detection
• Pseudorandom function (PRF) or pseudorandom number generator (PRNG)
• Generation of symmetric keys

3. Secure Hash Algorithm (SHA)

3.1 History of SHA

• Most widely used hash function.
• Developed by NIST, published as FIPS 180 in 1993.
• SHA-0 was revised in 1995 as SHA-1 (produces 160-bit hash value).
• SHA is based on the design of MD4 with key differences.
• NIST issued revision FIPS 180-2 in 2002 with SHA-256, SHA-384, SHA-512.
• Designed for compatibility with increased security provided by AES.

3.2 SHA Parameter Comparison

 Algorithm Message Size Block Size (bits) Word Size (bits) Digest Size
(bits)

SHA-1 < 2^64 512 32 160

SHA-224 < 2^64 512 32 224

SHA-256 < 2^64 512 32 256

SHA-384 < 2^128 1024 64 384

SHA-512 < 2^128 1024 64 512

SHA-512/224 < 2^128 1024 64 224

SHA-512/256 < 2^128 1024 64 256

4. SHA-512 Algorithm

4.1 SHA-512 Overview

• Takes input message with maximum length less than 2^128 bits.
• Produces 512-bit message digest.
• Input processed in 1024-bit blocks.

4.2 SHA-512 Steps

Step 1: Append Padding Bits
• Message padded so its length ≡ 896 (mod 1024).
• Number of padding bits is in range 1 to 1024.
• Padding: single '1' bit followed by necessary number of '0' bits.

📌 Note: Example: For message 'abc' (24 bits), we need 24+872 = 896 ≡ 896 mod 1024. Pad with 1 bit
followed by 871 zeros.

Step 2: Append Length

• A 128-bit block is appended to the message.
• Treated as unsigned 128-bit integer (MSB first).
• Contains the length of the original message in bits.
• Total after padding + length = multiple of 1024 bits.

Step 3: Initialize Hash Buffer

• A 512-bit buffer holds intermediate and final results.
• Represented as eight 64-bit registers (a, b, c, d, e, f, g, h).
Initial values (hexadecimal):
a=6A09E667F3BCC908 e=510E527FADE682D1
 b=BB67AE8584CAA73B f=9B05688C2B3E6C1F
c=3C6EF372FE94F82B g=1F83D9ABFB41BD6B
d=A54FF53A5F1D36F1 h=5BE0CD19137E2179

Step 4: Process Message in 1024-bit Blocks

• Heart of the algorithm is a module consisting of 80 rounds.
• Each round takes as input the 512-bit buffer value (abcdefgh) and updates it.
• The output of round 80 is added to the input of round 1 to produce H_i.

Step 5: Output
• After all 1024-bit blocks are processed, the output from the Nth stage is the 512-bit message digest.

4.3 Message Scheduling (Module F, Step 1)

• 1024-bit block M_i is divided into 80 words (W_0 to W_79), each 64 bits.
• First 16 values W_0 to W_15 taken directly from 16 words of the current block.
Remaining 64 words derived using:
W_t = σ1^512(W_{t-2}) + W_{t-7} + σ0^512(W_{t-15}) + W_{t-16}
Where:
• σ0^512(x) = ROTR^1(x) ⊕ ROTR^8(x) ⊕ SHR^7(x)
• σ1^512(x) = ROTR^19(x) ⊕ ROTR^61(x) ⊕ SHR^6(x)
• ROTR^n(x) = circular right shift of 64-bit argument x by n bits
• SHR^n(x) = right shift of 64-bit argument x by n bits with zero padding

4.4 SHA-512 Round Function

Each of the 80 rounds is defined by:
T1 = h + Ch(e,f,g) + Σ1^512(e) + W_t + K_t
T2 = Σ0^512(a) + Maj(a,b,c)
h=g, g=f, f=e, e=d+T1, d=c, c=b, b=a, a=T1+T2
Where:
• Ch(e,f,g) = (e AND f) ⊕ (NOT e AND g) — conditional: if e then f else g
• Maj(a,b,c) = (a AND b) ⊕ (a AND c) ⊕ (b AND c) — majority function
• Σ0^512(a) = ROTR^28(a) ⊕ ROTR^34(a) ⊕ ROTR^39(a)
• Σ1^512(e) = ROTR^14(e) ⊕ ROTR^18(e) ⊕ ROTR^41(e)

📌 Note: Observation: Six of eight output words involve only permutation. Only two words (a, e) are
generated by substitution.
4.5 Weakness in SHA-512
• Difficulty of finding two messages with same digest: ~2^256 operations.
• Difficulty of finding a message with a given digest: ~2^512 operations.

5. Message Authentication Codes (MAC)

5.1 Definition
A MAC (Message Authentication Code) is an algorithm that requires use of a secret key.
• Takes a variable-length message and secret key as input.
• Produces an authentication code.
• Recipient with the secret key can generate an authentication code to verify message integrity.

MAC = MAC(K, M)
Where M = input message, K = shared secret key

5.2 MAC vs Hash

• MAC is a many-to-one function — many messages may share same MAC.
• MAC provides authentication without requiring encryption of full message.
• A MAC is NOT a digital signature — it does not provide non-repudiation.

5.3 MAC Requirements

• Knowing a message and MAC, it must be infeasible to find another message with same MAC.
• MACs should be uniformly distributed.
• MAC should depend equally on all bits of the message.

5.4 Message Authentication Requirements

In network communications, following attacks must be addressed:
• Disclosure
• Traffic analysis
• Masquerade
• Content modification
• Sequence modification
• Timing modification
• Source repudiation
• Destination repudiation
5.5 Message Authentication Functions
• Hash Function: Maps message of any length into fixed-length hash value (authenticator).
• Message Encryption: Ciphertext of the entire message serves as its authenticator.
• MAC: Function of message and secret key producing a fixed-length value serving as authenticator.

5.6 Security of MACs

Two categories of attacks:
• Brute-force attacks: Strong collision resistance hash costs 2^(m/2). At least 128-bit MAC needed for
security.
• Cryptanalytic attacks: Exploit structure of the MAC algorithm.

6. HMAC

6.1 Why HMAC?

• Original proposal for MAC using hash: KeyedHash = Hash(Key|Message).
• Weaknesses were found → led to HMAC (RFC 2104).

6.2 HMAC Design Objectives (RFC 2104)

• Use available hash functions without modification.
• Allow easy replaceability of the embedded hash function.
• Preserve original performance of the hash function.
• Use and handle keys in a simple way.
• Have well-understood cryptographic analysis of strength.

6.3 HMAC Notation

Key parameters:
• H = embedded hash function (MD5, SHA-1, RIPEMD-160)
• b = number of bits in a block
• n = length of hash code produced
• K = secret key (recommended length ≥ n)
• K+ = K padded with zeros on left so result is b bits long
• ipad = 00110110 (0x36) repeated b/8 times
• opad = 01011100 (0x5C) repeated b/8 times

6.4 HMAC Formula

HMAC(K, M) = H[(K+ ⊕ opad) || H[(K+ ⊕ ipad) || M]]
6.5 HMAC Algorithm Steps
• Step 1: Append zeros to left end of K to create b-bit string K+
• Step 2: XOR K+ with ipad to produce b-bit block Si
• Step 3: Append M to Si
• Step 4: Apply H to stream from Step 3
• Step 5: XOR K+ with opad to produce b-bit block S0
• Step 6: Append hash result from Step 4 to S0
• Step 7: Apply H to stream from Step 6 and output the result

📌 Note: Security of HMAC: Attacking requires either brute-force on the key or birthday attack (requiring
observation of very large number of messages).

7. MACs Based on Block Ciphers: DAA and CMAC

7.1 Data Authentication Algorithm (DAA)

• Based on DES, one of the most widely used MACs.
• Uses cipher block chaining (CBC) mode of DES with initialization vector of zero.
• Data grouped into 64-bit blocks; final block padded with zeros.
Calculation:
O1 = E(K, D1)
O2 = E(K, D2 ⊕ O1)
ON = E(K, DN ⊕ ON-1)
• DAC = entire block or leftmost bits of the block ON.

7.2 Cipher-Based MAC (CMAC)

• Adopted by NIST — mode of operation for AES and triple DES.
• Specified in NIST Special Publication 800-38B.
• For AES: b = 128 bits; for triple DES: b = 64 bits.
• Uses k-bit encryption key K and n-bit constant K1 (or K2 for non-integer-multiple case).
Two cases:
• Case (a): Message length is integer multiple of block size → XOR last block with K1 before final encryption.
• Case (b): Message length is NOT integer multiple → pad last block with '10...0', then XOR with K2.

8. Digital Signatures

8.1 Introduction
• A digital signature is an authentication mechanism enabling the creator to attach a code acting as a
signature.
 • Formed by taking hash of message and encrypting with creator's private key.
• Guarantees source and integrity of message.
• The Digital Signature Standard (DSS) is an NIST standard using SHA.

Key facts about DSS:

• US Government approved signature scheme
• Designed by NIST & NSA in early 1990s
• Published as FIPS-186 in 1991; revised in 1993, 1996, 2000
• DSS is the standard; DSA is the algorithm
• DSA is digital signature only — unlike RSA
• It is a public-key technique

8.2 Digital Signature Properties

• Verify author, date & time of signature.
• Authenticate message contents.
• Be verified by third parties to resolve disputes.
• Include authentication function with additional capabilities.

8.3 Digital Signature Requirements

• Must depend on the message signed.
• Must use information unique to sender (prevents forgery and denial).
• Must be relatively easy to produce.
• Must be relatively easy to recognize and verify.
• Computationally infeasible to forge.
• Be practical to save in storage.

8.4 Direct Digital Signature

• Involves only sender and receiver.
• Receiver is assumed to have sender's public key.
• Signature made by sender signing entire message or hash with private key.
• Can also encrypt using receiver's public key.
• Important: sign first, then encrypt message & signature.
• Security depends on sender's private key.

8.5 DSS – Digital Signature Standard

• Creates: 320-bit signature
• Security: 512–1024 bit security
• Advantage: Smaller and faster than RSA
• Purpose: Digital signature only (not encryption)
 • Security basis: Difficulty of computing discrete logarithms
• Based on: Variant of ElGamal & Schnorr schemes

8.6 DSS Signing and Verifying

Global Public-Key Components
• p = prime number where 2^(L-1) < p < 2^L (512 ≤ L ≤ 1024, L multiple of 64)
• q = prime divisor of (p-1), where 2^159 < q < 2^160 (160 bits)
• g = h^((p-1)/q) mod p, where h is any integer 1 < h < (p-1)

Keys
• Private key x: random integer with 0 < x < q
• Public key y = g^x mod p
• Per-message secret k: random/pseudorandom with 0 < k < q

Signing
r = (g^k mod p) mod q
s = [k^(-1)(H(M) + xr)] mod q
Signature = (r, s)

Verifying
w = (s')^(-1) mod q
u1 = [H(M')w] mod q
u2 = (r')w mod q
v = [(g^u1 · y^u2) mod p] mod q
TEST: v = r' → Signature is valid

8.7 Attacks and Forgeries

Types of Attacks
• Key-only attack
• Known message attack
• Generic chosen message attack
• Directed chosen message attack
• Adaptive chosen message attack

Break Success Levels

• Total break
• Universal forgery
• Selective forgery
 • Existential forgery

9. Key Management and Distribution

9.1 Overview
• Strength of cryptographic system rests with the Key Distribution Mechanism.
• Key Distribution = function that exchanges a key between two parties in encrypted form.
• Involves master keys (infrequently used, long-lasting) and session keys (temporary).
• Public-key encryption is secure only if authenticity of the public key is assured.

9.2 Distribution of Public Keys – Four Approaches

• Public Announcement: Any participant broadcasts their public key. Major weakness: anyone can forge
such an announcement.
• Publicly Available Directory: A trusted authority maintains a {name, public key} directory. Participants
register public keys. Can replace keys when compromised.
• Public-Key Authority: Tighter control — central authority maintains dynamic directory. Each participant
knows authority's public key. Requires real-time access; can be a bottleneck.
• Public-Key Certificates: Uses X.509 certificates signed by a Certification Authority (CA). Certificates can be
stored publicly — unforgeable.

9.3 Key Distribution Issues

• Hierarchies of KDCs required for large networks.
• Session key lifetimes should be limited for greater security.
• Use of decentralized key distribution.
• Controlling key usage.

10. X.509 Authentication Service

10.1 Overview
• Part of CCITT X.500 directory service standards.
• Defines framework for authentication services.
• Directory may store public-key certificates.
• Uses public-key crypto and digital signatures (RSA recommended).
• Has 3 versions.

10.2 X.509 Certificate Fields

Notation: CA<<A>> = CA{V, SN, AI, CA, UCA, A, UA, Ap, TA}
 Field Description

V (Version) Version of certificate (1, 2, or 3)

SN (Serial Number) Unique within CA, identifies certificate

AI (Algorithm ID) Identifier of algorithm used to sign certificate

CA (Issuer Name) X.500 name of Certification Authority

TA (Validity Period) From–to dates of certificate validity

A (Subject Name) X.500 name of the owner

Ap (Public Key) Algorithm, parameters, and key of subject

UCA Optional unique identifier of CA (v2+)

UA Optional unique identifier of subject (v2+)

Extensions Extension fields (v3 only)

Signature Hash of all fields, encrypted with CA's private key

10.3 X.509 Certificate Use

• Unsigned certificate contains user ID and user's public key.
• Hash code of unsigned certificate is generated.
• Hash code is signed with CA's private key to form signature.
• Signed certificate: recipient can verify signature using CA's public key.

10.4 CA Hierarchy
• If both users share a common CA, they are assumed to know its public key.
• CAs form a hierarchy — use certificates linking members to validate other CAs.
• Each CA has certificates for clients (forward) and parent (backward).
• Enables verification of any certificate from one CA by users of all other CAs.

10.5 Certificate Revocation

Certificates may need revocation before expiry if:
• User's private key is compromised
• User is no longer certified by this CA
• CA's certificate is compromised

• CAs maintain a Certificate Revocation List (CRL).

• Users should check certificates with CA's CRL.

10.6 X.509 Version 3 Extensions

Extensions consist of: extension identifier, criticality indicator, extension value.
 • Key and Policy Information: Convey info about subject & issuer keys, plus certificate policy indicators.
• Certificate Subject and Issuer Attributes: Support alternative names and formats for certificate
subject/issuer.
• Certificate Path Constraints: Allow constraints on use of certificates by other CAs.

11. Quick Reference Summary

Topic Key Points

Hash Function Variable input → fixed output; one-way; collision-free

SHA-512 80 rounds; 1024-bit blocks; 512-bit digest; 8 x 64-bit registers

MAC Requires secret key; provides authentication; not a digital signature

HMAC Hash-based MAC; uses ipad (0x36) and opad (0x5C); double hashing

DAA DES-based MAC; CBC mode with IV=0; outputs leftmost bits of final block

CMAC AES/Triple-DES based; NIST standard SP 800-38B; handles variable-length

messages

Digital Signature Private key encrypts hash; public key verifies; provides non-repudiation

DSS/DSA 160-bit (r,s) signature; 512–1024 bit security; uses discrete logarithm

X.509 CA-issued certificates; version 1/2/3; used for public key authentication

CRL Certificate Revocation List; maintained by CA; users must check before
use

— End of Unit 4 Notes —