How SHA-256 Works Step-by-Step

https://blog.boot.dev/cryptography/how-sha-2-works-step-by-step-sha-256/

197 55 4 years ago

blog.boot.dev

emerged• 4 years ago

Every time one of these is posted, I’m expecting the steps to explain why they are being done. Like what makes this combination of operations have the particular properties we need?

RcouF1uZ4gsC• 4 years ago

Exactly. Also SHA-256 is in the same family as MD-5. It would be nice to kind of go over how the family in general works, what weaknesses were discovered, and what changes were incorporated into SHA-256 that addresses these issues.

abotsis2• 4 years ago

I’ve always been curious about whether it’s possible to have a collision when your input is 256 bits or less (in the case of sha256)… I even emailed Bruce Schneier. I got a polite response that he didn’t have time to look at it, which indicated to me he didn’t know “off the top of his head”, which I interpreted as “it’s not impossible”… but I still don’t know.

pvg2• 4 years ago

You're better off reading the Wikipedia page which covers things like that (for instance, the Merkle–Damgård construction) in some detail and without all the oversimplifications and almost unavoidable wrongness of slight write-ups like this.

greggsy• 4 years ago

On the contrary, I just want the dumbed down version. I’m not ever going to implement it (nobody should RYO crypto unless you really know what you’re doing), nor am I going to have to rely on the knowledge in my daily life - I’m not a maths educator, and I’m certainly not a cryptographer.

It’s still good to understand the basics.

I learnt a lot about PKI by forcing myself to learn the absolute basics of modulo, but I’ll never implement it or do a full calculation.

userbinator• 4 years ago

There's some good discussion in the comments of another "one of these" a short while ago: https://news.ycombinator.com/item?id=30244534

tptacek• 4 years ago

You're not wrong. You're 100% right. This is like posting a story about how a game engine works, and having it be just blocks of assembly language with no explanation other than "here's some code multiplying a matrix, and then...".

mewse2• 4 years ago

Geez, now I want to write an article about how a game engine works, explaining the rationale for every piece of it; I don't think I've ever seen somebody do that before. It's all kind of spread around in disparate bits and pieces, often quite hard to find (or even to know that you ought to be looking for it).

Problem is that such a work would probably have to be more of a textbook, in terms of length and impenetrability. And it's not immediately obvious who the audience would be, as the vast majority of game developers these days are using pre-existing engines, rather than building new ones. But maybe there's still enough conceptual underpinnings that are worth discussing which would still be relevant for Unity/Unreal/Godot folks.

lanecwagner• 4 years ago

huh, I didn't post this here, but I'm the author and kinda fun to just see it show up. Thanks for the feedback, it's a good point. I'll be making those updates soon.

InCityDreams• 4 years ago

Question: why didn't you post it to hn?

xiphias2• 4 years ago

Linear and differential cryptanalisis are the 2 classical way of breaking cryptographic hash functions, I think they are a cool way to learn about the importance of the current constructs being in use:

https://alldifferences.net/difference-between-linear-and-dif...

A simple way to look at them is this: if you change some specific bits in the input, maybe not all bits change by exacly 50% chance in the output, or they are not independent. For only a few rounds of S-Box-es you can probably find something like this by hand, for many rounds, SAT-solver or a special tool is needed.

schoen• 4 years ago

Can you help me understand how one might use a SAT solver to find ways in which cryptographic primitives (or their components) deviate from ideal pseudorandomness?

I know what all of these things are, my intuition just isn't jumping to a way to formulate statistical correlations as a SAT problem.

dragontamer3• 4 years ago

I wrote something up in a previous post. I'm no crypto-expert. But I did study it a bit.

https://news.ycombinator.com/item?id=30248439

Obviously, any actual crypto-experts can feel to correct me if I got history and/or understanding incorrect here.

-----

Addenendum to my previous post.

1. Confusion -- Bytes should turn into other bytes in random-looking ways. For example, the byte 0x25 may turn into 0x88. Aka: S-boxes in 90s-era ciphers.

2. Diffusion -- Bit-changes should "spread" to as many bits as possible.

3. Invertible -- Invertible operations minimizes the loss of information. Encryption/Decryption must be invertible by definition, but even Hash-functions should be largely built out of invertible operations. Try to make confusion and/or diffusion steps invertible.

4. ADD / XOR / Shift / Rotate -- These operations are the more popular way to make Invertible Confusion/Diffusion functions today.

5. SBox + Galois Fields -- For AES (a 90s-era algorithm), SBox was the source of confusion, and Galois Field arithmetic was the source of Diffusion. I could explain why but that gets more complicated.

5. Testing -- Test your functions against linear cryptography (how is the input related to the output?) and differential cryptography (how is each input bit related to each output bit on a bit-by-bit basis?)

------

Obviously, hash functions (like SHA256) must be non-invertible by the end of it all. But you want to carefully think about where the source of non-invertibility comes from, and to minimize the loss of entropy/information at any particular step.

With these principles, its not very hard to make your own hash function. I'd suggest studying Bob Jenkin's "JOAAT" hash, just-one-at-a-time. Its a non-crypto hash, but it is probably one of the simplest hashes that uses the above principles: https://en.wikipedia.org/wiki/Jenkins_hash_function

xmprt• 4 years ago

What differentiates a non-crypto hash from a crypto hash. Is there a fundamental difference between the two which prevents one from being used for cryptographic purposes?

l33t23282• 4 years ago

even Hash-functions should be largely built out of invertible operations

Why is that? I don’t understand why you should minimize the loss of entropy at any particular step. Is it to help resist collisions?

I could explain why but that gets more complicated.

If you’d care to go into more detail, I’d love to hear it. It was my understanding that the AES S-box was the result of some nonlinear transformation of the input bytes.

can16358p2• 4 years ago

Came here to ask the same. I enjoyed the blog, yet as a non-cryptographer, I'd like to see the reasons behind the actions: e.g. Okay we right rotate that input, but why are we doing this? Or Why are we taking cube roots of 64 primes? etc.

edflsafoiewq8• 4 years ago

Why are we taking cube roots of 64 primes?

https://en.wikipedia.org/wiki/Nothing-up-my-sleeve_number

Arnt• 4 years ago

AOL. It's like the articles that would explain how unix software by explaining in detail how to ./configured;make;make install and leave out everything specific to the software in question.

I can explain one small part, though. A lot of these things need some fixed constants that have to be not all-zero, not all-one, not easily predictable and not someone's backdoor. So people will say things like "we need five ten-digit numbers here, so we'll use the second to eleventh digits of the square roots of the first five primes".

That is, the use of the square root has nothing to do with being the square root of two, there's no deep math. The square root of two is just some number that you won't suspect of being a backdoor.

https://en.wikipedia.org/wiki/Nothing-up-my-sleeve_number

stigz• 4 years ago

Append a single 1:

Just begs the question, why?

trinovantes3• 4 years ago

If your input ends with a 0 and you don't append the 1, you have no idea if that 0 is part of the padding or input

edflsafoiewq8• 4 years ago

Yes you do, since you still have the length field.

edflsafoiewq8• 4 years ago

AFAIK the 1 bit does nothing. Padding with 1+(number of 0s)+(length of message) is traditional though and used by MD4/MD5/SHA1/SHA2.

You can read in a few places that this is the padding proposed by Merkle, but I looked it up and in my reading of One Way Hash Functions and DES he does not use the 1

As an aside, we note that x is padded with 0's until its size is an integral multiple of the size of the convenientlySizedChunks. Note that padding with 0s might introduce some ambiguity about the exact value of x that is being authenticated, as discussed by Juenernan[4]. The message "010110" padded to 8 bits would be "01011000" and it is now unclear how many trailing 0's were present in the original message. Several methods are available to resolve this ambiguity. We select a method that will also be useful in resolving a further problem: we append the length of x, in bits, at the end of x. To make this additional "length" field easy to find. we shall right justify it in the final block. If the length field won't fit, we add additional blocks to the end of x.

ConcernedCoder• 4 years ago

The wikipedia article spells it out pretty clearly, and the pseudo-code is easily translated into any language, here it is in JavaScript if anyone is interested:

sha-256: https://github.com/jeffallen6767/sha-256-js/blob/master/src/...

Once you understand the concept that most of these algos are simply dividing the input into computer-friendly sized blocks and then stacking and manipulating these bits in 3d space like a rubics cube, then the whole thing becomes a bit easier to understand.

Here's a few more for comparison:

sha-1: https://github.com/jeffallen6767/sha-1-js/blob/master/src/sh...

md5: https://github.com/jeffallen6767/md5-js/blob/master/src/md5....

keccak: https://github.com/jeffallen6767/keccak-p-js/blob/master/src...

side note, I also ended-up implementing the keccak algo in c for open cl usage, because I wanted to see if I could use it in parallel on my graphics card from nodejs ( spoiler: it's indeed possible ):

https://github.com/jeffallen6767/chain/blob/master/src/minin...

Please forgive my terrible programming style, this was done years ago...

How SHA-256 Works Step-by-Step

Related Stories