# Improving avalanche property of functions with bit rotations

#### Do you have a question? Post it now! No Registration Necessary.  Now with pictures!

•  Subject
• Author
• Posted on

If a n-bit 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 post-processing 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 pseudo-random
but independent of the
value of y would not contribute to the avalanche of the function, though
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
The amount of rotation
of bits was chosen to be the number of 1-bits in the n bits of y. (Note
that this rotation is
reversible.) The following is the statistical evaluation with 1000
pseudo-randomly generated
F's:

n    post-proc.    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

## Re: Improving avalanche property of functions with bit rotations

This thread seems like it would be more appropriate for sci.encryption,
not comp.security.*.

--
Barry Margolin, barmar@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***

## Re: Improving avalanche property of functions with bit rotations

Uh, I would then try to use/design a better function F. Why pile kludge
on top of it.

No. A bit rotation cannot improve the avalanch property. If say a one
bit change in the input produces a 3 bit change in the output, then no
matter how you rotate the bits, only 3 bits will change.

## Re: Improving avalanche property of functions with bit rotations

Am 13.12.2013 01:57, schrieb unruh:

the said post-processing into the function. If one bit of input
changes, then the number of bits before the post-processing changes.
Hence one rotates now with a different amount. Do you see that?

M. K. Shen

## Re: Improving avalanche property of functions with bit rotations

Who cares. a rotation does not change the number of 1 bits. Unless you
mean something different by the word "rotation" than I mean. a simple
rotation is "take bit 1 and make it bit 2, take bit 2 and make it bit 3,
.... take bit n and make it bit 1 (where n is the total number of bits).
That cannot change the number of 1 bits.

Note that post processing cannot do anything for the strength of the
cypher, since it can be removed based just on the output, unless you
make it depend on the key ( which you do not do from what I can see).
Since the recipient has to be able to reverse it and since it depends
just on the output, anyone can do that reverse operation.

## Re: Improving avalanche property of functions with bit rotations

Am 14.12.2013 19:19, schrieb unruh:

You misuderstood the scheme. In our case, since changes of different
bits of x change y differently to quite some extent, the amount of
rotation of y is generally different for different changes of single
bits of x, thus leading to an improvement in the average value of
avalanche over all changes of single bits, as the comutation results
clearly shows. In essense, one uses instead of F() the following
function G(). Note that bc depends on y and hence on x. If one bit
of x is modified, bc is generally dependent on "which" bit of x has
been modified. Hope that this explanation is clear.

def G(x):
y=F(x)
bc=bicount(y)
z=rotate(y,bc)
return(z)