4 ms·
It's sort of almost correct. He's fumbling his way towards the avalanche property: for a perfect cryptographic hash if you flip a single bit in the input, on av
by pja 15y ago
It's sort of almost correct. He's fumbling his way towards the avalanche property: for a perfect cryptographic hash if you flip a single bit in the input, on average half the bits in the output will change.
http://en.wikipedia.org/wiki/Avalanche_effect http://en.wikipedia.org/wiki/Avalanche_effect
- antirez 15y agoYes, but the Avalanche effect does not mean it is not invertible. It is possible to design a one way hash function with remarkable avalanche (50% of flipped bits on average after 1 bit change in input) effect but that is easily invertible. The simplest would be an hash function that outputs an N-bit hash where M bits are a pseudo-random sequence of bits (depending on the input, let's say SHA1(input)) that are used to key a stream cipher, and the rest N-M bits are the XOR between the stream cipher output and part of the input of the hash function. Perfect Avalanche effect, but the function is invertible.
- jacquesm 15y agoOnly in that special case where the input <= the output of the hash function, as in your example earlier in the thread.
- antirez 15y agoAn hash function is invertible enough if it will leak the first three bytes of the input. Does not need to be invertible as F^-1 in mathematical notation.