SHA Binary Principles

What Makes SHA a Bitwise Algorithm?

When I first looked under the hood of SHA-256, I expected something mathematically intimidating. What I found instead was a surprisingly compact set of bitwise operations — right rotations, XOR, AND, and NOT — repeated over 64 rounds. The entire cryptographic strength of SHA comes from how these simple bit operations mix the input data. There is no multiplication, no floating-point math, nothing beyond manipulating 32-bit words at the bit level.

The SHA-2 family (SHA-224, SHA-256, SHA-384, SHA-512) works by taking an input message, padding it to a multiple of the block size, and then processing each block through a compression function that uses only bitwise operations and modular addition. This design is deliberate: bitwise operations are fast in hardware and constant-time, meaning they don't leak timing information that could be exploited in side-channel attacks.

When I needed to implement a custom hash function for a file integrity checker, I based the compression function on SHA-2's bitwise design. The combination of rotations, shifts, and XORs in the round function produces excellent bit dispersion even in a simplified implementation.

The Four Core Bitwise Operations in SHA-256

SHA-256's 64 rounds use exactly four bitwise building blocks. Every line of the compression function is a combination of these.

1. Right Rotation (ROTR)

Right rotation is the most distinctive operation in SHA. Unlike a regular right shift that discards bits, ROTR wraps the bits that fall off the right end back around to the left. This preserves all 32 bits of entropy, which is critical for a hash function.

2. XOR (Exclusive OR)

XOR is the workhorse of SHA's mixing. SHA-256 defines two sigma functions that combine ROTR and XOR:

3. AND and NOT as Conditional Selectors

SHA-256 uses bitwise AND and NOT together as a conditional function. The Ch (choose) function uses AND to select bits from one of two sources depending on a third value. The Maj (majority) function uses AND to return the majority bit value across three inputs.

The 64-Round Compression Function

Each round of SHA-256 applies the Ch and Maj functions, two sigma sums, and a round constant to update eight working variables (A through H). Here is the core loop in pseudocode — I remember the first time I traced through this by hand with a binary example, it finally clicked how strong the mixing really is.

// One round of SHA-256 compression
T1 = H + Σ1(E) + Ch(E, F, G) + K[i] + W[i]
T2 = Σ0(A) + Maj(A, B, C)

H = G
G = F
F = E
E = D + T1
D = C
C = B
B = A
A = T1 + T2

After all 64 rounds, the working variables are added to the previous hash value using 32-bit modular addition. This cumulative addition ensures that every input bit influences every output bit — the avalanche effect. Change one bit in the input, and roughly half the bits in the output will flip.

The Message Schedule: Expanding 16 Words to 64

The message schedule is where bitwise operations prepare the data for all 64 rounds. The 512-bit input block is split into sixteen 32-bit words (W[0] through W[15]). Words W[16] through W[63] are computed using XOR and rotations of earlier words:

for i from 16 to 63:
    s0 = ROTR(W[i-15], 7) XOR ROTR(W[i-15], 18) XOR SHR(W[i-15], 3)
    s1 = ROTR(W[i-2], 17) XOR ROTR(W[i-2], 19) XOR SHR(W[i-2], 10)
    W[i] = W[i-16] + s0 + W[i-7] + s1

The addition here is modular 32-bit addition, not XOR. Each new word depends on four prior words spread across the schedule, which distributes the influence of each input bit across the entire 64-round computation.

Binary Padding: Preparing the Message

Before any hashing begins, the input message must be padded to a multiple of 512 bits. The padding itself is a bit-level operation:

// SHA-256 padding
1. Append a single '1' bit to the message
2. Append '0' bits until the length is 448 mod 512
3. Append the original message length as a 64-bit big-endian integer

// Example: padding "abc" (24 bits, or 3 bytes)
// Original:   01100001 01100010 01100011  (a, b, c)
// After step 1:  ... 01100011 1
// After step 2:  ... 01100011 1000...000  (423 zero bits)
// After step 3:  append 0x00000000 0x00000018 (24 in hex)

The padding guarantees that the length is encoded into the hash, which prevents certain types of length-extension attacks. This is one reason SHA-256 replaced SHA-1 in many applications.

SHA-1 vs SHA-256: Bitwise Differences

SHA-1 and SHA-256 share the same structural design but differ in critical bitwise details. SHA-1 uses 160-bit output and 32-bit words with 80 rounds. SHA-256 uses 256-bit output with a more complex round function. The key difference is in the message schedule and the sigma functions:

// SHA-1's simple round function (80 rounds)
f(t) = Ch(B,C,D) for 0 ≤ t ≤ 19
f(t) = Parity(B,C,D) for 20 ≤ t ≤ 39  // just XOR
f(t) = Maj(B,C,D) for 40 ≤ t ≤ 59
f(t) = Parity(B,C,D) for 60 ≤ t ≤ 79

// SHA-256 uses only Ch and Maj across all 64 rounds,
// but with more aggressive mixing via Σ0 and Σ1

SHA-1's simpler bitwise design was eventually broken by Google's SHAttered attack in 2017, which demonstrated a practical collision. SHA-256 remains collision-resistant largely because its bitwise mixing is more thorough, with more rotation distances and tighter feedback in the message schedule.