What Is SHA? The Only Deep Dive You’ll Ever Need

1. Introduction: Why Hashing Even Exists

SHA (Secure Hash Algorithm) was developed by the NSA and standardized by NIST in the 1990s.¹

The Historical Development of SHA and NSA Involvement

The SHA family has a complex history deeply intertwined with the U.S. National Security Agency (NSA). Here’s the full story:

The Origins (1970s-1980s):

• The NSA had been researching cryptographic hash functions since the 1970s
• They developed the original SHA-0 in 1993, but it was withdrawn shortly after. The NSA discovered a flaw and released the stronger SHA-1 in 1995, three years before a public collision attack was found by researchers Chabaud and Joux in 1998²
• This shows the NSA’s rigorous internal review process - they caught the flaw themselves

The Clinton Administration and Export Controls (1990s):

• In 1996, President Clinton signed Executive Order 13026, classifying encryption as “munitions”³
• This created the Export Control Classification Number (ECCN) 5A991, restricting export of strong crypto
• SHA-1 (published in 1995) offers 80 bits of collision resistance (due to its 160-bit output). While this complied with US export controls of the era, it is debated whether the NSA intentionally limited the strength or simply followed the standard design practices of the time⁴
• The NSA argued that 80-bit security was sufficient for commercial use, but they knew quantum computers would eventually break it

The Dual Standards Controversy:

• The NSA used classified, stronger algorithms internally while pushing weaker versions for public/commercial use
• This “dual standards” approach created distrust in the cryptographic community
• Bruce Schneier famously called this “the NSA’s two-crypto system”⁵

SHA-2 Development (2000s):

• After SHA-1 was broken in 2005, NIST called for SHA-2 (SHA-256, SHA-384, SHA-512)
• The NSA submitted the winning design. Unlike the later scandal with the Dual_EC_DRBG random number generator, SHA-2 uses “nothing up my sleeve” numbers (square roots of primes) for its constants.
• No backdoors have ever been found in SHA-2, and it remains the industry standard today⁶
• SHA-2 was standardized in 2001 as FIPS 180-2

SHA-3 Competition (2010s):

• After the SHA-2 controversy, NIST held an open competition for SHA-3
• 64 submissions from around the world, won by Keccak (pronounced “ketchak”)
• This was the first time the NSA didn’t submit the winning design
• SHA-3 was standardized in 2015 (FIPS 202), providing a completely different construction (sponge vs Merkle-Damgård). Note that Ethereum uses the original Keccak-256 submission, which has slightly different padding than the final SHA-3 standard.

The NSA’s Role Today:

• The NSA still influences NIST standards through the Commercial Solutions for Classified (CSfC) program
• They provide input on cryptographic standards but no longer dominate the process
• The agency has shifted focus to post-quantum cryptography and quantum-resistant algorithms

Encryption hides data. Hashing destroys it - irreversibly - and gives you a short fingerprint.

You can’t “decrypt” a hash. There is no key. There is no reverse function.

Hash functions solve three real problems:

1. Integrity: Did this file change in transit?
2. Deduplication: Are these two giant blobs actually identical?
3. Commitment: Prove you knew something in 2015 without revealing it in 2015.

Every Git commit, every Docker layer, every blockchain block, every TLS certificate fingerprint, every JWT you’ve ever sent - all live on SHA.

The Mathematical Reality: The Pigeonhole Principle

Why can’t you decrypt a hash? It’s not just about mixing; it’s about information loss.

SHA-256 produces a 256-bit output. That means there are exactly $2^{256}$ possible hashes. But the input space is effectively infinite (any file, any size).

By the Pigeonhole Principle, if you have more inputs than outputs, collisions must exist. In fact, for every single SHA-256 hash, there are an infinite number of matching inputs.

The security of a hash function isn’t that collisions don’t exist-it’s that finding them is computationally impossible.

The Birthday Paradox

How hard is it to find a collision? You might think you need to try $2^{256}$ inputs. Wrong. You only need $\approx \sqrt{2^{256}} = 2^{128}$ tries.

2. The SHA Family: SHA-0 → SHA-1 → SHA-2 → SHA-3

SHA-2 and SHA-3 are not upgrades of each other - they are parallel families. NIST kept both because diversity is defense.

3. What Makes a Hash Function Secure?

Five properties you must memorize:

Input:  "hello world"
SHA-256: b94d27b9934d3e08a52e52d7da7dabfac484efe37a5380ee9088f7ace2efcde9

Input:  "hellp world" (one letter changed)
SHA-256: cd59836a7318ed89a5328ee249c5b9ab8a273acdd52b9540eeef041ef3a38557
→ 100% of hex digits changed

Code: Proving the Avalanche Effect

Don’t believe it? Here is a Python script to prove that flipping 1 bit changes ~50% of the output bits.

1
import hashlib
2

3
def get_bits(s):
4
    return bin(int(s, 16))[2:].zfill(256)
5

6
def avalanche_demo():
7
    msg1 = b"hello world"
8
    msg2 = b"hello worle"  # only last bit flipped (d=01100100 → e=01100101)
9

10
    h1 = hashlib.sha256(msg1).hexdigest()
11
    h2 = hashlib.sha256(msg2).hexdigest()
12

13
    bits1 = get_bits(h1)
14
    bits2 = get_bits(h2)
15

16
    diff_count = sum(a != b for a, b in zip(bits1, bits2))
17

18
    print(f"Msg 1: {msg1}")
19
    print(f"Hash 1: {h1}")
20
    print(f"Msg 2: {msg2}")
21
    print(f"Hash 2: {h2}")
22
    print(f"Total bits: 256")
23
    print(f"Different bits: {diff_count}")
24
    print(f"Avalanche percentage: {diff_count / 256 * 100:.2f}%")
25

26
avalanche_demo()
27

28
# Typical Output:
29
# Different bits: 126
30
# Avalanche percentage: 49.22%

4. Inside SHA-256: How It Actually Works

SHA-256 is a Merkle–Damgård construction. It processes messages in blocks, feeding the result of one block into the next.

The Architecture

Step-by-Step Mechanics

1. Pad message so length $\equiv 448 \pmod{512}$, then append 64-bit length. This ensures the message is a perfect multiple of 512 bits.

2. Split into 512-bit blocks.
3. Initialize eight 32-bit constants ($H_0$ to $H_7$).
   • These aren’t random. They are the fractional parts of the square roots of the first 8 primes (2, 3, 5, 7, 11, 13, 17, 19).
   • Why? To prove there’s no “backdoor” or hidden structure.
4. The Compression Function (The Core):
   • Run 64 rounds of bitwise mixing.

The Math of the Rounds

Inside the loop, SHA-256 uses six logical functions on 32-bit words. Let $\oplus$ be XOR, $\land$ be AND, $\neg$ be NOT. $ROTR^n(x)$ is circular right rotation by $n$ bits. $SHR^n(x)$ is right shift by $n$ bits.

Python Implementation of the Compression Loop

This is what happens inside a single block processing step:

1
def right_rotate(value, amount):
2
    return ((value >> amount) | (value << (32 - amount))) & 0xFFFFFFFF
3

4
def sha256_compression(chunk, H):
5
    # 1. Prepare Message Schedule W[0..63]
6
    W = [0] * 64
7
    # Copy first 16 words from chunk
8
    for i in range(16):
9
        W[i] = int.from_bytes(chunk[i*4:(i+1)*4], 'big')
10

11
    # Expand to 64 words
12
    for i in range(16, 64):
13
        s0 = right_rotate(W[i-15], 7) ^ right_rotate(W[i-15], 18) ^ (W[i-15] >> 3)
14
        s1 = right_rotate(W[i-2], 17) ^ right_rotate(W[i-2], 19) ^ (W[i-2] >> 10)
15
        W[i] = (W[i-16] + s0 + W[i-7] + s1) & 0xFFFFFFFF
16

17
    # 2. Initialize Working Variables
18
    a, b, c, d, e, f, g, h = H
19

20
    # 3. Main Loop (64 rounds)
21
    for i in range(64):
22
        S1 = right_rotate(e, 6) ^ right_rotate(e, 11) ^ right_rotate(e, 25)
23
        ch = (e & f) ^ ((~e) & g)
24
        temp1 = (h + S1 + ch + K[i] + W[i]) & 0xFFFFFFFF
25

26
        S0 = right_rotate(a, 2) ^ right_rotate(a, 13) ^ right_rotate(a, 22)
27
        maj = (a & b) ^ (a & c) ^ (b & c)
28
        temp2 = (S0 + maj) & 0xFFFFFFFF
29

30
        h = g
31
        g = f
32
        f = e
33
        e = (d + temp1) & 0xFFFFFFFF
34
        d = c
35
        c = b
36
        b = a
37
        a = (temp1 + temp2) & 0xFFFFFFFF
38

39
    # 4. Add to current hash state
40
    return [
41
        (H[0] + a) & 0xFFFFFFFF,
42
        (H[1] + b) & 0xFFFFFFFF,
43
        # ... etc for all 8
44
    ]

5. SHA-3: Why It’s Built Completely Differently

SHA-3 (Keccak) uses a Sponge Construction. It doesn’t use the Merkle–Damgård structure at all.

• 1600-bit internal state (5×5×64 grid of bits).
• Absorb phase: XOR message chunks into the state, then run the permutation.
• Squeeze phase: Read parts of the state as output, run permutation, read more…

Why Sponge wins:

• Immune to Length Extension Attacks: The internal state is never fully exposed.
• Variable Output: Can produce infinite output stream (SHAKE128/SHAKE256).
• Simpler Math: Uses only XOR, AND, NOT, and Rotations. No addition modulo $2^{32}$.

6. Length Extension Attacks (The Bug Everyone Forgets)

This is the most dangerous subtle bug in crypto. SHA-256 (and all SHA-2/MD5) has this vulnerability.

The Flaw: If you know $H = \text{SHA256}(\text{Secret} \parallel \text{Message})$, you can calculate $\text{SHA256}(\text{Secret} \parallel \text{Message} \parallel \text{Padding} \parallel \text{MaliciousData})$ without knowing the Secret.

Why? Because the output of SHA-256 is the internal state of the hasher after processing the message. You can just load that state into your own hasher and keep going!

Exploit Code Example

Imagine a web API that signs requests like this: signature = sha256(SECRET_KEY + "user=john&role=user")

An attacker sees the signature 5d9c.... They want to become admin.

1
import hlextend  # Tool for length extension attacks
2

3
# Attacker knows:
4
original_msg = b"user=john&role=user"
5
original_sig = "5d9c..." # The hash they intercepted
6
append_msg = b"&role=admin"
7

8
# Attacker computes new signature WITHOUT knowing the secret:
9
sha = hlextend.new('sha256')
10
new_sig = sha.extend(append_msg, original_msg, length_of_secret, original_sig)
11

12
# Result:
13
# New Message: "user=john&role=user" + PADDING + "&role=admin"
14
# New Signature: Valid hash of (Secret + New Message)

The Fix:

1. Use HMAC: HMAC(key, message). It does nested hashing to prevent this.

Deep Dive: How HMAC Fixes It

HMAC isn’t just hash(key + msg). It’s a nested construction that isolates the internal state.

Where:

• $H$ is the hash function (SHA-256)
• $K'$ is the key (padded/hashed to block size)
• $opad$ is outer padding (0x5c5c...)
• $ipad$ is inner padding (0x3636...)

Because the output of the inner hash is processed again by the outer hash (with a different key mask), the attacker cannot extend the message. The internal state of the outer hash is finalized and “sealed”.

2. Use SHA-3 or BLAKE3: They are immune by design.
3. Use Double Hash: SHA256(SHA256(x)) (Bitcoin does this).

7. Where SHA Is Used in the Real World

Code: Bitcoin Mining (Proof of Work)

This is the actual logic running on millions of ASICs right now (simplified to Python).

1
import hashlib
2
import struct
3

4
def double_sha256(header_bytes):
5
    return hashlib.sha256(hashlib.sha256(header_bytes).digest()).digest()
6

7
def mine_block(block_header_prefix, target_difficulty):
8
    nonce = 0
9
    while True:
10
        # Construct header with current nonce (4 bytes)
11
        # <Prefix 76 bytes> + <Nonce 4 bytes>
12
        header = block_header_prefix + struct.pack("<I", nonce)
13

14
        block_hash = double_sha256(header)
15

16
        # Check if hash is below target (interpreted as big integer)
17
        # (In reality, Bitcoin compares little-endian, but logic holds)
18
        hash_int = int.from_bytes(block_hash, 'big')
19

20
        if hash_int < target_difficulty:
21
            print(f"Found Nonce: {nonce}")
22
            print(f"Hash: {block_hash.hex()}")
23
            return nonce
24

25
        nonce += 1
26
        if nonce % 1000000 == 0:
27
            print(f"Trying nonce {nonce}...")

8. How to Compute and Verify Hashes in Practice

Here’s the most common real-world use case: verifying that a file you downloaded hasn’t been corrupted or tampered with.

Example: Verifying a Debian Linux ISO

When you download debian-12.7.0-amd64-netinst.iso from a mirror, the official Debian repository provides a SHA-256 checksum on their website:

1
8fde79cfc6b20a696200fc5c15219cf6d721e8feb367e9e0e33a79d1cb68fa83

To verify on Linux/macOS:

# Compute the hash of the downloaded file
sha256sum debian-12.7.0-amd64-netinst.iso

# Expected output:
# 8fde79cfc6b20a696200fc5c15219cf6d721e8feb367e9e0e33a79d1cb68fa83  debian-12.7.0-amd64-netinst.iso

# If the hash matches → file is genuine
# If the hash differs → file was corrupted OR replaced by attacker

To verify on Windows (PowerShell):

(Get-FileHash -Path "debian-12.7.0-amd64-netinst.iso" -Algorithm SHA256).Hash
# Compare output to official SHA-256

To verify on macOS (using brew-installed gnu-coreutils):

sha256sum debian-12.7.0-amd64-netinst.iso
# Or with standard macOS sha256:
shasum -a 256 debian-12.7.0-amd64-netinst.iso

Advanced: Verifying Large Downloads with Streaming Hash

For multi-gigabyte files, you may want to compute the hash while downloading (to verify incrementally):

1
import hashlib
2

3
def compute_file_hash_streamed(filepath, chunk_size=65536):
4
    """Compute SHA-256 hash of a file, reading in chunks."""
5
    sha256_hash = hashlib.sha256()
6

7
    with open(filepath, "rb") as f:
8
        # Read file in 64KB chunks
9
        for chunk in iter(lambda: f.read(chunk_size), b""):
10
            sha256_hash.update(chunk)
11
            # Could print progress here: print(f"Read {bytes_read} bytes...")
12

13
    return sha256_hash.hexdigest()
14

15
# Usage
16
file_hash = compute_file_hash_streamed("debian-12.7.0-amd64-netinst.iso")
17
print(f"SHA-256: {file_hash}")
18

19
# Compare with official
20
official_hash = "8fde79cfc6b20a696200fc5c15219cf6d721e8feb367e9e0e33a79d1cb68fa83"
21
if file_hash == official_hash:
22
    print("✓ File verified as genuine")
23
else:
24
    print("✗ File has been modified - DO NOT USE")

Why This Protects You

Scenario 1: File corrupted in transit (your problem)

• Network bit flip changes 0 to 1 somewhere in the 700MB file
• Hash changes completely (avalanche effect)
• Verification catches it, you re-download

Scenario 2: Attacker replaces file

• Attacker modifies ISO to include malware
• To avoid detection, they need to craft modified ISO with same SHA-256
• Infeasible: $2^{128}$ computational effort (billions of years on all Earth’s computers combined)
• Attacker gives up, finds different target

Scenario 3: Man-in-the-middle attack

• Attacker intercepts download, replaces with trojanized version
• You verify hash, it doesn’t match
• You know not to use this file

The reason SHA-256 is so effective here is the collision resistance property: it is computationally impossible for an attacker to create two different files with the same hash.

9. Case Study: The SHAttered Attack (SHA-1 is Dead)

In 2017, Google and CWI Amsterdam announced SHAttered, the first practical collision for SHA-1.

How they did it: They used an Identical-Prefix Collision attack.

1. They created a special header for the PDF files.
2. They used 6,500 CPU years and 110 GPU years of computation (still 100,000x faster than brute force).
3. They found a collision in the compression function that allowed them to swap the content of the PDF (blue vs red) without changing the hash.

“We have broken SHA-1 in practice. … This is the result of a long line of research starting in 2005.” - shattered.io

The Impact: This killed SHA-1 for good. Browsers stopped accepting SHA-1 certificates, and Git moved to harden its SHA-1 usage (and eventually migrate to SHA-256).

10. Why SHA Should Never Be Used for Passwords

Grover’s algorithm gives a quadratic speedup. This means a quantum computer effectively halves the bit-strength of a hash function.

Rule of thumb: If you are building for the post-quantum era, use SHA-384 or SHA-512. 256 bits is not enough for collision resistance against a quantum adversary.

11. Alternatives to SHA (Use These Instead)

12. Final Summary: What Non-Experts Always Misunderstand

1. Hashing ≠ encryption. There is no key. You cannot “decrypt” it.
2. SHA-256 is not “broken” but it’s not future-proof against quantum.
3. Using raw SHA for passwords is professional negligence in 2025.
4. SHA is a family, not one algorithm. SHA-1 ≠ SHA-2 ≠ SHA-3.
5. Length-extension attacks exist. Never use raw SHA-2 as a MAC.
6. HMAC exists for a reason. Use it.
7. For new designs in 2025+: default to BLAKE3 or SHA-3.