Avalanche functions (by )

One way of looking at the design of a cipher is that you are taking a small fixed-block-size cipher of known good design, and finding a way to extend the security of that small block cipher to a larger block, potentially variable sized.

For example, stream ciphers (and their close cousins, 'cipher modes' like OFB, CFB, and so on) work by splitting the message into smaller blocks and applying the mini-cipher to each block in turn; but if they did that with the same key each time, the result would not be particularly secure for various reasons - weaker than the mini-cipher - so they use various means of causing interrelationships between the mini-blocks.

This brings about a property known as "avalanche"; namely, changing a single bit of the input should cause 'cascading changes' such that (on average) half of the output bits are changed, meaning that the new output is as related to the old output as two independently chosen random bit strings.

Pages: 1 2 3 4 5 6 7 8

2 Comments

  • 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 😉

Other Links to this Post

RSS feed for comments on this post. TrackBack URI

Leave a comment

WordPress Themes

Creative Commons Attribution-NonCommercial-ShareAlike 2.0 UK: England & Wales
Creative Commons Attribution-NonCommercial-ShareAlike 2.0 UK: England & Wales