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

31–40 of 56 posts

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

#31

Post by schoen »

xiphias2 wrote: post #20
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?

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…

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.

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

#32

Post by tialaramex »

Dylan16807 wrote: post #15
edflsafoiewq wrote: post #14

Earlier quoted context omitted.

The input is padded to form a sequence of 512 bit chunks, but that doesn't change anything, padding is one-to-one so there's still the same number of inputs.

> padding is one-to-one so there's still the same number of inputs That part is debatable, if we imagine different padding schemes. If the padding was just 0s, I would easily accept an argument that 111000 and 1110 are the same input giving the same hash. You could also say you consider the extra '1' bit in SHA-256 as part of the payload, not truly 'padding' because it's mandatory, and make a similar argument, and it…

> That part is debatable, if we imagine different padding schemes.

It isn't debatable because SHA-256 (and all these schemes) define the padding because it's necessary to have padding defeat the problem you're about to talk about and to do that they are in fact one-to-one:

> If the padding was just 0s, I would easily accept an argument that 111000 and 1110 are the same input giving the same hash.

As you might have guessed, this is not how it works.

SHA-256 appends that "extra 1 bit" you talk about, then zeroes until it is 64-bits short of a multiple of 512 bits, and then a 64-bit count.

So, as the earlier poster explained there are 2^257 -1 distinct hash inputs in abotsis' imagined set and thus there must be collisions by the pigeon hole principle, it really is that simple.

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

#33

Post by Dylan16807 »

tialaramex wrote: post #32
Dylan16807 wrote: post #15

Earlier quoted context omitted.

> padding is one-to-one so there's still the same number of inputs That part is debatable, if we imagine different padding schemes. If the padding was just 0s, I would easily accept an argument that 111000 and 1110 are the same input giving the same hash. You could also say you consider the extra '1' bit in SHA-256 as part of the payload, not truly 'padding' because it's mandatory, and make a similar argument, and it…

> That part is debatable, if we imagine different padding schemes. It isn't debatable because SHA-256 (and all these schemes) define the padding because it's necessary to have padding defeat the problem you're about to talk about and to do that they are in fact one-to-one: > If the padding was just 0s, I would easily accept an argument that 111000 and 1110 are the same input giving the same hash. As you might have gu…

> 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 principle, it really is that simple

Except they didn't just say there must be collisions in SHA-256, by my reading they were making an argument that the method of appending padding and stuff doesn't matter.

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

#34

Post by edflsafoiewq »

oconnor663 wrote: post #30
edflsafoiewq wrote: post #28

Earlier quoted context omitted.

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

Good point, I never thought about it that way. The reverse is also true: The length is probably unnecessary, since the "1" is there. I suppose the length makes it harder to produce collisions with inputs of different lengths, but in practice I don't think anyone actually tries to do that. If I had to take a wild guess, I'd guess that some early design in the family used only the "1", and that the length was added lat…

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.

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

#35

Post by tialaramex »

Dylan16807 wrote: post #33
tialaramex wrote: post #32

Earlier quoted context omitted.

> That part is debatable, if we imagine different padding schemes. It isn't debatable because SHA-256 (and all these schemes) define the padding because it's necessary to have padding defeat the problem you're about to talk about and to do that they are in fact one-to-one: > If the padding was just 0s, I would easily accept an argument that 111000 and 1110 are the same input giving the same hash. As you might have gu…

> 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 and Keccak are prominent because they're misuse resistant.

Consider the guillotine used to cut paper to size. Used correctly it's not very dangerous, but we don't let kids have access to a guillotine because it lacks misuse resistance. In contrast devices like a Rotatrim are safe for kids because they are resistant to misuse. It turns out most programmers are kids and we should not have given them C++ std::sort() or SHA-256 or ECB mode encryption because they will cut themselves.

> by my reading they were making an argument that the method of appending padding and stuff doesn't matter.

If your "method of appending padding" turns 2^257 -1 inputs into 2^256 outputs that was not, in fact, "padding" in the sense anybody knowledgeable in this field would use. You're supposed to be able to remove the padding in cryptography, if some of the "padded" structures are indistinguishable from each other you can't do that.

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

#36

Post by sigmoid10 »

mewse wrote: post #16
tptacek wrote: post #10

Earlier quoted context omitted.

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

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

I'm sure there's way too much variability to write a whole game engine and describe every detail as "this is the best way to do it because X" rather than "this is the way we did it because personal opinion/time/money/we had no clue how it works."

When it comes to the 3d renderer alone, there's at least enough common ground to explain the big ideas. Like "we multiply matrices because GPUs can do that very well in parallel and we describe our geometry as points because we can then describe the whole image using simple coordinate transformations which boil down to matrix multiplications."

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

#37

Post by InCityDreams »

lanecwagner wrote: post #12
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?

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.

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

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

#38

Post by mewse »

sigmoid10 wrote: post #36
mewse wrote: post #16

Earlier quoted context omitted.

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

I'm sure there's way too much variability to write a whole game engine and describe every detail as "this is the best way to do it because X" rather than "this is the way we did it because personal opinion/time/money/we had no clue how it works." When it comes to the 3d renderer alone, there's at least enough common ground to explain the big ideas. Like "we multiply matrices because GPUs can do that very well in para…

Yeah, I agree that you'd never get anywhere with a "this is the best way to do it because X" approach; it's just too divisive and often there's no single "best" answer that can be equally applied to every project.

I feel like a comprehensive article would need to be more of a catalog of "here are the basics of the various major approaches and how they differ and why you might choose one over another", rather than (for example) advocating specifically for forward shading vs. deferred vs. forward+ vs. clustered as being the universally "best" option. (especially when that whole discussion has become kind of moot for the majority of modern games developers, who mostly just take their engine's default rendering pipeline and just use it)

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

#39

Post by trinovantes »

edflsafoiewq wrote: post #34
oconnor663 wrote: post #30

Earlier quoted context omitted.

Good point, I never thought about it that way. The reverse is also true: The length is probably unnecessary, since the "1" is there. I suppose the length makes it harder to produce collisions with inputs of different lengths, but in practice I don't think anyone actually tries to do that. If I had to take a wild guess, I'd guess that some early design in the family used only the "1", and that the length was added lat…

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 by trial and error. This eventually led to the creation of HMAC H(H(secret^opad)|H(secret^ipad|M)).

In theory, the length suffix is no longer needed (or the "1" suffix but we save more space by removing the length). Maybe a cryptographer with more history knowledge can explain this but personally I think it's now one of those "don't fix what's not broken" things. It doesn't hurt security and it's already been thoroughly analyzed (and hardware optimized) so we just leave it.

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

#40

Post by xmprt »

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…

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?
Post reply on HN