1
$\begingroup$

I want to estimate when and wether different types of functions provide full or partial diffusion.

I'm trying to understand diffusion of basic operations, like:

  • addtion,
  • multiplication,
  • xoring.

If we change one bit in $a$ how many bits will be changed in average in result $c$ if we do:

$a+b \mod n = c$

If we change one bit in $a$ how many bits will be changed in average in result $c$ if we do:

$a \oplus b \mod n = c$

If we change one bit in $a$ how many bits will be changed in average in result $c$ if we do:

$a \cdot b \mod n = c$

And what if we change one bit in $a$ how many bits will be changed in average in result $c$ if we do:

$(a >> 1) \cdot b \mod n = c$

Is it fairly easy to deduce or do I have to write a program to check it?

In xor case only one bit would be changed if we compute it for $a$ differing by one bit. But what with other cases? I think in case of $a >> 1$ nearly half of the bits will be changed, because if we switch two bits that way, we have about 50% probability that they would be the same or not. So simple $a >> 1$ could provide good diffusion (if we combine it with other mixing operations, just repeating this operation over and over, of course, makes no sense).

EDIT:

Let's consider $n$ equal to power of $2$.

$\endgroup$
2
  • $\begingroup$ What kind of $n$ would that be? I think you forgot to copy that part of the assignment. $\endgroup$
    – Maarten Bodewes
    Oct 16, 2022 at 18:06
  • $\begingroup$ @MaartenBodewes I think you are right. I thought about n equal to power of two. $\endgroup$
    – Tom
    Oct 16, 2022 at 19:36

1 Answer 1

1
$\begingroup$

You can visually inspect the diffusion of different operations using an avalanche diagram.

I've generated the avalanche diagrams of these operations, the sizes I used for $a$ and $b$ are 64 bits. The result is also a 64-bit variable.

The tool I use generates the diagrams for all bit changes instead of just $a$, but it should still be informative.

Diffusion of $a \oplus b$

As you guessed; with plain XOR, the output bit $c_n$ is only affected by input bits $a_n$ and $b_n$. Here's what that looks like.

Avalanche diagram of XOR

Diffusion of $a + b$

A slight improvement is addition. You can see that instead of each bit only affecting itself, there is now a very slight diffusion around the bits.

Avalanche diagram of addition

Diffusion of $a \cdot b$

Multiplication provides a massive improvement. But multiplication only diffuses changes in one direction. And depending on the processor you are targeting, multiplications might be expensive or not constant time.

Avalanche diagram of multiplication

Diffusion by repeating simple mixers

If you take a bunch of invertible operations that somewhat diffuse the changes, and repetitively perform them, you can get much better results.

Below is an example with just XOR-shifts and add-shifts.

Avalanche diagram of repetition

Here's the operations that are being performed. As you can see, individually none of those diffuse that much, but if you repeat them enough, the mixing is much better.

for (size_t i = 0; i < 4; i++) {
    // Mix a
    a ^= a >> 7;
    a += a << 13;
    a ^= a >> 9;

    // Mix b
    b ^= b >> 7;
    b += b << 13;
    b ^= b >> 9;

    // Shift a and b into each other
    u64 a_old = a;
    u64 b_old = b;
    a = (a_old << 8) | ((b_old >> 56) & 0xFF);
    b = (b_old << 8) | ((a_old >> 56) & 0xFF);

}

u64 c = a ^ b;
$\endgroup$
5
  • $\begingroup$ Ok, I have many questions. 1. Did you make this diagrams in some program or generate it in c++ with some graphic library? What is the name of it? 2. Authors of Skein wrote about full diffusion, is it possible to get 100% diffusion? I thought about (a >> 1) * b. It could achieve full diffusion after 64 iterations, istn't it? $\endgroup$
    – Tom
    Oct 17, 2022 at 5:29
  • $\begingroup$ 3. It seems like this diffusions don't add to each other. I wanted to do thought experiment and calculate diffusion of n multiplications (e.g. by adding toegether n times diffusions of single multiplication), but of course some bits may remain unchanged, especially if low input bits would be all zeros. So to increase diffusion we have "move" green bits into black bits positions - somehow, by bit shifts or arithmetic operations. So it is hard to caclulate analytically final result. Can I use this method for scientific purposes, to estimate diffusion of some algorithm (is this accepted method)? $\endgroup$
    – Tom
    Oct 17, 2022 at 5:29
  • $\begingroup$ 4. It looks like in last diagram all pixels are green, but some are lighter. How to interpret that? Does it shows some bits are mixed less often? $\endgroup$
    – Tom
    Oct 17, 2022 at 6:16
  • $\begingroup$ @kelalaka diagrams are wrong? $\endgroup$
    – Tom
    Oct 18, 2022 at 5:24
  • $\begingroup$ Ok, the figures are confusing. X-or is fine, however, modular or not, addition can effect more than one bit and that is really depend on the size of modulus $n$ where it seems $2ˆ{64}$ $\endgroup$
    – kelalaka
    Oct 18, 2022 at 5:35

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.