3
$\begingroup$

I am wondering whether the confusion and diffusion are quantified in any way when we examine hashing algorithms and, if so, how they are quantified and what units (if any) are used to represent them.

$\endgroup$
2
  • 1
    $\begingroup$ For a full hash function, not really, but at the level of diffusion per round (for hash functions based on iterative block ciphers, at least) you can. Is that what you mean? $\endgroup$
    – forest
    Dec 26, 2019 at 2:50
  • $\begingroup$ @forest I didn't know that. Is it because making these quantifications for a full hash function would be too complicated? I think that quantifying diffusion per-round would also answer my question. $\endgroup$
    – chillsauce
    Dec 26, 2019 at 18:54

1 Answer 1

1
$\begingroup$

It depends a lot of why you want to do this and for what types of hashes and input data but I would think that for some purposes it may be sufficient to do so through sampling, though you would certainly want to be careful about how much you trust this sort of analysis depending on how you're using the hash values.

For example, if you know that the data you're hashing often has a certain format or is always a certain length you could generate a set of test inputs of manageable lengths. For the purposes of this answer let's say 4 bytes but in practice you'd probably want to pick an assortment of lengths that apply to your use-case.

You should include some simple values (e.g. 0x00000000, 0xFFFFFFFF), some patterned values (e.g. 0x40404040, 0x1ACEECA1), and some completely random values. Then take each one and hash it to get a baseline, $H$, of length $N$ bits (i.e. 32).

For diffusion you could then, for each bit of the input:

  • Flip the bit, $i$
  • Hash the altered value, $H_i$ (i.e. the hash with bit $i$ flipped)
  • Count the number of bits that differ between the new hash and the baseline hash, $d_i$
  • Calculate $1 - \frac{| d_i - N/2 |}{N/2}$ to get a rating $r_i$ between 0 to 1 (with 1 being ideal diffusion).

For confusion you could do something similar, checking that across $H_0$ to $H_{N-1}$ each bit is flipped relative to the baseline due to changes in as many input bits as possible, creating a score for each output bit.

Using these diffusion and confusion scores, you could then compare hashes depending on whatever criteria you're most looking for in your use-case.

All of that said, this is a somewhat brute-force method that could very easily miss issues in a hashing algorithm that could be important from a security perspective. So again, I would only consider using a method like this if you're considering the properties of the hash relative to a specific use-case that isn't security-critical. Making this kind of statistical argument when you don't already have some idea what types of inputs you might be seeing reducing the likelihood that it will tell you anything useful effectively to zero.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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