7 ms·

The SHA-256 Project: learn how hash functions work by implementing one yourself

213 points by oconnor663 5y ago

josnyder 5y ago
OP appears to be Jack O'Connor, one of the designers of BLAKE3, which is the fastest full-strength cryptographic hash function currently available. It's always nice to see practicing cryptographers also producing digestible cryptography content.
- mderazon 5y ago
  "fastest hash function" - I do not know much about cryptography, but isn't a hash function slow by design, or at least slow enough to prevent brute force ?
  - oconnor663 5y ago
    No but this is a common misconception. The key thing to remember is that a regular hash function and a "password hash" are very different. A password hash does need to be slow, because we want to make it expensive for an attacker who's stolen the hash to try to guess the password. But in most other use cases, we want hash functions to be as fast as possible, as long as they can uphold their security guarantees. A maybe-interesting sidebar: If your job is to design a password hash, you still want to take a fast hash function as a starting point. All the effort that goes into making the hash function both fast and secure gives you confidence that an attacker isn't going to be able to find some shortcut that lets them compute the hash it more quickly than everyone else.
  - foxyv 5y ago
    Hello, great question! Hashes must only be slow in certain circumstances where the plaintext of the hash is vulnerable to a "pre-image" attack. This means that the entropy of the plaintext is very low and there are very few possibilities. In these cases you use extremely slow hashes like bcrypt or be forced to use AES encryption before hashing. For example: Passwords, Credit Card Security Digits, Names, etc... Plaintext that has a LOT of entropy does not need a slow hash function. You can usually get by with SHA-256. For example: digital signatures, AES keys, Public/Private keys, large file hashes, etc... In addition, if you are only trying to verify integrity with no need for security, a quick hash function is useful. Like a checksum on a file system. In this case a fast hash function is more important. EG: https://ext4.wiki.kernel.org/index.php/Ext4_Metadata_Checksums https://ext4.wiki.kernel.org/index.php/Ext4_Metadata_Checksu...
    - oconnor663 5y ago
      All of this is mostly right, but I have some minor corrections: > or be forced to use AES encryption before hashing Encrypting before hashing doesn't actually help us, if our hash input has low entropy. The problem is, what AES key are we going to use? If the key is public/constant, the attacker can just repeat the AES step themselves while they try to guess the input. On the other hand, if the key is secret, then we need to store it somewhere. Most likely, we're going to store it in the same place/database where we store the hash. (In this case it's basically the same as a random "salt".) But that means than at attacker who steals password hashes is probably going to steal salts at the same time. > large file hashes This is often true, but we have to be careful. What we really care about isn't the size of the file per se, but the number of possible inputs the attacker has to guess. So for example, if we hash a video file we downloaded from a bittorrent site, it might be easy for someone else to figure out what file that was, because even though the file is large, the total number of files on these sites isn't so large.
      - foxyv 5y ago
        You are entirely correct. Unfortunately anything short of a textbook is going to be "Mostly Right" when it comes to security/encryption. > Encrypting before hashing doesn't actually help us Technically correct. There is no additional need to hash once you are encrypting already. However, when compliance tells you that you need to use hashing but you still need sub 10ms performance you sometimes need to use encryption. The disadvantage is the necessity for key management, HSMs, etc... Anything with low enough entropy is going to NEED encryption unless you are using ridiculous BCrypt or PBKDF2 parameters and are willing to wait a day or two to verify a hash. > Large file hashes If you salt the file data appropriately this is not an issue. The salt can be a part of the encrypted file ensuring that your hash doesn't collide.
staticassertion 5y ago
I really like this. Cryptography is obviously very hard to get right and complex, and for that reason people have said "don't roll your own crypto" - but really, that's stupid. What we need is accessible information to explain cryptography to people, so they know how to make smart crypto decisions, know what pitfalls exist, etc. I think crypto has done a particularly bad job of providing accessible materials, historically, and has had a terrible attitude towards doing so. Things are changing, and that's nice.
- zgs 5y ago
  The skills needed to write good crypto are different to those needed to use it. There is some overlap of course, but less than is implicated here. Probably the best advice for using crypto is to use algorithms for what they were intended. Which will require some reading and the materials aren't as accessible as they ought to be.
- traceroute66 5y ago
  > people have said "don't roll your own crypto" - but really, that's stupid. What we need is accessible information to explain cryptography to people, so they know how to make smart crypto decisions I disagree. The "crypto is hard" saying is there for a reason. It is scarily easy to make a crypto-breaking mistake in a simple looking piece of code. Yes people need to know "how to make smart crypto decisions", but when you are dealing with sysadmins or other end-users, I put it to you that they could not care less about the mathematical theory, what they really want/need to know is "what settings should I be using with $insert_name_of_crypto_library in my config file". Let me put it to you another way... If we extend your theory, then we would have to teach the world basic chemistry about Sodium hypochlorite so that they can make "smart decisions" about whether or not to drink a bottle of bleach. But maybe its just simpler to use the "crypto library" approach and stick a couple of globally recognised scary looking icons on the bottle along with a short paragraph of generic text in the local language ?
  - userbinator 5y ago
    then we would have to teach the world basic chemistry When I was in high school, they did. Is that not the case anymore?
y42 5y ago
Wrote a similar article, in Barbarian language for the German audience here, and completely in Python. I found it really difficult to find written and understandable material for this topic. Mostly people posts Youtube clickbait videos about that. Though, this one goes far beyond the simple process. So I almost don't dare to compare my profane post to this elaborarte description. "Wie funktioniert der SHA256 Algorithmus…im Detail? (Teil 1/2) – nicky reinert" https://nickyreinert.de/blog/2021/10/31/wie-funktioniert-der-sha256-algorithmusim-detail-teil-1-2/ https://nickyreinert.de/blog/2021/10/31/wie-funktioniert-der...
- k__ 5y ago
  "Deprecated: implode(): Passing glue string after array is deprecated. Swap the parameters in /htdocs/wp-content/plugins/crayon-syntax-highlighter/util/crayon_util.class.php on line 73" Just a heads up.
- chimeracoder 5y ago
  > in Barbarian language for the German audience here I assume this is supposed to say "Bavarian"?
- lfkdev 5y ago
  > Barbarian language nice
JaggerFoo 5y ago
I wonder how the newer hashes, like Reinforced Concrete, that are used in Zero-Knowledge applications compare to SHA-256. I mean can Reinforced Concrete replace SHA-256, as the primary hash, in a blockchain?
- deadbeeves 5y ago
  Hash functions are generally interchangeable except in their length and their speed.
  - zgs 5y ago
    and brokenness :)
userbinator 5y ago
The most interesting part of this is the section on Length Extension Attack. Implementing SHA256 isn't all that interesting since it's just a mechanistic translation of an algorithm, but the attack shows off one of the implications of how the function works.
7373737373 5y ago
I found this video to be an excellent explanation and sufficient to implement the algorithm: https://www.youtube.com/watch?v=f9EbD6iY9zI https://www.youtube.com/watch?v=f9EbD6iY9zI Code: https://gist.github.com/void4/6f5ff23a3df81d6115fceb6adefddd88 https://gist.github.com/void4/6f5ff23a3df81d6115fceb6adefddd... This site contains a nice visualization: https://sha256algorithm.com/ https://sha256algorithm.com/
f7ebc20c97 5y ago
Proof-of-work cryptocurrencies moved toward complex hash functions that are "ASIC resistant" in order to attempt to keep mining power as distributed as possible (for CPUs), because whatever highly-funded manufacturer designs the most-optimized and fastest ASICs gains concentrated mining power. ASIC hash/W efficiency doubles every couple of years, so using them as heaters becomes cost-ineffective as difficulty adjusts. But what if we turned this all on its head and intentionally designed a hash function that is "ASIC optimized" so that the perfect ASIC miner design could be found quickly (perhaps at its very conception), and miners became a generic commodity item, "grey goo miners", and used them as space heaters in cold climates, or maybe even wherever electric heating was needed in industry? That way mining would be as distributed as the need for electric heating, and its energy would be put to good use. It might also put a ceiling on the total electricity consumed because it would be hard to compete with any miner whose electric bills are "free" (relatively).
- deadbeeves 5y ago
  >what if we turned this all on its head and intentionally designed a hash function that is "ASIC optimized" so that the perfect ASIC miner design could be found quickly Since hash functions are applied to variable-sized parameters, optimizations always exist. You can always compute the hash by processing less of the input, or by processing it in parallel. Just because it's not known how to do this doesn't mean it's impossible. It's impossible to know when an implementation of an algorithm (whether in software or hardware) is optimal.
  - f7ebc20c97 5y ago
    Not necessarily. The mining algorithm could hash the block once using SHA256, then use that and a fixed-size nonce as a fixed-size parameter for the ASIC-optimized hash function.
    - f7ebc20c97 5y ago
      Isn't 99% optimal good enough?
    - deleted 5y ago
nemo1618 5y ago
I was hoping this would explain a bit more about why the algorithm does the things it does. Do we have proofs for why certain types of mixing are more secure than others? Also, it's funny how even world-class cryptographers can think it's perfectly fine to directly output internal state as the digest. Some things are only obvious in retrospect.
- dragontamer 5y ago
  > I was hoping this would explain a bit more about why the algorithm does the things it does. Do we have proofs for why certain types of mixing are more secure than others? Only the most simple of proofs for the most simple of circumstances. Lets say you have a 2-bit number (x0, and x1 for the two bits) that you want to mix up / encrypt. The output can be 0-bits, 1-bit, or 2-bits. 3-bits or more wouldn't work (8-outputs vs 4-inputs). 1-bit "wastes a bit" of information (you go from either 4-possible inputs into 2-possible outputs). Therefore, having 2-bit input (4-possible inputs), your maximal amount of "mixing up" you can do is to have 4-possible outputs. That is, a 2-bit input should mix into a 2-bit output. There are patterns for how to make these "bijections". AES used Galois Fields (which are always a bijection), as well as S-tables (substitution tables, or 8-bit / 256-input to 8-bit / 256-output tables to mix things up 8-bits at a time). It turns out that ADD / XOR / BITSHIFT are all you need to make a modern, high-speed bijection. So more modern ciphers prefer those functions instead. ------- From there on out, there's just a lot of testing that goes on. You run tests to see if any bits seem "corelated" to each other (ie: Differential Analysis. When Bit#25 changes, does that cause Bit#66 to change 50% of the time? Or does it change 52% of the time? Because 52% of the time would allow us to run probability attacks and figure out how Bit#25 and #66 are connected with just 25-or-so trials). So you try to make your functions as "flat" as possible, to defeat probability analysis (also known as differential analysis). There are other probability/statistical tests, but these are largely ad-hoc ideas. So you learn all the cryptography-probability tricks about how other ciphers have failed (correlation between bits, etc. etc.), and emperically test your functions against such analysis. Make your probability distributions as "flat" as possible (50.00000% correlation between bits), and you'll defeat differential-cryptoanalysis. -------- The only way for 2-bits of input to mix into 2-bits of output is to have a 1-to-1 and onto function, also known as a bijection (and sometimes called a permutation). > Also, it's funny how even world-class cryptographers can think it's perfectly fine to directly output internal state as the digest. Some things are only obvious in retrospect. What's wrong with this? There's the same information at that point. You only have another permutation function. Once the internal state is "sufficiently mixed up" (that is... in the 2-bit case... the 2-bits of input can become 2-bits of output in a sufficiently mixed up way), you can't get any better than just returning the input state. Once all 256-bits of input have a 50% chance of changing all 256-bits of state, then you can just output the internal state as your "answer". In fact, "mixing" them up any further might accidentally throw off your statistical analysis... so its better to NOT muck with the number anymore.

213 points by oconnor663 5y ago

OP appears to be Jack O'Connor, one of the designers of BLAKE3, which is the fastest full-strength cryptographic hash function currently available. It's always nice to see practicing cryptographers also producing digestible cryptography content.

mderazon 5y ago
"fastest hash function" - I do not know much about cryptography, but isn't a hash function slow by design, or at least slow enough to prevent brute force ?
- oconnor663 5y ago
  No but this is a common misconception. The key thing to remember is that a regular hash function and a "password hash" are very different. A password hash does need to be slow, because we want to make it expensive for an attacker who's stolen the hash to try to guess the password. But in most other use cases, we want hash functions to be as fast as possible, as long as they can uphold their security guarantees. A maybe-interesting sidebar: If your job is to design a password hash, you still want to take a fast hash function as a starting point. All the effort that goes into making the hash function both fast and secure gives you confidence that an attacker isn't going to be able to find some shortcut that lets them compute the hash it more quickly than everyone else.
- foxyv 5y ago
  Hello, great question! Hashes must only be slow in certain circumstances where the plaintext of the hash is vulnerable to a "pre-image" attack. This means that the entropy of the plaintext is very low and there are very few possibilities. In these cases you use extremely slow hashes like bcrypt or be forced to use AES encryption before hashing. For example: Passwords, Credit Card Security Digits, Names, etc... Plaintext that has a LOT of entropy does not need a slow hash function. You can usually get by with SHA-256. For example: digital signatures, AES keys, Public/Private keys, large file hashes, etc... In addition, if you are only trying to verify integrity with no need for security, a quick hash function is useful. Like a checksum on a file system. In this case a fast hash function is more important. EG: https://ext4.wiki.kernel.org/index.php/Ext4_Metadata_Checksums https://ext4.wiki.kernel.org/index.php/Ext4_Metadata_Checksu...
  - oconnor663 5y ago
    All of this is mostly right, but I have some minor corrections: > or be forced to use AES encryption before hashing Encrypting before hashing doesn't actually help us, if our hash input has low entropy. The problem is, what AES key are we going to use? If the key is public/constant, the attacker can just repeat the AES step themselves while they try to guess the input. On the other hand, if the key is secret, then we need to store it somewhere. Most likely, we're going to store it in the same place/database where we store the hash. (In this case it's basically the same as a random "salt".) But that means than at attacker who steals password hashes is probably going to steal salts at the same time. > large file hashes This is often true, but we have to be careful. What we really care about isn't the size of the file per se, but the number of possible inputs the attacker has to guess. So for example, if we hash a video file we downloaded from a bittorrent site, it might be easy for someone else to figure out what file that was, because even though the file is large, the total number of files on these sites isn't so large.
    - foxyv 5y ago
      You are entirely correct. Unfortunately anything short of a textbook is going to be "Mostly Right" when it comes to security/encryption. > Encrypting before hashing doesn't actually help us Technically correct. There is no additional need to hash once you are encrypting already. However, when compliance tells you that you need to use hashing but you still need sub 10ms performance you sometimes need to use encryption. The disadvantage is the necessity for key management, HSMs, etc... Anything with low enough entropy is going to NEED encryption unless you are using ridiculous BCrypt or PBKDF2 parameters and are willing to wait a day or two to verify a hash. > Large file hashes If you salt the file data appropriately this is not an issue. The salt can be a part of the encrypted file ensuring that your hash doesn't collide.

staticassertion 5y ago

I really like this. Cryptography is obviously very hard to get right and complex, and for that reason people have said "don't roll your own crypto" - but really, that's stupid. What we need is accessible information to explain cryptography to people, so they know how to make smart crypto decisions, know what pitfalls exist, etc. I think crypto has done a particularly bad job of providing accessible materials, historically, and has had a terrible attitude towards doing so. Things are changing, and that's nice.

zgs 5y ago
The skills needed to write good crypto are different to those needed to use it. There is some overlap of course, but less than is implicated here. Probably the best advice for using crypto is to use algorithms for what they were intended. Which will require some reading and the materials aren't as accessible as they ought to be.
traceroute66 5y ago
> people have said "don't roll your own crypto" - but really, that's stupid. What we need is accessible information to explain cryptography to people, so they know how to make smart crypto decisions I disagree. The "crypto is hard" saying is there for a reason. It is scarily easy to make a crypto-breaking mistake in a simple looking piece of code. Yes people need to know "how to make smart crypto decisions", but when you are dealing with sysadmins or other end-users, I put it to you that they could not care less about the mathematical theory, what they really want/need to know is "what settings should I be using with $insert_name_of_crypto_library in my config file". Let me put it to you another way... If we extend your theory, then we would have to teach the world basic chemistry about Sodium hypochlorite so that they can make "smart decisions" about whether or not to drink a bottle of bleach. But maybe its just simpler to use the "crypto library" approach and stick a couple of globally recognised scary looking icons on the bottle along with a short paragraph of generic text in the local language ?
- userbinator 5y ago
  then we would have to teach the world basic chemistry When I was in high school, they did. Is that not the case anymore?

y42 5y ago

Wrote a similar article, in Barbarian language for the German audience here, and completely in Python. I found it really difficult to find written and understandable material for this topic. Mostly people posts Youtube clickbait videos about that. Though, this one goes far beyond the simple process. So I almost don't dare to compare my profane post to this elaborarte description. "Wie funktioniert der SHA256 Algorithmus…im Detail? (Teil 1/2) – nicky reinert" https://nickyreinert.de/blog/2021/10/31/wie-funktioniert-der-sha256-algorithmusim-detail-teil-1-2/ https://nickyreinert.de/blog/2021/10/31/wie-funktioniert-der...

k__ 5y ago
"Deprecated: implode(): Passing glue string after array is deprecated. Swap the parameters in /htdocs/wp-content/plugins/crayon-syntax-highlighter/util/crayon_util.class.php on line 73" Just a heads up.
chimeracoder 5y ago
> in Barbarian language for the German audience here I assume this is supposed to say "Bavarian"?
lfkdev 5y ago
> Barbarian language nice

JaggerFoo 5y ago

I wonder how the newer hashes, like Reinforced Concrete, that are used in Zero-Knowledge applications compare to SHA-256. I mean can Reinforced Concrete replace SHA-256, as the primary hash, in a blockchain?

deadbeeves 5y ago
Hash functions are generally interchangeable except in their length and their speed.
- zgs 5y ago
  and brokenness :)

userbinator 5y ago

The most interesting part of this is the section on Length Extension Attack. Implementing SHA256 isn't all that interesting since it's just a mechanistic translation of an algorithm, but the attack shows off one of the implications of how the function works.

7373737373 5y ago

I found this video to be an excellent explanation and sufficient to implement the algorithm: https://www.youtube.com/watch?v=f9EbD6iY9zI https://www.youtube.com/watch?v=f9EbD6iY9zI Code: https://gist.github.com/void4/6f5ff23a3df81d6115fceb6adefddd88 https://gist.github.com/void4/6f5ff23a3df81d6115fceb6adefddd... This site contains a nice visualization: https://sha256algorithm.com/ https://sha256algorithm.com/

f7ebc20c97 5y ago

Proof-of-work cryptocurrencies moved toward complex hash functions that are "ASIC resistant" in order to attempt to keep mining power as distributed as possible (for CPUs), because whatever highly-funded manufacturer designs the most-optimized and fastest ASICs gains concentrated mining power. ASIC hash/W efficiency doubles every couple of years, so using them as heaters becomes cost-ineffective as difficulty adjusts. But what if we turned this all on its head and intentionally designed a hash function that is "ASIC optimized" so that the perfect ASIC miner design could be found quickly (perhaps at its very conception), and miners became a generic commodity item, "grey goo miners", and used them as space heaters in cold climates, or maybe even wherever electric heating was needed in industry? That way mining would be as distributed as the need for electric heating, and its energy would be put to good use. It might also put a ceiling on the total electricity consumed because it would be hard to compete with any miner whose electric bills are "free" (relatively).

deadbeeves 5y ago
>what if we turned this all on its head and intentionally designed a hash function that is "ASIC optimized" so that the perfect ASIC miner design could be found quickly Since hash functions are applied to variable-sized parameters, optimizations always exist. You can always compute the hash by processing less of the input, or by processing it in parallel. Just because it's not known how to do this doesn't mean it's impossible. It's impossible to know when an implementation of an algorithm (whether in software or hardware) is optimal.
- f7ebc20c97 5y ago
  Not necessarily. The mining algorithm could hash the block once using SHA256, then use that and a fixed-size nonce as a fixed-size parameter for the ASIC-optimized hash function.
  - f7ebc20c97 5y ago
    Isn't 99% optimal good enough?
  - deleted 5y ago

nemo1618 5y ago

I was hoping this would explain a bit more about why the algorithm does the things it does. Do we have proofs for why certain types of mixing are more secure than others? Also, it's funny how even world-class cryptographers can think it's perfectly fine to directly output internal state as the digest. Some things are only obvious in retrospect.

dragontamer 5y ago
> I was hoping this would explain a bit more about why the algorithm does the things it does. Do we have proofs for why certain types of mixing are more secure than others? Only the most simple of proofs for the most simple of circumstances. Lets say you have a 2-bit number (x0, and x1 for the two bits) that you want to mix up / encrypt. The output can be 0-bits, 1-bit, or 2-bits. 3-bits or more wouldn't work (8-outputs vs 4-inputs). 1-bit "wastes a bit" of information (you go from either 4-possible inputs into 2-possible outputs). Therefore, having 2-bit input (4-possible inputs), your maximal amount of "mixing up" you can do is to have 4-possible outputs. That is, a 2-bit input should mix into a 2-bit output. There are patterns for how to make these "bijections". AES used Galois Fields (which are always a bijection), as well as S-tables (substitution tables, or 8-bit / 256-input to 8-bit / 256-output tables to mix things up 8-bits at a time). It turns out that ADD / XOR / BITSHIFT are all you need to make a modern, high-speed bijection. So more modern ciphers prefer those functions instead. ------- From there on out, there's just a lot of testing that goes on. You run tests to see if any bits seem "corelated" to each other (ie: Differential Analysis. When Bit#25 changes, does that cause Bit#66 to change 50% of the time? Or does it change 52% of the time? Because 52% of the time would allow us to run probability attacks and figure out how Bit#25 and #66 are connected with just 25-or-so trials). So you try to make your functions as "flat" as possible, to defeat probability analysis (also known as differential analysis). There are other probability/statistical tests, but these are largely ad-hoc ideas. So you learn all the cryptography-probability tricks about how other ciphers have failed (correlation between bits, etc. etc.), and emperically test your functions against such analysis. Make your probability distributions as "flat" as possible (50.00000% correlation between bits), and you'll defeat differential-cryptoanalysis. -------- The only way for 2-bits of input to mix into 2-bits of output is to have a 1-to-1 and onto function, also known as a bijection (and sometimes called a permutation). > Also, it's funny how even world-class cryptographers can think it's perfectly fine to directly output internal state as the digest. Some things are only obvious in retrospect. What's wrong with this? There's the same information at that point. You only have another permutation function. Once the internal state is "sufficiently mixed up" (that is... in the 2-bit case... the 2-bits of input can become 2-bits of output in a sufficiently mixed up way), you can't get any better than just returning the input state. Once all 256-bits of input have a 50% chance of changing all 256-bits of state, then you can just output the internal state as your "answer". In fact, "mixing" them up any further might accidentally throw off your statistical analysis... so its better to NOT muck with the number anymore.