Avalanche functions (by alaric)
The fun thing is that this function is self-inverting.
Why?
Well, if each output subblock is the XOR sum of all the input subblocks except the one with the same index, then due to the self-inversion of XOR with a constant, this is the same as saying that each output block is the XOR-sum of ALL the input blocks, XORed with the input block with the same index again.
Let's call the XOR-sum of all the input blocks 'H'. So if we call output block N O(N) and input block N I(N), we can say:
H = XORSUM[1..N] I(N) O(N) = I(N) XOR H
But what is the XOR-sum of the output blocks? Let's call it X.
X = XORSUM[1..N] O(N) X = XORSUM[1..N] (I(N) XOR H) X = N * H XOR XORSUM[1..N] I(N)
...where * represents "XOR times", meaning "H XORed with itself N times".
Now, we said there had to be an even number of blocks, didn't we? And something XORed with itself an even number of times is always zero, since pairs of X XOR X turn into zeroes. So:
X = 0 XOR XORSUM[1..N] I(N) X = XORSUM[1..N] I(N)
...so X = H! In other words, this transformation has preserved the XOR-sum of the block.
Now, going back to our alternative definition of the function:
O(N) = I(N) XOR H
...we can see that the function really just boils down to XORing the XOR-sum into each block. If the XOR-sum is preserved, then running the function again will just XOR the same H into every block... undoing the previous run of the function.
So it self-inverts.
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 😉