2
$\begingroup$

Avalanche effect:

The strict avalanche criterion (SAC) is a formalization of the avalanche effect. It is satisfied if, whenever a single input bit is complemented, each of the output bits changes with a 50% probability.

My questions are:

  • Is a 50% bit-change-probability optimal for any hash or is it just the minimal value so satify the strict avalanche criterion?

  • What if a hash-algorithm had a 100% bit-change-probability?

$\endgroup$
  • $\begingroup$ "What if a hash-algorithm had a 100% bit-change-probability?" That's impossible. You would calculate one hash value, say over the empty string. Now any other input message would result in the same bit complement of the given hash value. Of course, this would also be the case for any other value then the empty string. But as we just saw, any other value should result in the same complement of the hash over the empty string, and it is impossible to be the same and the complement at the same time. Note that we are talking about the chance probability over bits, not of the complete hash. $\endgroup$ – Maarten Bodewes Oct 5 '18 at 13:23
4
$\begingroup$

Consider a function $H:\{0,1\}^m\to\{0,1\}^h$ (that is, from the set of $m$-bit bistrings to the set of $h$-bit bitstrings). Define $D_n=0^n\mathbin\|1\mathbin\|0^{m-n-1}$ (that is, the $m$-bit "disturbance" bitstring with only bit $n$ set).

By a possible definition, $H$ satisfies the Strict Avalanche Criterion when for each of the $m\cdot h$ pairs $(n,i)$ with $0\le n<m$ and $0\le i<h$, the arithmetic sum of bit $i$ of $H(M\oplus D_n)\oplus H(M)$ computed for all $M$ in $\{0,1\}^m$ is $2^{m-1}$ (that is, exactly 50% of the number of terms summed).

That can be extended to functions with variable-size input (such as usual hashes) by stating that for each input size $m\ge2$ supported, the function satisfies the SAC (Note: when $m<2$ and $h\ne0$, no function satisfies the SAC).


Is a 50% bit-change-probability optimal for any hash or is it just the minimal value to satisfy the strict avalanche criterion?

Neither.

50% is not the minimal value to satisfy the strict avalanche criterion. For the SAC to hold, the probability that a 1-bit change in input changes any particular bit of output must be exactly 50%, where that probability is computed over the $2^m$ inputs.

The optimal for a cryptographic hash is to behave like a random function, and a random function is extremely unlikely to satisfy the SAC (for $m=2$ that has probability $2^{-h}$, and that goes further down very fast when $m$ grows). If a practical cryptographic hash ($h\ge128$) satisfies the SAC for some $m$ with $2\le m\le50$, that's easily detectable and a weakness in some possible applications. For large $m$ and practical secure hashes, it is computationally impossible to test if $H$ satisfies the SAC or not. Otherwise said, for large messages, a practical secure hash behaves as if it met the SAC for all computational purposes, even though it most likely does not.

Mildly interesting problem: up to what $m$ is it possible to get experimental evidence that a practical hash does not meet the SAC?


What if a hash-algorithm had a 100% bit-change-probability?

Such function must produce the XOR of its $m$ input bit(s), repeated $h$ times to form a $h$-bit vector, then XORed with a $h$-bit arbitrary value dependent only on $m$. It is not a secure cryptographic hash by any measure. Independently, it does not meet the SAC.

$\endgroup$
  • $\begingroup$ Does it make sense to speak of "probability" with fixed-size inputs, or merely as a limit for arbitrary-size inputs? If a hash function converts arbitrary sized inputs to 256-bit outputs by treating the input as a giant integer I, and retrieving bits 256I to 256I+255 of a cryptographically-secure pseudorandom generator (ignore the obvious impracticality of doing so), then for any particular combination of input size, input bit position, and output bit position, there would be some number of possible inputs where flipping the input bit would flip the output bit, and that number would... $\endgroup$ – supercat Oct 5 '18 at 16:20
  • $\begingroup$ ...not really seem like a "probability". If one allows arbitrary inputs, however, then such a thing would make sense, though I'm not sure whether a single-pass hash function with a fixed-sized state might pose other issues. $\endgroup$ – supercat Oct 5 '18 at 16:23
  • $\begingroup$ @supercat: The standard definition of SAC uses "probability" of foo per its mathematical definition for discrete cases: the quotient of the number of cases where foo holds to the total number of cases; and wants that quantity to be exactly $\frac12$. It does so in the context of S-boxes, which have few enough inputs that this quotient/probability can be exactly computed. That use of probability is correct, but leads to misunderstandings. That's why I have given an equivalent definition that does not use probability. $\endgroup$ – fgrieu Oct 5 '18 at 17:19
  • $\begingroup$ So for each possible pair (i,j) of input and output bits, the "probability" would be the probability that an input chosen at random from among 2**m possibilities would have the property that flipping bit i of the input would flip bit j of the output? $\endgroup$ – supercat Oct 5 '18 at 18:59
  • $\begingroup$ @supercat: yes. $\endgroup$ – fgrieu Oct 5 '18 at 19:01
1
$\begingroup$

What if a hash-algorithm had a 100% bit-change-probability?

Well, it wouldn't be a hash. You might call it an oscillator or something, but certainly not a pseudo random function. One of the principal characteristics of a cryptographic hash is that the output appears pseudo random, given any input.

You're suggesting a behaviour like $f(b) = f'(a)$ as you'd have to maintain a memory of all of the previous output bits. There would be no randomness and no independence between the outputs. You'd then simply oscillate between the two outputs. It would be useless as a hash and no better than a quasi NOT operator.

The 50% bit-change-probability is not optimal. It's one of the fundamental requirements. But you'll also find that this will occur naturally with the construction of any good hash. A natural relationship between an output collision rate of $1/e$ and a 50% overall bit change emerges given enough internal bit mangling.

Be careful though. The avalanche effect and the strict avalanche effect are not the same, and folks tend to use them interchangeably. They're not and your wiki quote isn't explicitly correct. One is not simply the formalisation of the other. There's a succinct answer @ https://crypto.stackexchange.com/a/42471/23115 explaining this.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.