Show HN: SHA-256 explained step-by-step visually

It's an iterated design, like a block cipher, meaning that it's built around a simple round function that's repeated a bunch of times on each input, rather than a super-complicated function run once.

It belongs to a large, important family of cryptographic hashes called Merkle-Damgård, which pads messages to a fixed block size, chunks them into blocks, feeds and feeds each block to an iterated "compression function" (the heart of the hash) that takes a block and the chained n-1th compression value and spits out the nth compression value. So a lot of the mechanism in this illustration is just the vanilla mechanics of an MD hash.

Iterated cryptographic designs generally have "schedule" or "expansion" functions that take the (small) input to the iterated function and "expand" it so that not all the iterations are working on exactly the same data; in the same way, a block cipher will have a "key schedule" that expands your 128-bit key into distinct "round keys" for each round. Message and key schedules, to me, feel like tiny little ciphers embedded in the larger cipher, and they're yet more of the complexity you're looking at, but can be studied independently (the SHA2 message schedule is apparently a big part of what makes it difficult to attack).

When you see magic numbers in a block cryptography design like this, two relatively safe bets you can make is that they're either "nothing up my sleeve" numbers chosen from e.g. mathematical constants, just for the sake of avoiding arguments, or that they're the product of statistical testing to maximize things like diffusion or minimize things like linear or differential characteristics.

With all block cipher cryptography one goal you always have is introducing nonlinearity; you can accidentally design a simple iterated function that is actually linear, and that cipher will be solvable simply with Gaussian elimination. People have shown me CTF levels that, for instance, linearized the AES round function. So when you see particular operations chained together in a cipher/hash design, keep in mind that they're balancing goals of (1) ensuring nonlinearity, (2) maximizing diffusion, the rate at which a single-bit change in the message totally scrambles the output in the shortest number of rounds, (3) optimizing metrics to avoid differential and linear cryptanalysis, (4) maximizing performance on target hardware.

As was suggested downthread: a good way to come at this stuff is to start with MD4, and then read about MD5 (vs. MD4), then SHA1, and then take a closer look at SHA2. This stuff didn't get figured out all at once, and all these hashes are related. You might find MD4 easier to get your head around.

For the linear and differential cryptanalysis stuff, which is surprisingly (given its age) important in cipher/hash design, a great starting point is the Heys tutorial, which is built around worked examples of both attacks:

https://ioactive.com/wp-content/uploads/2015/07/ldc_tutorial...

The operation you're talking about is "sigma_0" and "sigma_1" I believe, which is defined as:

sigma_0(x) = Rotate7(x) XOR Rotate18(x) XOR shift3(x).

sigma_1(x) = Rotate17(x) XOR Rotate19(x) XOR shift10(x).

Where "shift3" and "shift10" are both lossy operations.

----------------

While "shift3" and "shift10" are lossy, I'm not 100% certain that "sigma_0" or "sigma_1" is lossy. But that discussion aside, both sigma_0 and sigma_1 are applied to the _message_, not the internal SHA256 state.

The _message_ needs to be compressed, so a lossy operation over the message is not only expected, but required. 4096-bits of input need to become 256-bits of output. 8192 bits of message-input needs to become 256-bits of output.

-----------

But if you look at the "intermediate hash chain" where H(i) = a + H(i-1) for 64 rounds, all operations over "a" and the internal hash-state are invertible operations (SIGMA_0 and SIGMA_1 are both invertible, being (x) XOR (rotate x) XOR (rotate x) style functions).

------

I'm not saying that the "whole" hash function needs to be invertible. I'm saying that __particular__ elements of the hash function _should_ be invertible. The design of these particular elements (in particular, SIGMA_0, which is (Rotate2(x) XOR Rotate13(x) XOR rotate22(x))) is _clearly_ and evidently invertible / 1-to-1 and onto bijection / confusion principles.

The particular constants (why "rotate2", "rotate13" and "rotate22") is chosen for other reasons: probably differential cryptoanalysis but I admit that I'm not 100% sure on that (that's my expectation though).

Don't worry. I'm not one either. And I think that's why I am actually able to tell you that invertibility / 1-to-1 onto bijections is an important concept :-)

An actual cryptographer would tell you its 1-to-1 and onto and move on.

> It's a thing I don't love about illustrations like the one we're discussing, in that it sort of presents this "intelligent design" problem of, like, "how did we arrive at this incredibly complex fully functioning eyeball", when there's a whole series of smaller evolutionary steps that led to this point; it's more productive maybe to look at the bones of the whole design before diving into the details of which bits go where at each precise step.

Agreed. There's a lot of history here, and knowing all of the history helps a _LOT_.

Go back 50 years ago, and ciphers are way easier to grok. DES / Feistel ciphers are really easy for example. But then we discovered issues about them and iteratively improved.

The old "DES" / Feistel cipher principles of confusion and diffusion remain with us today, but each step has been honed for 90s-era computers (SBoxes and 32-bit numbers), and then honed again for 2010s-era computers (recognition that XOR / Rotate / Add is a faster primitive today than memory-based SBoxes).

I don't think any of the principles have changed since DES / Feistel cipher days. Its just that today's designs are better for today's computers.

------

EDIT: As far as I can tell: "confusion" can be created by (data) XOR (rotate-data) XOR (rotate-data) primitives. "diffusion" can be created by the "ADD" operator (in particular: "carries" will diffuse the bits around).

So XOR, rotate, and Add are the only primitives you need to make a modern crypto-cipher. All three primitives are outrageously fast on modern machines.

AES and other older ciphers tried to make each round relatively high quality. Modern ciphers try to make each round low-quality, and then do something like 64-rounds or 80-rounds to make up for it.

So you'll see old ciphers like AES with just 11 rounds, but modern ciphers / crypto algorithms like SHA256 use 64-rounds.