Score:1

# Diffusion of arithmetic and bit operations

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:

• 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$$.

What kind of $n$ would that be? I think you forgot to copy that part of the assignment.
@MaartenBodewes I think you are right. I thought about n equal to power of two.
Score:1

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.

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

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

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

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;

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?
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)?
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?
@kelalaka diagrams are wrong?
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}$
I sit in a Tesla and translated this thread with Ai: