8 ms·

How SHA-256 Works Step-by-Step

197 points by kyleShropshire 4y ago

emerged 4y 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?
- Arnt 4y 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 https://en.wikipedia.org/wiki/Nothing-up-my-sleeve_number
- RcouF1uZ4gsC 4y 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.
  - abotsis 4y 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.
    - upofadown 4y ago
      What sort of collision? Or asking in a different way, what would you consider a collision?
      - _vdpp 4y ago
        2 messages producing the same digest. That’s actually a really interesting question.
      - mike_hock 4y ago
        I think he means a set-theoretical collision, not a feasible collision attack. I.e. "is SHA256 a bijection on 256-bit integers?"
    - edflsafoiewq 4y ago
      There are 2^257 - 1 inputs of 256 bits or less and only 2^256 possible hashes, so there must be a collision.
      - CamperBob2 4y ago
        The input is always padded out to 256 bits, though, isn't it?
        edflsafoiewq 4y ago
        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.
        Dylan16807 4y ago
        > 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 wouldn't be blatantly wrong.
- pvg 4y 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 4y 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.
    - pvg 4y ago
      This isn't really a 'dumbed down version' and the person I'm replying to specifically asked about the sort of things not covered in this version.
- userbinator 4y 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 https://news.ycombinator.com/item?id=30244534
- tptacek 4y 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...".
  - mewse 4y 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.
    - larusso 4y ago
      I think with most posts and also textbooks the problem is scope. I think the Handmade Hero project shows quite well what an amount of work it is to explain it. And there is the difference between a generic game engine like Unity and a specific engine for a specific project. And I mainly mean platform targeting and the likes. But I would read a blog post series :)
    - Sirenos 4y ago
      I think there is a middle ground. You can give a bird's eye view of the way things are done and a hand-wavy intuition for why they are done that way. Analogies go a long way towards building the latter. Then for those who want to dive deep, you can leave pointers to articles that cover such things in detail. It doesn't always have to be a choice between writing a book and nothing at all because the topic is too complex. I personally have benefited from bird's eye view blog posts and mini-articles more than I can remember. If you have the knowledge then go for it, someone out there will thank you.
    - 4y ago
- lanecwagner 4y 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 4y ago
    Question: why didn't you post it to hn?
- xiphias2 4y 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-differential-cryptanalysis/ 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 4y 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.
- dragontamer 4y 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 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 https://en.wikipedia.org/wiki/Jenkins_hash_function
  - xmprt 4y 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?
    - l33t2328 4y ago
      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.
- can16358p 4y 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.
  - edflsafoiewq 4y ago
    > Why are we taking cube roots of 64 primes? https://en.wikipedia.org/wiki/Nothing-up-my-sleeve_number https://en.wikipedia.org/wiki/Nothing-up-my-sleeve_number
    - can16358p 4y ago
      That was helpful. It'd be great if there are tips like these (even Wikipedia links like this is very helpful) are also present in the posts like the blog post.
stigz 4y ago
> Append a single 1: Just begs the question, why?
- trinovantes 4y 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
  - edflsafoiewq 4y ago
    Yes you do, since you still have the length field.
    - oconnor663 4y ago
      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 later?
      - edflsafoiewq 4y ago
        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.
        trinovantes 4y ago
        > 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.
ConcernedCoder 4y 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/sha256.js 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/sha1.js https://github.com/jeffallen6767/sha-1-js/blob/master/src/sh... md5: https://github.com/jeffallen6767/md5-js/blob/master/src/md5.js https://github.com/jeffallen6767/md5-js/blob/master/src/md5.... keccak: https://github.com/jeffallen6767/keccak-p-js/blob/master/src/keccak.js 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/mining/keccak.cl https://github.com/jeffallen6767/chain/blob/master/src/minin... Please forgive my terrible programming style, this was done 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?

Arnt 4y 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 https://en.wikipedia.org/wiki/Nothing-up-my-sleeve_number
RcouF1uZ4gsC 4y 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.
- abotsis 4y 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.
  - upofadown 4y ago
    What sort of collision? Or asking in a different way, what would you consider a collision?
    - _vdpp 4y ago
      2 messages producing the same digest. That’s actually a really interesting question.
    - mike_hock 4y ago
      I think he means a set-theoretical collision, not a feasible collision attack. I.e. "is SHA256 a bijection on 256-bit integers?"
  - edflsafoiewq 4y ago
    There are 2^257 - 1 inputs of 256 bits or less and only 2^256 possible hashes, so there must be a collision.
    - CamperBob2 4y ago
      The input is always padded out to 256 bits, though, isn't it?
      - edflsafoiewq 4y ago
        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.
        Dylan16807 4y ago
        > 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 wouldn't be blatantly wrong.
pvg 4y 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 4y 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.
  - pvg 4y ago
    This isn't really a 'dumbed down version' and the person I'm replying to specifically asked about the sort of things not covered in this version.
userbinator 4y 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 https://news.ycombinator.com/item?id=30244534
tptacek 4y 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...".
- mewse 4y 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.
  - larusso 4y ago
    I think with most posts and also textbooks the problem is scope. I think the Handmade Hero project shows quite well what an amount of work it is to explain it. And there is the difference between a generic game engine like Unity and a specific engine for a specific project. And I mainly mean platform targeting and the likes. But I would read a blog post series :)
  - Sirenos 4y ago
    I think there is a middle ground. You can give a bird's eye view of the way things are done and a hand-wavy intuition for why they are done that way. Analogies go a long way towards building the latter. Then for those who want to dive deep, you can leave pointers to articles that cover such things in detail. It doesn't always have to be a choice between writing a book and nothing at all because the topic is too complex. I personally have benefited from bird's eye view blog posts and mini-articles more than I can remember. If you have the knowledge then go for it, someone out there will thank you.
  - 4y ago
lanecwagner 4y 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 4y ago
  Question: why didn't you post it to hn?
xiphias2 4y 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-differential-cryptanalysis/ 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 4y 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.
dragontamer 4y 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 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 https://en.wikipedia.org/wiki/Jenkins_hash_function
- xmprt 4y 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?
  - l33t2328 4y ago
    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.
can16358p 4y 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.
- edflsafoiewq 4y ago
  > Why are we taking cube roots of 64 primes? https://en.wikipedia.org/wiki/Nothing-up-my-sleeve_number https://en.wikipedia.org/wiki/Nothing-up-my-sleeve_number
  - can16358p 4y ago
    That was helpful. It'd be great if there are tips like these (even Wikipedia links like this is very helpful) are also present in the posts like the blog post.

stigz 4y ago

> Append a single 1: Just begs the question, why?

trinovantes 4y 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
- edflsafoiewq 4y ago
  Yes you do, since you still have the length field.
  - oconnor663 4y ago
    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 later?
    - edflsafoiewq 4y ago
      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.
      - trinovantes 4y ago
        > 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.

ConcernedCoder 4y 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/sha256.js 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/sha1.js https://github.com/jeffallen6767/sha-1-js/blob/master/src/sh... md5: https://github.com/jeffallen6767/md5-js/blob/master/src/md5.js https://github.com/jeffallen6767/md5-js/blob/master/src/md5.... keccak: https://github.com/jeffallen6767/keccak-p-js/blob/master/src/keccak.js 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/mining/keccak.cl https://github.com/jeffallen6767/chain/blob/master/src/minin... Please forgive my terrible programming style, this was done years ago...