Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Improving avalanche property of functions with bit rotations
Posted:
Dec 12, 2013 3:27 PM


If a nbit bijective function F is used in an encryption algorithm to transform a value x to y, i.e. y = F(x), it is commonly desirable that its avalanche property be superior. That is, changing one single bit of x will produce lots of changes of bits of y. In case however the given F doesn't have very nice avalanche property, the question of potential improvements naturally arises.
I found that postprocessing y, the output of F, with a bit rotation of an amount that is variable and dependent on y can very effectively help, which in retrospect is easily understandable. Note that a rotation by a amount that is pseudorandom but independent of the value of y would not contribute to the avalanche of the function, though it can add some security to the function as it commonly does. (One can certainly also use a combination of both kinds of rotations, if considered desirable.) In an experiment F was chosen to be a 2nd degree permutation polynomial mod 2**n (its software implementation can be found in e.g. my Python code JADES, available in http://s13.zetaboards.com/Crypto/topic/7072208/1/). The amount of rotation of bits was chosen to be the number of 1bits in the n bits of y. (Note that this rotation is reversible.) The following is the statistical evaluation with 1000 pseudorandomly generated F's:
n postproc. mean avalanche standard deviation
64 no 16.73 0.97 yes 29.93 1.30
128 no 32.75 1.35 yes 60.71 1.67
256 no 64.79 1.96 yes 122.81 2.24
512 no 128.71 2.66 yes 248.44 2.82
M. K. Shen



