Security Hashing Fundamentals

# Hashing Fundamentals

> One-way functions for integrity verification, content addressing, and commitment schemes
> -- SHA-256 for interoperability, BLAKE3 for performance, and never MD5 or SHA-1 for
> security

## When to Use

- Verifying file or data integrity (checksums, download verification, package signing)
- Content addressing (deduplication, cache keys, Git object IDs, container image digests)
- Generating deterministic identifiers from variable-length input
- Choosing a hash function for a new system or migrating away from a deprecated one
- Reviewing code that uses hashing and assessing whether the right function and use
  pattern is applied
- Understanding why MD5 or SHA-1 must be replaced in security-sensitive contexts

## Threat Context

Weak hash functions enable collision attacks (finding two different inputs that produce
the same hash), preimage attacks (finding an input that produces a specific target hash),
and second preimage attacks (finding a different input with the same hash as a known
input). MD5 collisions can be generated in seconds on commodity hardware -- Wang et al.
demonstrated the first practical MD5 collision in 2004, and by 2012, the Flame malware
exploited an MD5 chosen-prefix collision to forge a Microsoft code-signing certificate,
enabling nation-state malware to masquerade as a legitimate Windows update. SHA-1
collisions were demonstrated practically by Google and CWI Amsterdam in 2017 (the
SHAttered attack), producing two distinct PDF files with identical SHA-1 hashes at a cost
of approximately $110,000 in cloud computing. These attacks enable forged digital
certificates, tampered software distribution packages, Git repository poisoning, and
bypassed integrity checks in any system relying on the compromised hash function.

## Instructions

1. **For general-purpose cryptographic hashing, use SHA-256.** SHA-256 (part of the SHA-2
   family, designed by the NSA, standardized by NIST in 2001) produces a 256-bit digest
   and provides 128-bit collision resistance and 256-bit preimage resistance. It is
   universally supported across every programming language, operating system, and
   cryptographic library. SHA-256 is the standard choice for integrity verification,
   digital signature hashing, certificate fingerprints, blockchain proof-of-work, and any
   context requiring a well-analyzed, interoperable cryptographic hash. SHA-512 offers the
   same security margin with better performance on 64-bit platforms due to its use of
   64-bit arithmetic operations.

2. **For performance-sensitive hashing, use BLAKE3.** BLAKE3 is a cryptographic hash
   function released in 2020, derived from the BLAKE2/ChaCha cipher family. It is 6-14x
   faster than SHA-256 on modern CPUs by exploiting SIMD parallelism (AVX-512, NEON) and
   internal tree hashing that parallelizes across multiple cores. BLAKE3 provides 128-bit
   security against all known attacks. Use BLAKE3 for content addressing, file
   deduplication, Merkle tree construction, and any use case where hash throughput is a
   bottleneck. BLAKE3 is not yet NIST-standardized, so use SHA-256 when FIPS 140-2/140-3
   compliance is required. BLAKE2b (BLAKE3's predecessor) is standardized in RFC 7693 and
   is a suitable intermediate choice.

3. **For defense-in-depth against structural attacks, consider SHA-3 (Keccak).** SHA-3
   uses the sponge construction, which is fundamentally different from the Merkle-Damgard
   construction used by SHA-2, MD5, and SHA-1. If a structural breakthrough ever
   compromises the Merkle-Damgard design (affecting the entire SHA-2 family
   simultaneously), SHA-3 would be unaffected. SHA-3-256 provides 128-bit collision
   resistance, identical to SHA-256. In practice, SHA-256 is not under credible threat,
   but defense-critical or long-lived systems (government archives, root certificate
   authorities) may use SHA-3-256 as a hedge. SHA-3 also natively supports
   variable-length output via SHAKE128 and SHAKE256 (extendable output functions), which
   is useful for key derivation and domain separation.

4. **Never use MD5 or SHA-1 for security purposes.** MD5 is completely broken for
   collision resistance -- chosen-prefix collisions (where the attacker controls prefixes
   of both inputs) can be computed in hours on a single machine. SHA-1 is similarly
   broken: the SHAttered attack demonstrated a practical collision, and further research
   (Leurent and Peyrin, 2020) reduced chosen-prefix collision cost to approximately
   $45,000. Both MD5 and SHA-1 are acceptable only for non-security checksums where
   adversarial tampering is not in the threat model (e.g., verifying data integrity over a
   reliable channel, deduplication in trusted storage). When encountering MD5 or SHA-1 in
   existing code, assess whether the context is security-sensitive; if so, migration to
   SHA-256 is urgent.

5. **Understand the three security properties of cryptographic hash functions:**
   - **Preimage resistance (one-wayness):** Given a hash output H, it is computationally
     infeasible to find any input m such that hash(m) = H. A hash function with n-bit
     output provides up to n-bit preimage resistance. This property ensures that hashes
     cannot be "reversed" to recover the original input.
   - **Second preimage resistance:** Given a specific input m1, it is computationally
     infeasible to find a different input m2 such that hash(m1) = hash(m2). This property
     ensures that an attacker cannot find a substitute input that matches a known hash,
     which would enable undetected document or data substitution.
   - **Collision resistance:** It is computationally infeasible to find any two distinct
     inputs m1 and m2 such that hash(m1) = hash(m2). Due to the birthday paradox,
     collision resistance is at most n/2 bits for an n-bit hash (2^128 operations for
     SHA-256). Collision resistance is the strongest property and implies second preimage
     resistance.

6. **Hashing is NOT encryption.** Hashing is a one-way function: given input m, you can
   compute hash(m), but given hash(m), you cannot recover m. Encryption is a two-way
   function: given plaintext and a key, you can encrypt; given ciphertext and the key, you
   can decrypt. Never hash data you need to recover (use encryption). Never encrypt data
   you only need to verify (use hashing). This distinction is fundamental: hashing
   provides integrity and commitment; encryption provides confidentiality.

7. **Hashing is NOT a MAC.** A bare hash -- SHA-256(message) -- does not authenticate
   the sender. Anyone who knows the message can compute its hash. A Message
   Authentication Code (MAC) combines the hash with a secret key, so only parties
   possessing the key can compute or verify the MAC. Use HMAC (HMAC-SHA256, HMAC-SHA384)
   when you need to verify both integrity and authenticity. Naive constructions like
   hash(key || message) are vulnerable to length extension attacks on Merkle-Damgard
   hashes. See the `security-hmac-signatures` skill.

## Details

### Length Extension Attacks

SHA-256, SHA-512, and all Merkle-Damgard hash functions are vulnerable to length
extension: given hash(m) and the length of m (but not m itself), an attacker can compute
hash(m || padding || attacker_suffix) for any chosen suffix, without knowing m. This is
possible because the final internal state of a Merkle-Damgard hash is the hash output,
and that state can be used to initialize a new hash computation that "continues" from
where the original left off.

This breaks naive keyed-hash authentication schemes like hash(secret || message): an
attacker who observes the hash and knows the message length can append arbitrary data and
compute a valid hash. Real-world exploits include API signature bypasses where servers
used hash(api_key || request_params) for authentication.

Mitigations:

- **HMAC** nests the hash in a specific construction -- hash(K XOR opad || hash(K XOR
  ipad || message)) -- that is provably secure against length extension.
- **SHA-3 (Keccak)** uses the sponge construction, which absorbs input and squeezes
  output through a capacity parameter. The internal state is larger than the output,
  making length extension infeasible.
- **BLAKE3** uses a tree/chaining construction that is also immune to length extension.

### Birthday Paradox and Collision Probability

The birthday paradox states that in a set of n randomly chosen values from a space of
size N, the probability of at least one collision exceeds 50% when n approaches sqrt(N).
For hash functions:

- **SHA-256** (256-bit output): collision expected after ~2^128 hashes --
  computationally infeasible with current or foreseeable technology.
- **SHA-1** (160-bit output): collision expected after ~2^80 hashes -- within reach of
  well-funded attackers, as SHAttered demonstrated.
- **MD5** (128-bit output): collision expected after ~2^64 hashes -- trivially achievable
  on modern hardware.

This is why hash output length matters for security: a 128-bit hash provides only 64-bit
collision resistance, which is insufficient for any security application.

### Content Addressing Pattern

Content addressing uses the hash of data as its identifier/address, making integrity
self-verifying:

- **Git** uses SHA-1 for object IDs (commits, trees, blobs), migrating to SHA-256 to
  address collision concerns.
- **IPFS** uses multihash (a self-describing format: hash function identifier + digest
  length + digest), allowing algorithm agility.
- **Docker/OCI** uses SHA-256 for layer digests and image manifests.
- **Content Delivery Networks** use content hashes for cache keys, enabling global
  deduplication.

The pattern: `store(hash(content), content)` and `retrieve(hash) -> content`. On
retrieval, recompute the hash and verify it matches the address. If the content has been
tampered with, the hash will not match and the tampering is detected. This provides
integrity without requiring a separate signature or MAC, as long as the hash-to-content
binding was established through a trusted channel.

### Hash Function Selection Decision Tree

- Need FIPS 140-2/140-3 compliance? Use **SHA-256** or **SHA-3-256**.
- Need maximum throughput and no FIPS requirement? Use **BLAKE3**.
- Need defense-in-depth against Merkle-Damgard structural attacks? Use **SHA-3-256**.
- Non-security checksum (error detection, not adversarial)? Use **CRC32** or **xxHash**
  (not cryptographic, but extremely fast).
- Password storage? **Not a general-purpose hash** -- use Argon2id, bcrypt, or scrypt
  (see `security-credential-storage`).
- HMAC / keyed authentication? Use **HMAC-SHA256** (see `security-hmac-signatures`).

## Anti-Patterns

1. **MD5 for integrity in adversarial contexts.** MD5 chosen-prefix collisions enable an
   attacker to create two files with identical hashes but different content. The Flame
   malware (2012) used an MD5 collision to forge a Microsoft code-signing certificate,
   allowing malware to be distributed through Windows Update. MD5 is acceptable only for
   non-security checksums where no adversary is in the threat model.

2. **SHA-256(password) for credential storage.** General-purpose hash functions are
   designed to be fast -- a modern GPU can compute billions of SHA-256 hashes per second.
   This speed advantage benefits attackers performing brute-force or dictionary attacks
   against password hashes. Purpose-built password hashing functions (Argon2id, bcrypt,
   scrypt) are deliberately slow, memory-hard, and parameterizable to maintain resistance
   as hardware improves. See `security-credential-storage`.

3. **hash(secret || message) for authentication.** Vulnerable to length extension attacks
   on all Merkle-Damgard hashes (SHA-256, SHA-512, MD5, SHA-1). An attacker who observes
   the hash output and knows the message can append arbitrary data and compute a valid
   hash without knowing the secret. Use HMAC(key, message) instead. HMAC is provably
   secure under standard assumptions and is immune to length extension regardless of the
   underlying hash function.

4. **Truncating hashes without understanding the security impact.** Truncating SHA-256
   output from 256 bits to 128 bits reduces collision resistance from 2^128 to 2^64 -- a
   reduction of 2^64 in the attacker's required work. If space constraints require shorter
   hashes, explicitly analyze whether the reduced collision resistance is acceptable for
   the specific threat model and document the decision. For content addressing where
   collision probability (not adversarial collision) is the concern, truncation may be
   acceptable with sufficient analysis.

5. **Assuming hash uniqueness as an invariant.** Hash functions map an infinite input
   space to a finite output space -- collisions exist by the pigeonhole principle. Systems
   that assume hash uniqueness without verification will fail silently when collisions
   occur (whether natural or adversarial). Content-addressed storage must verify that
   retrieved content matches the expected content, not just the hash. Database schemas
   using hash columns as unique keys must handle collision cases.