1

Let's say we have a cipher with such property, that every round change 50% of bits in every block in average. Is it obvious or it means that after few rounds we will get exactly 50% changed bits?

If I think about it, it looks like it doesn't have to be like that. Next round can delete some changes from previous round and so on. In the end we we can get a different number of bits changed, even if each round changes exactly 50% of the bits.

Am I right? If we have such property that every round change 50% of bits, how to be sure that in many rounds in the end we will also end up with 50% of bits changed? Can it be proven somehow or usually we have to rely on statistical tests?

Tom
  • 1,221
  • 6
  • 16
  • Are you looking for the Avalanche Effect for block ciphers?. What if it always changes the first half? – kelalaka Jul 03 '20 at 15:43
  • 3
    In general clearly no. If every round flips the same bits, every even number of rounds will have 0 bits flipped. – Maeher Jul 03 '20 at 15:44
  • A problematic bit in this question which I don't see addressed in answers is the phrase "in average". Please give more detail of how the algorithm chooses which bits to flip; is the number of bits always half the block length per block? – Adrian Self Jul 05 '20 at 17:08
  • No, the number of changed bits is not always half the block length per block. One round can change even only two bits in some specific block with specific key. If we take all blocks, then we will get half of bits changed in one round with every key. – Tom Jul 06 '20 at 23:51

2 Answers2

3

If we have such property that every round change 50% of bits, how to be sure that in many rounds in the end we will also end up with 50% of bits changed?

Well, obviously one can construct artificial examples where this doesn't happen; the most obvious (and trivial) being if round 1 and round 2 are inverses of each other (that is, round 1 followed by round 2 gives you the original plaintext); even if both rounds were individually ideal, we still don't get the avalanche effect after two rounds (even though we had it after one).

Symmetric ciphers are generally don't have enough structure to allow us to construct proofs that this doesn't happen (and adding structure generally makes the cipher weaker, not stronger; adversaries can also take advantage of structure); we generally have to rely on plausibility arguments.

poncho
  • 147,019
  • 11
  • 229
  • 360
  • So is the only thing we can do to check if the cipher changes exactly 50% bits are statistical tests? But then we can only measure asymptotic convergences. Let's say it turns out that in N samples about 50% changed. It still won't be proof, becasue cipher could change 49,99999% of bits in average, not 50%. And what is "structure"? – Tom Jul 06 '20 at 23:25
0

Here is a different point of view. As pointed out in comments, you can make structured choices which mean all or half the bits are flipped. Instead let us consider a model where randomness is used.

Let $b$ be the blocklength, which is always even, in fact usually power of 2. To model the process , let us say we randomly flip half the bits (an integer since $b$ is even) in the first round; then randomly and independently of what happened in round 1, choose a subset of $b/2$ bits and flip them in the second round, and so on.

Since the process is independent, the eventual number of flipped bits, compared to the input vector, will be distributed as a binomial $\mathrm{Bin}(b,1/2).$

The probability that exactly half the bits are flipped is $$ 2^{-b} \binom{b}{b/2}\approx \frac1{\sqrt{\pi b}}. $$ Now this may look paradoxical, the probability that exactly half the bits are flipped is slowly going down with $b$. If $b=32,$ this probability calculated exactly is $0.134$ while for $b=128,$ it is halved to $0.070$ as expected from the approximation.

However there is no paradox. If we ask what is the probability that we are within 5% of exactly half the bits being flipped, we sum a few binomial coefficients around the middle coefficient, as in $$ 2^{-b} \sum_{\lceil (1-\epsilon)b/2\rceil}^{\lfloor(1+\epsilon)b/2\rfloor} \binom{b}{k}. $$ If $b=32,$ and $\epsilon=0.05$, this probability calculated exactly is $0.134$ while for $b=128,$ it is has increased to $0.464$ as expected from the approximation.

kodlu
  • 22,423
  • 2
  • 27
  • 57