# 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 non-linearity 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 non-linear

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

- Prev by Date:
**Re: Good sboxes** - Next by Date:
**Re: Q: SAC** - Previous by thread:
**Re: Good sboxes** - Index(es):