Offensive Security Researcher & Quantum Cryptography Analyst

SHA Hashing Algorithm: Working, Explanation, and Cryptographic Security

Abdul Wahab Junaid
SHA algorithm and working of this algorithm

SHA algorithm and working of this algorithm

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

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:

  1. 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.
  2. I break the padded message into 512-bit blocks.
  3. 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.
  4. 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.
  5. 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).
  6. After all 64 rounds for a block, I add the resulting working variables back into the running hash state (h0 through h7).
  7. I repeat steps 4 through 6 for every block in the padded message, carrying the hash state forward from block to block.
  8. 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).

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

Disadvantages

Applications

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

Common Mistakes

Further Reading

Exit mobile version