Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How SHA-256 Works Step-by-Step

blog.boot.dev

Post reply on HN
Print view View original

41–50 of 56 posts

Re: How SHA-256 Works Step-by-Step

#41

Post by edflsafoiewq »

trinovantes wrote: post #39
edflsafoiewq wrote: post #34

Earlier quoted context omitted.

Padding without the length isn't suffix-free, ie. there's two different messages x and y with pad(x) a suffix of pad(y). You want that basically because if there's ever a collision part-way through the loop on two inputs, if there's a common suffix, the rest of the loop will be the same so there's no chance to "escape" the collision. Being some kind of artifact seems plausible.

> Padding without the length isn't suffix-free Can you give a more concrete example? Specifically with padding with 1 then all 0s without length. Appending the 1 then all 0s is supposed to prevent collisions. The length suffix is used as an early attempt to avoid length extension attacks on MACs of the form H(secret|M). However, we've later seen that it's not sufficient as it's easy to determine length of the secret…

Of it not being suffix-free? Just stick a full block on the front of the message.

Length padding isn't just for MACs, its used in the first place to prove Merkle-Damgard works at all, ie. is collision-preserving. If you have a hash collision with two messages with the same length, you can run through the Merkle-Damgard loop in parallel and find a collision in the compression function. For different lengths that doesn't work but if you just insert the length into the last block, you know you'll always have a collision in the final block in that case.

There's a proof here that being suffix-free is necessary and sufficient for a padding rule to make Merkle-Damgard collision-preserving: https://eprint.iacr.org/2009/325.pdf

Re: How SHA-256 Works Step-by-Step

#42

Post by l33t2328 »

xmprt wrote: post #40
dragontamer wrote: post #21

Earlier quoted context omitted.

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-boxe…

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?

Yes! We’d like our cryptographic hash functions to be collision resistant and preimage resistant.

That is, we’d like it to be hard to generate 2 different messages m1 and m2 where the hash of m1 is equal to the hash of m2, and we’d also like for it to be hard to compute any function of the message m(except the hash of m) if you’re given only the hash of m.

Non cryptographic hash functions don’t require these properties, and in fact some hashing algorithms used for data mining are designed to, for example, map near inputs to near outputs.

Re: How SHA-256 Works Step-by-Step

#43

Post by l33t2328 »

dragontamer wrote: post #21
emerged wrote: post #2

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?

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-boxe…

> 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.

Re: How SHA-256 Works Step-by-Step

#44

Post by dragontamer »

xmprt wrote: post #40
dragontamer wrote: post #21

Earlier quoted context omitted.

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-boxe…

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?

A non-crypto hash is run enough to confuse "simple" statistical tests.

A crypto-hash is run enough times to confuse "difficult" statistical tests from a dedicated adversary.

For example, the JOAAT hash is a simple add / shift / XOR hash run 1x round per byte. A singular round is all you need to confuse the "simple" statistical tests such as birthday attacks, dice rolls, etc. etc.

SHA-256 is also a simple add / shift / XOR hash, albeit using 256-bits at a time instead of 8-bits at a time. It is a 64-round hash function. That is: it is round(round(round(round(data)))) 64-times deep.

--------

If you wanted to turn JOAAT non-crypto hash into a crypto-hash, a good first step would be to run JOAAT(JOAAT(JOAAT...() maybe 64x or 128x over the data.

Obviously, you'd need to run cryptoanalysis over the end result, and also test for non-linearity and other such properties. But "large number of rounds" is probably the most obvious difference between non-crypto and crypto hashes.

---------

In the 90s, functions like AES were designed with "maximum confusion / diffusion per round". In just 10 rounds, the bits are mixed up enough that it defeats linear and differential cryptography.

I don't know which cipher "changed the meta", but maybe it was the XTEA cipher? Since XTEA was so simple, they knew it would need many-many rounds to defeat linear and differential crypto. So they just did 64-rounds and called it the end of it.

----------

So you can see, a "crypto" hash is effectively a regular old hash done an absurd number of times to defeat the most incredible statistical-tests known to man... done under the assumption that the "opponent" is performing the most difficult statistical tests.

Re: How SHA-256 Works Step-by-Step

#45

Post by abotsis »

abotsis wrote: post #5
RcouF1uZ4gsC wrote: post #3

Earlier quoted context omitted.

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.

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.

To give some further context, I stumbled across this thought while reading how “community ids” are calculated. Community ids are commonly used to simplify joining/lookups for network security tools (suracata, zeek). They essentially concatenate the “quad tuple” (src ip/port, dest ip/port), and a “seed”, then run sha against it. I didn’t entirely understand the reason the authors chose sha (other than being security people who might have just reached for a crypto secure hash function). SHA is slow vs something like xxh, and given the number of sessions these things process, seemed like overkill. Further, it’s unclear to me what’s gained by using sha vs xxh or simply concatenating the bits. Then I started wondering about the downsides: whether it’s possible to have a false correlation because two sessions yielded the same sha digest.

Re: How SHA-256 Works Step-by-Step

#46

Post by dragontamer »

l33t2328 wrote: post #43
dragontamer wrote: post #21

Earlier quoted context omitted.

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-boxe…

> 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 i…

> 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?

SHA 256 is built out of 64 rounds of an internal mixing function.

That is, SHA256 is basically a glorified mix(mix(mix(mix...(mix(internal_state))))))))))))))) function, with 64x mixes applied to the internal data per input.

Now consider how "mix" should be designed.

1. If "mix" is invertible, it means that every possible input "pigeonholes" to exactly one possible output. Mathematically, we'd call invertible functions "one-to-one" and "onto".

2. If "mix" is not invertible, then the above condition does not hold.

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

So lets look at the simplest non-invertible function for 3-bit numbers as an example. And see what happens when we use it as a "mixing" function.

    Input | Output
    --------------
    000   | 001
    001   | 010
    010   | 011
    011   | 100
    100   | 101
    101   | 110
    110   | 111
Notice that 110 and 111 both "map" to 111. So what happens when we run mix(mix(mix(mix...(data)))) ??

Eventually, after about 8 rounds, all your data turns into "111" eventually. You're "losing" information. It means that everyone can predict that your hash probably will be 111 eventually.

Now lets consider the invertible function:

    Input | Output
    --------------
    000   | 001
    001   | 010
    010   | 011
    011   | 100
    100   | 101
    101   | 110
    110   | 111 
    111   | 000
000 was "unchosen" in previous function, and now we have one-to-one and onto . invertibility. As such mix(mix(mix(mix(...(data)))) will 100% depend on the input data.

Of course, this mixing function is simply "(data+1) modulo 8", which is insufficient for mixing purposes. (The "confusion" is pretty bad and very predictable, but you can see how "add +1" is actually kind of good at diffusion when "all the carries" line up... such as 011 -> 100 is changing a lot of bits from one mix). But you can imagine that even in this simplest example, the invertible function leads to a less-predictable internal state than the non-invertible function.

---------

Functions should also be "nonlinear". The above x+1 mixing function is bad because its linear (5x mixing functions can be simplified into x+5). It turns out that combinations of XOR, bitshifts, and ADDs could be non-linear, but you need to run a bunch of tests over the inputs/outputs to be sure that your particular mixing function is sufficient.

Re: How SHA-256 Works Step-by-Step

#47

Post by Dylan16807 »

tialaramex wrote: post #35
Dylan16807 wrote: post #33

Earlier quoted context omitted.

> it's necessary to have padding defeat the problem you're about to talk about There is no way it's "necessary" to avoid that particular problem, yet at the same time unnecessary to avoid length extension attacks. > As you might have guessed, this is not how it works. That's a weirdly hostile way to respond to a clearly counterfactual thought experiment. > and thus there must be collisions by the pigeon hole principl…

> There is no way it's "necessary" to avoid that particular problem, yet at the same time unnecessary to avoid length extension attacks. Length extension attacks work because of a common misuse of these algorithms. If you use them properly you aren't vulnerable to a length extension attack whereas you would be in trouble with the terrible "padding" scheme you propose as a counterfactual. Algorithms like SHA-512/256 a…

If you had no size based padding, you could fake a document having a few more zero bytes at the end. That's almost never dangerous, and it also requires very specific (mis)use to cause problems, just like a length extension. Unless you can name a killer use case, I stand by length extension problems being a significantly bigger deal and more "necessary" to stop.

> You're supposed to be able to remove the padding in cryptography

It's a hash. You can never access the post-padding version of the input in the first place.

Re: How SHA-256 Works Step-by-Step

#48

Post by trinovantes »

edflsafoiewq wrote: post #41
trinovantes wrote: post #39

Earlier quoted context omitted.

> Padding without the length isn't suffix-free Can you give a more concrete example? Specifically with padding with 1 then all 0s without length. Appending the 1 then all 0s is supposed to prevent collisions. The length suffix is used as an early attempt to avoid length extension attacks on MACs of the form H(secret|M). However, we've later seen that it's not sufficient as it's easy to determine length of the secret…

Of it not being suffix-free? Just stick a full block on the front of the message. Length padding isn't just for MACs, its used in the first place to prove Merkle-Damgard works at all, ie. is collision-preserving. If you have a hash collision with two messages with the same length, you can run through the Merkle-Damgard loop in parallel and find a collision in the compression function. For different lengths that doesn…

> stick a full block on the front of the message

Yes, this will give you the same intermediate state in the hash function but if m1!=m2, then the final output H(pad'(x|m1)) != H(pad'(x|m2)) where pad' is just appending 1 then all 0s.

Maybe it's due to the years since my crypto class or maybe I'm just dense but I'm not following your logic at all. I'm asking for an actual example of m1 and m2 that will result in the same hash if they are not padded with their lengths.

I made the assertion that for all m1,m2 if m1!=m2 then H(pad'(m1))!=H(pad'(m2)). Disproving it is simply giving a counter example m1,m2.

EDIT: I took some time to skim through the paper you've linked and it supports my assertion:

> We also have shown that the simplest padding such as padding 10^d only can be sufficient for collision preserving property if we restrict collision resistant assumption of the underlying compression function for the first (t − 1) bits.

Since we know (or at least believe) the SHA2 compression function is collision resistant, then length padding is redundant.

Re: How SHA-256 Works Step-by-Step

#49

Post by edflsafoiewq »

trinovantes wrote: post #48
edflsafoiewq wrote: post #41

Earlier quoted context omitted.

Of it not being suffix-free? Just stick a full block on the front of the message. Length padding isn't just for MACs, its used in the first place to prove Merkle-Damgard works at all, ie. is collision-preserving. If you have a hash collision with two messages with the same length, you can run through the Merkle-Damgard loop in parallel and find a collision in the compression function. For different lengths that doesn…

> stick a full block on the front of the message Yes, this will give you the same intermediate state in the hash function but if m1!=m2, then the final output H(pad'(x|m1)) != H(pad'(x|m2)) where pad' is just appending 1 then all 0s. Maybe it's due to the years since my crypto class or maybe I'm just dense but I'm not following your logic at all. I'm asking for an actual example of m1 and m2 that will result in the s…

Oh, we're talking about different things. I'm only talking about proving collision-preservation, not something as spectacular as generating collisions.

Re: How SHA-256 Works Step-by-Step

#50

Post by tialaramex »

Dylan16807 wrote: post #47
tialaramex wrote: post #35

Earlier quoted context omitted.

> There is no way it's "necessary" to avoid that particular problem, yet at the same time unnecessary to avoid length extension attacks. Length extension attacks work because of a common misuse of these algorithms. If you use them properly you aren't vulnerable to a length extension attack whereas you would be in trouble with the terrible "padding" scheme you propose as a counterfactual. Algorithms like SHA-512/256 a…

If you had no size based padding, you could fake a document having a few more zero bytes at the end. That's almost never dangerous, and it also requires very specific (mis)use to cause problems, just like a length extension. Unless you can name a killer use case, I stand by length extension problems being a significantly bigger deal and more "necessary" to stop. > You're supposed to be able to remove the padding in c…

> Unless you can name a killer use case, I stand by length extension problems being a significantly bigger deal and more "necessary" to stop.

"it works as a cryptographic hash" is certainly a "killer use case" for a cryptographic hash.

Your "Dylan16807 hash" without working padding does not work as a cryptographic hash, it's useless.

Post reply on HN