Hashing and Integrity

Hashing and Integrity: Core Concepts

When you download a 2 GB ISO file, how do you know it arrived intact? When a system stores your password, how does it verify you typed the right one without storing the password itself? Both questions are answered by cryptographic hashing — a function that maps arbitrary-length data to a fixed-length digest.

What a Cryptographic Hash Does

A cryptographic hash function takes any input — a single character, a book, a 100 GB database — and produces a fixed-length output called a digest or fingerprint. For SHA-256, the output is always 256 bits (64 hexadecimal characters), regardless of input size.

# SHA-256 of a short string
echo -n "hello" | sha256sum
# Output: 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824

# SHA-256 of a different string
echo -n "Hello" | sha256sum
# Output: 185f8db32271fe25f561a6fc938b2e264306ec304eda518007d1764826381969

Notice that changing one character (lowercase 'h' to uppercase 'H') produces a completely different digest. This is the avalanche effect: any change to the input, no matter how small, produces a dramatically different output.

The Three Properties of Cryptographic Hashes

A hash function is considered cryptographically secure only if it satisfies three properties:

1. Pre-image resistance — Given a digest, it is computationally infeasible to find any input that produces that digest. You cannot "reverse" a hash.
2. Second pre-image resistance — Given an input, it is computationally infeasible to find a different input that produces the same digest.
3. Collision resistance — It is computationally infeasible to find any two different inputs that produce the same digest.

These properties make hashes useful for integrity verification: if the digest of a file matches the expected digest, the file has not been modified.

Common Hash Functions

MD5 and SHA-1 should never be used for security purposes. While they are still found in legacy systems and non-security contexts (like checksums for data corruption detection), they provide no protection against a determined attacker.

Integrity vs. Authenticity

A hash proves that data has not changed, but it does not prove who created the data. If an attacker modifies a file and publishes the new hash alongside it, the hash still matches — but the file is malicious.

To prove both integrity and authenticity, you need a Message Authentication Code (MAC) like HMAC, which combines a hash with a secret key, or a digital signature, which uses asymmetric cryptography. The hash alone is not enough.

Where It Fits

Hashing is the foundation of many cryptographic protocols. Password storage uses hashes (with salts). Digital signatures hash the message before signing. TLS uses hashes for key derivation and integrity checks. Study Active Directory Fundamentals first to understand how authentication systems use hashes, then move to Symmetric Encryption to see how hashes combine with encryption.

Hashing and Integrity: Practice

Hashing is deceptively simple — the complexity comes from knowing when and how to use it correctly. The exercises below cover the most common real-world applications.

Exercise 1: Verify a File Download

When you download software, the publisher often provides a SHA-256 hash so you can verify the file was not corrupted or tampered with during download:

# On Linux/macOS
sha256sum downloaded_file.iso
# Compare the output to the publisher's published hash

# On Windows (PowerShell)
Get-FileHash -Algorithm SHA256 downloaded_file.iso

# On Windows (certutil)
certutil -hashfile downloaded_file.iso SHA256

If the hashes match, the file is intact. If they differ, the file was corrupted during download, or worse, replaced with a malicious version.

Exercise 2: Detect Duplicate Files

Hashes let you find duplicate files without comparing their contents byte by byte:

# Find duplicate files in a directory by hash
find /path/to/dir -type f -exec sha256sum {} + | sort | uniq -w64 -dD

This computes the SHA-256 of every file, sorts by hash, and prints only files with identical hashes. This is much faster than diff for large files because you only need to compare 64-character strings.

Exercise 3: Build a Simple Integrity Checker

Create a script that monitors critical files for unauthorized changes:

#!/usr/bin/env bash
# integrity_check.sh — Verify file integrity against a baseline

BASELINE="/var/lib/integrity/baseline.sha256"

# Generate a baseline (run once)
if [ ! -f "$BASELINE" ]; then
    sha256sum /etc/passwd /etc/shadow /etc/ssh/sshd_config > "$BASELINE"
    echo "Baseline created."
    exit 0
fi

# Verify against the baseline
sha256sum -c "$BASELINE"

Run this script via cron to detect unauthorized modifications to critical system files. Any change will cause sha256sum -c to report a mismatch.

Exercise 4: Understand Why MD5 Is Broken

Demonstrate that MD5 collisions are trivial to find:

# Install the md5collgen tool (from the hashclash project)
# Generate two different files with the same MD5 hash
md5collgen -p prefix -o file1.bin file2.bin

# Verify they have the same MD5 but different SHA-256
md5sum file1.bin file2.bin    # Same hash
sha256sum file1.bin file2.bin  # Different hashes

This demonstrates why MD5 cannot be trusted for integrity: an attacker can create two files with the same MD5 hash, substitute the malicious one, and the hash check will pass.

Check Your Understanding

• Why can't you reverse a hash to find the original input?
• What is the difference between a hash and an HMAC?
• Why is SHA-256 still considered secure while SHA-1 is not?

Hashing and Integrity: Trade-offs and Interviews

Hashing is one of the most widely used cryptographic primitives, but it is also one of the most misunderstood. Knowing when to use it — and when not to — is critical.

When Hashing Is the Wrong Tool

• Encryption: A hash is one-way. If you need to recover the original data, use encryption, not hashing. Hashes verify integrity; encryption provides confidentiality.
• Password storage without salting: Hashing passwords without a salt makes them vulnerable to rainbow table attacks. Always use a unique salt per password, and use a slow hash function like bcrypt, scrypt, or Argon2 — not SHA-256.
• Data compression: Hashes are fixed-length and lossy. You cannot reconstruct the original data from a hash, so they cannot be used for compression.
• Authentication without a key: A bare hash proves integrity but not authenticity. If you need to verify both, use HMAC (hash + secret key) or a digital signature.

The Birthday Paradox and Collision Resistance

The birthday paradox states that in a group of just 23 people, there is a 50% chance that two share a birthday. The same principle applies to hash collisions: you only need to try about 2^(n/2) inputs to find a collision for an n-bit hash.

For SHA-256 (256 bits), you would need approximately 2^128 operations to find a collision — computationally infeasible with current technology. For MD5 (128 bits), you need only 2^64 operations, and in practice collisions can be found in seconds on a modern computer.

This is why hash length matters: a 256-bit hash provides 128-bit collision resistance, which is beyond the reach of any foreseeable computing power.

Performance Considerations

SHA-256 is fast — often too fast for password storage. When an attacker obtains a password hash database, they can try billions of SHA-256 computations per second on a GPU. This is why password hashing uses deliberately slow functions:

• bcrypt — Based on Blowfish, with a configurable work factor
• scrypt — Memory-hard, making GPU/ASIC attacks expensive
• Argon2 — Winner of the Password Hashing Competition, memory-hard and resistant to side-channel attacks

For non-password integrity verification (file downloads, data corruption detection), SHA-256's speed is an advantage, not a liability.

How This Comes Up in Interviews

• "How do you verify a file download hasn't been tampered with?" Compare the SHA-256 hash of the downloaded file against the hash published by the software vendor. If they match, the file is intact. For authenticity, verify the vendor's signature on the hash.
• "Why shouldn't we use SHA-256 for password storage?" SHA-256 is too fast. An attacker with a GPU can try billions of hashes per second. Use bcrypt, scrypt, or Argon2 with a unique salt per password.
• "What is the difference between a hash and a MAC?" A hash proves integrity (data hasn't changed). A MAC (like HMAC) proves both integrity and authenticity (data hasn't changed and came from the expected sender) by incorporating a secret key.