Avalanche functions (by alaric)
So we could take an existing complex cipher with a block size of 64 or 128 bits, and use that with an avalanche function using a block size of 32 or 64 bits respectively, or the same block size with two rounds. However, those wide block ciphers are complex - so slow to compute, and hard to analyse for security.
Now, a key-dependent S-box is really a perfect cipher, for its block size. With the correct keying of the S-boxes, it can express any other cipher of the same block size; it's the superset of all possible ciphers. But due to the prohibitive storage requirements, it's difficult to work with S-boxes of more than 16 bits width; a 16 bit S-box takes up 128KB of RAM. A 32 bit S-box would take up 16GB.
So we would really like to be able to work with a 16-bit ECB block size. Perhaps the solution is to have several rounds, each "avalanching" 8 bits across. But how many rounds? If the message we are encrypting is 1GB in size, we would want more avalanche bandwidth than one of just 16 bytes. So perhaps we need more rounds as the message grows - resulting in encryption taking time proportional to the square of the message size.
But then again, that is inevitable. The very definition of good avalanche states that every output bit should be a function of all (or very nearly all) the input bits - so for N bits, that's N functions that must take at least N steps since they examine N input bits...
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 😉