Avalanche functions (by alaric)
For example, one could dispense with the complex Feistel networks and other such hard-to-analyse multi-round messes as are found within most popular block ciphers if one could find a good enough avalanche function (ideally, where every bit of the output is a function of every bit of the input), and just sandwich it between two layers of ECB encryption with key-dependent 16-bit S-boxes, which are fairly ideal ciphers; up to 931 kilobits of key (if using a saner sized key, like 128 or 256 bits, be sure to use a good enough mechanism to fill the S-box that the fact only a tiny subset of the possible S-boxes are possible does not invite exploitation).
So where might we find such a function?
In my idle theorising, I've found a potential candidate - surprisingly simple, but with some useful properties.
- Divide the input into an even number of sub-blocks, each of which is smaller than the sub-blocks used in the ECB encryption. Eg, if using a 16-bit S-box as your sub-cipher, choose an 8-bit sub-block for the avalanche function, so there will always be an even number of sub-blocks.
- Each output sub-block is the XOR-sum of all the input sub-blocks, except the one with the same index as the output sub-block being computed
Voila! Each output sub-block is a function of nearly all the input sub-blocks - to be more precise, each output bit is a function of one bit from all the input sub-blocks but one.
Now, looking at the message in terms of the ECB sub-blocks, each sub-block after the avalanche function is indeed a function of all the sub-blocks before the avalanche function (if you're not sure why, look at the two avalanche sub-blocks that make up the ECB sub-block, and what they are functions of)
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 😉