I think of the Secure Hash Algorithm (SHA) family as the workhorse behind data integrity checking across nearly every secure system I interact with. A hash function takes an input of arbitrary size and produces a fixed-size output, called a digest or hash, in a way that is deterministic (same input always gives the same output), fast to compute, and — critically for security purposes — practically impossible to reverse or to find two different inputs that produce the same output. SHA is a specific family of such cryptographic hash functions, standardized by the U.S. National Institute of Standards and Technology (NIST). Its importance comes from how many things depend on it under the hood: digital signatures, password storage, blockchain systems, file integrity verification, and certificate authorities all rely on SHA or its close relatives to guarantee that data hasn’t been tampered with.
History and Background
I trace the SHA family back to 1993, when NIST published SHA-0 (originally just called SHA) as part of the Secure Hash Standard, working alongside the National Security Agency (NSA), which contributed to its design. SHA-0 was quickly withdrawn after a flaw was discovered, and NIST published a corrected version, SHA-1, in 1995 — this became widely deployed for nearly two decades. As cryptanalysis techniques advanced, weaknesses were found in SHA-1’s design, and researchers demonstrated a practical collision attack (finding two different inputs producing the same hash) in 2017, in an attack named “SHAttered,” which effectively ended SHA-1’s use for security-critical purposes. Anticipating this, NIST had already published SHA-2 in 2001, a family including SHA-224, SHA-256, SHA-384, and SHA-512, with a substantially larger internal state and more rounds of mixing, making it far more resistant to the kinds of attacks that broke SHA-1. To diversify further and hedge against unforeseen weaknesses in the SHA-2 design (which shares structural similarities with SHA-1), NIST ran a public competition and standardized SHA-3 in 2015, based on the Keccak algorithm designed by Guido Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche — notably, SHA-3 uses an entirely different internal structure (a sponge construction) rather than the Merkle-Damgård structure used by SHA-1 and SHA-2.
Problem Statement
I use SHA to solve the problem of verifying data integrity and authenticity in situations where I need a compact, fixed-size “fingerprint” of arbitrary data that changes unpredictably if even a single bit of the original data changes, and that cannot feasibly be reverse-engineered or forged. Before cryptographic hash functions, verifying that a large file or message hadn’t been altered required comparing the entire content, which is impractical for many use cases like digital signatures (where I want to sign a short digest rather than an entire large document) or password storage (where I never want to store the actual password). The problem SHA solves is producing such a fingerprint efficiently, with strong guarantees against being forged or reversed.
Core Concepts
- Digest/hash: The fixed-size output produced by the hash function, regardless of the input’s length (e.g., SHA-256 always produces 256 bits, 32 bytes).
- Preimage resistance: Given a hash output, it should be computationally infeasible to find any input that produces it.
- Second preimage resistance: Given a specific input and its hash, it should be infeasible to find a different input producing the same hash.
- Collision resistance: It should be infeasible to find any two distinct inputs that produce the same hash output.
- Avalanche effect: A small change in input (even a single bit) should produce a drastically different, unpredictable output hash.
- Padding: A process of extending the input message to a length that’s a multiple of the algorithm’s block size, in a way that unambiguously encodes the original message length.
- Compression function: The core building block that processes each fixed-size block of the padded message, updating an internal state.
How It Works
I’ll describe the process for SHA-256, the most widely used member of the SHA-2 family, since its structure is representative of the Merkle-Damgård approach used across SHA-1 and SHA-2:
- I take the input message and pad it: append a single ‘1’ bit, then enough ‘0’ bits to make the length congruent to 448 mod 512, then append the original message length as a 64-bit integer, so the total padded length is a multiple of 512 bits.
- I break the padded message into 512-bit blocks.
- I initialize eight 32-bit hash state values (h0 through h7) to specific fixed constants, derived from the fractional parts of the square roots of the first eight prime numbers.
- For each 512-bit block, I expand it into 64 32-bit “message schedule” words using a specified mixing formula that combines earlier words through bitwise rotations, shifts, and XOR operations.
- I run 64 rounds of compression on this block, where each round mixes the message schedule word for that round into eight working variables using a series of bitwise operations (AND, XOR, NOT, modular addition, and specific bitwise rotation functions).
- After all 64 rounds for a block, I add the resulting working variables back into the running hash state (h0 through h7).
- I repeat steps 4 through 6 for every block in the padded message, carrying the hash state forward from block to block.
- After processing the final block, I concatenate h0 through h7 to produce the final 256-bit digest.
Working Principle
I think about the internal logic of SHA-256 as a carefully engineered mixing machine designed to destroy any predictable relationship between input and output. Each round applies nonlinear bitwise functions (majority and choice functions) along with modular addition and bit rotations, and because these operations are repeated 64 times per block, even a single flipped bit in the input cascades and spreads unpredictably through the entire internal state by the time processing finishes — this is the avalanche effect I mentioned earlier. The Merkle-Damgård construction, which chains blocks together by feeding the output hash state of one block in as the starting state for the next, ensures that the final digest depends on every bit of the entire input, not just the last block processed. The specific choice of constants (derived from properties of prime numbers, chosen to avoid any suspicion of hidden backdoors, a design principle called “nothing-up-my-sleeve numbers”) and the specific bitwise operations were carefully selected by cryptographers to resist all known classes of cryptanalytic attack, including differential and linear cryptanalysis.
Mathematical Foundation
I’ll describe the core operations of SHA-256 mathematically. Given a 512-bit message block, it is expanded into 64 words $W_0, \dots, W_63$ (each 32 bits), where for $t \ge 16$:
$$ W_t = \sigma_1(W_{t-2}) + W_{t-7} + \sigma_0(W_{t-15}) + W_{t-16} \pmod{2^{32}} $$
with the small sigma functions defined using rotate-right (ROTR) and shift-right (SHR) operations:
$$ \sigma_0(x) = \text{ROTR}^7(x) \oplus \text{ROTR}^{18}(x) \oplus \text{SHR}^3(x) $$
$$ \sigma_1(x) = \text{ROTR}^{17}(x) \oplus \text{ROTR}^{19}(x) \oplus \text{SHR}^{10}(x) $$
Each of the 64 compression rounds updates eight working variables $a,b,c,d,e,f,g,h$ using:
$$ T_1 = h + \Sigma_1(e) + \text{Ch}(e,f,g) + K_t + W_t $$
$$ T_2 = \Sigma_0(a) + \text{Maj}(a,b,c) $$
where the choice and majority functions are:
$$ \text{Ch}(e,f,g) = (e \wedge f) \oplus (\lnot e \wedge g) $$
$$ \text{Maj}(a,b,c) = (a \wedge b) \oplus (a \wedge c) \oplus (b \wedge c) $$
and the large sigma functions are:
$$ \Sigma_0(x) = \text{ROTR}^2(x) \oplus \text{ROTR}^{13}(x) \oplus \text{ROTR}^{22}(x) $$
$$ \Sigma_1(x) = \text{ROTR}^6(x) \oplus \text{ROTR}^{11}(x) \oplus \text{ROTR}^{25}(x) $$
The working variables are then rotated for the next round: $h=g, g=f, f=e, e=d+T_1, d=c, c=b, b=a, a=T_1+T_2$ (all additions modulo $2^{32}$), and $K_t$ is a round-specific constant derived from the fractional parts of cube roots of the first 64 primes.
Diagrams
flowchart TD
A[Input message] --> B[Pad message to multiple of 512 bits]
B --> C[Split into 512-bit blocks]
C --> D[Initialize hash state h0..h7]
D --> E[For each block: expand into 64 message schedule words]
E --> F[Run 64 rounds of compression mixing state with schedule words]
F --> G[Add compressed block result into running hash state]
G --> H{More blocks remaining?}
H -- Yes --> E
H -- No --> I[Concatenate h0..h7 as final digest]Pseudocode
function SHA256(message):
message = pad_message(message) // append 1 bit, zero bits, 64-bit length
blocks = split_into_512_bit_blocks(message)
h0..h7 = initial_hash_constants() // fixed standard constants
K0..K63 = round_constants() // fixed standard constants
for each block in blocks:
W[0..15] = split_block_into_16_words(block)
for t in 16 to 63:
W[t] = sigma1(W[t-2]) + W[t-7] + sigma0(W[t-15]) + W[t-16] (mod 2^32)
a,b,c,d,e,f,g,h = h0,h1,h2,h3,h4,h5,h6,h7
for t in 0 to 63:
T1 = h + BigSigma1(e) + Ch(e,f,g) + K[t] + W[t] (mod 2^32)
T2 = BigSigma0(a) + Maj(a,b,c) (mod 2^32)
h = g; g = f; f = e; e = d + T1 (mod 2^32)
d = c; c = b; b = a; a = T1 + T2 (mod 2^32)
h0 += a; h1 += b; h2 += c; h3 += d
h4 += e; h5 += f; h6 += g; h7 += h (all mod 2^32)
return concatenate(h0, h1, h2, h3, h4, h5, h6, h7)
Step-by-Step Example
I want to walk through the padding step concretely, since it’s the part that’s easiest to trace by hand, and then describe (without hand-computing 64 rounds of bitwise mixing, which isn’t practical to do manually) what happens next.
Suppose my input message is the ASCII string “abc” (3 bytes, 24 bits).
- I append a single ‘1’ bit: the bit pattern becomes the 24 bits of “abc” followed by a
1bit. - I then append ‘0’ bits until the total length is congruent to 448 modulo 512. Since I have 25 bits so far, I need $448 – 25 = 423$ zero bits.
- I then append the original message length (24, in bits) as a 64-bit big-endian integer, bringing the total length to exactly 512 bits — one complete block.
- This single 512-bit block is then processed through the message schedule expansion (producing 64 32-bit words) and 64 rounds of compression as described above, updating the eight working variables and finally the hash state h0 through h7.
- After processing this one block, concatenating h0 through h7 gives the final SHA-256 digest. The well-known, verifiable result for SHA-256(“abc”) is the hexadecimal digest
ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad. I include this so I have a fixed reference point I can check any implementation against — feeding “abc” into a correct SHA-256 implementation should always reproduce exactly this digest.
Time Complexity
Processing a message of $n$ bits requires padding it and splitting it into $\lceil n/512 \rceil$ blocks, and each block requires a fixed amount of work: 64 rounds of compression, each round performing a constant number of bitwise and arithmetic operations, plus the message schedule expansion, which is also a fixed 64 operations per block. So the total time complexity is $O(n)$, linear in the length of the input message — this is one of the practically important properties of cryptographic hash functions, since I need to be able to hash even very large files efficiently, and SHA-256 processes data at a consistent, predictable rate regardless of content.
Space Complexity
I need to store the eight 32-bit hash state values (32 bytes total), the round constants (64 fixed 32-bit values, though these are typically hardcoded rather than computed at runtime), and, while processing each block, the 64-word message schedule (256 bytes). None of this scales with the size of the input message — I only need to hold one block’s worth of working state at a time, streaming through the input block by block. So the space complexity is $O(1)$ relative to input size (constant, aside from needing to read the input itself), which is another important practical property, letting SHA-256 hash arbitrarily large files without needing to hold the entire file in memory at once.
Correctness Analysis
I think about correctness for a cryptographic hash function differently than for an optimization algorithm — there’s no single “correct answer” to converge to; instead, correctness means that the specific, standardized sequence of operations (padding, message schedule expansion, compression rounds, and final state concatenation) is implemented exactly as specified in the NIST FIPS 180-4 standard, since any deviation, however small, produces a completely different (and non-standard, non-interoperable) hash function. I verify implementation correctness empirically, using known test vectors — such as the SHA-256(“abc”) result I cited above — published by NIST specifically for this purpose. Security correctness, meaning that SHA-256 actually provides the properties of preimage resistance, second preimage resistance, and collision resistance, rests on decades of cryptanalytic scrutiny by the research community rather than a formal mathematical proof; no efficient attack better than generic brute-force or birthday-bound attacks (both computationally infeasible for 256-bit output, requiring on the order of $2^{256}$ or $2^{128}$ operations respectively) has been publicly demonstrated against SHA-256 as of my knowledge, which stands in contrast to SHA-1, where practical collision attacks eventually broke this assumption.
Advantages
- It is deterministic, always producing the same output for the same input, which is essential for verification use cases.
- It produces a fixed-size output regardless of input size, making it efficient to store, compare, and transmit as a fingerprint of much larger data.
- The avalanche effect means even a tiny change in input produces a completely different, unpredictable hash, making tampering easy to detect.
- SHA-256 and SHA-3 remain, as of my knowledge, resistant to all known practical attacks, unlike the now-broken SHA-1.
- It’s extremely fast to compute, processing data at high throughput even on modest hardware, and requires only constant memory regardless of input size.
Disadvantages
- SHA-1 and SHA-0 are cryptographically broken and should not be used for any security-sensitive purpose, though SHA-1 is still occasionally found in legacy systems.
- SHA-2 (including SHA-256) shares structural similarities with SHA-1 (the Merkle-Damgård construction), which, while not currently a known weakness, was part of the motivation for standardizing the structurally different SHA-3.
- As a plain hash function, SHA-256 is not suitable on its own for password storage, since its speed (a strength for integrity checking) is a weakness against brute-force password guessing; purpose-built password hashing functions like bcrypt, scrypt, or Argon2 (which are deliberately slow and memory-hard) should be used instead.
- It provides no built-in mechanism for authentication (proving who created the hash) — for that, a keyed variant like HMAC-SHA256 or a full digital signature scheme is needed.
- Being a widely deployed standard for decades, weaknesses (as seen with SHA-1) can take years to be discovered and even longer for systems to migrate away from once found.
Applications
- Digital signatures, where a message is hashed before being signed, letting cryptographic signature algorithms operate efficiently on a fixed-size digest rather than the entire message.
- TLS/SSL certificates and the broader public key infrastructure, using SHA-2 family hashes extensively.
- Blockchain and cryptocurrency systems, such as Bitcoin, which uses SHA-256 extensively for both mining (proof-of-work) and transaction/block identification.
- File integrity verification, letting me confirm a downloaded file hasn’t been corrupted or tampered with by comparing published hash values.
- Version control systems, where content-addressable storage (like Git, which historically used SHA-1 and has been transitioning toward SHA-256) uses hashes to uniquely identify content.
- HMAC (Hash-based Message Authentication Code) constructions, combining SHA with a secret key to provide both integrity and authenticity for messages.
Implementation in C
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stdlib.h>
// A simplified, self-contained SHA-256 implementation, following FIPS 180-4.
#define ROTR(x,n) (((x) >> (n)) | ((x) << (32 - (n))))
static const uint32_t K[64] = {
0x428a2f98,0x71374491,0xb5c0fbcf,0xe9b5dba5,0x3956c25b,0x59f111f1,0x923f82a4,0xab1c5ed5,
0xd807aa98,0x12835b01,0x243185be,0x550c7dc3,0x72be5d74,0x80deb1fe,0x9bdc06a7,0xc19bf174,
0xe49b69c1,0xefbe4786,0x0fc19dc6,0x240ca1cc,0x2de92c6f,0x4a7484aa,0x5cb0a9dc,0x76f988da,
0x983e5152,0xa831c66d,0xb00327c8,0xbf597fc7,0xc6e00bf3,0xd5a79147,0x06ca6351,0x14292967,
0x27b70a85,0x2e1b2138,0x4d2c6dfc,0x53380d13,0x650a7354,0x766a0abb,0x81c2c92e,0x92722c85,
0xa2bfe8a1,0xa81a664b,0xc24b8b70,0xc76c51a3,0xd192e819,0xd6990624,0xf40e3585,0x106aa070,
0x19a4c116,0x1e376c08,0x2748774c,0x34b0bcb5,0x391c0cb3,0x4ed8aa4a,0x5b9cca4f,0x682e6ff3,
0x748f82ee,0x78a5636f,0x84c87814,0x8cc70208,0x90befffa,0xa4506ceb,0xbef9a3f7,0xc67178f2
};
void sha256(const uint8_t *msg, uint64_t msg_len, uint8_t digest[32]) {
uint32_t h[8] = {
0x6a09e667,0xbb67ae85,0x3c6ef372,0xa54ff53a,
0x510e527f,0x9b05688c,0x1f83d9ab,0x5be0cd19
};
// Step 1: compute padded length (multiple of 64 bytes / 512 bits)
uint64_t bit_len = msg_len * 8;
uint64_t padded_len = ((msg_len + 9 + 63) / 64) * 64;
uint8_t *padded = calloc(padded_len, 1);
memcpy(padded, msg, msg_len);
padded[msg_len] = 0x80; // append the single '1' bit (as 0x80 byte)
for (int i = 0; i < 8; i++)
padded[padded_len - 1 - i] = (uint8_t)(bit_len >> (8 * i)); // append length, big-endian
// Step 2: process each 512-bit (64-byte) block
for (uint64_t offset = 0; offset < padded_len; offset += 64) {
uint32_t w[64];
for (int t = 0; t < 16; t++) {
w[t] = (padded[offset+t*4] << 24) | (padded[offset+t*4+1] << 16)
| (padded[offset+t*4+2] << 8) | (padded[offset+t*4+3]);
}
for (int t = 16; t < 64; t++) {
uint32_t s0 = ROTR(w[t-15],7) ^ ROTR(w[t-15],18) ^ (w[t-15] >> 3);
uint32_t s1 = ROTR(w[t-2],17) ^ ROTR(w[t-2],19) ^ (w[t-2] >> 10);
w[t] = w[t-16] + s0 + w[t-7] + s1;
}
uint32_t a=h[0],b=h[1],c=h[2],d=h[3],e=h[4],f=h[5],g=h[6],hh=h[7];
for (int t = 0; t < 64; t++) {
uint32_t S1 = ROTR(e,6) ^ ROTR(e,11) ^ ROTR(e,25);
uint32_t ch = (e & f) ^ (~e & g);
uint32_t temp1 = hh + S1 + ch + K[t] + w[t];
uint32_t S0 = ROTR(a,2) ^ ROTR(a,13) ^ ROTR(a,22);
uint32_t maj = (a & b) ^ (a & c) ^ (b & c);
uint32_t temp2 = S0 + maj;
hh = g; g = f; f = e; e = d + temp1;
d = c; c = b; b = a; a = temp1 + temp2;
}
h[0]+=a; h[1]+=b; h[2]+=c; h[3]+=d;
h[4]+=e; h[5]+=f; h[6]+=g; h[7]+=hh;
}
free(padded);
// Step 3: produce final digest (big-endian bytes of h0..h7)
for (int i = 0; i < 8; i++) {
digest[i*4] = (uint8_t)(h[i] >> 24);
digest[i*4+1] = (uint8_t)(h[i] >> 16);
digest[i*4+2] = (uint8_t)(h[i] >> 8);
digest[i*4+3] = (uint8_t)(h[i]);
}
}
int main() {
const char *message = "abc";
uint8_t digest[32];
sha256((const uint8_t *) message, strlen(message), digest);
printf("SHA-256(\"%s\") = ", message);
for (int i = 0; i < 32; i++)
printf("%02x", digest[i]);
printf("\n");
return 0;
}
Sample Input and Output
Running the program above on the input string “abc” produces:
SHA-256("abc") = ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad
This matches the official NIST test vector for SHA-256, confirming the implementation is correct.
Optimization Techniques
- Hardware acceleration: Modern CPUs include dedicated SHA extension instructions (like Intel SHA-NI) that dramatically speed up SHA-256 computation compared to pure software implementations.
- Precomputed constants: I hardcode the round constants $K_t$ and initial hash values rather than recomputing them at runtime, saving startup cost.
- Streaming/incremental hashing: For very large inputs (like large files), I process data block by block as it becomes available rather than loading the entire input into memory first, keeping memory usage constant.
- SIMD parallelization: When hashing many independent messages at once, vectorized (SIMD) implementations can process multiple SHA-256 computations in parallel lanes.
- Avoiding unnecessary copies: Careful buffer management (processing data in place where possible) reduces memory bandwidth overhead in high-throughput applications.
Common Mistakes
- Implementing the padding step incorrectly (wrong bit ordering, forgetting the 64-bit length field, or getting the modular arithmetic for padding length wrong), which silently produces a non-standard, incorrect hash.
- Using SHA-1 or SHA-0 in new systems, both of which are cryptographically broken for collision resistance.
- Using a plain hash function like SHA-256 directly for password storage instead of a dedicated, slow, memory-hard password hashing function like bcrypt, scrypt, or Argon2.
- Mixing up endianness when converting between byte arrays and 32-bit words, which produces incorrect digests even when the core algorithm logic is otherwise correct.
- Assuming that hashing alone provides authentication; without a secret key (as in HMAC) or a digital signature, anyone can compute a matching hash for data they control, so a hash alone doesn’t prove who produced it.
Further Reading
- NIST FIPS 180-4, “Secure Hash Standard (SHS)”: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.180-4.pdf
- NIST FIPS 202, “SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions”: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.202.pdf
- Stevens, M. et al. “The First Collision for Full SHA-1” (the SHAttered attack), 2017: https://shattered.io/
- Menezes, A. J., van Oorschot, P. C., Vanstone, S. A. “Handbook of Applied Cryptography.” CRC Press: https://cacr.uwaterloo.ca/hac/
- Wikipedia overview: https://en.wikipedia.org/wiki/SHA-2
