Avalanche functions (by alaric)
So how many rounds do we need? If each round has 8 bits of "avalanche bandwidth" due to an 8-bit H being XORed into every byte, do we need as many rounds as there are bytes in the message?
No - because the ECB layers cause some avalanche. Each of those will already cause every output bit of a block to be a function of every input bit, if it's a key dependent S-box. (Yes, I know a 'weak key' could result in an S-box for which every output is the same as the input, but the attacker cannot know if this is the case or not; and if this highly unlikely possibility is a worry, the algorithm used to initialise the S-box from a key can be chosen to mandate good avalanche properties from the result).
So the ECB layer can be thought of as multiplying a single bit change into an order of N/2 bit change, if the ECB block size is N.
And my avalanche function takes a single bit change and turns it into an (L/M)-1 bit change, if M is the size of a avalanche block and L is the length of the message (in bits).
So after the inital ECB, which cause an avalanche factor of N/2, each round involves a single avalanche and another ECB, resulting in an avalanche factor of:
((L/M)-1)*N/2
The total avalanche factor of R rounds is, therefore:
N/2 * (((L/M)-1)*N/2) ^ R
We need to find R such that this number is >= L.
N/2 * (((L/M)-1)*N/2) ^ R >= L (((L/M)-1)*N/2) ^ R >= L*(2/N) R log (((L/M)-1)*N/2) >= log (L*2/N) R >= log (L*2/N) / log (((L/M)-1)*N/2) R >= (log (L)-log(N/2)) / (log ((L/M)-1)+log(N/2))
...that can probably be simplified with a bit of approximation (bear in mind that the N/2 avalanche function is just "on average" anyway, so approximations are OK) to something fairly sane. I would simplify it, where it not 2am and my maths A-level about 8 years old. Probably L times a function of M and N.
UPDATE: That analysis is useless. I make a better one here.
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 😉