Applied Cryptography

Chapter 5
Hashing Algorithms and Public Key Digital Signatures
Hash Algorithms
Hash Algorithms
• It is a mathematical function that takes an input of arbitrary size (such as
data, a file, or a key) and converts it into a fixed-size value called a hash
or hash code.
• The output is typically a sequence of numbers or characters and is
designed to uniquely represent the input data.
• Hashing algorithms are commonly used for fast data retrieval, data
integrity verification, and security applications such as password storage
and digital signatures.
• A good hashing algorithm produces the same hash for the same input,
minimizes collisions (different inputs producing the same hash), and
makes it computationally infeasible to reconstruct the original input from
the hash.
Hash Algorithms
• There are clear similarities in the evolution of hash functions and block
ciphers.
• The increasing computational power available for brute-force attacks has driven
changes in cryptographic design.
• This increase in attack capability has led to the continuous evolution of
cryptographic algorithms.
• In block ciphers, this evolution is seen in the transition from DES to AES.
• In hash algorithms, it is reflected in the progression from MD4 and MD5 to SHA-1
and RIPEMD-160.
• Like block ciphers, modern hash functions often employ a common
iterative structure in their design.
MD5
• Designed by Ronald Rivest (the R in RSA)
• It is the latest algorithm in the MD family, following MD2 and MD4.
• MD5 produces a 128-bit hash value.
• Until recently, MD5 was the most widely used hashing algorithm.
• In recent years, MD5 has faced serious brute-force and cryptanalytic security
concerns.
• MD5 is specified as an Internet standard in RFC 1321.
MD5 Overview
1. Pad the message so that its length is congruent to 448 modulo 512.
2. Append a 64-bit value representing the original message length.
3. Initialize a 4-word (128-bit) MD buffer, labeled A, B, C, and D.
4. Process the message in 16-word (512-bit) blocks.
• For each block, perform four rounds, each consisting of 16 bitwise operations
on the message block and the buffer.
• Add the output of each block’s processing to the current buffer value to form
a new buffer.
5. The final hash value is obtained from the final buffer contents.
MD5 Overview
MD5 Overview
MD5 Compression Function
• In the MD5 compression function, each round consists of 16 steps.
• Each step has the general form:
a = b+((a+g(b,c,d)+X[k]+T[i])<<<s)
• The variables a, b, c, and d represent the four words of the MD
buffer, used in different permutations during the computation.
• Each step updates only one word of the buffer.
• After completing 16 steps, each buffer word is updated four times.
• The function g(b, c, d) is a nonlinear Boolean function, which differs
in each round (F, G, H, and I).
• T[i] is a constant value derived from the sine function.
MD5 Compression Function
MD5 Compression Function
• Initialize MD buffer: Here, we use the 4
buffers i.e. A B, C, and D. The size of each
buffer is 32 bits.

A = 0x67425301
B = 0xEDFCBA45
C = 0x98CBADFE
D = 0x13DCE476
Strength of MD5
• The MD5 hash value depends on all bits of the input message.
• Ronald Rivest claimed that the security of MD5 is as strong as possible for
its design.
• Several cryptanalytic attacks on MD5 have been reported, including:
• Berson (1992), who successfully attacked a single round of MD5 using differential
cryptanalysis, but was unable to extend the attack to the full algorithm.
• Boer and Bosselaers (1993), who discovered a pseudo-collision, though they could
not extend it to a full collision.
• Dobbertin (1996), who generated collisions in the MD compression function, but
these could not be exploited due to the use of initial constants.
• The overall conclusion is that MD5 appears increasingly vulnerable and is
likely to be broken in the near future.
MD5
• Is MD5 secure? No
• Collision vulnerability: MD5 produces 128-bit hashes, but researchers have found
practical methods to create two different messages with the same hash
(collisions).
• Known attacks: Since the early 1990s, attacks such as differential cryptanalysis
and collision generation have been demonstrated. By 2004, full collision attacks
became practical.
• Cryptographic consequences: Because of collisions, MD5 should not be used for
digital signatures, certificates, or security-critical applications. Attackers could
exploit collisions to forge documents or certificates.
• Modern alternatives: SHA-256, SHA-3, and RIPEMD-160 are widely recommended
instead of MD5.
MD4
• MD4 is the precursor to MD5.
• It also produces a 128-bit hash value of the input message.
• MD4 uses three rounds of 16 steps, compared to four rounds in
MD5.
• The design goals of MD4 include:
• Collision resistance, making it difficult to find two messages with the same
hash.
• Direct security, meaning it does not rely on external “hard” mathematical
problems.
• Being fast, simple, and compact in implementation.
• Optimization for little-endian systems, such as personal computers.
Secure Hash Algorithm (SHA-1)
• The Secure Hash Algorithm (SHA-1) was designed by NIST and the NSA in
1993, and revised in 1995 as SHA-1.
• SHA-1 is a U.S. federal standard used with the Digital Signature Algorithm
(DSA).
• The standard is specified in FIPS 180-1 (1995) and also published as Internet RFC
3174.
• The algorithm is called SHA, while the standard is known as the Secure Hash
Standard (SHS).
• SHA-1 produces 160-bit hash values.
• It has been generally preferred over earlier hash algorithms.
• SHA-1 is based on the design of MD4, but includes important structural
differences to improve security.
SHA Overview
1. Pad the message so that its length is congruent to 448 modulo 512.
2. Append a 64-bit value representing the original message length.
3. Initialize a 5-word (160-bit) buffer, labeled A, B, C, D, and E, with
the values: (67452301, EFCDAB89, 98BADCFE, 10325476,
C3D2E1F0).
4. Process the message in 16-word (512-bit) blocks.
• Expand the 16 words into 80 words using bit mixing and shifting operations.
• Perform four rounds, each consisting of 20 bitwise operations, on the
message block and the buffer.
• Add the output of each block’s processing to the current buffer to form a new
buffer value.
5. The final hash value is obtained from the final buffer contents.
SHA-1 Compression Function
• In the SHA-1 compression function, each round consists of 20 steps.
• Each step updates the 5 buffer words according to the formula:
(A, B, C, D, E) ← (E + f(t, B, C, D) + (A << 5) + Wt + Kt, A, (B <<
30), C, D)
• A, B, C, D, E are the five words of the buffer, with A–D being used in
permutations during the computation.
• t is the step number within the round.
• f(t, B, C, D) is a nonlinear Boolean function that varies depending
on the round.
• Wt is a word derived from the expanded message block.
• Kt is a constant value derived from the sine function.
SHA-1 Compression Function
SHA-1 verses MD5
• Brute-force attacks are harder on SHA-1 than on MD5, because SHA-1
uses 160-bit hash values, compared to 128-bit hashes in MD5.
• SHA-1 is not vulnerable to the known attacks that affect MD4 and
MD5.
• SHA-1 is slightly slower than MD5, as it uses 80 steps compared to 64
steps in MD5.
• Both SHA-1 and MD5 were designed to be simple and compact.
• SHA-1 is optimized for big-endian CPU architectures, whereas MD5 is
optimized for little-endian CPUs.
Revised Secure Hash Standard
• NIST issued a revision of the Secure Hash Standard as FIPS 180-2.
• This revision adds three new hash algorithms: SHA-256, SHA-384, and
SHA-512.
• These algorithms were designed to be compatible with the increased
security strength of the AES cipher.
• Their structure and operational details are similar to SHA-1.
• As a result, the cryptanalytic analysis approaches for these algorithms
are expected to be similar to those used for SHA-1.
 Revised Secure Hash Standard
A revised document was issued as FIP PUB 180-3 in 2008, which added a
224-bit version.
RIPEMD-160
• RIPEMD-160 was developed in Europe in 1996 as part of the RIPE project.
• It was designed by researchers who were involved in cryptanalytic attacks
on MD4 and MD5.
• The initial proposal was strengthened based on cryptanalysis, resulting in
the final algorithm known as RIPEMD-160.
• RIPEMD-160 is somewhat similar in structure to MD5 and SHA.
• It uses two parallel processing lines, each consisting of five rounds of 16
steps.
• RIPEMD-160 produces a 160-bit hash value.
• It is slower than SHA, but is considered probably more secure.
RIPEMD-160 Overview
1. Pad the message so that its length is congruent to 448 modulo 512.
2. Append a 64-bit value representing the original message length to
the message.
3. Initialize a 5-word (160-bit) buffer, labeled A, B, C, D, and E, with the
values: (67452301, EFCDAB89, 98BADCFE, 10325476, C3D2E1F0).
4. Process the message in 16-word (512-bit) blocks.
• For each block, perform 10 rounds of 16 bitwise operations on the message
block and the buffer, organized into two parallel lines of five rounds each.
• Add the output of each block’s processing to the input buffer to form a new
buffer value.
5. The final hash value is obtained from the final buffer contents.
RIPEMD-160 Round
RIPEMD-160 Compression Function
RIPEMD-160 Design Criteria
• The algorithm uses two parallel processing lines, each consisting of
five rounds, to increase overall complexity.
• For simplicity, the two parallel lines are very similar in structure.
• The step operation is very close to that used in MD5.
• Permutations are applied to vary which parts of the message are
used in each step.
• Circular shift operations are carefully designed to achieve optimal
security and diffusion.
RIPEMD-160 verses MD5 & SHA-1
• Brute-force attacks are harder because the algorithm uses 160-bit hash
values (similar to SHA-1), compared to 128-bit hashes in MD5.
• It is not vulnerable to the known attacks that affect MD4 and MD5,
and is considered stronger, comparable to or better than SHA-1.
• It is slower than MD5 due to a larger number of processing steps.
• All of these hash algorithms were designed to be simple and compact.
• SHA-1 is optimized for big-endian CPU architectures, whereas
RIPEMD-160 and MD5 are optimized for little-endian CPUs.
Keyed Hash Functions as MACs
• have desire to create a MAC using a hash function rather than a block
cipher
• because hash functions are generally faster
• not limited by export controls unlike block ciphers
• hash includes a key along with the message
• original proposal:
KeyedHash = Hash(Key|Message)
• some weaknesses were found with this
• eventually led to development of HMAC
HMAC
• specified as Internet standard RFC2104
• uses hash function on the message:
HMACK = Hash[(K+ XOR opad) ||
Hash[(K+ XOR ipad)||M)]]
• where K+ is the key padded out to size
• and opad, ipad are specified padding constants
• overhead is just 3 more hash calculations than the message needs
alone
• any of MD5, SHA-1, RIPEMD-160 can be used
HMAC Overview
HMAC Security
• know that the security of HMAC relates to that of the underlying hash
algorithm
• attacking HMAC requires either:
• brute force attack on key used
• birthday attack (but since keyed would need to observe a very large number
of messages)
• choose hash function used based on speed verses security constraints
Digital Signatures
Digital Signatures
• Message authentication techniques have been studied, but they do
not address the problem of a lack of trust between parties.
• Digital signatures provide the ability to:
• Verify the author of a message.
• Verify the date and time at which the message was signed.
• Authenticate the contents of the message.
• Be verified by third parties to help resolve disputes.
• Therefore, digital signatures include message authentication
functions along with additional trust-related capabilities.
Digital Signature Properties
• A digital signature must depend on the specific message being signed.
• It must use information unique to the sender.
• This uniqueness helps prevent both forgery and denial (repudiation).
• A digital signature should be relatively easy to generate by the legitimate
sender.
• It should be relatively easy to recognize and verify by others.
• It must be computationally infeasible to forge, including:
• Creating a new message that matches an existing digital signature.
• Creating a fraudulent digital signature for a given message.
• It should be practical to store the digital signature for future verification.
Direct Digital Signatures
• Direct digital signatures involve only the sender and the receiver.
• It is assumed that the receiver already possesses the sender’s public key.
• The sender creates the digital signature by signing the entire message or a
hash of the message using their private key.
• The message and signature may then be encrypted using the receiver’s
public key for confidentiality.
• It is important to sign the message first and then encrypt both the message
and the signature.
• The security of this approach depends on the protection of the sender’s
private key.
Arbitrated Digital Signatures
• It involves the use of a trusted arbiter (A).
• The arbiter validates any signed message before it is accepted.
• After validation, the message is dated and forwarded to the recipient.
• This approach requires a suitable level of trust in the arbiter.
• It can be implemented using either private-key or public-key
cryptographic algorithms.
• Depending on the implementation, the arbiter may or may not have
access to the message contents.
Authentication Protocols
• Are used to convince communicating parties of each other’s identity
and to exchange session keys securely.
• These protocols may provide one-way authentication or mutual
authentication.
• The key issues in authentication protocols include:
• Confidentiality, to protect session keys from disclosure.
• Timeliness, to prevent replay attacks.
Replay Attacks
• These attacks occur when a valid signed message is copied and resent at a
later time.
• Types of replay attacks include:
• Simple replay, where a previously valid message is resent.
• Repetition that can be logged, allowing detection through records.
• Repetition that cannot be detected, making the attack harder to identify.
• Backward replay without modification, where old messages are resent unchanged.
• Countermeasures against replay attacks include:
• The use of sequence numbers, though this is generally impractical.
• Timestamps, which require synchronized clocks between parties.
• Challenge–response mechanisms, using a unique nonce for each session.
Using Symmetric Encryption
• When using symmetric encryption, a two-level hierarchy of keys can
be employed.
• This approach typically involves a trusted Key Distribution Center
(KDC).
• Each communicating party shares its own master key with the KDC.
• The KDC generates session keys for secure connections between parties.
• Master keys are used to securely distribute the session keys to the
communicating parties.
Needham-Schroeder Protocol
• The Needham–Schroeder protocol is an original third-party key distribution protocol.
• It is used to establish a session between two parties (A and B), mediated by a Key
Distribution Center (KDC).
• The protocol operates as follows:
1. A → KDC: A sends its identity (IDA), B’s identity (IDB), and a nonce (N1).
2. KDC → A: The KDC replies with a message encrypted using A’s master key (EKa),
containing the session key (Ks), B’s identity, the nonce N1, and a ticket for B
encrypted with B’s master key (EKb[Ks || IDA]).
3. A → B: A forwards the ticket EKb[Ks || IDA] to B.
4. B → A: B challenges A by sending a nonce (N2) encrypted with the session key
(EKs[N2]).
5. A → B: A responds by returning a function of the nonce (f(N2)) encrypted with the
session key, confirming possession of Ks.
Needham-Schroeder Protocol
• Assumptions
• A trusted Key Distribution Center
(KDC) exists.
• Each user shares a long-term secret
key with the KDC.
• The network is insecure and may be
monitored by attackers.
• Security Properties
• Provides mutual authentication.
• Ensures confidentiality of the
session key.
• Relies on trusted third-party
security.
Needham-Schroeder Protocol
• This protocol is used to securely distribute a new session key for
communication between A and B.
• However, it is vulnerable to a replay attack if an old session key is
compromised.
• In such a case, message 3 can be replayed, misleading B into believing it is
communicating with A.
• To address this vulnerability, the protocol has been modified to
include:
• Timestamps, as proposed by Denning (1981).
• The use of an additional nonce, as proposed by Neuman (1993).
Using Public-Key Encryption
• Public-key encryption supports a range of authentication approaches
based on the use of public–private key pairs.
• It is essential to ensure the authenticity of public keys belonging to
other parties.
• This is often achieved by using a central Authentication Server (AS).
• Various authentication protocols exist that rely on timestamps or
nonces to ensure freshness and prevent replay attacks.
Denning Authentication Server (AS) Protocol
• The Denning Authentication Server (AS) Protocol was presented in Denning, 1981.
• The protocol operates as follows:
• A → AS: A sends its identity (IDA) and B’s identity (IDB) to the Authentication Server.
• AS → A: The AS replies with two encrypted messages:
• EKRas[IDA || KUa || T] for A
• EKRas[IDB || KUb || T] for B
• where T is a timestamp and KRas is the key shared with the AS.
• A → B: A forwards to B:
• EKRas[IDA || KUa || T]
• EKRas[IDB || KUb || T]
• EKUb[EKRas[Ks || T]], where Ks is the session key chosen by A and encrypted for B.
• The session key is chosen by A, so the AS does not need to be fully trusted to protect it.
• Timestamps prevent replay attacks, but their use requires synchronized clocks between
parties.
One-Way Authentication
• One-way authentication is required when the sender and receiver
are not communicating at the same time, such as in email.
• The message may include a header in clear text so it can be delivered
by the email system.
• It is often desirable for the body of the message to be protected
while also allowing the sender to be authenticated.
Using Symmetric Encryption
• When using symmetric encryption, the use of a Key Distribution Center
(KDC) can be refined, but the final exchange of nonces may not be possible.
• The protocol operates as follows:
1. A → KDC: A sends its identity (IDA), B’s identity (IDB), and a nonce (N1)
to the KDC.
2. KDC → A: The KDC replies with EKa[Ks || IDB || N1 || EKb[Ks || IDA]],
where Ks is the session key.
3. A → B: A sends EKb[Ks || IDA] || EKs[M], delivering the session key and
the encrypted message.
• This approach does not protect against replay attacks.
• One possible mitigation is to include a timestamp in the message, though email delays
can make this unreliable.
Public-Key Approaches
• Public-key approaches provide several methods for secure
communication.
• If confidentiality is the primary concern, one approach is:
• A → B: EKUb[Ks] || EKs[M], where Ks is a session key, and M is the message.
• This ensures that both the session key and the message are encrypted.
• If authentication is also required, a digital signature with a digital
certificate can be used:
• A → B: M || EKRa[H(M)] || EKRas[T || IDA || KUa], where:
• H(M) is the hash of the message (digital signature),
• EKRa[H(M)] is the signature using A’s private key,
• EKRas[T || IDA || KUa] is the certificate containing a timestamp, sender ID, and public key.
• This approach ensures message authenticity, integrity, and trust.
Digital Signature Standard (DSS)
• The U.S. government–approved digital signature scheme specified in FIPS
186.
• DSS uses the SHA hash algorithm for message hashing.
• It was designed by NIST and the NSA in the early 1990s.
• DSS refers to the standard, while DSA refers to the digital signature algorithm
defined by the standard.
• DSA is a variant of the ElGamal and Schnorr signature schemes.
• It generates a 320-bit digital signature, providing 512–1024-bit security
strength depending on parameters.
• The security of DSS/DSA relies on the difficulty of computing discrete
logarithms in a finite field.
DSA Key Generation
• DSA key generation begins with shared global public key parameters:
p, q, and g.
• p is a large prime, where p = 2L and L ranges from 512 to 1024 bits (multiple
of 64).
• q is a 160-bit prime factor of p − 1.
• g is computed as g = h((p−1)/q) mod p, where h < p − 1 and h((p−1)/q) mod p > 1.
• Each user selects a private key x, where x < q.
• The corresponding public key y is computed as y = gx mod p.
DSA Signature Creation
• To sign a message M using DSA, the sender performs the following
steps:
• Generate a random signature key k, where k < q.
• Important: k must be truly random, destroyed after use, and never reused.
• Compute the signature pair (r, s):
• r = (gk mod p) mod q
• s = (k⁻¹ · SHA(M) + x·r) mod q, where x is the sender’s private
key.
• Send the signature (r, s) along with the message M to the
recipient.
DSA Signature Verification
• Upon receiving a message M and its DSA signature (r, s), the
recipient verifies the signature as follows:
• Compute w = s⁻¹ mod q.
• Compute u₁ = (SHA(M) · w) mod q.
• Compute u₂ = (r · w) mod q.
• Compute v = ((gu₁ · yu₂) mod p) mod q, where y is the sender’s
public key.
• If v = r, then the signature is verified as valid.
• For the detailed mathematical proof, refer to the textbook or its
accompanying website.
Summary
• We have considered digital signatures and their role in message
authentication and integrity.
• We have examined authentication protocols, including both mutual
and one-way authentication.
• We have reviewed the Digital Signature Standard (DSS) and its
associated Digital Signature Algorithm (DSA).
Key-Exchange Algorithms
Introduction to Key-Exchange Algorithms
• Purpose: Enable secure sharing of cryptographic keys between
parties.
• Goal: Ensure confidentiality, integrity, and authentication during key
exchange.
• Types: Symmetric vs Public-Key based key exchange.
 Recap on Diffie-Hellman Key Exchange
• Diffie-Hellman Key Exchange is the first practical public-key key-exchange
protocol.
• It allows two parties to agree on a shared secret even over an insecure channel.
• Steps:
• Agree on a large prime number (p) and a base (g).
• Each party selects a private key (a for A, b for B) and computes public values:
• A computes A = ga mod p
• B computes B = gb mod p
• Exchange the public values, then compute the shared secret:
• A computes s = Ba mod p
• B computes s = Ab mod p
• Security: Based on the difficulty of solving the discrete logarithm problem.
• Visual: Step-by-step diagram showing the public value exchange and shared
secret computation.
Station-to-Station (STS) Protocol
• Station-to-Station (STS) Protocol enhances Diffie-Hellman by providing
mutual authentication.
• It uses digital signatures and public-key encryption to prevent man-in-
the-middle attacks.
• Key features:
• Diffie-Hellman for secure key agreement.
• Digital signatures to authenticate the communicating parties.
• Optional encryption to ensure the confidentiality of exchanged data.
Station-to-Station (STS) Protocol
Shamir's Three-Pass Protocol
• Shamir’s Three-Pass Protocol enables secure key exchange without
requiring shared secrets or pre-shared keys.
• It relies on commutative encryption functions, where E(E(M)) = E(E(M)).
• Steps:
• A encrypts the message or key with their secret and sends it to B.
• B encrypts the received message again with their secret and sends it back to A.
• A removes their encryption and sends the result back to B.
• Result: B obtains the original message or key.
• Security: The message is never transmitted in plaintext, maintaining
confidentiality.
Shamir's Three-Pass Protocol
COMSET (Commercial SET Protocol)
• It is a key-exchange protocol designed for secure online transactions.
• It combines symmetric and public-key cryptography for secure
communication.
• Purpose: To securely distribute session keys for e-commerce and
online payment systems.
• Key features:
• Authentication of the sender and receiver.
• Confidentiality of the session key during distribution.
• Visual: Diagram showing client ↔ server session key exchange.
Encrypted Key Exchange (EKE)
• Combines password-based authentication with public-key encryption.
• Prevents offline dictionary attacks.
• Steps:
1. User encrypts public key with password.
2. Server decrypts, exchanges session key.

• Used in secure password-authenticated key exchange (PAKE)

protocols.
Fortified Key Negotiation
• Strengthened key negotiation protocols to resist:
✦Man-in-the-middle attacks
✦Replay attacks
✦Compromised keys
• Often combines symmetric and asymmetric techniques, sometimes
with nonces or timestamps.
• Goal: robust, authenticated, and forward-secure key establishment.
Conference Key Distribution & Secret Broadcasting
• Conference Key Distribution:
✧Distributes a shared session key to multiple parties for group communication.
✧Example: Secure conference calls, video meetings.
• Secret Broadcasting:
• Sender broadcasts encrypted messages so that only authorized recipients can
decrypt.
• Uses techniques like tree-based key
management or subset key sharing.

Tree diagram showing sender → multiple recipients

 Comparison of Key-Exchange Algorithms
Algorithm Type Security Basis Strengths Weaknesses
Diffie-Hellman Public-key Discrete logarithm Simple, well-known No authentication
Mutual
STS Public-key DH + signatures Slightly complex
authentication

Commutative Requires
Shamir 3-pass Commutative No prior key needed
encryption commutative cipher

Limited to
COMSET Symmetric + PK Transactional E-commerce ready
commercial use
EKE PK + password Encrypted exchange Password-secure More computation
Fortified Symmetric + PK Hybrid Resistant to attacks Complexity
Conference/Secret Multi-party Key management
Symmetric Group key
Broadcast communication overhead
Key Takeaways
• Key-exchange algorithms establish session keys securely over
insecure channels.
• Authentication and protection against replay/MITM attacks are
crucial.
• Different protocols suit different scenarios: two-party, multi-party,
password-based, or e-commerce.
• Modern applications combine efficiency, security, and scalability.
Thank you!