Hash Functions, MACs, and Password Security

Introduction

Modern information systems must answer three related questions: Has data been changed? Did the message come from an approved sender? Can a user’s secret be stored without exposing it if a database is stolen? Cryptographic hash functions, message authentication codes (MACs), and password-specific key-derivation functions provide central answers.

A hash function compresses an input of arbitrary length into a fixed-length digest. A MAC combines a message with a secret key to produce an authentication tag. A password-hashing or key-derivation function transforms a password into a deliberately expensive derived value, usually with a unique salt. These mechanisms are related, but they are not interchangeable. A plain hash is not authentication; a MAC is not a password-storage scheme; and encryption is not a substitute for either.

This chapter develops the foundations and practical use of these mechanisms. It also examines collision, preimage, and offline password attacks, followed by a case study involving insecure credential storage.

Learning Objectives

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

1. Explain the purpose and security properties of cryptographic hash functions.
2. Distinguish collision, preimage, and second-preimage resistance.
3. Select appropriate hashes, MACs, and password-hashing functions for common tasks.
4. Explain salting, peppering, key stretching, and secure credential storage.
5. Verify file integrity and authenticate messages using appropriate designs.
6. Recognize practical attacks and limitations, including length-extension risks and offline guessing.
7. Apply professional, ethical, and governance requirements to credential protection.

1. Cryptographic Hash Functions

A cryptographic hash function maps an input message of arbitrary length to a fixed-length output called a hash, digest, or message digest. Formally:

Here, m is the input message, H is the hash function, and h is the digest. The output length is fixed for a particular algorithm. For example, SHA-256 produces 256 bits, or 32 bytes, regardless of whether the input is one byte or several gigabytes. The digest is commonly represented as hexadecimal, so 256 bits require 64 hexadecimal characters because each hexadecimal character represents 4 bits.

A secure cryptographic hash normally has these properties:

• Determinism: the same input always produces the same output.
• Efficient computation: computing H(m) is practical for legitimate users.
• Preimage resistance: given a digest h, it should be computationally infeasible to find any message m such that H(m) = h.
• Second-preimage resistance: given a particular message m₁, it should be infeasible to find a different message m₂ with the same digest.
• Collision resistance: it should be infeasible to find any two distinct messages m₁ and m₂ such that H(m₁) = H(m₂).
• Avalanche effect: a small input change should produce an apparently unrelated digest.

“Computationally infeasible” does not mean mathematically impossible. Hash functions have finite outputs, so collisions must exist when the input space is larger than the output space. Security means that finding useful collisions should require impractical resources under the relevant threat model.

1.1 Hashes Are Not Encryption

Encryption is designed to be reversible by a holder of a decryption key. A cryptographic hash is normally one-way and has no decryption key. Hashing is therefore suitable for fingerprints, integrity checks, digital-signature preprocessing, and constructions such as MACs and key derivation. It is not suitable for storing data that must later be recovered, such as a customer’s original address. That data should be encrypted when confidentiality is required.

1.2 Common Hash Algorithms

The SHA-2 family includes SHA-224, SHA-256, SHA-384, and SHA-512. SHA-256 and SHA-512 are widely deployed general-purpose hashes. SHA-3 is a separate standardized family based on a sponge construction. Both SHA-2 and SHA-3 remain appropriate choices for general-purpose hashing when implemented correctly.

MD5 and SHA-1 should not be selected for collision-sensitive security applications. Practical collision attacks have been demonstrated against both. They may remain visible in legacy checksum systems, but replacing them is preferable where security decisions depend on the result.

A hash should be selected according to the security purpose, not simply because it is fast or familiar. General-purpose hashes are intentionally fast. That is useful for file integrity and signatures but dangerous for password storage, because attackers can test enormous numbers of password guesses.

2. Understanding Hash Attacks

2.1 Preimage Attacks

A preimage attack starts with a target digest and attempts to find an input that produces it. For an ideal n-bit hash, a generic preimage search has expected work on the order of 2ⁿ evaluations. This is a general security estimate, not a guarantee for every algorithm or attack.

2.2 Second-Preimage Attacks

In a second-preimage attack, the attacker is given a legitimate message and seeks a different message with the same digest. This matters when a digest authenticates or identifies a particular document. For an ideal n-bit hash, the generic work factor is also approximately 2ⁿ.

2.3 Collision Attacks and the Birthday Effect

A collision attack seeks any two different messages with the same digest. The birthday effect makes this easier than finding a preimage. For an ideal n-bit hash, a generic collision search requires approximately:

hash evaluations, rather than 2ⁿ. Thus, a 256-bit hash has an ideal generic collision strength of approximately 128 bits. This does not mean that an attacker can automatically forge every 256-bit-hash application at that cost; the actual risk depends on the algorithm, protocol, message structure, and whether the digest is authenticated.

2.4 Length-Extension Concerns

Some iterated hash constructions allow a party knowing H(secret || message) to calculate a digest related to secret || message || padding || extension without knowing the secret. This is called a length-extension attack. Therefore, a construction such as H(secret || message) should not be assumed to be a safe MAC. HMAC is designed to avoid this class of misuse.

3. Integrity Verification

Integrity verification detects accidental or unauthorized modification. A downloaded software package may be accompanied by a digest. The user computes the digest of the received file and compares it with the trusted value. If the values differ, the file is not identical to the original.

However, an unauthenticated digest does not prove who supplied the digest. If an attacker can replace both the file and its published checksum, the comparison provides no meaningful security. Stronger designs distribute the digest through an authenticated channel or use a digital signature. A digital signature provides origin authentication, integrity, and non-repudiation properties under its applicable legal and technical assumptions; a bare hash does not.

A secure verification procedure should:

1. Obtain the expected digest or signature from a trusted source.
2. Compute the digest using a maintained cryptographic library.
3. Compare values using a reliable comparison method.
4. Reject mismatches and investigate the source.
5. Record algorithm and encoding details to avoid ambiguity.

4. Message Authentication Codes

A MAC provides integrity and source authentication to parties sharing a secret key. It is commonly represented as:

where K is a secret key, m is the message, and t is the authentication tag. The receiver recomputes the tag using the shared key and accepts the message only if the tags match.

A secure MAC should make it infeasible for an attacker without the key to create a valid tag for a new message. It should also make it difficult to distinguish valid tags from random values. The tag may be truncated for protocol reasons, but truncation reduces the guessing resistance. If a tag has t bits, a blind forgery attempt succeeds with probability approximately 1/2^t per independent attempt, assuming an ideal MAC and no rate limitation. Repeated attempts require monitoring and throttling.

4.1 HMAC

HMAC is a widely used hash-based MAC. Its conceptual form is:

Here, H is a suitable hash, K' is the key normalized to the hash block size, ipad and opad are fixed inner and outer padding constants, ⊕ denotes bitwise exclusive OR, and || denotes concatenation. The formula assumes the standard HMAC construction and correct key processing as defined by its specification. Application developers should use a tested library rather than implement this formula manually.

HMAC-SHA-256 is a common choice for API request authentication, authenticated tokens, and integrity protection in systems where both endpoints can securely share a key. Keys should be generated randomly, protected in a key-management system, rotated according to risk, and never embedded in public client applications.

4.2 MACs Compared with Digital Signatures

A MAC uses one shared secret. Any party possessing that secret can generate a valid tag, so a MAC cannot prove which party generated a message. A digital signature uses a private key to sign and a public key to verify. This supports verification by many parties without distributing a signing secret, although signatures involve certificate management and more computational and operational complexity.

4.3 MAC Verification Practices

Verification must use the same canonical representation of the message used during generation. Differences in whitespace, character encoding, field order, or line endings can produce different tags. Systems should define canonical serialization, reject malformed inputs, use constant-time tag comparison where applicable, and include freshness information such as a timestamp, nonce, or sequence number. A valid MAC on an old message is still a valid MAC unless replay protection is designed separately.

5. Passwords and Threat Models

Passwords are low-entropy human-chosen secrets. An attacker may obtain a credential database through a web vulnerability, stolen backup, insider action, or compromised administrator account. Once password records are available, the attacker can perform offline guesses without contacting the application. Online controls such as account lockout do not adequately defend against this situation.

The attacker commonly:

1. Obtains a password record.
2. Selects likely passwords from dictionaries, breached-password lists, and personal information.
3. Applies the recorded algorithm and parameters to each guess.
4. Compares the result with the stored value.
5. Reuses recovered passwords against other services.

A password-storage design should therefore make each guess expensive, limit the value of precomputation, and avoid exposing the original password.

6. Salting, Peppering, and Key Derivation

6.1 Salts

A salt is a unique, randomly generated value stored with each password record. A simplified password record is:

The password-processing relationship can be written as:

where P is the password, salt is public random data, parameters specify cost settings, and D is the derived value. The salt is not intended to be secret. Its purpose is to ensure that identical passwords produce different records and to prevent one precomputed table from efficiently attacking many accounts.

A salt does not make a weak password strong. An attacker who has the record can still guess the password and use the known salt. Salting instead makes attacks more individualized and costly.

6.2 Peppers

A pepper is an additional secret kept separately from the password database, such as in a hardware security module or secrets manager. It can increase resistance to a database-only compromise, but it introduces key-management and availability requirements. Losing the pepper may make all records unusable; exposing it may remove the intended protection. A pepper should not be treated as a replacement for salts or a strong KDF.

6.3 Key-Derivation Functions

A key-derivation function (KDF) derives cryptographic keys from passwords or other inputs. Password-focused KDFs deliberately consume time and memory. Their parameters must be tuned to the organization’s hardware and threat model.

PBKDF2 applies a pseudorandom function repeatedly. Its approximate work grows with the iteration count, but it is relatively less resistant to highly parallel hardware than memory-hard designs. Argon2id is designed to use both computation and memory and is a strong modern choice where available. scrypt also imposes substantial memory requirements. bcrypt remains useful in legacy and widely supported systems, although its design is older and its memory-hardness is limited.

A practical password record should include the algorithm identifier, version, salt, and cost parameters. This permits gradual upgrades: after successful login, the system can rehash a password with stronger parameters.

6.4 Why Fast Hashes Are Inappropriate for Passwords

A record such as SHA-256(password || salt) is generally inadequate as a password-storage design. GPUs and specialized hardware can compute vast numbers of fast hashes. A password KDF intentionally reduces the number of guesses an attacker can test per second. The objective is not to make legitimate login impossible, but to make large-scale guessing economically unattractive.

7. Secure Credential-Storage Design

A robust design includes the following practices:

• Use Argon2id, scrypt, bcrypt, or PBKDF2 according to current organizational guidance and platform support.
• Generate a cryptographically secure, unique random salt for every password.
• Store the salt and KDF parameters with the derived value; they do not need to be hidden.
• Select cost parameters through benchmarking on production-like hardware.
• Upgrade parameters over time and rehash after successful authentication.
• Reject common, breached, and obviously predictable passwords while avoiding unnecessary composition rules.
• Apply rate limits, anomaly detection, multi-factor authentication, and secure recovery procedures.
• Protect password-reset tokens as high-value secrets, make them single-use, and give them short lifetimes.
• Never log passwords, password-reset links, derived values, or secret peppers.
• Restrict database access, encrypt backups, monitor administrative access, and test restoration.
• Compare derived values using a library’s safe verification function.

Passwords should normally be verified rather than decrypted. If an application needs to recover a secret, such as an API credential used by a service, it may require authenticated encryption and a dedicated key-management design rather than password hashing.

7.1 Authentication Flow

During registration, the system validates the password policy, generates a salt, derives a value using the selected KDF, and stores the algorithm, parameters, salt, and derived value. During login, it retrieves the record, runs the same KDF on the submitted password, compares the result safely, and issues a session only after successful verification. The password itself should exist only transiently in protected process memory and should never be written to logs.

A generic record might look like:

algorithm = Argon2id
version = current-supported-version
memory = configured-cost
iterations = configured-cost
parallelism = configured-cost
salt = random-per-user-value
derived_value = KDF(password, salt, parameters)

The exact values must be selected by benchmarking and current security guidance; fixed values in a textbook should not be copied blindly into production.

8. Integrity, Authentication, and Confidentiality Compared

These mechanisms can be combined. For example, an encrypted message should normally use authenticated encryption, which protects confidentiality and detects tampering. Separately hashing an encrypted message without authenticating the hash key does not automatically provide the same security.

9. Illustrative Case Study: University Portal Credential Breach

Background

A fictional university operates a student portal. Its legacy application stores each password as a fast SHA-1 digest with no salt. The database is exposed through a vulnerable reporting service. The institution discovers suspicious login activity involving student accounts.

Problem

The same passwords produce identical records, allowing attackers to identify users with common passwords and use precomputed lists. SHA-1 is fast, so an attacker can test guesses rapidly. Students also reuse passwords on external services, increasing the impact.

Analysis

The incident involves several failures rather than one defective algorithm. The system used an obsolete general-purpose hash for password storage, omitted salts, lacked effective rate limiting, and did not enforce multi-factor authentication for administrative users. Password records were also included in an unencrypted backup accessible to a broad operations group.

Approach and Solution

The response team first contained the exposure, preserved evidence, revoked suspicious sessions, and required password resets based on risk. It notified affected parties according to applicable law and institutional policy. The replacement design used a supported password KDF with a unique random salt and stored parameters for future upgrades. The team added breached-password screening, rate limiting, MFA for staff and privileged users, secure reset tokens, restricted backup access, and monitoring for credential stuffing.

During migration, users who successfully authenticated were transparently rehashed using the new KDF. Accounts that did not log in within the migration period were required to complete a reset. The institution did not attempt to recover original passwords because secure password hashing is intentionally non-reversible.

Outcome

The new design made identical passwords produce different records, substantially increased the cost of offline guessing, reduced online abuse, and improved detection. It did not eliminate risk: weak user passwords, phishing, malware, and stolen active sessions remained possible. MFA and user education therefore remained necessary.

Learning Points

1. A fast hash can be secure for one purpose and unsuitable for another.
2. Salts prevent useful cross-account precomputation but do not hide passwords.
3. Database security, backups, logging, and recovery processes are part of credential security.
4. Password hashing must be combined with rate limiting, MFA, and secure recovery.
5. Incident response should address both technical containment and legal or ethical duties.

10. Challenges, Limitations, and Governance

No hash or KDF can compensate for a password already disclosed through phishing or malware. A strong KDF also cannot prevent credential stuffing if users reuse passwords and the service lacks rate controls. Higher cost parameters consume server resources and may create denial-of-service opportunities if login requests are unrestricted. Systems should benchmark, monitor, and rate-limit authentication operations.

Organizations should follow applicable data-protection, breach-notification, payment, education, and sector-specific requirements. Password databases are sensitive personal-security data even when values are derived. Access should follow least privilege, and retention should be limited. Security teams must not conduct password-cracking exercises against real user credentials without documented authorization, defined scope, and safe handling of results.

Artificial intelligence can improve defensive monitoring by identifying unusual login patterns and prioritizing exposed credentials, but it also assists attackers in generating targeted guesses and persuasive phishing messages. AI systems should not receive plaintext passwords or production credential databases. Their outputs require human review, privacy controls, and documented governance.

11. Contemporary Best Practices

Current professional practice emphasizes memory-hard password hashing where feasible, MFA for sensitive accounts, password managers, breached-password detection, and secure-by-default libraries. Protocols should use established constructions such as HMAC rather than ad hoc combinations of hashes and secrets. Software dependencies should be maintained, cryptographic algorithms should be inventoried, and migration plans should exist for algorithm or parameter upgrades.

Security architecture should begin with the threat model. For public file distribution, signatures may be more appropriate than a bare checksum. For an API shared between trusted services, HMAC may be appropriate. For human passwords, a password KDF with unique salts is required. For recoverable confidential data, authenticated encryption and key management are needed. Choosing the mechanism by task is more important than choosing the most fashionable algorithm.

Chapter Summary

Cryptographic hashes produce fixed-length fingerprints and support integrity checks, signatures, and other constructions. Their important security properties include preimage, second-preimage, and collision resistance. Because collision searching benefits from the birthday effect, an ideal n-bit hash has generic collision work of approximately 2^(n/2). A hash alone does not authenticate the source of data.

MACs add a shared secret and provide message integrity and authentication. HMAC is a well-established hash-based construction, while digital signatures provide public-key verification. Replay protection, canonical serialization, secure key management, and safe tag comparison remain necessary around the MAC itself.

Passwords require specialized treatment because they are often guessable. A unique salt prevents identical passwords from producing identical records and defeats broad precomputation, but it does not make weak passwords strong. Password KDFs such as Argon2id, scrypt, bcrypt, and PBKDF2 deliberately increase the cost of guessing. Secure credential storage also requires parameter upgrades, rate limiting, MFA, secure recovery, restricted backups, monitoring, and ethical governance.

Key Terms

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

Digest: The fixed-length output of a hash function.

Preimage resistance: The difficulty of finding an input for a specified digest.

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

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

Avalanche effect: The property that a small input change produces a substantially different output.

MAC: A keyed mechanism that authenticates message integrity to parties sharing a secret.

HMAC: A standardized MAC construction using a cryptographic hash and a secret key.

Authentication tag: The value generated by a MAC and checked by the receiver.

Salt: Public, unique random data added to a password KDF input.

Pepper: An additional secret used in password protection and stored separately from the database.

Password KDF: A function designed to derive values from passwords while increasing guessing cost.

Key stretching: Increasing the computational effort required to test a password guess.

Memory-hardness: A design property requiring substantial memory as well as computation.

Offline attack: Guessing performed against stolen records without interacting with the target service.

Credential stuffing: Using previously exposed username-password pairs against other services.

Length-extension attack: An attack affecting certain hash constructions when a secret is improperly prepended to a message.

Canonicalization: Converting data into a single agreed representation before authentication or hashing.

Replay attack: Reusing a previously valid message or authentication exchange.

Authenticated encryption: Encryption that provides confidentiality and integrity together.

Review Questions

Short Answer Questions

1. What is the difference between a cryptographic hash and encryption?
2. Define collision resistance and preimage resistance.
3. Why is a salt stored with a password-derived value?
4. What security services does HMAC provide?
5. Why are fast hashes such as SHA-256 generally unsuitable for password storage when used alone?

Long Answer Questions

1. Explain the main security properties of cryptographic hash functions and discuss their practical relevance.
2. Compare HMAC and digital signatures with respect to keys, verification, scalability, and trust.
3. Describe a secure password-registration and login process from input validation to successful session creation.
4. Explain how collision attacks differ from preimage and second-preimage attacks, including the birthday effect.
5. Discuss the technical and governance controls required after a password database breach.

Analytical / Application Questions

1. A system publishes a file and an unauthenticated SHA-256 checksum on the same website. Analyse what an attacker can and cannot prove by replacing both the file and checksum, and recommend a stronger distribution method.
2. An organization stores SHA-256(password || salt) with unique salts but observes very high offline-guessing rates after a database theft. Diagnose the design weakness and propose a migration plan.
3. An API authenticates requests with H(secret || message). Explain the potential construction problem and recommend a safer authenticated-message design, including replay protection.

Multiple Choice Questions with Answers

Question 1

Which property describes the difficulty of finding any two distinct messages with the same hash value?

A. Preimage resistance

B. Collision resistance

C. Forward secrecy

D. Key indistinguishability

Correct Answer: B. Collision resistance

Question 2

What is the primary purpose of a unique salt in password storage?

A. To make the password recoverable

B. To keep the password database encrypted

C. To ensure identical passwords produce different derived records

D. To authenticate messages between servers

Correct Answer: C. To ensure identical passwords produce different derived records

Question 3

Which mechanism is designed to authenticate a message using a shared secret key?

A. HMAC

B. Plain SHA-256

C. A random salt

D. A checksum without a key

Correct Answer: A. HMAC

Question 4

For an ideal n-bit hash, the approximate generic work factor for finding a collision is:

A. 2^n

B. n^2

C. 2^(n/2)

D. n/2

Correct Answer: C. 2^(n/2)

Question 5

Why is a general-purpose fast hash usually unsuitable for password storage by itself?

A. It cannot produce a fixed-length output

B. It enables attackers to test guesses very rapidly

C. It always reveals the plaintext password

D. It requires a public verification key

Correct Answer: B. It enables attackers to test guesses very rapidly

Question 6

Which item should normally be stored with a password-derived value to support future verification and upgrades?

A. The plaintext password

B. The private encryption key for every user

C. The algorithm identifier and cost parameters

D. A copy of the user’s previous password

Correct Answer: C. The algorithm identifier and cost parameters

Question 7

What is a major limitation of an unauthenticated file digest published by the same site that hosts the file?

A. The digest cannot detect accidental changes

B. An attacker who replaces both may defeat the comparison

C. The digest always provides confidentiality

D. The digest requires the recipient’s password

Correct Answer: B. An attacker who replaces both may defeat the comparison

Question 8

Which statement about a pepper is correct?

A. It is public data stored beside every salt

B. It replaces the need for a password KDF

C. It is an additional secret kept separately from the password database

D. It is the digest output of a general-purpose hash

Correct Answer: C. It is an additional secret kept separately from the password database

Question 9

Which feature helps prevent a valid old MAC-authenticated message from being reused?

A. A nonce, timestamp, or sequence number with replay checks

B. A longer username

C. A public salt only

D. A faster hash function

Correct Answer: A. A nonce, timestamp, or sequence number with replay checks

Question 10

Which mechanism is normally appropriate when data must remain recoverable while also being protected against tampering?

A. Plain hashing

B. Password hashing

C. Authenticated encryption

D. An unauthenticated checksum

Correct Answer: C. Authenticated encryption