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