SHA-256 Hash Function

What is a cryptographic hash?

A hash function turns input of any size into a short fixed-size digest (fingerprint). SHA-256 always gives 256 bits, usually written as 64 hex digits:

Input	SHA-256
abc	ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad
abd	a52d159f262b2c6ddb724a61840befc36eb30c88877a4030b65cbe86298449c9
hello	2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824

One changed letter (abc → abd) changes 122 of the 256 bits. A good cryptographic hash has these properties:

• Deterministic: the same input always gives the same hash.
• Fast to compute for any input.
• Preimage resistant: given a hash, you cannot find an input that produces it.
• Second-preimage resistant: given one input, you cannot find another with the same hash.
• Collision resistant: you cannot find any two inputs with the same hash.
• Avalanche effect: a tiny change in the input flips about half of the output bits.

A hash is not encryption: there is no key and no way back. Hash tables use simple hash functions for speed. Cryptographic hashes like SHA-256 are slower, but designed so that nobody can steer the output.

Where SHA-256 is used

• Digital signatures: RSA and ECDSA sign the hash of a document, not the whole document.
• Integrity checks: download pages list the SHA-256 of a file so you can check it was not corrupted or tampered with.
• TLS certificates, HMAC and key derivation in HTTPS.
• Bitcoin: mining means finding a block whose (double) SHA-256 hash starts with enough zeros.
• Git is moving from SHA-1 to SHA-256 to name every commit and file.

SHA-256 belongs to the SHA-2 family, designed by the NSA and published in 2001. Its predecessors MD5 and SHA-1 are broken: real collisions were found in 2004 and 2017. SHA-3 (2015) is a completely different design, kept as a backup.

Step 1: padding

SHA-256 works on 512-bit (64-byte) blocks. The message is padded to a multiple of 512 bits:

1. Append a single 1 bit (the byte 80).
2. Append zeros until the length is 448 bits (56 bytes) modulo 512.
3. Append the original length in bits as a 64-bit big-endian number.

For “abc” (3 bytes = 24 bits) the single block is 61 62 63 80, then 52 zero bytes, then 00 00 00 00 00 00 00 18 (0x18 = 24).

Step 2: the message schedule

The block is split into 16 words of 32 bits, W[0] … W[15]. They are expanded to 64 words:

W[t] = σ1(W[t−2]) + W[t−7] + σ0(W[t−15]) + W[t−16] (for t = 16 … 63)

All additions are mod 2³². For “abc”, W[0] = 61626380 and W[15] = 00000018.

Step 3: 64 rounds of compression

Eight 32-bit registers a, b, c, d, e, f, g, h start with the initial hash H0 … H7: the first 32 bits of the fractional parts of the square roots of the first 8 primes (√2 = 1.6a09e667…₁₆, so H0 = 6a09e667). Then 64 rounds run, each with its own constant K[t] (from the cube roots of the first 64 primes) and message word W[t]:

• T1 = h + Σ1(e) + Ch(e, f, g) + K[t] + W[t]
• T2 = Σ0(a) + Maj(a, b, c)
• Shift: h ← g, g ← f, f ← e, e ← d + T1, d ← c, c ← b, b ← a, a ← T1 + T2

Function	Definition	Idea
Ch(e, f, g)	(e AND f) XOR (NOT e AND g)	“Choose”: each bit of e picks the bit from f or g
Maj(a, b, c)	(a AND b) XOR (a AND c) XOR (b AND c)	“Majority” of the three bits
Σ0(a)	ROTR²(a) ⊕ ROTR¹³(a) ⊕ ROTR²²(a)	Mixes bits of a
Σ1(e)	ROTR⁶(e) ⊕ ROTR¹¹(e) ⊕ ROTR²⁵(e)	Mixes bits of e
σ0(x)	ROTR⁷(x) ⊕ ROTR¹⁸(x) ⊕ SHR³(x)	Message schedule
σ1(x)	ROTR¹⁷(x) ⊕ ROTR¹⁹(x) ⊕ SHR¹⁰(x)	Message schedule

ROTR is a rotation to the right; SHR is a shift to the right (bits fall off). Mixing XOR, AND and addition mod 2³² is what makes SHA-256 non-linear and hard to reverse.

Step 4: the digest

After 64 rounds, each register is added to the value it started from: H0 ← H0 + a, …, H7 ← H7 + h (mod 2³²). For a longer message, these H values are the starting point for the next block: this chaining is the Merkle–Damgård construction. After the last block, H0 ‖ H1 ‖ … ‖ H7 is the 256-bit hash.

How hard is it to break?

• Preimage: to find an input for a given hash you must try about 2²⁵⁶ inputs.
• Collision: by the birthday paradox (23 people already give a 50 % chance of a shared birthday), you expect a collision after about √(2²⁵⁶) = 2¹²⁸ tries. Even every computer on Earth running for billions of years would not get close.

No attack better than these generic ones is known for full SHA-256.

Hashing vs encryption

	Hash (SHA-256)	Encryption (AES)
Key	None	Secret key
Reversible	No	Yes, with the key
Output size	Fixed (256 bits)	About the same as the input
Purpose	Fingerprint, integrity, signatures	Confidentiality

Code

In real programs, use the standard library:

import hashlib

print(hashlib.sha256(b"abc").hexdigest())
# ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad

with open("download.iso", "rb") as f:          # check a downloaded file
    print(hashlib.file_digest(f, "sha256").hexdigest())   # Python 3.11+

SHA-256 from scratch, following the four steps above. The constants are computed exactly with integer roots:

import math

def primes(n):
    found, k = [], 2
    while len(found) < n:
        if all(k % p for p in found):
            found.append(k)
        k += 1
    return found

def icbrt(n):                                  # integer cube root
    lo, hi = 0, 1 << (n.bit_length() // 3 + 2)
    while lo < hi:
        mid = (lo + hi + 1) // 2
        lo, hi = (mid, hi) if mid ** 3 <= n else (lo, mid - 1)
    return lo

M = 0xFFFFFFFF
H0 = [math.isqrt(p << 64) & M for p in primes(8)]     # fractional bits of √p
K = [icbrt(p << 96) & M for p in primes(64)]          # fractional bits of ∛p

def rotr(x, n):
    return ((x >> n) | (x << (32 - n))) & M

def sha256(msg: bytes) -> str:
    bits = len(msg) * 8
    msg += b"\x80" + b"\x00" * ((55 - len(msg)) % 64) + bits.to_bytes(8, "big")
    h = H0[:]
    for off in range(0, len(msg), 64):
        w = [int.from_bytes(msg[off + 4 * t:off + 4 * t + 4], "big") for t in range(16)]
        for t in range(16, 64):
            s0 = rotr(w[t - 15], 7) ^ rotr(w[t - 15], 18) ^ (w[t - 15] >> 3)
            s1 = rotr(w[t - 2], 17) ^ rotr(w[t - 2], 19) ^ (w[t - 2] >> 10)
            w.append((s1 + w[t - 7] + s0 + w[t - 16]) & M)
        a, b, c, d, e, f, g, hh = h
        for t in range(64):
            t1 = (hh + (rotr(e, 6) ^ rotr(e, 11) ^ rotr(e, 25)) + ((e & f) ^ (~e & g)) + K[t] + w[t]) & M
            t2 = ((rotr(a, 2) ^ rotr(a, 13) ^ rotr(a, 22)) + ((a & b) ^ (a & c) ^ (b & c))) & M
            hh, g, f, e, d, c, b, a = g, f, e, (d + t1) & M, c, b, a, (t1 + t2) & M
        h = [(x + y) & M for x, y in zip(h, [a, b, c, d, e, f, g, hh])]
    return "".join(f"{x:08x}" for x in h)

print(sha256(b"abc"))     # ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad

Common mistakes

• Storing the length in bytes. The last 64 bits hold the length in bits: 3 bytes → 24.
• Forgetting the 1 bit. Even if the message is exactly 56 bytes, the 80 byte is still added, which pushes the length into a second block.
• Calling hashing “encryption”. A hash cannot be decrypted. “Decrypting” an MD5 or SHA-256 hash really means guessing inputs until one matches.
• Hashing passwords with plain SHA-256. Use a salt and a slow password hash (bcrypt, scrypt, Argon2).
• Assuming similar inputs give similar hashes. The avalanche effect makes the hashes of “abc” and “abd” look completely unrelated.