1
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ Are you looking for the Avalanche Effect for block ciphers?. What if it always changes the first half? $\endgroup$
    – kelalaka
    Jul 3, 2020 at 15:43
  • 3
    $\begingroup$ In general clearly no. If every round flips the same bits, every even number of rounds will have 0 bits flipped. $\endgroup$
    – Maeher
    Jul 3, 2020 at 15:44
  • $\begingroup$ 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? $\endgroup$ Jul 5, 2020 at 17:08
  • $\begingroup$ 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. $\endgroup$
    – Tom
    Jul 6, 2020 at 23:51

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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"? $\endgroup$
    – Tom
    Jul 6, 2020 at 23:25
0
$\begingroup$

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.

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