Do you have a question? Post it now! No Registration Necessary. Now with pictures!
- Subject
- Posted on
- Mok-Kong Shen
December 12, 2013, 9:03 pm
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
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
JADE-S, available in http://s13.zetaboards.com/Crypto/topic/7072208/1 /).
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
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 computation result clearly contradicts your thought. One integrates
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
The computation result clearly contradicts your thought. One integrates
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)
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)
Site Timeline
- » RSA Key Extraction via Low-Bandwidth Acoustic Cryptanalysis
- — Next thread in » General Computer Security
- » Are iOS native email clients MITM-free?
- — Previous thread in » General Computer Security
- » Special Offers
- — Newest thread in » General Computer Security
- » SSD partition alignment revisited
- — The site's Newest Thread. Posted in » Computer Hardware