Hash Functions, MACs, and Digital Signatures

Introduction

Modern information systems must answer several related questions: Has this data been altered? Did it come from an authenticated source? Can a password be stored without storing the password itself? Can a recipient demonstrate that a particular signer approved a document? Hash functions, message authentication codes (MACs), password-hashing functions, and digital signatures provide different answers to these questions.

These mechanisms are related because they use cryptographic transformations, but they are not interchangeable. A cryptographic hash normally provides integrity evidence without proving who created a message. A MAC provides integrity and authentication to parties sharing a secret key. A digital signature uses asymmetric cryptography and can be verified using a public key. Password-hashing functions are deliberately expensive and specialised for protecting password verifiers against guessing attacks.

Learning Objectives

By the end of this chapter, you should be able to:

• explain the security properties and limitations of cryptographic hash functions;
• distinguish collision resistance, preimage resistance, and second-preimage resistance;
• use HMAC for message integrity and shared-key authentication;
• explain why ordinary hashes are unsuitable for password storage;
• describe how salts, work factors, and memory requirements improve password protection;
• explain the creation and verification of digital signatures;
• select an appropriate mechanism for integrity, authentication, evidence, and non-repudiation;
• identify implementation, governance, and operational risks.

1. Cryptographic Hash Functions

A cryptographic hash function maps an input of arbitrary length to a fixed-length output called a digest, hash, or message fingerprint. It is deterministic: identical inputs produce identical outputs. A small change in the input should produce a substantially different output, a property commonly called the avalanche effect.

A hash function is written as:

Here, m is the message, H is the hash algorithm, and h is the fixed-length digest. The digest is not encryption: it is normally infeasible to recover the original message from it, and there is no decryption key.

Important security properties are:

• Preimage resistance: Given a digest y, it should be computationally infeasible to find any message m such that H(m) = y.
• Second-preimage resistance: Given a specific message m₁, it should be infeasible to find a different message m₂ with H(m₁) = H(m₂).
• Collision resistance: It should be infeasible to find any two distinct messages m₁ and m₂ with the same digest.
• Avalanche behavior: Changing a small part of the input should produce an apparently unpredictable change in the output.

Because the output space is finite while the input space is effectively unlimited, collisions must exist mathematically. Security means that finding a useful collision is computationally impractical, not impossible.

Digest Length and the Birthday Effect

For an ideal hash with an n-bit output, a random preimage search requires approximately 2ⁿ trials on average in the generic case. A generic collision search requires approximately 2^n/2 trials because of the birthday effect. Thus, a 256-bit hash has approximately 128 bits of generic collision security, although real attacks depend on the algorithm and the attack model.

A useful approximation for the probability of at least one collision after hashing q randomly selected messages into 2ⁿ possible outputs is:

This approximation assumes independently and uniformly distributed outputs and is most useful when q is not close to the entire output space. It illustrates why collision resistance is not equal to digest length.

Common Hash Algorithms

MD5 and SHA-1 are unsuitable for security-critical collision-resistance applications because practical collision attacks exist. SHA-2, including SHA-256 and SHA-512, remains widely deployed. SHA-3 uses a different internal construction and is standardised for general cryptographic use. The correct choice depends on approved standards, platform support, interoperability, and the required security lifetime.

A hash can support software distribution, file-integrity monitoring, data deduplication, forensic evidence handling, and content addressing. However, publishing a file hash alone does not authenticate the publisher: an attacker who can replace both the file and its hash can preserve apparent consistency. An authenticated channel, MAC, or digital signature is needed when origin matters.

2. Message Authentication Codes

A message authentication code is a keyed authenticator. A sender and receiver share a secret key and compute a tag over a message:

The receiver recomputes the tag using the same key and accepts only if the received tag matches. A secure MAC provides message integrity and source authentication to parties that possess the key. It does not provide public verifiability: either key holder could have generated the tag.

HMAC

HMAC is a widely used MAC construction based on a cryptographic hash. In simplified notation:

Here, K′ is the key normalised to the hash block size, ipad and opad are fixed inner and outer padding constants, ⊕ means exclusive OR, and ∥ means concatenation. The formula assumes the standard HMAC construction and a secure underlying hash. Implementations should use a vetted library rather than reproducing this construction manually.

HMAC is appropriate for API request authentication, service-to-service messages, session tokens, and integrity-protected records. It does not encrypt the message, so confidentiality requires encryption as a separate control. It also does not stop replay by itself. Systems should include a timestamp, sequence number, nonce, or unique request identifier and enforce an acceptance policy.

Tags must be compared using a constant-time comparison routine where feasible. A conventional comparison that returns immediately at the first unequal byte may reveal information through timing differences. Keys should be generated randomly, stored in a key-management system, rotated according to policy, and separated by purpose.

Hashes versus HMAC

3. Password Hashing and Secure Credential Storage

Passwords have low and uneven entropy. A fast general-purpose hash is therefore dangerous for password storage: an attacker can obtain a database and test billions of guesses using specialised hardware. The system should store a password verifier, not the plaintext password, and should make each guess expensive.

A password-hashing record typically contains an algorithm identifier, a random salt, cost parameters, and the derived value:

The salt is not secret. Its purpose is to ensure that identical passwords receive different stored values and to defeat precomputed rainbow tables. Each account must have a unique, randomly generated salt with sufficient length for the selected standard. A salt does not make a weak password strong; it makes large-scale reuse and precomputation less effective.

Suitable contemporary choices include Argon2id, scrypt, and, in appropriate environments, bcrypt or PBKDF2. Memory-hard functions such as Argon2id and scrypt require substantial memory as well as computation, reducing the advantage of some parallel cracking hardware. PBKDF2 is widely standardised and can be appropriate where compatibility or regulatory requirements matter, but its parameters must be strong and current.

The work factor must be calibrated on the actual authentication infrastructure. A legitimate verification should take long enough to impede guessing but not so long that it creates denial-of-service risk. Parameters should be recorded with each password hash so that accounts can be upgraded during successful login. A server may also use a separate application-level pepper stored outside the password database, preferably in a secrets-management system or hardware security module.

Password storage should be complemented by rate limiting, breached-password screening, multi-factor authentication, secure reset procedures, and monitoring. Password hashes should not be used as encryption keys without an appropriate key derivation design, and passwords should not be encrypted merely because the application expects to recover them.

4. Digital Signatures

A digital signature uses asymmetric cryptography. A signer has a private key and a corresponding public key. The private key creates a signature over a message or its digest; anyone with the trusted public key can verify it.

A conceptual signing process is:

Verification is:

Here, sk is the private signing key, pk is the public verification key, σ is the signature, and m is the message. Actual algorithms define the encoding, hashing, randomness, and verification rules precisely. A signature must never be implemented by simply encrypting a hash with a private key.

A valid signature normally supports three conclusions: the signed data has not changed since signing; the signature was generated by the holder of the corresponding private key; and the public key is bound to an identity through an appropriate trust model. The last conclusion depends on certificates, key directories, trust anchors, or another reliable key-distribution process.

Digital signatures are used for software releases, electronic documents, certificates, secure email, code signing, package repositories, and supply-chain attestations. They offer public verifiability, unlike HMAC. They do not automatically provide confidentiality, and they do not prove that a human personally understood a document. Non-repudiation is a socio-technical and legal claim, not merely a mathematical property. It depends on private-key control, identity proofing, signing procedures, evidence preservation, and applicable law.

Signature Algorithms and Operational Controls

RSA-PSS, ECDSA, and EdDSA are examples of signature systems used in contemporary practice. Algorithm selection must consider standards, interoperability, key sizes, implementation quality, and lifecycle requirements. ECDSA requires secure, unique per-signature randomness; reuse or predictable generation can expose the private key. Deterministic variants reduce one class of randomness failure but still require correct implementation.

Private keys must be protected with access controls, encryption at rest, hardware-backed storage where justified, and audit logging. Organisations need certificate issuance, renewal, revocation, compromise response, and secure destruction procedures. Long-lived signatures may require archival timestamping and algorithm migration planning because algorithms and trust anchors can become obsolete.

5. Choosing the Right Mechanism

The design question should begin with the security claim, not the available library.

Authenticated encryption, such as an approved AEAD mode, is generally preferred when confidentiality and integrity are both required. Combining cryptographic primitives ad hoc can produce subtle vulnerabilities; use established protocol designs and reviewed libraries.

6. Applied Case: Signed Software Releases

Background. A small software company distributes updates through a public download server. Attackers previously replaced an installer on a compromised mirror. A published SHA-256 digest did not solve the problem because the attacker replaced the digest page as well.

Problem. Customers need assurance that an update originated from the company and has not been modified. The company also needs an auditable process for key compromise and employee departure.

Analysis. A bare hash offers integrity only when the digest is obtained through an independently trusted channel. HMAC would authenticate the update to customers only if every customer received and protected a shared secret, which is operationally unsuitable and would make public verification impossible. A digital signature allows customers to verify the release using a public key.

Approach. The company generates a signing key in a protected environment, stores the private key in a hardware-backed service, and publishes the verification key through its established website, package metadata, and documentation. The build pipeline produces a reproducible or traceable artifact. A release manifest contains filenames, versions, hashes, and metadata; the manifest is digitally signed. Release personnel require approval separation, and signing operations are logged. Customers verify the signature before using the hashes to validate individual files. The organisation publishes a key-rotation and revocation process and maintains an offline recovery strategy.

Outcome. An attacker who changes an installer or manifest without access to the private signing key produces an invalid signature. The design still requires customers to obtain the authentic public key initially and requires prompt response if the signing key is compromised.

Learning points. Hashes identify content, signatures authenticate a publisher, and trust depends on key distribution and operational controls. Cryptography cannot compensate for an untrusted initial key or an uncontrolled build pipeline.

7. Limitations, Ethics, and Governance

Cryptographic mechanisms can fail through poor key management, weak randomness, outdated algorithms, incorrect encoding, ambiguous message formats, logging of secrets, or inadequate incident response. Canonicalisation is especially important: two systems must sign and verify exactly the same bytes or an unambiguous representation. Length-extension vulnerabilities in some naive constructions show why a raw hash should not be used as a MAC; HMAC is designed for this purpose.

Password-hashing systems create an availability trade-off. Increasing cost improves resistance to offline guessing but increases authentication workload. Organisations should test capacity, rate-limit suspicious activity, and design recovery paths. They should never use password hashes to identify or profile individuals beyond legitimate security needs.

Digital signatures can be misused to create deceptive documents, automate harmful actions, or give unjustified confidence in an identity. Governance should define who may sign, what may be signed, approval thresholds, retention periods, accessibility requirements, and how disputes are handled. Legal recognition varies by jurisdiction, so technical evidence should be preserved with relevant records and legal advice.

Artificial intelligence systems introduce additional integrity concerns. Models, datasets, prompts, and generated artifacts may be signed or hashed to support provenance, but a signature proves control of a key at signing time; it does not prove that content is truthful, unbiased, safe, or human-authored. Provenance metadata should therefore be interpreted alongside process evidence and independent review.

8. Best Practices

1. Use modern, approved libraries and protocols; do not invent cryptographic constructions.
2. Prefer SHA-256, SHA-3, or another currently approved hash; retire MD5 and SHA-1 for security purposes.
3. Use HMAC for shared-secret authentication and include anti-replay data in the authenticated message.
4. Use a password-specific KDF with a unique random salt and a calibrated work factor.
5. Protect keys separately from the data they authenticate; apply least privilege and rotation.
6. Use constant-time comparison for secret-derived tags and carefully validate encodings.
7. Sign a canonical, well-defined representation and verify the entire security-relevant context.
8. Plan certificate, key, algorithm, and trust-anchor migration before compromise or obsolescence.
9. Log security events without logging passwords, private keys, or reusable authentication tags.
10. Test failure cases, including altered messages, missing keys, expired certificates, replayed requests, and malformed signatures.

Chapter Summary

Cryptographic hashes produce fixed-length digests and are useful for integrity and identification, but a plain hash does not authenticate its source. Collision resistance, preimage resistance, and second-preimage resistance describe different attack goals. HMAC adds a shared secret to provide message integrity and authentication, but it does not provide confidentiality, public verification, or replay protection by itself. Password-hashing functions use salts and substantial work, often including memory requirements, to make offline guessing more difficult. Digital signatures use private keys for signing and public keys for verification, enabling public verifiability when key identity is trustworthy. Correct mechanism selection, secure key management, canonical data formats, lifecycle planning, and governance are as important as the cryptographic primitive.

Key Terms

Cryptographic hash: A deterministic function that maps arbitrary-length input to a fixed-length digest.

Digest: The output produced by a cryptographic hash function.

Preimage resistance: Difficulty of finding an input for a chosen digest.

Second-preimage resistance: Difficulty of finding a different input with the same digest as a specified input.

Collision resistance: Difficulty of finding any two different inputs with the same digest.

Avalanche effect: Large apparent output change caused by a small input change.

MAC: A keyed message authentication code providing integrity and shared-key authentication.

HMAC: A standard MAC construction based on a cryptographic hash.

Salt: A public, random value added to password processing to make each password record unique.

Password KDF: A key derivation function designed to process passwords with an expensive work factor.

Work factor: Configured computational or memory cost of password verification.

Pepper: A secret application-wide value used in addition to password salts.

Digital signature: An asymmetric cryptographic proof created with a private key and checked with a public key.

Private key: Secret key used for signing or other private-key operations.

Public key: Distributable key used to verify signatures or perform other public-key operations.

Non-repudiation: A broader legal and evidentiary claim supported, but not guaranteed, by signatures and controls.

Replay attack: Reuse of a previously valid message or authenticator.

Canonicalisation: Conversion of data into a unique representation before hashing or signing.

Key rotation: Planned replacement of cryptographic keys.

Review Questions

5 Short Answer Questions

1. What is the difference between a cryptographic hash and encryption?
2. Define collision resistance and preimage resistance.
3. Why does HMAC require a secret key?
4. What purpose does a salt serve in password storage?
5. Why does a digital signature not provide confidentiality?

5 Long Answer Questions

1. Explain the security properties of cryptographic hashes and discuss the birthday effect.
2. Describe HMAC operation, appropriate uses, and limitations.
3. Compare ordinary hashing, password hashing, and encryption for storing passwords.
4. Explain digital-signature creation, verification, trust, and operational key management.
5. Develop a policy for protecting and rotating software-release signing keys.

3 Analytical / Application Questions

1. A company publishes a file and its SHA-256 digest on the same server. Analyse whether this protects users from a malicious server compromise and recommend a stronger design.
2. An API accepts valid HMAC-authenticated requests that were captured hours earlier. Identify the weakness and design an anti-replay control.
3. A database breach exposes salted password hashes. Evaluate the factors that determine cracking risk and propose technical and organisational mitigations.

Multiple Choice Questions with Answers

Question 1

Which property describes the difficulty of finding any two different messages with the same hash output?

A. Preimage resistance

B. Collision resistance

C. Confidentiality

D. Forward secrecy

Correct Answer: B. Collision resistance

Question 2

What does HMAC add to a hash-based integrity check?

A. A shared secret key

B. Automatic encryption of the message

C. A public certificate

D. A password salt only

Correct Answer: A. A shared secret key

Question 3

Why should each password record use a unique random salt?

A. To make the password recoverable

B. To provide confidentiality for the database

C. To prevent identical passwords from having identical stored values

D. To replace the need for a work factor

Correct Answer: C. To prevent identical passwords from having identical stored values

Question 4

Which mechanism permits public verification without sharing a signing secret with every verifier?

A. Plain hash

B. HMAC

C. Digital signature

D. Password hash

Correct Answer: C. Digital signature

Question 5

A 256-bit ideal hash has approximately how many bits of generic collision security?

A. 64

B. 128

C. 256

D. 512

Correct Answer: B. 128

Question 6

Which statement about a plain published file hash is correct?

A. It proves the publisher’s identity in all cases

B. It provides confidentiality

C. An attacker able to replace both file and hash can defeat the check

D. It prevents replay attacks

Correct Answer: C. An attacker able to replace both file and hash can defeat the check

Question 7

What is a primary purpose of a password-hashing work factor?

A. To make offline password guesses more expensive

B. To allow administrators to decrypt passwords

C. To make salts secret

D. To create public signatures

Correct Answer: A. To make offline password guesses more expensive

Question 8

Which control is most directly designed to detect reuse of an old valid authenticated request?

A. A longer digest

B. A nonce, timestamp, or sequence number

C. A public web page

D. A second password hash

Correct Answer: B. A nonce, timestamp, or sequence number

Question 9

What key creates a digital signature in a conventional asymmetric signature system?

A. The recipient’s public key

B. The signer’s private key

C. The recipient’s password

D. A publicly disclosed HMAC key

Correct Answer: B. The signer’s private key

Question 10

Why is constant-time tag comparison recommended?

A. To increase digest length

B. To prevent timing leakage during comparison

C. To encrypt the tag

D. To generate salts automatically

Correct Answer: B. To prevent timing leakage during comparison