Re: Good sboxes
 From: Tom St Denis <tom@xxxxxxx>
 Date: Thu, 24 Sep 2009 03:55:49 0700 (PDT)
On Sep 24, 2:49 am, Maaartin <grajc...@xxxxxxxxx> wrote:
Excuse me for opening a similar topic, but I'd like to get the answer
(without having to read all the comments on trolls, etc.). So the
questions:
What are the best measures for quality of m:n sboxes? Surelly non
linearity, number of monomials, what else?
What are the best sboxes known for different values of m and n?
I'd be happy about some pointers to good papers (instead of direct
replies).
I don't have urls handy [it's 6am leave me alone] but generally you
want something with
1. Good differential immunity [low DPmax]
2. Good linear immunity [low LPmax]
3. High algebraic degree [high degree multivariate expression]
4. Usually people express a desire for no fixed points, but I don't
really know why that's a requirement
The thing about "diffusion" and all that is handled if your cipher has
a good linear component which delivers a high enough branch. Don't
count on your sboxes for diffusion.
Take AES for instance, after 8 rounds there are at least 50 active
sboxes, regardless of design of the sbox (so long as it's bijective
and doesn't have a DPmax of 1/1). Now the sbox in AES has a DPmax of
4/256 or 2^6 which means any differential through the cipher has a
maximum probability of 2^300 of holding after 8 rounds. Clearly this
is overkill. AES would be just as secure from differential attacks if
it had a random sbox with a DPmax of 12/256 [trail of 8 rounds =>
2^220]. Same thing for linear attacks [I don't recall the LPmax off
the top of my head... again it's 6am].
What none of this addresses though are the scores of other attacks,
like truncated differentials, integration [summation, square] attacks,
impossible differentials, etc. No bijective sbox is more secure than
another in AES against square like integration attacks. It's just the
nature of the design.
So in reality a lot of the early [and by that I mean 80s/90s]
discussion on SAC and sboxes with high avalanche is really moot. You
want sboxes with good nonlinearity and differential properties, but
overall the rest of the cipher is more important. You need high
branch, fast diffusion, same for the key schedule, etc... And
nowadays that sort of properties are being promoted by more rigorous
means than bit twiddling and relying on the sboxes. Instead people
use things like MDS matrices which have much easier to study
properties.
You look at a cipher like DES and off the top of your head you can't
really figure out what the branch is. IIRC from the Biham et al.
differential analysis it's 3. That means over any 2R differential
there is at least 3 sboxes active [iirc 6 for 4R and so on]. Same
thing with a lot of ciphers, like Twofish. I consider Twofish to be
very likely secure, but by that same token I have yet to see a proof
of a minimal 2R branch. In the case of AES it's very easy to prove
its 5 for 2R and 25 for 4R.
Where AES fails a bit aside from the key schedule weaknesses, is the
choice of sbox which is highly algebraic. So far that hasn't been
exploited, and maybe it won't be. But for me, it would have made more
sense to choose a random 8x8 that had good properties to start with.
Or to be a bit more hardware friendly, construct it out of nonlinear
4x4s with a simple PHT or something. They didn't need the LP and DP
maximums that they have for this sort of cipher since it has a very
high branch.
Tom
.
 References:
 Good sboxes
 From: Maaartin
 Good sboxes
 Prev by Date: Re: Good sboxes
 Next by Date: Re: Q: SAC
 Previous by thread: Re: Good sboxes
 Index(es):
Relevant Pages
