Avalanche functions (by alaric)
Now, looking at a slightly smaller scale, inside the workings of things like AES or DES or IDEA, we see that the ciphers themselves are composed of simple well-studied blocks like S-boxes, XORing, binary rotates, modulo 2n-1 multiplication, and so on.
And these small components are arranged in such a way as to, again, encourage this property of a single bit change in the input producing two outputs that don't appear to be related in any simple way.
Seeing this fundamental requirement of composing smaller ciphers to make larger ciphers occuring on two different levels, I've made a bit of a study of general techniques for doing this.
I've considered a cipher architecture where the input block is divided into sub-blocks, each of which is encrypted independently (ECB again) with a sub-cipher. However, after doing this, the output is then processed with an avalance function, that need not be key-dependent, and exists purely to cause interrelationships between the sub-blocks; the output of the avalanche function is then ECB-encrypted again (otherwise, the attacker could simply undo the documented and non-key-dependent avalanche function and attack the result as per ECB).
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 😉