Trap Doors In S-Box

HI,

Pls don't consider as this some lecture from me but just
a few things which I felt writing.

A trap door one way function is a * way function with
a secter trap door .Its easy to compute in one direction
but difficult to compute in the other order.
It would be easy in Feistel Networks to encrypt but
the reverse process(decrypting) is difficult with out
the keys.

How ever if u know the secret you can decrypt
function f(x).While ncrytping ,given x it is easy to compute
f(x) but difficult to compute x given f(x).
But with the secret it becomes possible to calculate
x given f(x).
This was initially the problem with GOST.The GOST
standards didnot discuss how to generate S-Boxes.
So if u use an S-Box that some * gave u,it might turn
out to be a bad S-Box or delebrately made bad(i,e the
values in the S-Box are biased.) so that they can eavs
drop on ur communication.
As a result vendors started making their own S-Boxes
using random number generators.The S-boxes are used
in GOST one way hash function.So a bad S-Box is
always a vulnerability.
I suppose i mean to say its not wise to take S-boxes
which are given to u as it might turn to be a jack in
the box :)
What about ANSI & NIST certified?
The ANSI agreed DES to be a standard,so did the
NIST(then NBS) certify &re-certify des as standard.

A few guidelines for making good S-Box are given in
*:> C.M Adams & S.E Tavares-"The structured
dsign of cryptographically good S-Boxes",Journal of
Cryptography

2:>"Designing S-Boxes for cipher resistant to
differential cryptanalysis"-same author as above.

*:>"K.Nyberg.Differential S-Boxes for cipher resistant to
Differential Cryptanalysis"-Advances in cryptography,
EUROCRYPT -**"

The IBM team which proposed DES as standard had a
**2 bit key but its commercial(standard) key length was
reduced to 56 bit key.Also the S-Box send to the NBS
(now NIST) WAS CHANGED BY THE ns@.
The commercial version of DES used the reduced key
length of 56 bit and the new S-Boxes supplied back
by the NS@.
There r 2 distinct possbilites here.
*:>Either the NS@ want to eavsdrop public's
encryption with their tainted S-Box or...
2:>They didn't trust IBM fearing that the S-Box
they put in the S-Box had a hidden trap door.

Its possible that the * st is true since they halved the key size.
Also * & 2 may be true as the NS@couldn't say for sure
if IBM put a hidden trap door in the S-Box so as to
eavsdrop on DES communicatoin.
It is very difficult to confirm even by the analysis of the
S-Box whether it contains a hidden tap door in it or
not.
DES is more resistant to differential cryptanalysis
than its is to linear cryptanalysis and is usualy the
heart of strength of various Feistel Networks.A lot
revolves around the S-Box.

A generalised criterila for S-box

Consider a m*n bit S-Box which has m input bits
and n output bit.
(pls note that it is not a m*n matrix consisting of m
rows & n colunmns).
The larger the S-Box is ,the more difficult it is for
linear & differential cryptanalysis.
Increasing the size of n makes it difficult for differential
cryptanalysis but greatly reduces the difficulty for
linear cryptanalysis.Hence it is important to choose
an optimal value for m,if the algorithm is more
susecptable to linear cryptanalysis.

Let ^ denote exponent
If n>= (2^m)-m there is a defenite linear relation
between the input & output bits of the S-Box.
If n>=(2^m) ,there is a linear relation of only the
out put bits.
The CAST & BL0WF|SH have 8**2 bit S-Boxes.

Is *2>=2^8 ?
*2>=256 ?

which is false.
So thereis no linear relation ship between the output bits
of the S-Box which make CAST & BL0WF|sh even
more difficult to cryptanalyse.

Using large S-Boxes makes ur algorithm strong but I
really wouldn't s***est S-Boxes like in CRAB which
I beleive can be optimised if the design criteria for
making S-Boxes are met with.

Another good reference will be

*:>"On Matsui's Linear Cryptanalysis"-Advances in
cryptography -EURO CRYPT-*4 by E.Biham.

I hope I have convinced the reader not to blindly
accept S-Boxes as gifts on ur b'day as gifts.
Who knows,they might launch a birthday attack :P

Regards Data.