Avalanche functions (by alaric)
The downside is that there is a limited "bandwidth of avalanche". If we make a change somewhere in the first half of a block, then no matter how much we change down there, there are only 256 possible avalanched changes (when using an 8-bit block size) that can occur in the upper half of the output of the block, since there are only H bits being 'communicated' between blocks.
Maybe we can use a large block size. Perhaps 128 bits - that's plenty of entropy to smear about. However, if we use an ECB block size of less than twice the avalanche block size, bad things happen. If we use an ECB block size that's the same as the avalanche block size, we don't get total avalanche; changing a single input bit will, due to the avalanche of the ECB cipher, cause a single ECB-block to be properly avalanched after the first ECB. The avalanche function will then cause every block apart from the one with the same index as the one that was changed to have the change avalanched into them. The final ECB will cause further avalanche of the change within each block, but the one block that was not avalanched into the by the avalanche function will encrypt to the same output ciphertext as would have been produced had the input not been changed, meaning that less than half of the bits, on average, will be changed by the single input change. Therefore, imperfect avalanche.
However, this can be fixed if we perform two 'rounds'; ECB, avalanche, ECB again, avalanche again, ECB once more. This will ensure total avalanche for an avalanche block the same size as the ECB block, at the cost of more computation.
If we use a larger avalanche block than our ECB block, however, it gets a lot worse. Say we have two ECB blocks to the avalanche block. A single bit change in the input will, due to the ECB, avalanche to a single ECB-block change. The avalanche function will cause the corresponding half of every avalanche-block apart from one to be changed - leaving half of the ECB-blocks plus one unchanged, which the second ECB will not fix. Very bad.
Crypto / security | alaric | 
Mon 4th Jul 2005 1:07 am
2 Comments
Other Links to this Post
RSS feed for comments on this post. TrackBack URI
Subscribe
By Ketos, Tue 8th May 2007 @ 9:56 pm
This function really doesn't work very well. What has happened is that each output subblock is the input subblock XORed with the sum of all of the input subblocks. Hence you retain pattern: (I_i is the ith input block. O_i is the ith output block) O_i = I_1 + ... + I_i-1 + I_i+1 +... + I_n = = I_1 + ... + I_i-1 + I_i+1 +... + I_n + I_i + I_i because XORing twice makes no difference = Sum + I_i
Hence O_i + O_j = Sum + I_i + Sum + I_j = I_i + I_j This property will be retained through multiple repetitions. For lots of data (esp. text or other structured stuff) these XOR differences let you reproduce the plaintext.
By alaric, Thu 10th May 2007 @ 4:30 pm
Yep - it's not a cryptosystem in itself (there's no key, for a start!). It's just a way of diffusing changes. There's certainly no advantage in multiple repetitions since it's self inverting...
However, if you have a small fixed-block-size cipher with decent properties (eg, AES) and want to apply it to an arbitrarily sized block, you can apply it to each subblock in parallel, then diffuse dependencies by using the XOR avalanche function, then apply AES to each subblock once more, diffuse again, AES again. Three rounds of AES is certainly the minimum required for security, maybe more.
Think of it as a mode rather than as a cipher 😉