3 ms·

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 th

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.
- schoen 5y ago
  > 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. I'm sure the original poster is referring to https://en.wikipedia.org/wiki/Length_extension_attack https://en.wikipedia.org/wiki/Length_extension_attack It seems like the general solution in the SHA family has been to return a subset of the internal state ("truncation"). This then creates unknown state that an attacker would have to guess in order to perform a length extension. https://en.wikipedia.org/wiki/SHA-2#Comparison_of_SHA_functions https://en.wikipedia.org/wiki/SHA-2#Comparison_of_SHA_functi... Edit: Indeed, the original article turns out to teach you to implement the length extension attack at the end, and states that it "was a design mistake" in SHA-256 not to truncate.
  - dragontamer 5y ago
    Fair enough. But that argument is a bit subtle. Going back to the 2 bit input example, if your internal state is 4 bits, you only have 2 bits of entropy. So outputting the first two bits of your 4 but state is still (probably) valid as far as a hash is concerned, assuming a good enough mixing function. But at the same time, if you need all 4 bits to adequately continue the hash, then 'hiding' those other two bits will help out. So it's not so much the truncation, as much as it is the unnecessary expansion and then later truncation steps that's useful for hashing. (Ex: SHA512 truncated to 256 bits is immune to the attack described). In any case, these attacks are ad-hoc and don't seem to have any pattern. Crypto-experts design against attacks like these. Since there is no pattern, you end up having to study all these attacks and designing against all of them.

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.

schoen 5y ago
> 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. I'm sure the original poster is referring to https://en.wikipedia.org/wiki/Length_extension_attack https://en.wikipedia.org/wiki/Length_extension_attack It seems like the general solution in the SHA family has been to return a subset of the internal state ("truncation"). This then creates unknown state that an attacker would have to guess in order to perform a length extension. https://en.wikipedia.org/wiki/SHA-2#Comparison_of_SHA_functions https://en.wikipedia.org/wiki/SHA-2#Comparison_of_SHA_functi... Edit: Indeed, the original article turns out to teach you to implement the length extension attack at the end, and states that it "was a design mistake" in SHA-256 not to truncate.
- dragontamer 5y ago
  Fair enough. But that argument is a bit subtle. Going back to the 2 bit input example, if your internal state is 4 bits, you only have 2 bits of entropy. So outputting the first two bits of your 4 but state is still (probably) valid as far as a hash is concerned, assuming a good enough mixing function. But at the same time, if you need all 4 bits to adequately continue the hash, then 'hiding' those other two bits will help out. So it's not so much the truncation, as much as it is the unnecessary expansion and then later truncation steps that's useful for hashing. (Ex: SHA512 truncated to 256 bits is immune to the attack described). In any case, these attacks are ad-hoc and don't seem to have any pattern. Crypto-experts design against attacks like these. Since there is no pattern, you end up having to study all these attacks and designing against all of them.