Overview on S-Box Design Principles - Cryptography and Network Security Video Lecture - Computer Science Engineering (CSE)

okay so in today's class we shall be
discussing about the principles of
designing an sbox okay so you have seen
that this box plays a very key role to
the security of the block cipher in
talking in terms of Union and
differential cryptanalysis so today's
class the objective will be to
understand some of the design criteria
that this box must satisfy okay so what
we have seen essentially till now is
that this box is some is a table with
elements which are being filled by
entries which are which look to be quite
random right so our bit values but
actually they are not random and there
is actually a quite deep
science involved behind the design okay
so you try to understand how this box
this is design or rather at least see
some of the features or which this box
should satisfy some of the property
properties which ace Box should satisfy
okay okay so so first of all we will go
straight to the question that what is an
S box okay so what is an S box this box
we have already seen essentially till
now it is a mapping it is a boolean
mapping from M bits to n bits so
therefore it takes an M bit input and it
produces and in bit output okay so we
can also call it an M cross n mapping
right so so therefore the essentially
you can imagine that all the outputs
that you produce essentially our
individual boolean functions okay so
they operate upon M boolean inputs and
each of these component functions
essentially is a map from M bits to one
bit okay so in other words each
component function is a boolean function
in M in boolean variables okay so
boolean variables means the values can
be 0 & 1 right so therefore you see that
each of the output each of the N
component output bits can be either 0 or
can be 1 right so therefore we have to
understand that how essentially these
boolean functions are designed okay so I
try to address this issue in today's
class ok so that is the objective right
so
so let's little bit go back into our
what we know about boolean functions and
you know that boolean functions is
essentially means what so if there are M
input bits I would like to obtain one
corresponding output bit right so any
boolean function you know you can
represent that in the form of a truth
table right so the truth table was a
canonical representation which means
that it was a unique kind of
representation of a given boolean
function right so once given a boolean
function I can always we have know that
we know that by using we can express
these express it using either mean terms
or max terms so basically we know that
we are quite familiar with the de
présentation which is known as an end or
representation right so that means that
I am expressing something a boolean
function using and' and or' as as my
logic logic operations okay so but in
what way when we talk about cryptography
and actually cryptographic boolean
functions then another representation is
commonly used it is known as the ant
eggs or form okay or the ant eggs or
expression so it is called any form of
the algebraic normal form so how does an
algebraic normal form look like it looks
like this so therefore it is quite I
mean if you if you observe in this space
so for this plus okay in this case
actually this plus does not mean or it
means an egg's or so all these
operations are eggs or operations and
you have got exhausts and you also have
got ads like you see x1 and x2 okay so
similarly you have got the final term as
X 1 and X 2 and so on till X n so all
these coefficients like coefficients
running from a0 a1 till am then you have
got a 1 2 A 1 3 and similarly like like
you go on till a n minus 1 comma N and
then finally for the final term like x1
to xn you have got a 1 2 and so on till
n so therefore all these coefficients
can take two values right it can either
be 0 or it can either be 1 right so how
many such boolean functions are possible
we can easily enumerate from this
because you know that
there are how many how many possible
boolean functions to ^ 2 ^ M ok so so
therefore you see that these boolean
functions essentially comprise of what
we can actually represent all possible
boolean functions using this form and
also this form is a normal form so what
does it mean it means that if I present
them in this in a I mean if I if I would
like to be present I can obtain a unique
representation just like my truth table
this is an equivalent representation ok
and actually there are algorithms quite
easy algorithms which takes a given
truth table and can represent them in
this particular form so so I am NOT
going into those conversions but you can
easily do that so maybe you can take it
as a just in home as exercise and you
can just try to find out some algorithms
for doing that ok this just represents
coefficient so therefore this can be
values of so this is just how the
notation has been denoted right so when
you are considering that term X 1 into X
2 then the corresponding coefficient is
a 1 comma 2 ok similarly when you are
considering the coefficient of say xn
minus 1 and xn then I represent that by
a n minus 1 comma n so that is only a
different notational thing okay so
therefore these values can be either
zeros and ones okay so you note one
thing that we essentially will be
addressing linear functions and
nonlinear functions ok and also another
function which is known as affine
functions so what is affine function we
have already seen how an affine function
looks like so you see that in this
particular form of the equation if we
substitute all these values which have
got n terms as zeros like I mean I'm
going to say the coefficient
corresponding to this n terms of zeros
right then you have got a 0 exhort with
a 1 X 1 and so on till in X n so apart
from this all of the other terms go to 0
so what is the correspondence but this
equation which is remaining is actually
an affine equation ok so if this a 0
value that is a constant value also goes
to 0 then you have got only these terms
then it actually becomes a linear
equation a linear function so so
therefore if apart from this all other
functions are non linear and you know
why it is non linear it is nonlinear
with respect to the XOR operation ok so
we have a address this in context to
linear cryptanalysis we know what's a
linear function and why it's called
linear and if it is nonlinear Whites
nonlinear it is always with respect to a
particular operation right so in this
operation in our case is eggs are ok so
how many possible linear functions are
possible we can also enumerate from this
particular expression this description
right so so you can work out how many
linear functions are possible how many
non linear functions are possible and so
on ok so I can give a very simple
example so it is good to see some
example like suppose you have got X 1
and X 2 as two variables and let us
consider the simple function of X 1 or X
2 ok so therefore how will the truth
table look like 0 0 0 1 1 0 & 1 1 say
apart from this all the other terms will
be once with a simple or function right
so this particular thing we would like
to express using a ANF form okay so let
us just try how we can represent this so
I call this function as Y and just see
that y equal to X 1 X or X 2 exhort with
X 1 X 2 does it work so you see what is
X 1 X or X 2 exhort with a X 1 X 2
does it does it match
right so you see that I can I can
actually represent so if I mean this is
this particular notation or this
particular representation is known as
the NA free presentation okay so
therefore there are actually algorithms
you can easily express them I mean given
a and or form you can actually convert
that into an and XOR form now can Weis
watch also okay so so therefore so
therefore we have understood what is an
a form so why it's a linear form so
important
the NA form is important for various
reasons okay so one of the important
reasons is that you can easily obtain
the degree of a particular boolean
equation okay so anyway so we will go
into this the the various properties
with a boolean function of cryptographic
boolean functions to satisfy one after
the other okay so consider a boolean
function which is a mapping from M bits
to r2 one particular bit okay so let F
essentially which takes in an N bit
number and convert that into a 0 1 bit
be a boolean function okay so therefore
this is a simple example of a boolean
function and then we define something
which is known as a binary sequence ok
so binary sequence essentially means I
would like to represent them in the form
of F alpha 0 F alpha 1 and so on till F
alpha 2 power n minus 1 so this is so
therefore this particular notation is we
know commonly as a truth table right so
what does it mean that I will take every
possible assignments of my input and
find out what is the corresponding
output if the input is been sensitized
by that particular value like for
example this boolean function f if I
give an input of alpha 0 the
corresponding output is f alpha 0 okay
and how many such possible inputs can I
give I can give 2 power n possible
inputs okay am i store them or store all
the outputs in a table which is commonly
known as the truth table ok so that is a
definition of a truth table so there is
a some there is another quite closely
associated term which is called the
sequence of a boolean function ok so
what is a sequence so the sequence is
quite simple I mean similar to a truth
table only thing is that each element is
represented by minus
to the power of that particular element
like -1 ^ FL + 0 -1 ^ f alpha 1 and so
on till - alpha ^ -1 ^ f alpha to the
power of n minus 1 so what do you do is
that you take the truth table elements
and you raise each element to the power
of minus 1 okay so therefore what will
be the sequence in this particular
example so if my for example if if they
the truth table elements are 0 1 1 1
then what will be my sequence look like
it will be minus 1 to the power of 0
minus 1 to the power of 1 minus 1 to the
power of 1 and minus 1 to the power of 1
right so therefore I will write this as
1 minus 1 minus 1 and minus 1 okay so
therefore in a sequence each of the
elements can be either plus 1 or minus 1
okay so that is how a sequence of a
truth table is defined truth table of a
sequence of a truth table for a given
boolean function is defined okay so then
we will see certain criteria which a
good boolean function should satisfy
okay see as I told you that for all
attacks the main objective was to find
distinguishes right distinguishes from
random mappings okay so we know that if
you take a random function then what you
expect is the number of zeros and ones
should be essentially equal right so one
of the criteria which a boolean function
should satisfy and it is quite obvious
also is that the number of zeros and
ones should be same right and that is
called the balanced nests of a function
okay so a balanced function is a boolean
function if it stood stable has got
equal number of zeros and ones okay so
therefore we also note this term we know
we know this term called Hamming weight
so therefore if I have got a binary
sequence okay so the Hamming weight of a
binary sequence is the number of ones
right so therefore you know that the
number of false and number of zeros for
a given particular truth table should
essentially will be identical okay
so therefore if you have got a n bit
boolean function then how many number of
ones are expected to ^ n by 2 so that is
2 power of n minus 1 right that is the
expected number of ones
okay so then we define something which
is called a scalar product of two
sequences okay so what is a scalar
product of two sequences so we have
defined what is a sequence so they were
given a boolean function f and G we can
define their sequences by these two
symbols okay so one I call one of them I
call ETA and the other one is safe salon
okay so now we define so therefore if
you take the scalar product so you know
what is caleb define les so therefore
this is the rotation of the scalar
product then you can see that this is
equal to the number of cases when F and
G are equal minus number of cases when F
and G are not equal okay so all of you
see that
so therefore the this is what is a dot
product or a scalar product of the two
sequences right so whenever you see that
F and G are both the same then that will
add up to this particular product and
when F and G are not the same then we
will actually subtract minus 1 from that
ok because you note that your sequence
has got only two elements right it has
got either plus 1 or it has got minus 1
right so when they are not equal then
you have got one in one case and minus
one in the other case and when both of
them are same then you have got either 1
1 or minus 1 minus 1 so both the cases
the product computes 2 plus 1 right so
therefore you have got either
so therefore this you can enumerate by
the number of cases when F and G match
minus number of cases when F and G do
not match do follow
yes so so therefore using this
particular notation you will define
something which is called a
non-linearity so we have all the time we
have been talking about non-linearity
right but we have not really quantized
what non-linearity means so I will take
that example to at least address to you
what is non-linearity I think after that
this particular slide will make better
sense okay so take this example like x1
x2 and so we know that there are
possible values like 0 1 1 0 and 1 1 and
take the same example so x1 or x2 and we
will try to find out what is the
corresponding non-linearity of this
boolean function ok so what is the truth
table we have seen 0 1 1 and 1 ok so the
idea is that you find out all possible
linear functions in these two variables
x1 and x2 so what are the possible
linear functions possible one of them is
0
like all of them is 0 ok so the other
one the other possible linear functions
could be x1 itself
okay x2 itself and x1 exhort with x2 ok
so considering linearity with respect to
the XOR operation right so what are the
corresponding truth table for this 0 0 0
0 for X 1 it is equal to 0 0 1 1 for X 2
it is 0 1 0 1 and for X 1 X or X 2 it is
0 1 1 and 0 ok
so these are my possible enumerations of
the possible linear functions ok next
what I do is that I take this particular
truth table and I take all the linear
functions or linear possible linear
functions and I find out what is the
Hamming distance of these truth tables
with this hamming it with this 2 3 ok
that is why we define the term Hamming
distance okay so what is the
corresponding Hamming distance of these
two tooth tables what is that how many
cases do they differ that is the thing
right so how many cases is the differ
differ in 3 cases okay so that is D 1 I
call them as say 3
okay how many cases so how do I mean
what is this how many cases does this
value differ from this particular column
he refers in one case okay how many
cases this differs sure yeah so it
differs in one case how many cases does
this differ yeah it is one okay so your
non-linearity is defined as the minimum
of d1 okay so they call them d1 d2 and
d3 and d4 D 1 comedy 2 comedy 3 kanaa d4
so in this case that is equal to 1 okay
so that is the definition of
non-linearity so which means that now we
can generalize this right so therefore
if you have got an N variable boolean
function then you obtain all possible
linear approximations enumerate their
truth tables and find out the distances
okay and out of them the minimum
distance corresponds to the
non-linearity of the boolean function
okay so you can note certain interesting
things like for example if you take two
linear functions how many cases do the
differ it is always half the possible
number of cases so you see that there
are four zeros and there are two
differences like so in two cases the
differ similarly if you take these two
linear functions how many cases do they
differ it also differs in two cases okay
you take these two things it also
differs in one case here and one case
here so two cases so all possible linear
functions you will differ in 2 power n
minus 1 cases okay so in here so
actually we will find that a linear
function ok and a nonlinear function
with the distance I mean so what we are
essentially considered is about the
distance right so you will find that the
distance is never equal to 2 power n
minus 1 but it is always less than 2
power n minus 1 okay so only two linear
functions differ in 2 power n minus 1
cases ok but a nonlinear function will
actually be falling less than none so it
is assumed you can just assume this as
if the linear functions form a space ok
so form various axis and
nonlinear functions come somewhere in
between so therefore therefore designing
a nonlinear function is quite tricky so
if you make it far away from one
particular linear function it may fall
close to the other linear function okay
but what you have to ensure is that the
nonlinear function maintains quite a
safe distance from all possible linear
functions right so therefore our idea
will be essentially or rather our
objective will be to maximize this
non-linearity so we have to maximize
this particular metric called
non-linearity okay so how do we do that
but before we go into that let us define
generally what non-linearity means so
non-linearity of a boolean function can
be defined as a distance between the
function and the set of all the find
functions but actually it is a minimum
distance okay so therefore you take F
and you find out all possible affine
functions and I denote them by say G and
then you find out the distances with the
corresponding bit between them and you
denote the minimum of them or at assign
the minimum of them to your
non-linearity
okay so non-linearity is defined in this
way so you see that NF is equal to
minimum of D from F comma G where G
belongs to a n where a n is the set of
all affine functions over Sigma n Sigma
n means over n so therefore it is an
alphabet which is formed using n
particular letters okay in particular
symbols okay forget the notation but the
idea is as simple as that okay so now
you can try to up you can try to
understand why your D F comma G is equal
so what we are essentially concerned is
with the distance of F with G right so
your distance with F comma G will be
equal to 2 power n minus 1 minus half of
ETA comma Epsilon okay so that follows
from the definition of ETA or definition
of this particular dot product okay so I
leave it to you as an exercise to think
why then it is follows straight away
from the definition
so therefore if you know this then
defining non-linearity becomes quite
simple because in that case
non-linearity becomes equal to 2 power n
minus 1 minus 1/2 of this distance right
and what we are interested is in making
this distance minimum so what we will
see if we make the distance minimum then
we will make this particular scalar
product as maximum so therefore we write
here maximum and that is how it is
defined so therefore you see that what
we observed intuitively whether
non-linearity is always less than 2
power n minus 1 okay it is minus 1/2 of
something so therefore this term is
actually a positive term so you will
find that this is all known yet it is
always less than 2 power n minus 1 ok so
so therefore you can just give a third
that why it works
any idea why it is ok why it is correct
or shall I show it to ok so I will just
give a hint ok and leave the complete
complete the entire thing to leave the
entire completing the proof to you so
how was this define this was defined as
number of cases when F is equal to G
minus number of cases when F is not
equal to G so now what we are interested
is in number of cases when F is not
equal to G right so how can you write
express this in the in terms of this it
is equal to 2 power n minus number of
cases when F is not equal to G so you
know you have also got minus number of
cases when F is not equal to G so you
have basically got 2 power n minus 2
times number of cases when F is not
equal to G okay so now you can actually
rearrange this because this is what you
are interested in right you are
interested in the distance between F and
G right so you are interested in the
distance means you are interested in
finding out this value so now you can
just rearrange this and you will obtain
that corresponding expression ok
so now there is actually just we will
address this that there is a very nice
commentarial tool called high demand
matrixes through which you can actually
enumerate or compactly represent all
possible linear functions ok so so
therefore if you see the definition of
high demand matrices you will see that
the definition of Herriman buttresses
works like this you take H 0 equal to 1
okay and your H 2 forever H 1 is defined
as H 1 H 1 H 1 and minus H 1 so what
does it mean it means 1 1 1 and minus 1
ok similarly you can also write H 2 so
what will be H 2 equal to 1 1 1 minus 1
1 1 1 minus 1 1 1 1 minus 1 and you take
the negative of this minus 1 minus 1
minus 1 and plus 1
ok so what is why are we doing all these
things so you see that heroin matrix has
got a nice property the property is that
each of the rows ok so if you take each
of the rows then they then they denote
the sequence of a so if you were
considering for example H 1 then each of
the rows will denote the sequence of a 1
variable gradient function ok so what is
the 1 variable boolean function possible
it can be either 0 or say X ok so what
is the corresponding sequence for 0 so
if you consider a 1 variable boolean
function ok so what are the possible
boolean functions what are the possible
linear functions possible it is either 0
or X ok so what are the sequence is
possible what are the possible sequences
it is either 1 1 ok or its 0 1 so what
is the corresponding sequence was 0 1 is
minus 1 1 minus 1 ok so 1 minus 1 so you
see that precisely that is what your
high demand matrix gives it gives you 1
1 and
- one similarly you see that you see
that for you can extend that to h2 also
okay so the first one represents all
possible so therefore you see one one
one one so that you present the linear
function zero okay the next one is 1
minus 1 1 minus 1 so that is X 1 for
example this okay what about this 1 1
minus 1 minus 1 so that is another
variables XT okay what about this 1
minus 1 minus 1 1 that is X 1 XOR with X
2 so you see that you can form all two
variable functions two variable linear
functions in this fashion okay so
therefore if I am able to find out or
recursively express HN okay in terms of
HN minus 1 then essentially each of the
rows of the matrix H n denote linear
functions of n variables okay the
sequences of the linear functions of n
variables okay so what you have to do is
essentially if you have to obtain the
corresponding so therefore this is a
very compact expression so therefore if
I want the corresponding linear
expression for a given row then what I
have to do is that I have to take the
corresponding binary representation of
this so therefore if I know that one for
example 1 minus 1 1 minus 1 is my
sequence ok and I can obtain the binary
sequence from this and the binary
sequence would have been 0 1 0 & 1
ok and then I have got my variable list
as say so I have got my corresponding
variable list so therefore what is the
variable list
it is so therefore if I take the dot
product of this with the corresponding
boolean function then I can obtain from
this that is my boolean function is
equal to x1 okay similarly I could have
obtained that my for this particular row
it is equal to x2 and for this one it is
equal to x1 X or X 2 okay so given the
high demand matrix from there I can
obtain all possible linear functions
okay so therefore if you are told to
generate all possible linear functions
then there is a nice recursive way of
doing that
okay using this combinatorial to so now
we are addressing the issue of
non-linearity so you see that if there
is so there are some properties which we
will just address but we'll leave the
proof but just for this tough timing
just try to understand I mean that it
works okay try to be safe basically
understand the inside so it say that if
a boolean function FX is balanced then
so is f X be exhort with a so a is an N
bit vector and B is an N cross n 0 1
invertible matrix so it means that if
you have got an F function who has got a
certain amount of non-linearity then
doing an affine mapping in the inputs
does not really make any change to the
non-linearity okay so if you do an
affine mapping to the inputs this is the
input variables X using a invertible
invertible matrix that is if this
particular matrix b is invertible and if
you take this and if you do this
operation then still then the
non-linearity does not change okay and
so therefore what it says is that the
non-linearity of f and g are the same so
so therefore not only really does not
change two operations like this but our
sbox
should also satisfy another very
important criteria which is known as a
strict Avalanche criteria but I think I
have told somewhere what is meant by
Avalanche effect so it means that if I
change only one bit of the input half of
the output gets changed okay so the bad
thing is that formally we will try to
define it so what it says is that if
there is a boolean function FX okay and
you define an a vector called alpha
whose weight is 1 so what it is you mean
that only one bit is changed okay so if
you take X X XOR alpha so if its weight
is weight of alpha is 1 means it is
basically a binary string in which only
one of them is 1 the rest of zeroes
right so if you take X XOR alpha so you
see that in X XOR alpha and X how many
bits are changed only one bit is split
right so this particular function that
is FX X or F X XOR alpha is actually a
balance
function so that is the criteria of
strict Avalanche criteria okay so it
says that if there is a function say for
example FX okay and there is a function
called F X XOR alpha okay so let us try
to understand why is only one bit is
changed so you take for example X as say
x1 x2 and x3 okay and here alpha as say
0 1 0 so what does X XOR alpha represent
s it is equal to x1 x2 X or with 1 and
x3 so you know for the properties of X
are that x2 X or 1 means what complement
of x2 right so therefore you can
represent this as X 1 comma X 2
compliment comma X 3 so you see that
from this X between X this X and this X
XOR alpha there is only 1 bit which has
been changed and the idea is that FX
exhort with FX exhort with alpha should
be a balanced function okay should
essentially should be still balanced
okay
and what we say is that there is also
another way of representing ly so we
call this as strict Avalanche criteria
or often referred as sack okay when we
also says that it satisfies propagation
criteria something which is called a
propagation criteria of order 1 ok order
1 why because the weight of alpha was
equal to 1 okay so the weight of alpha
was equal to 1 in this case right so
similarly you can understand since I
have said propagation criteria of order
1 I can also have propagation criteria
for order 2 so what does it mean I will
just make the weight of alpha to be 2
and check for a similar property ok see
idea is that we are always trying to
find out distinguishes from a random
mapping okay so in your in a random
mapping if you change one bit of the
input you are expect to get half of the
output bits to get changed right
so therefore this idea what we are
trying to do as a designer is try to
maintain that all the property looks
seemingly random okay trying various
kind of tests and ensuring ensuring that
really the function really looks like
random okay so you see that when we
define something is called FX eggs or FX
eggs are alpha and say that the weight
of alpha is 1 we say that the sbox are
the boolean function satisfied what will
be known as the strict Avalanche
criteria but higher-order sacs are also
possible when more than one input beats
change so both the sac and the
higher-order sac together make one
something which is called the
propagation criteria okay
so you see that can can can you see that
where this propagation criteria can be
useful in terms of linear and
differential cryptanalysis immediately
you can see that if you can maintain all
these things okay then you essentially
get a good differential property because
what you are doing easier is basically
subjecting the input to a differential
various kind of differentials okay so
remember your difference distribution
table right
so therefore what you do in your
difference distribution table you are
subjecting the input to differentials
means what you are considering various
cases where you have given a
differential to the input and we are
checking that what is what is the
possible output differential right so
basically what you are doing is that you
are taking one instance of the cipher or
the sbox and applying an input and
checking its output and maintaining a
differential say alpha and giving an
input say X XOR alpha and again
obtaining the output and then you are
obtaining what is the corresponding
differential between FX and FX XOR alpha
okay and what you if you can show that
half of the cases I mean it is a uniform
distribution then you are not then you
will get a distribution table which is
seemingly quite strong right which I
mean which you really cannot maybe
exploit so much for doing a differential
attack okay so so if you see that the
previous study of non-linearity of
non-linearity was helping to something
to overcome linear cryptanalysis whereas
this particular study is helping to
somewhat protect against differential
cryptanalysis
okay so therefore given any boolean
function we can actually make certain
transformations and make it satisfy Shaq
okay so what it says you consider a
boolean function FX and consider a non
linear singular matrix 0 1 matrix of
dimension n cross n ok so what it says
that if for each row of the matrix a if
this property satisfies that is if X
exhort with FXX or gamma is balanced
where gamma is a row of the matrix a
then actually GX which is equal to FX a
satisfies the sack okay so you see that
why it's true so also it is quite
trivial if you follow the definition of
sack okay so let's see what it says so
it says that GX is equal to FX a
satisfies sack okay so we have tri we
have to try to understand why why why
does right so if we say if we claim that
GX satisfies sack then what is the
property that GX which satisfy the given
any alpha given any alpha such that the
weight of alpha is equal to 1 G X XOR
with G X XOR alpha should be balanced
right so what is GX this means that FX a
XR with exhort with alpha a should be
balanced right instead of X we have
written X XOR alpha okay so you see that
what it means is if X a XR with FX a
exhort with alpha a should be balanced
okay and what is the property that you
have okay first of all what is this X a
X or with alpha a what is alpha a so
given any matrix a okay
find that a suppose a has got various
rows like gamma one so it was a is a
matrix you have got gamma 2 and
similarly you have got say some gamma n
rows ok so what does alpha a represent
so remember the Alpha has got weight of
only 1 ok so what does it represent what
does alpha I mean column or row it means
so for example you can just imagine that
alpha is equal to 1 u 0 and so on 0 okay
so what does alpha I represent first row
here you are you are having alpha the
beginning and then a right so you have
got the first row okay so you have got
gamma 1 here right only one row which is
gamma 1 right so what you are basically
saying is that FX a okay XOR with FX a
ex-ored with gamma 1 is balanced right
and what was my design criteria design
criteria was the FX exert with FX absorb
gamma is balanced
another thing is important here is that
this non singularity property of the
matrix y because what we have showed
here is that FX a exhort with FX ax or
gamma 1 is balanced okay and in order to
ensure that this particular function FX
a if this so the therefore if this
matrix a is a non singular matrix ok
then this this function will look
exactly like the FXX or gamma function
alright so if this function a is a non
singular matrix then FX a and FX will
behave in the identical way there will
be a one-to-one relation between the
both between both right so therefore
what you see is that if the condition is
that if there is a non singular matrix
of dimension n cross N and such that if
for each row of the matrix a if FX X are
FXX or gamma is balanced ok then
X equal to FX a satisfies the strict
Avalanche criteria so we will just see
one example in order to understand so
you consider like X 1 into X to exhort
with X 3 which does not satisfy that Y
just consider this example say alpha is
equal to 0 0 1 so if we address this f
obtain FX and I and I would like to
obtain FX exert with alpha then what
does it mean I am NOT actually flipping
x1 x2 but only flipping x3 okay so what
does it become it becomes X 1 X 2 X or X
3 X or with 1 right so if I now take the
eggs or between these two I obtain 1 and
which is not a balanced function do you
see this okay so therefore what I am
saying is that if X is equal to X 1 X 2
X or with X 3 okay so consider alpha is
equal to 0 0 & 1 so what is FX exhort
with alpha but what is xx or alpha first
of all it is equal to X 1 comma X 2
comma X 3 bar right so therefore that
means that if X XOR alpha is X 1 X 2 X
or with X 3 bar so what does it mean it
is equal to X 1 X 2 X or with X 3 X or
with 1 I can write in this fashion so
now if you take FX exhort with FX exhort
alpha and what do you obtain you obtain
only 1 right because this part and this
part gets cancelled okay so now is this
function a balance function no because
everything is 1 right so therefore it
does not satisfy the strict Avalanche
criteria so we will see how we can make
it satisfy strict Avalanche criteria
okay so which means that we have to find
out that particular matrix a right and
here is an example so we are going into
how to find we will see that it works
like you take a where a is equal to 1 0
0 0 1 0 1 1 1 so what you have to do is
that you have to find out y 1 e 2 and E
3
that affects exhort with FX X or d1 is
balanced FX X or X FX X or T 2 is
balanced and FX X odd if X XOR with d3
is also balanced so therefore here as I
say some examples u 1 e 2 and E 3 and
note that all these rows or rather all
these vectors are also linearly
independent why is that important
because we would also like to make the
matrix a as a non singular matrix ok it
should not be it should be an invertible
matrix right it should have full rank
so therefore this matrix a essentially
will look like this and now you can
check actually that GX and define is
like FX a will actually satisfy the
strict Avalanche criteria ok so which
means that if you make if you make this
transformation of the input variables X
using this particular function or rather
you using this particular matrix
transformation then this part is
composed function or transform function
will actually satisfy the strict
Avalanche criteria ok so which means
that if there is a particular boolean
function which does not satisfy the
strict Avalanche criteria you can
actually make it satisfy the strict
Avalanche criteria and note another
thing that what you have done is that
you have just taken X and multiply that
with an invertible matrix ok
therefore by my previous discussion the
non linearity of the function FX and FX
a are actually are actually the same ok
so therefore this particular
transformation FX a does not disturb the
non linearity of FX so therefore without
disturbing the non linearity of if ok
you can actually satisfy the strict
Avalanche criteria also ok therefore if
you know how to make a good non-linear
function which does not satisfy the
strict Avalanche criteria after that you
can make actually make it satisfy strict
Avalanche criteria without disturbing
the nonlinear okay do you follow that
okay so therefore these are some things
which you can just keep in your mind
that for any invariable boolean function
actually there is an upper bound to what
the non-linearity can be okay so we will
not prove this but actually you can show
the non-linearity of any invariable
boolean function is actually lesser than
2 power n minus 1 minus 2 power n by 2
minus 1 okay and this works when n is
even okay so you see that n by 2 has to
be an integer okay and these functions
are sometimes referred to as something
which is called bent function okay so
these are called bent functions and
actually they it can be shown that they
satisfy the propagation criteria for all
values of alpha for all orders okay but
there is a problem with Bend functions
also the problem is that it is actually
an unbalanced function so what does it
mean the number of zeros and ones are
not the same can you say why okay so I
will so therefore these Bend functions
has got a non-linearity of the maximal
value so therefore the non-linearity of
a bend function is actually equal to 2
power n minus 1 minus 2 power n by 2
minus 1 okay for all other cases it is
lesser than that right so therefore the
non-linearity of a Bend function is
actually equal to 2 power n minus 1
minus 2 power n by 2 minus 1 ok so now
can we relate to the fact that why it is
an unbalanced function
okay so we will just give a second to it
I will come back to it okay
so therefore there is an example of a
bend function so you can take like X
there are four variables X 1 X 2 X 3 and
X 4 you just take FX is equal to X 1
into X 2 XOR with X 3 X X 4 okay so this
is an example of a Ben function in 4
variables so what does so if it is a
Bend function what do you expect the
non-linearity of these to be equal to 2
power 4 minus 1 minus 2 power 4 by 2
minus 1 so what is that equal to how
much does it work 2 to 6 so we can check
that all 4 variable boolean functions
actually will have a non-linearity which
is not a Bend function we have a
non-linearity which is less than that ok
so there are some again properties like
if you take an F which is a Bend
function then so is f exhort with affine
function so for if I take this and I
exert that with X 1 X or X 2 or
something like that then it's still the
nominee does not change okay similarly
you can also say therefore any non
singular binary matrix a and if you do a
similar kind of transformation to your
inputs then it still remains bent ok the
Bennis does not change so now I can come
back to that problem that again that why
Ben functions are not balanced ok so you
can see that since Ben functions
maintain a non-linearity of at least 2
power of 2 power n minus 1 minus 2 power
N by 2 minus 1 so therefore if I
consider the distance from the all 0
function still then that distance should
be 2 power n minus 1 plus y I mean plus
2 power n by 2 minus 1 right so
therefore the number of zeros in a
balanced function is how much 2 power n
minus 1 right so therefore you see that
the number of ones is actually equal to
2 is actually more than 2 power n minus
1 plus 2 by n by N by 2 minus 1 ok so
why have I written a minus also here
because actually what I am considering
is that all 1 function also so if we
maintain that if we look for both the
functions then actually you can ensure
that you are not anyway you are not able
to obtain that number you are not able
to maintain the number of zeros or
number of ones to equal to 2 power n
minus 1 okay so that is not possible
so therefore brain functions are not
balanced that is the idea although it
maintains high amount of non-linearity
but they are not balanced just okay so
therefore this is the idea so which I've
already told you so so you can actually
what you can do is that you can actually
create balanced nonlinear functions so
therefore I am not really going into
this what what it just says is that you
can take some linear functions and you
can start concatenating them okay so you
can just see this and you will obtain
that if you take say to power n minus KK
variable linear functions where K is
greater than n by 2 and start cutting at
the linear truth tables then you will
obtain an n cross K mapping which is
nonlinear so therefore you can just take
it an exercise and just try to work out
and I am Li I mean you can just prove
also that the non-linearity of this will
be actually greater than 2 power n minus
1 minus 2 power K minus 1 it will also
be balanced and it can be made to
satisfy the strict Avalanche criteria
also okay so therefore so therefore if
the question is is the sbox which you
design good against linear cryptanalysis
and differential cryptanalysis okay so
not only on the component function is
good but they have to satisfy high
vomity like satisfy propagation data
etcetera but also the problem is that
they are nonzero linear combinations
also should satisfy these properties so
therefore it is a quite challenging
problem to design a good x box okay so
so I will just conclude with this that S
box designing is quite complex although
you have to satisfy so many things and
then also finally what you can ensure
you can end up is that this leaks
informations in the form of some side
channels and things like that so
therefore it can happen and although you
do so much mathematics you can actually
break these ciphers in minutes even
after all the hard work ok so then there
are other classes of attacks algebraic
attacks we have not really touched into
so actually it is quite hard to design a
good s box okay so therefore I just
conclude with this that these are the
properties which would satisfy balance
this non-linearity and also strict
Avalanche criteria and also high
algebraic degree that is the number of n
products in your algebra normal form
should also very high okay so you can
take this an exercise that is you can
enumerate eight distinct linear
functions in
five variables X 1 X 2 X 3 X 4 and X 5
so you can see you can just choose 8
distinct linear functions in five
variables okay so you just take five
variables and form eight possible linear
functions and then concatenate their
truth tables to obtain an 8 input 5
output function so you can just see that
why it works okay there you can just
take these functions linear functions
and you start them start contacting
concatenating they're truth tables okay
so then you store the resultant mapping
as an 8 cross 5s box like what we have
seen for des for example another s-boxes
so a question is that what is the
non-linearity of your S box and does it
satisfy strict Avalanche criteria
if not then modify the function to do so
okay so you can take this an exercise
along with your previous summation which
is still pending like the des s box you
also submit this as an exercise ok so so
these are some of the references that
I've followed Sabre is paper is quite
interesting you can read that and then
there is also 9 box paper which you can
read ok so next day we will talk about
modes of operation of block ciphers
you